《数据结构Ⅱ》在线平时作业1-00001

试卷总分:100  得分:100

一、单选题 (共 20 道试题,共 100 分)

1.若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为

A.f,c,b

B.f,d,b

C.g,c,b

D.g,d,b

2.对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时所需进行的关键字比较次数的平均值为

A.39/15

B.49/15

C.51/15

D.55/15

3.如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为

A.插入排序

B.归并排序

C.冒泡排序

D.堆排序

4.导致栈上溢的操作是

A.栈满时执行的出栈

B.栈满时执行的入栈

C.栈空时执行的出栈

D.栈空时执行的入栈

5.在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系

A.不一定相同

B.都相同

C.都不相同

D.互为逆序

6.以下属于逻辑结构的是

A.顺序表

B.哈希表

C.有序表

D.单链表

7.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是

A.2，4，3，1，5，6

B.3，2，4，1，6，5

C.4，3，2，1，5，6

D.2，3，5，1，6，4

8.对于哈希函数H(key)=key%13,被称为同义词的关键字是

A.35和41

B.23和39

C.15和44

D.25和51

9.下列陈述中正确的是

A.二叉树是度为2的有序树

B.二叉树中结点只有一个孩子时无左右之分

C.二叉树中必有度为2的结点

D.二叉树中最多只有两棵子树，并且有左右之分

10.下面关于数据结构正确的说法是

A.一种数据类型

B.数据的存储结构

C.一组性质相同的数据元素的集合

D.相互之间存在一种或多种特定关系的数据元素的集合

11.若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的

A.层次遍历算法

B.前序遍历算法

C.中序遍历算法

D.后序遍历算法

12.二叉树中第5层上的结点个数最多为

A.8

B.15

C.16

D.32

13.在用邻接表表示图时，拓扑排序算法时间复杂度为

A.O(n)

B.O(n＋e)

C.O(n*n)

D.O(n*n*n)

14.下列关键字序列中，构成小根堆的是

A.{84，46，62，41，28，58，15，37}

B.{84，62，58，46，41，37，28，15}

C.{15，28，46，37，84，41，58，62}

D.{15，28，46，37，84，58，62，41}

15.算法的时间复杂度主要取决于

A.问题的规模

B.待处理数据的初态

C.难度

D.A和B

16.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为

A.O(0)

B.O(1)

C.O(n)

D.O(n2)

17.由同一关键字集合构造的各棵二叉排序树

A.其形态不一定相同，但平均查找长度相同

B.其形态不一定相同，平均查找长度也不一定相同

C.其形态均相同，但平均查找长度不一定相同

D.其形态均相同，平均查找长度也都相同

18.为使平均查找长度达到最小,当由关键字集合{05,11,21,25,37,40,41,62,84}构建二叉排序树时,第一个插入的关键字应为

A.5

B.37

C.41

D.62

19.已知一个散列表如图所示，其散列函数为H(key)=key％11，采用二次探查法处理冲突，则下一个插入的关键字49的地址为

A.2

B.3

C.8

D.9

20.对长度为n的关键字序列进行堆排序的空间复杂度为

A.O（log2n）

B.O（1）

C.O（n）

D.O（n*log2n）