22春《数据结构》作业4题目

试卷总分:100  得分:100

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

1.下列四种排序中___的空间复杂度最大。

A.插入排序

B.冒泡排序

C.堆排序

D.归并排序

2.

A.A

B.B

C.C

D.D

3.顺序查找法适合于存储结构为___的线性表。

A.散列存储

B.顺序存储或链式存储

C.压缩存储

D.索引存储

4.由权值分别为11,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为___。

A.24

B.71

C.48

D.53

5.

A.A

B.B

C.C

D.D

6.设一组初始记录关键字序列为（345,253,674,924,627），则用基数排序需要进行___趟的分配和回收才能使得初始关键字序列变成有序序列。

A.3

B.4

C.5

D.8

7.如果最常用的操作是取第i个结点及其前驱，则采用___存储方式最节省时间。

A.单链表

B.双链表

C.单循环链表

D.顺序表

8.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有___个空指针域。

A.2m-1

B.2m

C.2m+1

D.4m

9.

A.A

B.B

C.C

D.D

10.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用___存储方式最节省运算时间。

A.单链表

B.给出表头指针的单循环链表

C.双链表

D.带头结点的双循环链表

11.设某棵二叉树中有2000个结点，则该二叉树的最小高度为___。

A.9

B.10

C.11

D.12

12.若有18个元素的有序表存放在一堆数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A[3]的比较序列的下标依次为___。

A.1,2,3

B.9,5,2,3

C.9,5,3

D.9,4,2,3

13.若已知一个栈序列是1,2,3,...,n，其输出序列为p1,p2,p3,...,pn，若p1=n，则pi为___。

A.i

B.n-i

C.n-i+1

D.不确定

14.下述哪一条是顺序存储结构的优点___。

A.插入运算方便

B.可方便地用于各种逻辑结构的存储表示

C.存储密度大

D.删除运算方便

15.线性表的链式存储结构是一种___。

A.随机存取的存储结构

B.顺序存取的存储结构

C.索引存取的存储结构

D.Hash存取的存储结构

16.

A.A

B.B

C.C

D.D

17.

A.a

B.b

C.c

D.d

18.在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为___。

A.n

B.n/2

C.(n+1)/2

D.(n-1)/2

19.线性表是具有n个___的有限序列。

A.字符

B.数据元素

C.数据项

D.表元素

20.

A.A

B.B

C.C

D.D

奥鹏，国开，广开，电大在线，各省平台，新疆一体化等平台学习
详情请咨询QQ : 3230981406或微信:aopopenfd777