数据结构（Java语言版）模拟试卷2（含参考答案）x.pdf

数据结构试卷（二）

一、选择题（每题3分，共24分）

1.下面关于线性表的叙述错误的是（D）。

A.线性表采用顺序存储必须占用一片连续的存储空间

B.线性表采用链式存储不必占用一片连续的存储空间

C.线性表采用链式存储便于插入和删除操作的实现

D.线性表采用顺序存储便于插入和删除操作的实现

2.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共

有（B）个空指针域。

A.2m-1

B.2m

C.2m+1

D.4m

3.设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元

素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为

（C）。

A.R-F

B.F-R

C.(R-F+M)％M

D.(F-R+M)％M

4.设某棵二叉树的中序遍历序列为ABCD、前序遍历序列为CABD，则后序遍历该二叉树

得到的序列为（A）。

A.BADC

B.BCDA

C.CDAB

D.CBDA

5.设某完全无向图中有n个顶点，则该完全无向图中有(A)条边。

A.n(n-1)/2

B.n(n-1)

C.n2

2

D.n-1

6.设某棵二叉树中有2000个结点，则该二叉树的最小高度为(C)。

A.9

B.10

C.11

D.12

7.设某有向图中有n个顶点，则该有向图对应的邻接表中有（B）个表头结点。

A.n-1

B.n

C.n+1

D.2n-1

8.设有一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟

快速排序的结果为（C）。

A.2，3，5，8，6

B.3，2，5，8，6

C.3，2，5，6，8

D.2，3，6，5，8

二、填空题(每空2分，共24分)

1.为了能有效地应用Hash查找技术，必须解决的两个问题是___如何构造哈希函数和如何

解决冲突。

2.下面程序段的功能实现数据x进栈，要求在下画线处填上正确的语句。

1classSqStack:

2def__init__(self):

3self.data=[None]*100

4self.top=0

5#......

6

7#......

8

9defpush(self,x):

10ifself.top==100:

11raise(overflow)

12else:

13__self.data[top]=x____

14___top=top+1___

3.中序遍历二叉排序树所得到的序列是____有序____序列(填有序或无序)。

2

4.快速排序的最坏时间复杂度为___O(n)_____，平均时间复杂度为___O(nlogn)_____。

5.设某棵二叉树中度数为0的结点数为N0，度数为1的结点数为N1，则该二叉树中度数

为2的结点数为____N-1___；若采用二叉链表作为该二叉树的存储结构，则该二叉树中共

0

有____N+2N____个空指针域。

10

6.设某无向图中的顶点数和边数分别为n和e，所有顶点的度数之和为d，则

e=____d/2____。

7.设一组初始记录关键字序列为(55，63，44，38，75，80，31，56)，则利用筛选法建立的

初始堆为____大根堆：（80，75，55，56，63，44，31，38）

小根堆：（31，38，44，56，75，80，55，63