2012韩山师范学院专升本插班生考试《数据结构》试卷

(A卷)第 1 页 共 8 页

韩山师范学院2012年专升本插班生考试

计算机科学与技术 专业 数据结构 试卷 (A卷)

题号 得分 得分 评卷人 一、 单项选择题(每题1.5分,共30分)

题号 答案 1 2 12 3 13 4 14 5 15 6 16 7 17 8 18 9 19 10 20 一 二 三 四 五 六 总分 评卷人 题号 11 答案 1、数据的不可分割的最小单位是( C )。

A.数据元素 B.数据对象 C.数据项 D.数据串

2、一个算法应该具有一些重要特性,下列不是算法特性的是( D ) 。

A.有穷性 B.确定性 C.可行性 D.健壮性 E.至少一个输出 3、下面关于线性表的表述中,( B )是错误的?

A.若线性表采用顺序存储,必须占用一片连续的存储单元。 B.若线性表采用顺序存储,便于进行插入和删除操作。 C.线性表采用链接存储,占用的存储单元不一定是连续的。 D.线性表采用链接存储,便于插入和删除操作。 4、下列哪个不是链表所具有的特点是( A )。

A.可随机访问表中元素

B.插入、删除不需要移动元素 D.所需空间与线性长度成正比

C.线性链表必须有一个指针域

[解析] 链表是线性表的链式存储,是用结点来存储数据元素。线性表采用链表作为存储结构时,不能进行数据元素的随机访问,其优点是插入和删除操作不需要移动(A卷)第 2 页 共 8 页

元素。 5、若线性表的长度为 n,且采用顺序存储结构,则等概率删除其第 i个元

素的算法的时间复杂度为( D )(1<=i<=n)。

A. O(i) B. O(n-i) C. O(1) D. O(n) 6、静态链表中指针表示的是( B )。

A. 内存地址 B.数组下标 C.表头地址 D.下一元素地址 7、下列关于串的叙述中正确的是 B 。

A.串中所含的字母个数称为串的长度 C.串中的字母不区分大小写

B.串是一种特殊的线性表 D.由空格组成的串称为空串

8、设有一个采用压缩存储的9 阶对称矩阵A,以行序为主存储,第一个元素

a11的存储地址为 0,每个元素占一个地址空间,则a86 的地址为( ) 。 A. 26 B. 27 C. 36 D. 37 E.46 F.47 9、判断一个带表头的循环链表H为空表的判定条件是( A )

A.H==NULL

B.H->next==NULL C.H->next=NULL D.H->next==H

10、若一个栈的输入序列为 1,2,3,…,n,输出序列的第一个元素是 i,则第

j 个输出元素是( B )。 A. 不确定的

B. i-j

C. j-i+1

D. i-j-1

11、在一个单链表中,若q所指结点是p所指结点的前驱结点,若要删除p所

指的结点,则执行( B )。 A. q->next=p C. p=q->next;

B. q->next=p->next; D. p->next= q->next;

12、广义表A=(a,(b,c),(d,e),(f,g)),则Head(Tail(Head(Tail(Tail(A)))))

式子的值为( C )。

A. (f) B.f C. e D. (e)

13、在一棵度为3的树中,度数为3的结点有2个,度数为2的结点有2个,

则度为0的结点个数为( A )

A.7 B.8 C.9 D.10 14、在下述结论中,正确的是( C )

(A卷)第 3 页 共 8 页

①只有一个结点的二叉树的度为 0; ②二叉树的度为 2; ③二叉树的左右子树可任意交换; ④深度为 K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A.①②③ B.②③④ C.②④ D.①④ 15、算术表达式 a+b*(c+d/e)转为后缀表达式后为( A )

A.abcde/+*+ B. ab+cde/+* C.abcde/*++ D.abcde*/++ 16、一个有 n 个结点的图,最多有( A )个连通分量。

A.n B.n-1 C.1 D.0

17、若目标串的长度为n,模式串的长度为[n/4],则执行模式匹配算法时,

在最坏情况下的时间复杂度是( D )

A.O( nlogn) B.O(n/4) C.O(n) D.O(n2) 18、设一组初始记录关键字序列(7,2,8, 6,3,10, 5),以第一个关键字

7为基准进行一趟快速排序的结果为( B )。

A. 2,5,6,3,7, 8, 10 B. 5,2,3,6,7, 10, 8 C. 2,3,5,6, 7, 8,10 D. 5,2,6,3, 7, 8, 10 19、向二叉搜索树中插入一个元素的时间复杂度是( B )。

A.O(n)

B.O(log2n) C.O(n*log2n)

D.O(n+log2n) E.O(n2) F.O(n3) 20、一个递归算法必须包括( C )。

A. 初始条件和递归部分 B.初始条件和迭代部分 C.终止条件和递归部分 D.终止条件和迭代部分

二、问答题(共10分)

1、什么叫完全二叉树(4分),

深度为K的,有N个结点的二叉树,当且仅当其每个结点都与深度为K的满二叉树中编号从1至N的结点一一对应时,称之为完全二叉树。 得分 评卷人 (A卷)第 4 页 共 8 页

2、简述顺序存储队列的假溢出的避免方法及队列满和空的条件。(6分) 得分 评卷人 三、填空题(每空1分,共20分)

1、根据线性表的链式存储结构中每一个结点包含的指针个数,将线性链表分成__单链表__和__双链表_;而又根据指针的连接方式,链表又可分成_____ ___和___ _____。

(A卷)第 5 页 共 8 页

2、对于一个具有n个顶点和e条边的有向图和无向图,在其对应的邻接表中,

所含边结点分别有___________个和__________个。

3、数据结构中评价算法的两个重要指标是算法的时间复杂度 和空间复杂度 。 4、循环队列的引入,目的是为了克服__ _____。 5、串是一种特殊的线性表,其特殊性表现在_数据元素是一个字符_ ;串的

两种最基本的存储方式是_顺序存储方式_、_链式存储方式_;两个串相等的充分必要条件是 两个串的长度相等且对应位置的字符相同_。 6、设 n 行 n 列的下三角矩阵 A 已压缩到一维数组 B[1..n*(n+1)/2]中,

若按行为主序存储,则 A[i][j]对应的 B 中存储位置为__ _____。 7、二叉树中某结点的左子树深度减去右子树深度称为该结点的

_____________ _,平衡二叉树的结点的可能取值是______________。 8、已知一个图如右图所示,若采用深度优先遍历该图,则遍

历的序列为 abcdegf 。

9、设某棵二叉树中度数为0的结点数为N0,度数为1的结点数为N1,则该二

叉树中度数为2的结点数为__N0-1_;若采用二叉链表作为该二叉树的存储结构,则该二叉树中共有_______个空指针域。

10、直接插入排序用监视哨的作用是 缓冲作用 。 得分 评卷人 四、判断题(每小题1分,共10分)

1、数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构。 ( )

2、链表中的头结点仅起到标识的作用。( )

3、为了很方便的插入和删除数据,可以使用双向链表存放数据。( ) 4、若输入序列为 1,2,3,4,5,6,则通过一个栈可以输出序列 1,5,4,6,2,3。( )

5、完全二叉树一定是满二叉树,满二叉树不一定是完全二叉树。( )

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4