数据结构习题

数据结构习题

一、 单选题

1. 研究数据结构就是研究 D

A) 数据的逻辑结构

B) 数据的逻辑结构和存储结构 C) 数据的存储结构

D) 数据的逻辑结构、存储结构及其数据在运算上的实现 2. 下面关于算法的说法，错误的是 D 。

A) 算法最终必须由计算机程序实现

B) 为解决某问题的算法与为该问题编写的程序含义是相同的 C) 算法的可行性是指指令不能有二义性 D) 以上几个都是错误的

3. 计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备

5个特性输入、输出 、 B 。 A) 可执行性、可移植性和可扩充性 B) 可执行性、有穷性和确定性 C) 确定性、有穷性和稳定性 D) 易读性、稳定性和确定性

4. 以下属于逻辑结构的概念是 C 。

A) 顺序表 B) 哈希表 C) 有序表 D) 单链表

5. 具有线性结构的数据结构是 D 。

A) 图 B) 树 C) 广义表 D) 栈

6. 数据的存储结构包括顺序、链接、散列和 D 种基本类型。

A) 向量 B) 数组 C) 集合 D) 索引

7. 根椐数据元素之间关系的不同特性，以下4类基本逻辑结构反映了4

类基本数据组织形式。下列解释错误的是 B 。

1

集合中任何两个结点之间都有逻辑关系，但组织形式松散 线性结构中结点按逻辑关系依次存储成一行

树型结构具有分支、层次特性，其形态有点像自然界中的树 图状结构中各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接

8. 在数据结构中，从逻辑上可以把数据结构分成 C 。

A) 动态结构和静态结构 B) 紧凑结构和非紧凑结构 C) 线性结构和非线性结构 D) 内部结构和外部结构

9. 与数据元素本身的形式、内容、相对位置、个数无关的是数据的

C 。

A) 存储结构 B) 存储实现 C) 逻辑结构 D) 运算实现

10. 以下说法错误的是 D 。

A) 程序设计的实质是算法设计

B) 数据的逻辑结构是数据的组织形式，基本运算规定了数据的基本

操作方式

C) 运算实现是完成运算功能的算法或这些算法的设计 D) 算法设计思想总是与数据的某种相应存储形式相联系

11. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除

第一个元素，则采用 D 存储方式最节省运算时间。 A) 单链表

B) 仅有头指针的单循环链表 C) 双链表

D) 仅有尾指针的单循环链表

12. 单链表的主要优点是 D 。

A) 便于随机查询 B) 存储密度高

C) 逻辑上相邻的元素在物理上也是相邻的 D) 插入和删除比较方便

13. 线性表采用链式存储时，其地址 D 。

A) 必须连续 B) 一定不连续 C) 部分连续

A) B) C) D)

2

D) 连续与否均可

14. 对于一个线性表，既要求能够较快地进行插入和删除，又要求存储结

构能够反映数据元素之间的逻辑关系，则应该 B 。 A) 以顺序方式存储 B) 以链接方式存储 C) 以散列方式存储 D) 以上均可

15. 若线性表中最常用的操作是取第i个的前趋元素，采用__A____

存储方式最节省时间。 A) 顺序表 B) 单链表 C) 双链表 D) 单循环链表

16. 若用单链表来表示队列，则应该选用 B 。

A) 带尾指针的非循环链表 B) 带尾指针的循环链表 C) 带头指针的非循环链表 D) 带头指针的循环链表

17. 若用一个大小为6的数组来实现循环队列，且当rear和front的值分

别为0和3。从队列中出队一个元素，再进队两个元素后，rear和front的值分别为 B A) 1和5 B) 2和4 C) 4和2 D) 5和1

18. 设栈的输入序列是(1、2、3，4)，则 D 不可能输出的序

列。

A) 1243 B) 2134 C) 1432 D) 4312

19. 一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的

是 B 。 A) 23415 B) 54132 C) 23145 D) 15432

3

20. 设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依

次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是 C 。 A) 6 B) 4 C) 3 D) 2

21. 一般情况下，将递归算法转换成等价的非递增归算法应该设置

A 。 A) 堆栈 B) 队列

C) 堆栈或队列 D) 数组

22. 设栈的输入序列是1、2、?、n，若输出序列的第一个元素是n，则第

i个输出元素 B 。 A) 不确定 B) n-i+l C) c D) n-i

23. 假定一个顺序循环队列的队首和队尾指针分别用front和rear表示，

则判队空的条件是 D 。 A) front+1==rear B) front==rear+1 C) front==O D) front==rear

24. 假定一个顺序循环队列存储于数组a[n]中，其队首和队尾指针分别用

front和rear表示，则判断队满的条件是 C 。 A) (rear-1)％n==front B) rear==(front-1)％／n C) (rear+1)％n==front D) rear==(front+1)％／n

25. 采用 D 数据结构设计一个判别表达式中左、右括号是否配

的算法最佳。

A) 线性表的顺序存储结构 B) 队列

C) 线性表的链式存储结构 D) 栈

4

26. 在下列算法描述中，涉及到队运算的算法是 D 。

A) 表达式求值算法 B) 深度优先搜索

C) 二叉树前中后序遍历 D) 广度优先搜索

27. 当利用大小为N的数组存储顺序循环队列时，该队列的最大长度为

B 。 A) N-2 B) N-1 C) N D) N+l

28. 链栈与顺序栈相比有一个明显的优点，即 B 。

A) 插入操作更加方便

B) 通常不会出现栈满的情况 C) 不会出现栈空的情况 D) 删除操作更加方便

29. 一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二

叉树一定满足 C 。

A) 所有的结点均无左孩子 B) 所有的结点均无右孩子 C) 只有一个叶子结点 D) 是任意一棵二叉树

30. 一棵完全二叉树上有1001个结点，其中叶子结点的个数是 D 。

A) 250 B) 500 C) 505 D) 501

31. 以下说法正确的是 C 。

A) 若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必

是该子树后序遍历序列中的最后一个结点

B) 若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必

是该子树中序遍历序列中的最后一个结点

C) 在二叉树中，具有两个子女的父结点，在中序遍历序列中，它的

后继结点最多只能有一个子女结点

D) 在二叉树中，具有一个子女的父结点，在中序遍历序列中，它没

有后继子女结点

32. 以下说法错误的是 C 。

5

A) 哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根

较近

B) 若一个二叉树的树叶是某子树中序遍历序列中的第一个结点，则

它必是该子树后序遍历序列中的第一个结点

C) 己知二叉树的前序遍历和后序遍历并不能惟一地确定这棵树，因

为不知道树的根结点是哪一个

D) 在前序遍历二叉树的序列中，任何结点其子树的所有结点都是直

接跟在该结点之后的

33. 二叉树在线索化后，仍不能有效求解的问题是 D 。

A) 前序线索二叉树中求前序后继 B) 中序线索二叉树中求中序后继 C) 中序线索二叉树中求中序前趋 D) 后序线索二叉树中求后序后继

34. 若二叉树采用链式存储结构，要交换其所有分支结点左、右子树的位

置，利用 A 遍历方法最合适。 A) 前序 B) 中序 C) 后序 D) 层次

35. 一棵有124个叶结点的完全叉树，最多有 B 个结点。

A) 247 B) 248 C) 249 D) 250

36. 设a、b为一棵二叉树上的两个结点。在中序遍历时，a在b前面的条

件是 B A) a在b的右方 B) a在b的左方 C) a是b的祖先 D) a是b的子孙

37. 在一棵具有n个结点的完全二叉树中，分枝结点的最大编号为

C 。

A) ((n+1)／2)下限取整 B) ((n-1)／2) 下限取整 C) (n／2) 下限取整 D) (n／2) 上限取整

38. 在N个结点的线索二叉树中，线索的数目为 C 。

6

A) N-1 B) N C) N+1 D) 2N

39. 设深度为K的二叉树上只有度为0和2的结点，则这类二叉树上所含

的结点总数至少为 C 。 A) K+1 B) 2K C) 2K-1 D) 2K+1

40. 设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有 D

个结点。 A) 13 B) 12 C) 26 D) 25

41. 以下说法错误的是 B 。

A) 存在这样的二叉树，对它采用任何次序遍历其结点访问序列均相

同

B) 二叉树是树的特殊情形

C) 由树转换成二叉树，其根结点的右子树总是空的

D) 在二叉树只有一棵子树的情况下也要明确指出该子树是左子树

还是右子树

42. 若二叉树是 C 则从二叉树的任一结点出发到根的路径上

所经过的结点序列按其关键字有序。 A) 二叉排序树 B) 哈夫曼树 C) 堆

D) 退化二叉树

43. 一棵有n个结点的二叉树，按层次从上到下，同一层从左到右的顺序

存储在一维数组A[1．．n)中，则二叉树中第i个结点(i从1开始用上述方法编号)的右孩子在数组A中的位置是 D 。 A) A[2i] (2i≤n B) A[2i+1) (2i+1≤n) C) A[i/2]

