数据结构试题库 .pdfVIP

数据结构试题库

数据结构试题库

一、单项选择题

1.下列程序段所代表的算法的时间复杂度为（D）。

x=n;

y=0;

while(x=(y+1)*(y+1))

y++;

(A)O(n)(B)O(n2)(C)O(log2n)(D)O(n)

2.在一个长度为n的以顺序结构存储的线性表中，假设在线性表

的任何位置删除

元素的概率相等，则删除一个元素时线性表所需移动元素的平均

次数为（B）。

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

3.在一个栈顶指针为HS的链栈中插入一个*s结点时，应执行执

行操作为

（C）。

(A)HS-next=s;(B)s-next=HS-next;HS-next=s;

(C)s-next=HS;HS=s;(D)s-next=HS;HS=HSnext;

4.假设以带头结点的循环链表表示队列Q，并且队列只设一个头

指针front，不设

队列尾指针。若要进队一个元素*s，则在下列程序算法的空白处

应添加的操作语

句是（A）。

voidAddQueue(structlinkqueueQ)

{p=Q-front;

while(p-next!=Q-front)p=p-next;

}

(A)p-next=s;s-next=Q-front;

(B)Q-front-next=s;Q-front=s;

(C)s-next=p;p-next=Q-front;

(D)Q-front-next=s;s-next=p;

5.设高度为h的二叉树上只有度为0和度为2的结点，则此类二

叉树中所包含的

结点数至少为（B）。

(A)2h-1(B)2h-1+1(C)2h-1(D)2h-1-3

6．现有数据集{53,30,37,12,45,24,96}，从空二叉树逐个插入数

据形成二叉排序树，

v5

v4^

v1v2

v5^

v2^

v3

v3v6^

v6^v3^

v4^

v5v4

v6

^

若希望查找此二叉树中任一结点的平均查找长度最小，则应选择

下面哪个序列输入（C）。(A)45,24,53,12,37,96,30(B)

30,24,12,37,45,96,53

(C)37,24,12,30,53,45,96

(D)12,24,30,37,45,53,96

7.有一组数值{5,12,9,20,3}，用以构造哈夫曼树，则其带权路径

长度

WPL值为

（D）。(A)93

(B)96

(C)123

(D)103

8.已知一个有向图G的顶点v={v1,v2,v3,v4,v5,v6}，其邻接表如

下图所示，根据

有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点遍

历序列是（B）。(A)v1,v2,v3,v6,v4,v5(B)v1,v2,v3,v6,v5,v4

(C)v1,v2,v5,v6,v3,v4

(D)v1,v2,v5,v3,v4,v6

9.设有m=2n-1个关键字，假设对每个关键字查找的概率相等，

查找失败的概率为

0，若采用二分法查找一个关键字，则平均查找长度为（D）。

(A)n-1

(B)n-n/m

(C)(n-1)-n/m

(D)(n-1)+n/m

10．已知一个待散列存储的线性表

{18,81,58,34,26,75,67,49,93}

，散列函数为

h(k)=k%11，散列地址空间为0~10。若采用线性探查法解决冲

突，则平均查