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

试卷总分:100  得分:100

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

1.在一个带权连通图G中，权值最小的边一定包含在G的

A.最小生成树中

B.深度优先生成树中

C.广度优先生成树中

D.深度优先生成森林中

2.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1  则T中的叶子数为

A.5

B.6

C.7

D.8

3.在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next=

  head,则

A.p指向头结点

B.p指向尾结点

C.p的直接后继是头结点

D.P的直接后继是尾结点

4.在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为

A.O(n)

B.O(n+e)

C.O(n2)

D.O(n3)

5.下列序列中，不构成堆的是

A.（1，2，5，3，4，6，7，8，9，10）

B.（10，5，8，4，2，6，7，1，3）

C.（10，9，8，7，3，5，4，6，2）

D.（1，2，3，4，10，9，8，7，6，5）

6.以下说法不正确的是

A.无向图中的极大连通子图称为连通分量

B.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点

C.图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点

D.有向图的遍历不可采用广度优先搜索

7.设一个栈的输入序列为12345，则借助一个栈所得到的输出序列不可能是

A.23415

B.54132

C.23145

D.15432

8.设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为

A.21

B.23

C.41

D.62

9.栈和队列都是

A.限制存取位置的线性结构

B.顺序存储的线性结构

C.链式存储的线性结构

D.限制存取位置的非线性结构

10.连通网的最小生成树是其所有生成树中

A.顶点集最小的生成树

B.边集最小的生成树

C.顶点权值之和最小的生成树

D.边的权值之和最小的生成树

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

A.35和41

B.23和39

C.15和44

D.25和51

12.对n个关键字的序列进行快速排序，平均情况下的空间复杂度为

A.O(1)

B.O(logn)

C.O(n)

D.O(n logn)

13.设有一个顺序栈的入栈序列是a、b、c，则3个元素都出栈的可能不同排列个数为

A.4

B.5

C.6

D.7

14.当采用分快查找时，数据的组织方式为

A.数据分成若干块，每块内数据有序

B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块

C.数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块

D.数据分成若干块，每块（除最后一块外）中数据个数需相同

15.若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是

A.10

B.11

C.12

D.15

16.文件中，主关键字能唯一标识

A.一个记录

B.一组记录

C.一个类型

D.一个文件

17.若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上

A.操作的有限集合

B.映象的有限集合

C.类型的有限集合

D.关系的有限集合

18.．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是

A.逆拓扑有序

B.拓扑有序

C.无序的

D.A和B

19.抽象数据类型的三个组成部分分别为

A.数据对象、数据关系和基本操作

B.数据元素、逻辑结构和存储结构

C.数据项、数据元素和数据类型

D.数据元素、数据结构和数据类型

20.树有先根遍历和后根遍历，树可以转化为对应的二叉树。下面的说法正确的是

A.树的后根遍历与其对应的二叉树的后根遍历相同

B.树的后根遍历与其对应的二叉树的中根遍历相同

C.树的先根遍历与其对应的二叉树的中根遍历相同

D.以上都不对