D) 条件不充分，无法确定

44. 将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉

7

树的高度是 C 。

A) 4 B) 5 C) 6 D) 7

45. 下列有关二叉树的说法正确的是 B 。

A) 二叉树的度为2

B) 一棵二叉树度可以小于2

C) 二叉树中至少有一个结点的度为2 D) 二叉树中任一个结点的度都为2

46. 某二叉树中序序列为ABCDEFG，后序序列为BDCAFGE，则前序序列是

B 。， A) EGFACDB B) EACBDGF C) EAGCFBD

D) 上面的都不对

47. 对二叉排序树进行 B 遍历，可以得到该二叉树所有结点构

成的排序序列 A) 前序 B) 中序 C) 后序 D) 按层次

48. C 的遍历仍需要栈的支持。

A) 前序线索树 B) 中序线索树 C) 后序线索树 D) 层次遍历

49. 在一棵深度为h的完全二叉树中，所含结点的个数不小于

D 。

h

A) 2

h+1

B) 2

h

C) 2-1

h-1

D) 2

50. 在一棵具有n个结点的二叉树第i层上，最多具有 C 个结

点。

i

A) 2

i+1

B) 2

8

C) 2

n

D) 2

51. 树最适合用来表示 C 。

A) 有序数据元素 B) 无序数据元素

C) 元素之间具有分支层次关系的数据 D) 元素之间无联系的数据

52. 以下说法错误的是 D 。

A) 一般在哈夫曼树中，权值越大的叶子离根结点越近 B) 哈大曼树中没有度数为1的分支结点

C) 若初始森林中共有n棵二叉树，最终求得的哈夫曼树中共有2n-1

个结点

D) 若初始森林中共有n棵二叉树，进行2n-1次合并后才能剩下最终

的哈夫曼树

53. 以下说法错误的是 C 。

A) 二叉树可以是空集

B) 二叉树的任一结点都可以有两棵子树 C) 二叉树与树具有相同的树形结构

D) 二叉树中任一结点的两棵子树有次序之分

54. 某二叉树的前序序列和后序序列正好相反，则该二叉树一定是

________A 的二叉树。

A) 空或只有一个结点 B) 任一结点无左子树 C) 高度等于其结点数 D) 任一结点无右子树

55. 设无向图的顶点个数为n，则该无向图最多有 B 条边。

A) n-1

B) n(n-1)/2 C) n(n+1)/2 D) 0

2

E) n

56. 采用邻接表存储的图，其深度优先遍历类似于二叉树的 B 。

A) 中序遍历 B) 先序遍历 C) 后序遍历 D) 按层次遍历

57. 采用邻接表存储的图，其广度优先遍历类似于二叉树的 A 。

i-1

9

A) 按层次遍历 B) 中序遍历 C) 后序遍历

D) 先序遍历 ，

58. 一个图中包含有七个连通分量，若按深度优先(DFS)遍历,必须调用

____A___次深度优先遍历算法。 A) k B) 1 C) k-1 D) k+1

59. 下列说法中不正确的是 D

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

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

的顶点

C) 图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D) 有向图的遍历不可采用广度优先搜索方法

60. 具有n个顶点的有向图最多有 B 条边。

A) n

B) n(n-1) C) n(n+1)

2

D) n

61. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情况下

不可能出现的是 D 。

A) G中有弧

B) G中有一条从Vi到Vj的路径 C) G中没有弧

D) G中有一条从Vj到Vi的路径

62. 一个n个顶点的连通无向图，其边的个数至少为 A 。

A) n-1 B) n C) n+l D) nlog2n

63. 下列说法中，正确的有 C 。

A) 最小生成树也是哈夫曼树。 B) 最小生成树惟一

2

C) 普里姆(Prim)最小生成树算法时间复杂度为O(n)

D) 克鲁斯卡尔(Kruskal)最小生成树算法比普里姆算法更适合于边

10

稠密的网

64. 判定一个有向图是否存在回路，除了可以利用拓扑排序的方法外，还

可以利用 C 。

A) 求关键路径的方法

B) 求最短路径的Dijkstra方法 C) 深度优先遍历算法 D) 广度优先遍历算法

65. 在一个具有n个顶点的有向图中，若所有顶点的出度之和为s，则所

有顶点的入度之和为 A 。

A) s B) s-1 C) s+l D) n

66. 在一个无向图中，若两个顶点之间的路径长度为k条边，则该路径上

的顶点数为 B 。 A) k B) k+l C) k+2 D) 2k

67. 一个有n个顶点的无向连通图，它所包含的连通分量个数为

B 。 A) 0 B) 1 C) n D) n+1

68. 对于一个有向图，若一个顶点的入度为k1、出度为k2，则对应邻接表

中该顶点单链表中的结点数为 B 。 A) kl B) k2 C) k1-k2 D) k1+k2

69. 对于一个有向图，若一个顶点的入度为k1、出度为k2，则对应逆邻接

表中该顶点单链表中的结点数为 A 。 A) kl B) k2 C) k1-k2 D) k1+k2

11

70. 对于一个无向图，下面 A 的说法是正确的。

A) 每个顶点的入度等于出度

B) 每个顶点的度等于其入度与出度之和 C) 每个顶点的入度为0 D) 每个顶点的出度为0

71. 为了方便地对图状结构的数据进行存取操作，则其中数据存储结构宜

采用 B 。 A) 顺序存储 B) 链式存储 C) 索引存储 D) 散列存储

72. 设有一个按各元素的值排好序的线性表且长度大于2，对给定的值X，

分别用顺序查找法和二分查找法查找一个与K相等的元素，比较次数分别是s和b：在查找不成功的情况下，正确的s和b的数量关系是 B 。

A) 总有s=b B) 总有s>b C) 总有s

D) 与K值大小有关

73. 若在线性表中采用折半查找法查找元素，该线性表应该 C 。

A) 元素按值有序 B) 采用顺序存储结构

C) 元素按值有序，且采用顺序存储结构 D) 元素按值有序，且采用链式存储结构

74. 假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入

散列表中，至少要进行 D 次探测。 A) k-1次 B) k次 C) k+1次

D) k(k+1)／2次

75. 设散列地址空间0～m-1，k为关键字，用p去除k，将余数作为k的

散列地址 (h(k)=k%p)，为了减少发生冲突的可能性，一般取P为 B 。

A) 小于m的最大奇数 B) 小于m的最大素数 C) 小于m的最大偶数 D) 小于m的最大合数

12

76. 设散列表的长m=14，散列函数为h(k)=k，表中已有4个记录(如图

所示)如果用二次探测再散列来处理冲突，则关键字为49的记录其存储地址是 D 。

0 1 2 3 4 5 6 7 8 9 10 11 12 13 15 38 61 84 图 散列表

A) 8 B) 3 C) 5 D) 9

77. 从具有n个结点的二叉排序树中查找一个元素时，最坏情况下的时间

复杂性 A 。

A) O(n) B) O(1) C) O(log2n)

2

D) O(n)

78. 下面关于二叉排序树论述中，错误的是 C 。

A) 当所有结点的权值都相等时，用这些结点构造的二叉排序树除根

结点外只有右子树

B) 中序遍历二叉排序树的结点就可以得到排好序的结点序列

C) 任一二叉排序树的平均查找时间都小于用顺序查找法查找同样

结点的线性表的平均查找时间

D) 对两棵具有相同关键字集合而形状不同的二叉排序树，按中序遍

历得到的序列是一样的

79. 以下说法错误的是 B 。

A) 散列法存储的基本思想是由关键码值决定数据的存储地址 B) 散列表的结点中只包含数据元素自身的信息，不包含任何指针 C) 装填因子是散列法的一个重要参数，它反映了散列表的装填程度 D) 散列表的查找效率主要取决于散列表造表时选取的散列函数和

处理冲突的方法

80. 设有一个用线性探测法解决冲突得到的散列表如图所示

0 1 2 3 4 5 6 7 8 9 10 13 25 80 16 17 6 14 图 散列表

散列函数为H=％11，若要查找元素14，探测的次数是 D 。

A) 8 B) 9

13

C) 3 D) 6

81. 如果要求一个线性表既能较快地查找，又能适应动态变化的要求，则

可采用的查找方法是 A 。 A) 分块查找 B) 顺序查找 C) 折半查找 D) 基于属性查找

82. 有数据{53，30，37，12，45，24，96}，从空二叉树开始逐个插入数

据来形成二叉排序树，若希望高度最小，则应选择下面哪个序列输入 B 。

A) 45,24,53，12,37,96,30 B) 37,24,12,30,53,45,96 C) 12,24,30,37,45,53,96 D) 30,24,12,37,45,96,53

83. 建立序列{50，72，43，85，75，20，35，45，65，30}对应的二叉排

序树以后，查找元素35要进行 A 元素间的比较 A) 4次 B) 5次 C) 7次 D) 10次

