计算机考研数据结构试卷十（练习题含答案）.pdf

计算机考研数据结构试卷十（练习题含答案）

共25套适用于计算机考研数据结构系统练习

（PS：其他正在整理，敬请期待）

数据结构试卷10

一、选择题

1．下列程序段的时间复杂度为（）。

i=0，s=0；while(s

(A)O(n1/2)(B)O(n1/3)(C)O(n)(D)O(n2)

2．设某链表中最常用的操作是在链表的尾部插入或删除元素，则

选用下列（）存储方式最节省运算时间。

(A)单向链表(B)单向循环链表

(C)双向链表(D)双向循环链表

3．设指针q指向单链表中结点A，指针p指向单链表中结点A的

后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入

结点X的操作序列为（）。

(A)s-next=p-next；p-next=-s；

(B)q-next=s；s-next=p；

(C)p-next=s-next；s-next=p；

(D)p-next=s；s-next=q；

4．设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得

到的输出序列为（）。

(A)5，3，4，6，1，2(B)3，2，5，6，4，1

(C)3，1，2，5，4，6(D)1，5，4，6，2，3

5．设有一个10阶的下三角矩阵A（包括对角线），按照从上到

下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占

1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为（）。

(A)10(B)19(C)28(D)55

6．设一棵m叉树中有N

1个度数为1的结点，N

2

个度数为2的结点，……，Nm个

度数为m的结点，则该树中共有（）个叶子结点。

(A)∑

=-

m

i

i

N

i

1

)1

((B)∑

=

m

i

i

N

1

(C)∑

=

m

i

i

N

2

(D)∑

=

-

+

m

i

i

N

i

2

)1

(

1

7.二叉排序树中左子树上所有结点的值均（）根结点的值。

(A)(B)(C)=(D)!=

8.设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根

据这些权值集合

构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（）。

(A)129(B)219(C)189(D)229

9.设有n个关键字具有相同的Hash函数值，则用线性探测法把

这n个关键字映

射到HASH表中需要做（）次线性探测。

(A)n2(B)n(n+1)(C)n(n+1)/2(D)n(n-1)/2

10.设某棵二叉树中只有度数为0和度数为2的结点且度数为0的

结点数为n，

则这棵二叉中共有（）个结点。

(A)2n(B)n+l(C)2n-1(D)2n+l

11.设一组初始记录关键字的长度为8，则最多经过（）趟插入排

序可以得到

有序序列。

(A)6(B)7(C)8(D)9

12.设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，

R，D，F，X)，

则按字母升序的第一趟冒泡排序结束后的结果是（）。

(A)F，H，C，D，P，A，M，Q，R，S，Y，X

(B)P，A，C，S，Q，D，F，X，R，H，M，Y

(C)A，D，C，R，F，Q，M，S，Y，P，