84. 在顺序表(n足够大)中进行顺序查找，其查找不成功的平均长度是

D 。

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

85. 对线性表进行二分检索时，要求线性表必须 C 。

A) 以顺序存储方式存储 B) 以链式存储方式存储

C) 以顺序存储方式存储且数据有序 D) 以链式存储方式存储且数据有序

86. 在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最

长查找长度 A) n B) log2n C) (h+1)／2

14

D) h

87. 在散列查找中，平均查找长度主要与 C 有关。

A) 散列表长度 B) 散列元素个数 C) 装填因子 D) 处理冲突方法

88. 若根据查找表建立长度为m的散列表并采用二次探测处理冲突，假定

对—个元素第一次计算的散列地址为d，则第四次计算的散列地址为 C 。

A) (d+1)％m B) (d-1)％m C) (d+4)％m D) (d-4)％m

89. 以下说法正确的是 A 。

A) 数字分析法需事先知道所有可能出现的键值及所有键值的每一

位上各数字分布情况，并且键值的位数比散列地址的位数多 B) 除余法要求事先知道全部键值

C) 平方取中法需要事先掌握键值的分布情况 D) 随机数法适用于键值不相等的场合 90. 分块查找的时间效率 B 。

A) 低于二分查找

B) 高于顺序查找而低于二分查找 C) 高于顺序查找

D) 低于顺序查找而高于二分查找

91. 在一个具有n个结点的单链表中查找值为m的某结点，若查找成功，

则平均比较 D 个结点。 A) n B) n／2 C) (n-1)／2 D) (n+1)／2

92. 以下序列不是堆的是 D 。

A) (100,85,98,77,80,60,82,40,20,10,66) B) (100,98,85,82,80,77,66,60,40,20,10,) C) (10,20,40,60,66,77,80,82,85,98,100) D) (100,85,40,77,80,60,66,98,82,10,20,)

93. 在文件“局部有序”或文件长度较小的情况下，最佳内部排序方法是

____A

15

A) 直接插入排序 B) 冒泡排序 C) 简单选择排序 D) 归并排序 94. 在下列算法中， C 算法可能出现下列情况：在最后一趟开始之前，

所有的元素都不在其最终的位置上。 A) 堆排序 B) 冒泡排序 C) 插入排序 D) 快速排序

95. 从未排序的序列中依次取出一个元素与已排序序列中的元素依次进行

比较，然后将其放在排序序列的合适位置，该排序方法称为 A 排序法。 A) 插入 B) 选择 C) 希尔 D) 二路归并

96. 下面给出的四种排序法中， D 排序是不稳定排序法。

A) 插入 B) 冒泡 C) 二路归并 D) 堆

2

97. 快速排序在最坏情况下时间复杂度是O(n)，比 A 的性能差。

A) 堆排序 B) 冒泡排序 C) 选择排序 D) 二路归并

98. 对给出的一组关键字{14，5，19，20，11，19}。若按关键字非递减排

序，第一趟排序结果为{14，5，19，20，11，19}，问采用的排序算法是 C 。

A) 简单选择排序 B) 快速排序 C) 希尔排序 D) 二路归并排序

99. 就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关

系是 A 。

A) 堆排序<快速排序<归并排序

16

B) 堆排序<归并排序<快速排序 C) 堆排序>归并排序>快速排序 D) 堆排序>快速排序>归并排序 E) 以上答案都不对

100.假设某文件经过内部排序得到27个初始归并段，若要使多路归并3

趟完成，则应取归并的路数为 B 。 A) 2 B) 3 C) 4 D) 5

101.下面排序方法中，关键字比较次数与记录的初始排列无关的是 D 。

A) 希尔(Shell)排序 B) 冒泡排序 C) 直接插入排序 D) 直接选择排序

102.对记录的关键字集合key={50，26，38，80，70，90，8，30，40，20}

进行排序，各趟排序结束时的结果为: 50 26 38 80 70 90 8 30 40 20 50 8 30 40 20 90 26 38 80 70 26 8 30 40 20 80 50 38 90 70 8 20 26 30 38 40 50 70 80 90 其使用的排序方法是 C 。

A) 快速排序 B) 基数排序 C) 希尔排序 D) 归并排序

103.一组记录的关键字为{45，80，50，40，42，85}则利用堆排序的方法

建立的初始堆为 B 。 A) 45 50 40 42 85 B) 80 50 40 42 45 C) 80 50 45 42 40 D) 50 80 42 45，40，

104.一组记录的关键字为{25，50，15，35，80，85，20，40，36，70}，

其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果为 A 。

A) 15，25，35，50，20，40，80，85，36，70 B) 15，25，35，50，80，20，85，40，70，36

17

C) 15，25；50，35，80，85，20，36，40，70 D) 15，25，35，50，80，20，36，40，70，85

105.在对n个元素进行冒泡排序的过程中，最好情况下的时间复杂性为

D 。

A) O(1) B) O(Log2n)

2

C) O(n) D) O(n)

106.在对n个元素进行快速排序的过程中，第一次划分最多需要移动

次元素(包括开始将基准元素移到临时变量的那一次)___D____。 A) n／2 B) n-1 C) n D) n+1

107.下述几种排序方法中，要求内存量最大的是 D 。

A) 插入排序 B) 选择排序 C) 快速排序 D) 归并排序

2

108.下面排序方法中，时间复杂性不是O(n)的是 B 。

A) 直接插入排序 B) 二路归并排序 C) 冒泡排序 D) 直接选择排序

109.一个序列中有10000个元素，若只想得到其中前10个最小元素，最好

采用 B 法。 A) 快速排序 B) 堆排序 C) 插入排序 D) 二路归并排序

110.对下列4个序列用快速排序方法进行排序，以序列的第1个元素为基

准进行划分。在第1趟划分过程中，元素移动次数最多的是序列 A 。

A) 70，75，82，90，23，16，10，68 B) 70，75，68，23，10，16，90，82 C) 82，75，70，16，10，90，68，23 D) 23，10，16，70，82，75，68，90

18

111.在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是

B 。

A) O(log2n) B) O(1) C) O(n)

D) O(nlog2n)

112.对下列4种排序方法，在排序中关键字比较次数同记录初始排列无关

的是 A 。 A) 直接插入 B) 二分法插入 C) 快速排序 D) 归并排序

113.采用简单选择排序，比较次数与移动次数分别是 C 。

A) O(n)，O(log2n)

2

B) O(log2n)，O(n)

2

C) O(n)，O(n) D) O(nlog2n)，O(n)

114.归并排序中，归并的趟数是 B 。

A) O(n) B) O(log2n) C) O(nlog2n)

2

D) O(n)

115.在待排序的元素序列基本有序的前提下，效率最高的排序方法是

A 。

A) 插入排序 B) 选择排序 C) 快速排序 D) 归并排序

116.直接插入排序在最好情况下的时间复杂度为 B 。

A) O(log2n) B) O(n)

C) O(nlog2n)

2

D) O(n)

117.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数

是 A 。 A) n B) 2n-1

19

C) 2n D) n-1

118.下列排序算法中，稳定的排序算法是 C 。

A) 堆排序 B) 快速排序 C) 基数排序 D) 希尔排序

119.就平均性能而言，目前最好的内排序方法是 D 排序法。

A) 冒泡 B) 希尔插入 C) 交换 D) 快速

120.快速排序 C 在情况下不利于发挥其长处。

A) 待排序数据量太大 B) 待排序数据相同值过 C) 待排序数据已基本有序 D) 待排序数据值差过大

121.在对n个元素进行直接选择排序过程中，第i趟需从 A 个元素中

选择出最小元素。 A) n-i+l B) n-i C) i D) i+1

122.若对n个元素进行直接选择排序,是进行任一趟排序的过程中，为寻找

最小值元素所需要的时间复杂性为 D 。 A) O(1) B) O(log2n)

2

C) O(n) D) O(n)

123.在下列排序方法中，空间复杂性为O(log2n)的方法是 D 。

A) 直接选择排序 B) 归并排序 C) 堆排序 D) 快速排序

124.从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进

行比较，将其放入已排序序列的正确位置上的方法，称为 C 。 A) 希尔排序

20

于2，其他结点的度数必须等于2的二叉排序树才是最佳二叉树。(对) 64. 任意一棵二叉排序树的平均查找时间都小于用顺序查找法查找同样结

点的线性表的平均查找时间。(错)

65. 哈希表的查找效率主要取决于哈希表造表时选取的哈希函数和处理冲

突的方法。(对)

66. 在采用线性探测法处理冲突的散列表中，所有同义词在表中一定相邻。

(错)

67. 对二叉排序树的查找都是从根结点开始的，则查找失败一定落在叶子

上。(错)

68. 顺序查找法适用于存储结构为顺序或链接存储的线性表。(对)

69. 负载因子(装填因子)是散列表的一个重要参数，它反映散列表的装满

程度。(对)

70. 中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。(对) 71. 二叉排序树的查找和折半查找时间的性能相同。(错)

72. 散列法存储的基本思想是由关键码的值决定数据的存储地址。(对) 73. 虽然关键字序列的顺序不一样，但依次生成的二叉排序树是一样的。

(错)

74. 在所有结点的权都相等的情况下，具有平衡特性的二叉排序树一定是

最佳二叉排序树。(对)

75. 快速排序的速度在所有排序方法中为最快，而且所需附加空间也最少。

(错)

76. 外部排序是把外存文件调入内存，可利用内部排序的方法进行排序，

因此排序所花的时间取决于内部排序的时间。(错) 77. 一般说来，外排序所需要的总时间=内排序时间+外存信息读写时间+内

部归并所需要的时间。(对)

78. 外排序过程主要分为两个阶段：生成初始归并段和对归并段进行逐趟

归并的阶段。(对)

79. 内排序中的快速排序方法，在任何情况下均可得到最快的排序效果。

(错)

80. 基数排序的设计思想是依照对关键字值的比较来实施的。(错) 81. 在快速排序算法中，不可以用队列替代栈。(错)

82. 用希尔(Shell)方法排序时，若关键字的初始排序杂乱无序，则排序效

率就低。(错)

83. 当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多

的时间，这是影响时间复杂度的主要因素。(对)

84. 对于n个记录的集合进行归并排序，在最坏情况下所需要的时间是

2

O(n)。(错)

41

85. 对于n个记录的集合进行冒泡排序，在最坏情况下所需要的时间是

2

O(n)。(对)

86. 对一个堆，按二叉树层次进行遍历可以得到一个有序序列。(错) 87. 有一最小堆，堆中任意结点的关键字均小于它的左、右孩子关键字。

则其具有最大值的结点一定是一个叶结点并可能在堆的最后两层中。(对)

88. (101，88，46，70，34，39，45，58，66，10)是堆。(对) 89. 减少初始归并段的数量，可使外排序的时间缩短。(错) 90. 采用多路归并方法可以减少初始归并段的数量。(对)

91. 如果某种排序算法是不稳定的，则该方法没有实际应用价值。(错) 92. 对于n个记录的集合进行快速排序，所需要的附加空间数是O(n)。(错)

2

93. 对n个记录进行快速排序，在最坏情况下所需要的时间是O(n) (对) 94. 堆排序所需时间与待排序记录的个数无关。(错) 95. 外部排序与外部设备的特性无关。(错) 96. 归并排序要求的辅加空间最多。(错) 97. 用ISAM组织文件适合于磁带。(错)

98. 检索出文件中关键码值落在某个连续范围内的全部记录，这种操作称

为范围检索。对经常需要作范围检索的文件进行组织，采用散列法优于采用顺序索引法。(对)

99. 顺序文件是利用磁带的特有性质实现的，因此顺序文件只能存放在磁

带中。(错)

100.变更磁盘上顺序文件的记录内容时，不一定要复制整个文件。(对) 101.索引顺序文件是一种特殊的顺序文件，因此通常存放在磁带上。(错) 102.对于满足折半查找和分块查找条件的文件而言，无论它存放在何种介

质上，均能进行顺序查找、折半查找和分块查找(错)

103.文件中每个记录最多只有一个后继记录和一个前驱记录，而文件的第

一个记录只有后继而没有前驱，最后一个记录只有前驱却没有后继；因此，文件可看成是一种线性结构。(对)

104.在索引顺序文件中插入新的记录时，必须复制整个文件。(错) 105.直接访问文件也能顺序访问，但一般效率较差。(对)

106.记录的逻辑结构是记录在用户面前呈现的方式，是用户对数据的表示

和存取方式。(对)

107.磁盘上顺序文件插入新的记录时，必须复制整个文件。(错)

108.记录的物理结构是数据在物理存储介质上的存储方式，是数据的物理

表示和组织。(对)

109.文件是记录的集合，每个记录由一个或多个数据项组成，因而一个文

件可看作由多个记录组成的数据结构。(对)

42

110.存放在磁带、磁盘上的文件，既可以是顺序文件也可以是索引结构或

其他结构类型的文件。(错)

五、 简答题

1. 试比较顺序存储结构和链式存储结构的优劣性 2. 试述数据结构的定义 3. 简述结构类型的组成

4. 简述顺序存储和动态存储的特点 5. 简述算法效率的评价内容

6. 简述静态存储分配和动态存储分配的特点 7. 哈希查找技术发生冲突的原因 8. 算法和程序的关系

9. 试述分类二叉树的特点及如何构造深度最小的分类二叉树 10. 试述堆树的特点

11. 一棵非空的二叉树其先序序列和后序序列正好相反，画出这棵二叉树

的可能形状。

12. 试证明有n0个叶子结点的哈夫曼树共有2n0-1个结点。 13. 一棵有k个叶结点的完全叉树，最多有2k个结点。

14. 设深度为K的二叉树上只有度为0和2的结点，则这类二叉树上所含

的结点总数至少为2k+1。

15. 设有k个值，用它们组成一棵二叉哈夫曼树，则该哈夫曼树共有多少

个结点？

六、 图示给出算法执行过程及结果

1. 给出数据{4，6，50，10，20，3}为结点权值所构成的哈夫曼

树（给出步骤）及加权路径长度。

2. 给出数据{18，14，25，30，24，15}组成的分类二叉树（左

小右大）及前序、中序、后序遍历的结果。 3. 给出下列数据结点值构成的初始堆的过程。 0 1 2 3 4 5 6 7 8 9 10 53 12 5 97 55 24 15 36 16 62

4. 给出图的0点到其它顶点间的最短路径（给出步骤）。(8分)

43

０ 20 120

１ ４ 25

10

20 30

２ ３ 30

5. 给出图的所有顶点间的最短路径（给出步骤）。 ０ 20 120

25 １ ４

10 20 30 ２ ３ 30

6. 给出图的0点到其它顶点的最短路径（给出步骤）。 答：

０ 20 43

25 １ ４

17 7 10 20 30

２ ３ 30

7. 给出下面二叉树的中序左右线索树。（５分）

44

8. 用Prim算法给出图的最小生成树（画出步骤）。

9. 用Kruskal算法给出图的最小生成树（画出步骤）。

45

B) 冒泡排序 C) 插入排序 D) 选择排序

125.从未排序序列中挑选元素，并将其依次放入已排序序列(初始时为空)

一端的方法称为 D 。 A) 希尔排序 B) 归并排序 C) 插入排序 D) 选择排序

126.用ISAM和VSAM组织文件属于 B 。

A) 顺序文件 B) 索引文件 C) 散列文件

127.索引顺序文件是 B 。

A) HASH文件 B) ISAM文件 C) 顺序文件 D) 索引文件

128.删除ISAM文件记录时，一般 A 。

A) 只需做删除标志 B) 需移动记录 C) 需改变指针

D) 一旦删除就要做整理

129.直接存取方法是利用 A 进行组织的文件。

A) HASH法 B) 顺序索引法 C) VSAM法 D) ISAM法

130.倒排文件的主要优点是 D 。

A) 便于进行插入和删除运算 B) 便于节省存储空间 C) 便于进行文件合并

D) 能大大提高基于非关键字的检索速度

131.散列文件使用散列函数将记录的关键字值计算转化为记录的存放地

址，因为散列函数是一对一的关系，所以选择好的 D 方法是散列文件(Hash)的关键。 A) 散列函数

21

B) 除余法中的质数 C) 冲突处理

D) 散列函数和冲突处理

132.倒排文件包含有若干个倒排表，倒排表的内容是 D ，倒排文件检

查速度快但修改、维护较难。

A) 一个关键字值和该关键字的记录地址 B) 一个属性值和该属性的一个记录地址 C) 一个属性值和该属性的全部记录地址

D) 承多个关键字值和它们相对应的某个记录地址 133.影响文件检索效率的一个重要因素是 C 。

A) 逻辑记录的大小 B) 物理记录的大小 C) 访问外存的次数 D) 设备的读写速度 134.顺序文件适于 B 。

A) 直接存取 B) 成批处理 C) 按关键字存取 D) 随机存取

135.对散列文件，以下说法错误的是 D 。

A) 散列文件插入、删除方便，不需要索引区且节省存储空间 B) 散列文件只能按关键字随机存取且存取速度快

C) 经过多次插入、删除后，可能出现溢出桶满而基桶内多数记录已

被删除的情况

D) 散列文件顺序存取方便

136.对于一个索引顺序文件，索引表中的每个索引项对应主文件中的

B 。

A) 一条记录 B) 多条记录 C) 所有记录 D) 三条以下记录

137.对于索引文件，稠密索引中的每个索引项对应被索引表中的 C 。

A) 所有记录 B) n条以下记录 C) 一条记录 D) 多条记录

138.VSAM文件的索引集是一个 D 。

22

A) 二叉排序树结构 B) 散列表结构 C) 线性表结构 D) B+树结构

139.散列文件又称按桶散列文件，若散列文件中含有m个基桶，每个桶能

够存储m个记录，若不使用溢出桶，则该散列文件最多能够存储 ___D___个记录。 A) m+k B) m×k-1 C) m×k+l D) m×k

140.对文件进行直接存取的依据是 A 。

A) 按逻辑记录号去存取某个记录 B) 按逻辑记录的结构去存取某个记录 C) 按逻辑记录的关键字去存取某个记录 D) 按逻辑记录的具体内容去存取某个记录 141.直接存取文件的特点是 D 。

A) 记录按关键字排序 B) 记录可以进行顺序存取

C) 存取速度快但占用较多的存储空间 D) 记录不需要排序且存取效率高

142.索引顺序文件的记录，在逻辑上按关键字的顺序排列，但物理上不一

定按关键字顺序存储，故需建立一张指示逻辑记录和物理记录之间一一对应关系的 A 。 A) 索引表 B) 链接表 C) 符号表 D) 交叉访问表

143.以下说法错误的是 D 。

A) 在磁带上的顺序文件的最后添加新的记录时不必复制整个文件 B) 索引顺序文件既能顺序访问又能随机访问

C) 变更磁盘上的顺序文件记录的内容时，不一定要复制整个文件 D) 索引顺序文件是一种特殊的顺序文件，因此通常放在磁带上

二、 多项选择题

1. 数据元素是 BDE 。

23

A) 数据集合中的一个个体 B) 数据的基本单位 C) 数据的最小单位 D) 一个结点 E) 一个记录

2. 数据结构被形式地定义为(K，R)，其中K是 B 的有限集，R是K

上的 D 有限集。 A) 算法 B) 数据元素 C) 数据操作 D) 逻辑结构

A) 操作 B) 映像 C) 存储 D) 关系

3. 线性表的说法错误的是 ABC

A) 每个元素都有一个直接前驱和一个直接后继 B) 线性表中至少要有一个元素

C) 表中诸元素的排列顺序必须是由小到大或由大到小

D) 除第一个和最后一个元素外，其余每个元素都有一个且仅有一个

直接前驱和直接后继

4. 以下说法错误的是 ABC

A) 顺序存储方式的优点是存储密度大且插入、删除运算效率高 B) 链表的每个结点中都恰好包含一个指针 C) 线性表的顺序存储结构优于链式存储结构

D) 顺序存储结构属于静态结构而链式结构属于动态结构

5. 以下说法正确的是 BCD

A) 对循环链表来说，从表中任一结点出发都能通过前后移操作扫描

整个循环链表

B) 对简单链表来说，只有从头结点开始才能扫描表中全部结点 C) 双链表的特点是找结点的前趋和后继都很容易

D) 对双链表中来说，结点中既存放其前趋结点指针，也存放后继结

点指针

6. 以下说法正确的是 ABC 。

24

A) 求表长、定位这两种运算在采用顺序存储结构时实现的效率不比

采用链式存储结构时实现的效率低 B) 顺序存储的线性表可以直接存取

C) 由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活 D) 线性表的链式存储结构优于顺序存储结构 7. 便于插入和删除操作的是 ACD

A) 单链表 B) 顺序表 C) 双链表 D) 循环链

8. 从表中任一结点出发都能扫描整个链表的是 CD

A) 单链表 B) 顺序表 C) 双链表 D) 循环链表

9. 双向链表的主要优点是 BD 。

A) 不再需要头指针

B) 已知某结点位置后能容易找到其直接前趋 C) 在进行插入、删除运算时能保证链表不断开 D) 从表中任一结点出发都能扫描整个链表

10. 对顺序表的优缺点，以下说法正确的是 ABD 。

A) 无需为表示结点间的逻辑关系而增加额外的存储空间 B) 可以方便地随机取表中的任一结点 C) 插入和删除运算较为方便

D) 由于要求占用连续空间，所以存储分配只能预先进行(静态分配) 11. 循环队列是 AC 。

A) 顺序存储结构 B) 不会产生下溢 C) 不会产生假溢 D) 不会产生上溢

12. 以下说法正确的是 ACD 。

A) 存在这样的二叉树，对它采用任何次序遍历其结点访问序列均相

同

B) 二叉树是树的特殊情形

C) 由树转换成二叉树，其根结点的右子树总是空的

D) 在二叉树只有一棵子树的情况下也要明确指出该子树是左子树

还是右子树

25

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

少为 B ，至多为 B 。 A) 2h B) 2h-1 C) 2h+1 D) h+1

h-1

A) 2

h

B) 2-1

h+1

C) 2+1

h

D) 2+1

14. 对于前序遍历与中序遍历结果相同的_____F 。前序遍历与后序遍历

结果相同的二叉树为____B 。 A) 一般二叉树

B) 只有根结点的二叉树 C) 根结点无左孩子的二叉树 D) 根结点无右孩子的二叉树 E) 所有结点只有左子树的二叉树 F) 所有结点只有右子树的二叉树

15. 完全二叉树 AD 。

A) 适合于用顺序结构存储 B) 叶子结点可在任一层出现

C) 某些结点有左子树则必有右子树 D) 某些结点有右子树则必有左子树

16. 下列有关二叉树的说法错误的是 ACD 。

A) 二叉树的度为2

B) 一棵二叉树度可以小于2

C) 二叉树中至少有一个结点的度为2 D) 二叉树中任一个结点的度都为2

17. 下面哪一个方法可以判断出一个有向图中是否有环(回路)。__AB___

A) 深度优先遍历 B) 拓扑排序 C) 求最短路径 D) 求关键路径

26

18. 对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表

向量的大小为(1)__A__，所有顶点的邻接表的结点总数为(2)__C__。 (1) A)n B)n+1 C)n-1 D)n+e (2) A)e／2 B)e C)2e D)n+e 19. 图的应用算法有 ABD 。

A) 克鲁斯卡尔算法 B) 哈夫曼算法 C) 拓扑排序算法 D) 迪杰斯特拉算法

20. 对初始状态为递增序列的表按递增序列排序，最省时间的是(1 C )

算法，最费时间的是（2 B ）算法 A) 堆排序 B) 快速排序 C) 插入排序 D) 归并排序

21. 在下述排序算法中，所需辅助存储量最多的是 (1B)，所需辅助存储量

最少的是(2C)，平均速度最快的是(3A) A) 快速排序 B) 归并排序 C) 堆排序

22. 在堆排序过程中，由n个待排序的记录建成初始堆需要(1B)次筛选：

由初始堆到排序结束需要进行(2D)上次筛选运算；在每次筛选运算的过程中，记录的比较和移动次数的数量级为(3E)，堆排序算法的时间复杂度为(4G)。 A) n B) n／2 C) log2n D) n-1

E) O(log2n) F) O(n)

G) O(nlog2n)

2

H) O(n)

23. 下面的排序算法中不稳定的是 CDE 。

A) 起泡排序

27

B) 折半插入排序 C) 简单选择排序 D) 希尔排序 E) 基数排序 F) 堆排序

24. 稳定的排序方法有 BDE 。

A) 希尔排序法 B) 归并排序法 C) 直接选择法 D) 直接插入法 E) 冒泡排序法

2

25. 下列那些排序算法的时间复杂度是O(n)的有 ADE 。

A) 冒泡法 B) 归并法 C) 堆排序 D) 直接插入 E) 直接选择

26. 在排序算法中实施过程中，使用辅助存储空间为O(1)的有 AD 。

A) 直接插入排序法 B) 快速排序递归算法 C) 归并排序法 D) 堆排序法

27. 如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相

互位置发生颠倒，则称该排序算法是不稳定的， CE 就是不稳定的排序算法。 A) 起泡排序 B) 归并排序 C) Shell排序 D) 直接插入排序 E) 简单选择排序

28. 堆排序是(1E)类排序，堆排序平均执行的时间复杂度和需要附加的存

储空间复杂度分别是(2G)。 A) 插入 B) 交换 C) 归并 D) 基数 E) 选择

28

F) 0(n)和O(1) G) O(nlog2n)和O(1) H) O(nlog2n)和O(n)

2

I) O(n)和O(n)

29. 直接插入排序和冒泡排序的时间复杂度为(1D)，若初始数据有序(即正

序)，则时间复杂度为(2A)。 A) O(n) B) O(log2n) C) O(nlog2n)

2

D) O(n)

30. 在直接选择排序中，记录比较次数为(1C)数量级，记录的移动次数为

(2A)数量级。 A) O(n) B) O(log2n

2

C) O(n) D) O(nlog2n)

31. 在平均情况下，快速排序的时间复杂度为(1C)，空间复杂性为(2B)，

在最坏情况下(如初始记录已有序)，快速排序的时间复杂度为(3D)，空间复杂性为(4A)。 A) O(n) B) O(log2n) C) O(nlog2n)

2

D) O(n)

32. 在归并排序中，归并趟数的数量级表示为(1B)，每趟需要进行记录的

比较和移动次数的数量级表示为(2A)，归并排序算法的时间复杂度为(3C)。 A) O(n) B) O(log2n) C) O(nlog2n)

2

D) O(n)

33. 通过建立索引表来存取数据的文件有 BCE 。

A) 散列文件 B) VSAM文件 C) ISAM文件 D) 顺序文件 E) 倒排文件

34. 索引顺序文件既能进行(1A)存取，又能进行(2D)存取，因而是最常用

2

29

的文件组织方法之一，通常用(3H)结构来组织索引。 A) 顺序 B) 分块 C) 随机 D) 二分 E) 链表 F) 顺序表 G) 数组 H) 树

35. 散列文件的优点是 ABDE 。

A) 文件可随机存放，记录无需排序 B) 存取速度快

C) 能够进行顺序存取

D) 无需索引区，节省存储空间 E) 插入、删除操作方便

三、 填空题

1. 一个数据结构在计算机中的 映象 称为存储结构。 2. 对于给定的n个元素，可以构造出的逻辑结构有 集合 线性结构 树

形结构 图结构 或 线性结构和非线性结构。

3. 从一维数组a[n)中顺序查找出一个最大值元素的平均时间复杂性为

O（n） ，读取一个二维数组b[m][n]中任一元素的时间复杂性为 O(1) 。

4. 线性结构中元素之间存在 一对一 关系，树形结构中元素之间存

在 一对多 关系，图结构中元素存在 多对多 关系，而集合结构中元素之间不存在 逻辑 关系。

5. 数据结构是研究数据的 物理结构 和 逻辑结构 以及它们之间的相

互关系，并对这种结构定义相应的 运算，并设计出相应的算法 。 6. 由一种 逻辑 结构和一组 基本运算 构成的整体是实际问题的一

种数学模型，这种数学模型的建立、选择和实现是数据结构的核心问题。

7. 数据的 逻辑 结构与数据元素本身的内容和形式无关。

8. 一个算法具有5个特性：有穷性、确定性、可行性、输入、输出。 9. 算法的时间复杂度是指该算法所求解问题 规模 ． 10. 从逻辑关系上讲数据结构主要分为两大类，它们是 线性结构和非线性

结构

30

11. 数据结构的基本任务是数据结构的 设计 和 实现 。

12. 对于双向链表，在两个结点之间插入一个新结点时需修改的指针共有

4 个，单链表为 2 个。

13. 顺序存储结构使线性表中逻辑上相邻的数据元素在物理位置上也相

邻。因此，这种表便于 直接 存取。

14. 对一个线性表分别进行遍历和逆置运算，其最好的时间复杂性量级分

别为 O（n） 和O(n) 。

15. 在一个循环单链表中，表尾结点的指针域与表头指针值 相同 。 16. 求顺序表和单链表长度的时间复杂性的量级分别为 O（1） 和 O

（n） 。

17. 在线性表的顺序存储中，元素之间的逻辑关系是通过 物理存储位置

决定的，链表式存储中，元素之间的逻辑关系是通过 链指针 决定的。 18. 单链表表示法的基本思想是用 链指针 表示结点间的逻辑关系。 19. 头结点的first域值是指示单链表的 第一个数据结点的存储地址。 20. 线性表的两种存储结构分别为 顺序 和 链式。 21. 在线性表的单链表存储中，若一个元素所在结点地址为p，则其后继结

点的地址为 p->link 。

22. 表长为0的线性表称为 空表 。

23. 用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234，为了

得到1342出栈顺序，相应的S和X操作串为 sxssxsxx 。

24. 用下标0开始的N元数组实现循环队列时，为实现下标变量m加1后

在数组有效下标范围内循环，可采用的表达式是m= (m+1)%n 。 25. 表达式求值是 栈 数据结构应用的一个典型例子 26. 用数组Q(其下标在O．．n-1中，共有n个元素)表示一个循环队列，front

为当前队头元素的前一位置，rear为队尾元素的位置。假定队列元素个数总小于n，求队列中元素个数的公式是 (rear-front+n)%n 。 27. 用链表表示的队列，长度为n，若只设头指针，则出队和入队的时间复

杂度分别是 O(n) 和 O(1) 。

28. 队列是特殊的线性表，其特殊性在于 在表的一端进行插入，在另一端

进行删除 。

29. 一个循环队列存于a[m]中，假定队首和队尾指针分别为front和rear，

front为当前队头元素的前一位置，rear为队尾元素的位置。则判断队空的条件为 front==rear，判断队满的条件为 (rear+1)%m==front。 30. 向一个循环队列存入新元素时，需要首先移动 队尾指针 ，然后再向

它所指位置 存入 新元素。 31. 队 又称作先进先出表。

32. 设栈S和队列Q的初始状态为空，元素a、b、c、d、e、f依次通过栈

31

S，一个元素出栈后即进入队列Q。若这6个元素出队列的顺序是b、d、c、f、e、a，则栈S的容量至少应该是 3 。

33. 栈是特殊的线性表，其特殊性在于 只能在栈顶插入或删除元素 。 34. 栈又称为 先进后出 表，队列又称为 先进先出 表。

35. 在一个用一维数组A[N]表示的顺序栈中，该栈所含元素的个数最少为

0 ,最多为 N 个。

36. 在一个用一维数组A[n]存储的循环队列中，该队列中的元素个数最少

为 0 最多为 n-1 个。

37. 8层完全二叉树至少有 128 个结点，拥有100个结点的完全二叉树

的最大层数为 7

38. 线索二叉树的左线索指向其 某种遍历序列的直接前驱 ，右线索

指向其 某种遍历序列的直接后驱 。

39. 一棵有n个结点的满二叉树有 0个度为1的结点，有 (n/2)下限取整

个分支(非终端)结点和 (n/2)下限取整加1 个叶子，该满二叉树的深度为 log2n下限取整加1 。

40. 设一棵后序线索树的高度是50，结点x是树中的一个结点，其双亲是

结点y，y的右子树高度是31，x是y的左孩子，则确定x的后继最多需经过 31 中间结点(不含后继及x本身)。

41. 设F是由Tl、T2、T3，三棵树组成的森林，与F对应的二叉树为B。

已知Tl、T2、T3，的结点数分别为n1、n2和n3，则二叉树B的左子树中有 n1-1 个结点，二叉树B的右子树中有 n2+n3 个结点。 42. 若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结

点，则它必是该子树的 前序遍历 序列中的最后一个结点。 43. 一棵共有n个结点的树，其中所有分支结点的度均为k，则该树中的叶

子结点个数为 (n(k-1)+1)/k 。

k-1

44. 深度为k(设根的层数为1)的完全二叉树至少有 2 个结点，至多有

k

2-1个结点。

45. 包含结点A，B，C的二叉树有 5 种不同的形态， 30 种不同的二

叉树。

46. 包含结点A，B，C的树有 2 种不同的形态， 12 种不同的树。 47. 若二叉树有n个结点，深度为树h，对它分别进行前序遍历、中序遍历、

后序遍历时，开辟的栈分别为 h，h，h 存储单元。

48. 一棵完全二叉树有999个结点，它的深度是 10 。

49. 对于一棵具有n个结点的树，该树中所有结点的度数之和为 n-1 。

n-1

50. 有n个结点并且其高度为n的二叉树有 2 个。

51. 一棵具有n个结点的二叉树，若它有n0个叶子结点，则该二叉树上度

为1的结点n1= n-2n0+1 。

32

52. 若一棵二叉树的叶子结点数目为n0，则该二叉树中左、右子树皆非空

的结点个数为 n0-1 。

53. 设n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有 2n0-1 个结点。 54. 如果结点A有3兄弟，而且B是A的双亲，则B的度是 4 。

h

55. 高度为h的二叉树中叶子结点的数目至多为 2-1 。

56. 具有n个结点的二叉树，采用二叉链表存储，共有n+1个空链域。 57. 利用树的孩子兄弟表示法存储，可以将一棵树转换成 一棵二叉树 。 58. 二叉树的线索化实质是将二叉链表中的 空指针域 改为存放该结点

的前趋或后继信息 。

59. 在一棵树中 树根 结点没有前驱结点，其余每个结点有且只有一个双

亲（或前驱） ，可以有任意多个 孩子（或后继）结点。 60. 对于一棵完全二叉树，设一个结点的编号为i，若它的左孩子结点存在，

则其编号为 2i ,若右孩子结点存在，则其编号为 2i+1 ；而双亲结点的编号为 i/2下限取整 。

61. 对于一棵具有n个结点的二叉树，对应二叉链表中指针总数为2n

个，其中 n-1 个用于指向孩子结点 n+1 个指针空闲着。

62. 一棵左右子树均不空的二叉树在先序线索化后，其空指针域有 0

个。

63. 用一维数组存放一棵完全二叉树：ABCDEFGHIJKL，则后序遍历该二叉树

的结点序列为 HIDJKEBLFGCA 。

k-1

64. 深度为k的完全二叉树，其前k-1层共有 2-1 个结点。

65. 对任何二叉树，若度为2的结点数为n2，则叶子数n0= n2+1 。 66. 具有n个结点的完全二叉树若按层次从上到下、从左到右对其编号(根

结点为1)，则编号最大的分支结点序号是 n/2下限取整 ，编号量小的分支结点序号是 1 。编号最大的叶子结点序号是 n ，编号量小的叶子结点序号是 n/2下限取整再加1 。

67. 结点最少的树为 只有一个（根）结点的树 ，结点最少的二叉树为 空

二叉树 。

68. 若二叉树的一个叶子结点是某子树中根遍历序列中的第一个结点，则它

必然是该子树后根遍历序列中的 第一 个结点。

69. 哈夫曼树是带权路径长度 最短 的树，通常权值较大的结点离根较

近 。

70. 如果含n个顶点的图形成一个环，则它有 n 棵生成树。 71. 具有10个顶点的无向图，边的总数最多为 45 。

72. 在有n个顶点的有向图中，每个顶点的度最大可达 2（n-1） 。 73. 若一个连通图中每个边上的权值均不同，则得到的最小生成树是 惟

一 的。

33

74. 设图G有n个顶点和e条边，则对用邻接矩阵表示的图进行深度或广

2

度优先搜索遍历时的时间复杂度为 O（n） ，而对用邻接表表示的图进行深度或广度优先搜索遍历时的时间复杂度为 O（e） ；图的深度或广度优先搜索遍历时的空间复杂度均为 O(n) 。 75. 深度优先搜索遍历类似于树的前序遍历，它所用到的数据结构是栈 ；

广度优先搜索遍历类似于树的按层次遍历，它所用到的数据结构是队列。

76. 一个图的 邻接矩阵 表示法是惟一的，而 邻接表 表示法是不惟

一的。

77. 对无向图，若它有n个顶点e条边，则其邻接表中需要个 2e+n 结

点。其中， 2e 个结点构成邻接表， n 个结点构成顶点表。 78. 有n个顶点的有向图，至少需要 n-1 条弧才能保证是连通的。 79. 一个连通图的 生成树 是一个极小连通子图。 80. n个顶点的连通图用邻接矩阵表示时，该矩阵至少有 n-1 个非零元

素。

81. 有向图中的结点前驱后继关系的特征是 一个结点可能有若干个前

驱，也可能有若干个后继 。

82. 普里姆算法适用于求于 边稠密 的网的最小生成树。克鲁斯卡尔算

法适用于求 边稀疏 的网的最小生成树；

83. 有向图的极大强连通子图称为 有向图的强连通分量 。

84. 在一个具有n个顶点的无向完全图中，包含有 n(n-1)/2 条边。在

一个具有n个顶点的有向完全图中，包含有 n(n-1) 条边。

85. 根据图的存储结构进行某种次序的遍历，得到的顶点序列是 惟一

的。

86. 若无向图G的顶点度数最小值大于等于 2 时，G至少有一条回路。 87. 连通分量是无向图中的 极大 连通子图。

88. 假定有k个关键字互为同义词，若用线性探测再散列法把这个k个关

键字存入散列表中，至少要进行 (k(k+1))/2 次探测。

89. 顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多

为 n 次：当使用监视哨时，若查找失败，则比较关键字的次数为 n+1 次。

90. 构造哈希函数的方法有 数字分析法、直接定址法、平方取中法、折

叠法、除留余数法、随机数法等。

91. 在n个记录的有序顺序表中进行折半查找，最大的比较次数是 log2n

下限取整再加1 。

92. 用二分法查找一个线性表时，该线性表必须具有的特点是 顺序存储

器且有序 ；而分块查找法要求将待查找的表均匀地分成若干块且

34

块中诸记录的顺序可以是任意的，但块与块之间 有序

93. 对于二叉排序树的查找，若根结点元素的键值大于被查元素的键值，

则应该在二叉树的 左子树 上继续查找

94. 设线性表(al，a2，?，a500)元素的值由小到大排列，对一个给定的

k值用二分法查找线性表，在查找不成功的情况下至多需比较 9 次。

95. 二叉排序树的查找效率与树的形态有关。当二叉排序树退化为单支树

时，查找算法退化为 顺序 查找，其平均查找长度上升为 (n+1)/2 。

96. 二叉排序树的查找长度不仅与 结点数n 有关，也与二叉排序树的

生成过程 有关。

97. 一个无序序列可以通过构造一棵 二叉排序 树而变成一个有序序

列，构造树的过程即为对无序序列进行排序的过程。

98. 在一棵有n个结点的非平衡二叉树中进行查找，平均时间复杂度的上

限(即最坏情况平均时间复杂度)为 （n+1）/2 。

99. 已知有序表为(12，18，24，35，47，50，62，83，90，115，134)，

当用二分法查找90时，需进行 2 次查找可确定成功；查找47时需进行 4 次查找可确定成功；查找100时，需进行3次查找才能确定不成功。

100. 假设有n个关键字，它们具有相同的Hash函数值，用线性探测方法

解决冲突，把这n个关键字散列到大小为n的地址空间中，共计需要做 n（n+1）/2 次插入和探测操作。 101. 直接定址 法构造的哈希函数肯定不会发生冲突。

102. 在顺序表上施行的三个查找算法，就平均查找长度来看， 折半法

最小， 顺序法 最大。

103. 在一棵二叉树排序树上实施 中序 遍历后，其关键字序列是一个

有序表。

104. 二分查找的存储结构仅限于 顺序存储结构 ，且是 有序的 。 105. 散列表 查找法的平均查找长度与元素个数n无关。 106. 对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的

比较次数为 (n(n-1))/2 。

107. 对于关键字序列(12，13，11，18，60，15，7，20，25，100)，用

筛选法建堆，必须从键值为 60 的关键字开始 108. 基数 排序不需要进行记录关键字间的比较

109. 设有关键码序列(Q，H，C，Y，Q，A，M，S，R，D，F，X)，要按照

关键码值递增的次序进行排序，若采用初始步长为4的shell排序法，则一趟扫描的结果是 （Q,A,C,S,Q,D,F,X,R,H,M,Y） ；若采35

用以第一个元素为分界元素的快速排序法，则一趟扫描的结果是 (H,C,D,Q,A,M,Q,R,S,Y,X) 。

110. 对一组记录(54，38，96，23，15，72，60，45，83)进行直接插入

排序时，当把第60插入到已排序的有序表时，为寻找其插入位置需比较 3 次。

111. 每次从无序子表中取出一个元素，把它插入到有序子表中的适当位

置，此种排序方法叫做 插入 排序；每次从无序子表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做 选择 排序。

112. 每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就

交换它们的位置，此种排序方法叫做 快速 排序；每次使两个相邻的有序表合并成一个有序表的排序方法叫做 归并 排序。

113. 若对顺序存储在A[1]～A[9]的记录(76，38，62，53，80，74，83，

65，85)进行堆排序，已知除第一个元素76外，以其余元素为根的结点都已是堆，则对第一个元素进行调整运算时，它将最终被筛到A数组下标为 8 的位置上。

114. 快速 排序方法采用的是二分法的思想， 堆 排序方法其数据的

组织采用完全二叉树结构。

115. 在时间复杂性为O(log2n)的排序方法中， 归并 排序方法是稳定

的;在时间复杂性为O(n)的排序方法中， 直接选择 排序方法是不稳定的。

116. 对一组记录(54，38，96，23，15，72，60，45，83)进行快速排序

时，递归调用使用的栈所能达到的最大深度为 3 ，共需递归调用 4 次，其中第二次递归调用是对一组记录 （23，38，15） 进行快速排序。

117. 设表中元素的初态是按键值递增的，若分别用堆排序、快速排序、

冒泡排序和归并排序方法对其仍按递增顺序进行排序，则 冒泡排序 最省时间， 快速排序 最费时间。

118. 从一个无序序列建立一个堆的方法是：首先将要排序的所有键值分

放到一棵树的各个结点中，然后从i= （n/2）下限取整 的结点ki开始，逐步把以Ki-l、Ki-2、?、K1为根的子树排成堆，直到以K1为根的树排成堆，就完成了建堆的过程。

119. 对n个元素进行初始建堆的过程中，最多进行 n-1 数据比较。 120. 快速排序最大递归深度是 n ，最小递归深度是 log2n下限取整

再加1 。

121. 外部排序中两个相对独立的阶段是 划分归并段 和 归并排

序 。

36

122. 基于关键字比较大小的排序算法中， 快速排序 排序算法的平均

时间复杂度最优。

123. 对用数组存储的线性表(16,15,32,11,6,30)，用快速排序算法进行

由小到大排序，若排序下标范围为0～5，选择元素16作为支点，调用一趟快速排序算法后，元素16在数组中的下标位置为 3 。 124. 排序有哪几种方法 插入排序、交换排序、选择排序、归并排序、

基数据排序 。

125. 归并排序的时间复杂度是 O(nlog2n) 。

126. 对n个元素进行冒泡排序时，最少的比较次数是 n-1 。

127. 在二路归并排序中，对n个记录进行归并的趟数为 log2n上限取

整 。

128. 在内部排序中，平均比较次数最少的是 快速排序 ，要求附加存

储空间最大的是 归并排序 ，排序时不稳定的有 shell排序 、 堆排序 、 选择排序 和 快速排序 。

129. 快速排序 方法是对序列中的元素通过适当的位置交换将有关元素

一次性地放置在其最终位置上。

130. 索引顺序文件既可以顺序存取，也可以 直接 存取。

131. 顺序文件是指记录按进入文件的先后顺序存放，其 逻辑顺序的物

理顺序 相一致。

132. 文件是多个性质相同的记录的集合。一般说来，文件的操作有检索

和维护 。

133. 索引文件由 索引表 和主文件两部分组成。

134. 对文件的检索有 顺序 、 直接 和 按关键字 检索三种方式。 135. 一个索引文件中的索引表都是按 关键字 有序的。

136. 稠密索引中的每个索引项对应主文件中的 1 条记录，稀疏索引中

的每个索引项对应主文件的 多条 条记录。

137. 若主文件无序，则只能建立 稠密 索引，若主文件有序，则既能

建立 稠密 索引，也能建立 稀疏 索引。

138. ISAM文件的索引系统包括 主索引 、 柱面索引 、和 磁道索

引 三级索引。

139. 对于散列文件中的每个散列地址其对应单链表中的第一个结点称为

基桶 ，其余结点称为 溢出桶 。

140. 散列文件中的每个桶能够存储 多 个同义词记录。 141. 在多重表文件中，每个索引表通常都是 稀疏索引 。

142. 在每个倒排表中，主属性为主文件中相应的次关键字，非主属性为

主文件中的 记录号 。

37

143. 常见的文件存储结构有 顺序组织 、 索引组织 、 散列组织

和 链组织 四种。

144. 索引文件中的索引表是一张指示 逻辑记录和物理记录 之间对应

关系的表，索引表中的每项称作 索引项 。

145. 在磁带上的顺序文件中插入新的记录时，必须 复制整个文件 ，

但是变更磁盘上的顺序文件的记录内容时，则不一定要 复制整个文件 。

四、 判断题

1. 顺序存储方式只能用于存储线性结构。 （错） 2. 数据元素是数据的最小单位。（错）

3. 算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言

描述，算法实际上就是程序了。（错）

4. 算法只能用语言描述，如果用C语言或PASCAL语言等高级语言描述。

（错）

5. 数据结构是带有结构和关系的数据元素的集合。（对）

6. 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据需要而

建立的。（对）

7. 数据的物理结构是指数据在计算机内实际的存储形式。（对） 8. 栈和队列都是限制存取点的线性结构。 (对)

9. 即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和

出栈组合操作，所得的输出序列也一定相同 (错,不同的入栈和出栈组合将得到不同的输出序列。)

10. 消除递归不一定需要使用栈。 (对,如尾递归可将其转换成递推而

不需要栈。)

11. 完全二叉树的某结点若无左孩子，则它必是叶结点。(对)

12. 存在这样的二叉树，对它采用任何次序的遍历，结果相同。(对) 13. 二叉树就是结点度为2的树。(错)

14. 二叉树中不存在度大于2的结点，当某个结点只有一棵子树时无所谓

左、右子树之分。(错)

15. 任何一棵二叉树都可以不用栈实现前序线索树的前序遍历。(对) 16. 对任何二叉树的后序线索树进行后序遍历时都必须用栈。(对)

17. 一般来说，若深度为k的n个结点的二叉树具有最小路径长度，那么

k-1k-1

从根结点到第k-1层具有最多的结点数为2-1，余下的n-2+1个结点在第k层的任一位置上。(对)

18. 若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则

38

它必是该子树的前序遍历序列中的最后一个结点。 (错)

19. 若一个结点是某二叉树子树的前序遍历序列中的最后一个结点，则它

必是该子树中序遍历序列中的最后一个结点。(错。)

20. 已知二叉树的前序遍历序列和后序遍历序列并不能惟一地确定这棵

树，因为不知道树的根结点是哪一个。 (对)

21. 在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对

于这种情况应作特殊处理。 (错。)

22. 对n个结点的二叉树用递归程序进行中序遍历时，最坏情况下要附加n

个辅助存储空间。(对)

k-1

23. 当k≥1时，高度为k的二叉树至多有2个结点。(错)

24. 中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。(对) 25. 将一棵树转换成二叉树后，根结点没有左子树。(错) 26. 用树的前序遍历和中序遍历可以导出树的后序遍历。(对) 27. 哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。

(对)

28. 在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉

树。 (错。)

29. 后序遍历森林和中序遍历与该森林相对应的二叉树其结果不同。(错) 30. 若一个二叉树的树叶是某子树的中序遍历序列中的第一个结点，则它

必是该子树的后序遍历序列中的第一个结点(对)

31. 不使用递归也能实现二叉树前序、中序和后序遍历。(对)

32. 对于后序线索二叉树要找它的任一结点的后继有时是很困难的，因此

还需要使用栈。(对)

33. 在二叉树中，具有一个子女的父结点，在中序遍历序列中，它没有后

继子女结点。(错)

34. 中序线索二叉树的优点之一是便于在中序下查找前驱结点和后继结

点。 (对)

35. 前序遍历森林和前序遍历与该森林对应的二叉树其结果不同。(错) 36. 二叉树中每个结点有两个子女结点，而对一般的树则无此限制，因此

二叉树是树的特殊情形。(错)

37. 用一维数组存储二叉树时，总是以前序遍历顺序存储结点。(错) 38. 一棵左右子树均不空的二叉树在先序线索化后其空指针域数为n-1。

(错)

39. 在n个结点的无向图中，若边数>n-1，则该图必是连通图。(错) 40. 对于一个有向图，除了拓扑排序方法外，还可以通过对有向图进行深

度优先遍历的方法来判断有向图中是否有环存在。(对) 41. 一个图的广度优先搜索树是惟一的。(错)

39

42. 图的深度优先搜索序列和广度优先搜索序列不是惟一的。(对)

43. 有n个顶点的无向图，采用邻接矩阵表示，图中的边数等于邻接矩阵

中非零元素之和的一半。(对)

44. 若连通图上各边权值均不相同，则该图的最小生成树是惟一的。(对) 45. 无向图的邻接矩阵一定是对称矩阵，且有向图的邻接矩阵一定是非对

称矩阵。(错)

46. 用邻接矩阵存储一个图时，所占用的存储空间大小只与图中结点的个

数有关，而与图的边数无关。(对)

47. 邻接表只能用于存储有向图，而邻接矩阵则可存储有向图和无向图。

(错)

48. 无向图的邻接矩阵是对称的，因此可只存储邻接矩阵的下(或上)三角

阵。(对)

49. 连通分量是无向图中的极小连通子图。(错) 50. 强连通分量是有向图中的极大强连通子图。(对)

51. 如果连通网中存在相同权值的边，则最小生成树不惟一。(对) 52. 用邻接矩阵表示图时，矩阵元素的个数与边的条数有关。(错)

53. 用顺序表和单链表表示的有序表均可使用折半查找方法来提高查找速

度。(错)

54. 有n个数存放在一维数组A[1．．n]中，在进行顺序查找时，这n个数

的排列有序或无序其平均查找长度不同。(错)

55. 在任意一棵非空二叉树中，删除某结点后又将其插入，则所得二叉排

序树与删除前原二叉树排序树相同。(错) 56. 二叉树中除叶子结点外，对于任一结点X，其左子树根结点的值小于该

结点(X)的值，其右子树结点的值不小于该结点(X)的值，则此二叉树一定是二叉排序树。(错)

57. 折半查找是先确定待查有序表记录的范围，然后逐步缩小范围，直到

找到或找不到该记录为止。(对)

58. 二叉排序树的任意一棵子树中，关键字最小的结点必无左孩子，关键

字最大的结点必无右孩子。(对)

59. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。

(错)

60. 散列表的结点中包含数据元素自身的信息，不包含任何指针。(错) 61. 对二棵具有相同关键字集合而形状不同的二叉排序树，按中序遍历它

们得到的序列顺序是一样的。(对)

62. 在二叉排序树上删除一个结点时，不必移动其他结点，只要将该结点

的父结点的相应指针域置空即可。(错)

63. 在所有结点的权都相等的情况下，只有最下面两层结点的度数可以小

40