102. 向一棵AVL树插入元素时，可能引起对最小不平衡子树的双向旋转的调整过程，此时需要修改相关( )个指针域的值。
A. 2 B. 3 C. 4 D. 5
103. 设G1=（V1，E1）和G2=（V2，E2）为两个图，如果V1?V2，E1?E2，则称 ( )。 A．G1是G2的子图 B．G2是G1的子图 C．G1是G2的连通分量 D．G2是G1的连通分量
104. 有向图的一个顶点的度数等于该顶点的 ( )。 A．入度 B．出度 C．入度与出度之和 D．（入度+出度）／２
105. 一个连通图的生成树是包含图中所有顶点的一个 ( )。
A．极小子图 B．连通子图 C．极小连通子图 D．无环子图
106. n个顶点的连通图中至少含有 ( )。
A．n-1条边 B．n条边 C．n(n-1)/2条边 D．n(n-1)条边
107. n个顶点的强连通图中至少含有 ( )。
A．n-1条有向边 B．n条有向边 C．n(n-1)/2条有向边 D．n(n-1)条有向边
108. 在一个带权连通图G中，权值最小的边一定包含在G的( ) 中。 A．最小生成树 B．生成树 C．广度优先生成树 D．深度优先生成树
109. 对于具有e条边的无向图，它的邻接表中有 ( ) 个边结点。 A．e-1 B．e C．2(e-1) D．2e
110. 具有n个顶点的有向无环图最多可包含 ( ) 条有向边。 A．n-1 B．n C．n(n-1)/2 D．n(n-1)
111. 一个有n个顶点和n条边的无向图一定是 ( )。
A．连通的 B．不连通的 C．无环的 D．有环的
112. 在n个顶点的有向无环图的邻接矩阵中至少有 ( ) 个零元素。 A．n B．n(n-1)/2 C．n(n+1)/2 D．n(n-1)
113. 对于有向图，其邻接矩阵表示比邻接表表示更易于 ( )。 A．查找一条边 B．求一个顶点的邻接点 C．进行图的深度优先遍历 D．进行图的广度优先遍历
114. 在一个有向图的邻接矩阵表示中，删除一条边
11
115. 与邻接矩阵相比，邻接表更适合于存储 ( )。 A．无向图 B．连通图 C．稀疏图 D．稠密图
116. 设一个有n个顶点和e条边的有向图采用邻矩阵表示，要计算某个顶点的出度 所耗费的时间是 ( )。
2
A．O(n) B．O(e) C．O(n+e) D．O(n)
117. 为了实现图的广度优先遍历，BFS算法使用的一个辅助数据结构是 ( )。 A．栈 B．队列 C．二叉树 D．树
118. 设无向图的顶点个数为n，则该图最多有（ ）条边。
A. n-1 B. n(n-1)/2 C. n(n+1)/2 D. n(n-1)
119. 在一个无向图中，所有顶点的度数之和等于所有边数的 ( ) 倍。
A. 3 B. 2 C. 1 D. 1/2
120. 若采用邻接矩阵存储具有n个顶点的无向图，则该邻接矩阵是一个 ( )。
A. 上三角矩阵 B. 稀疏矩阵 C. 对角矩阵 D. 对称矩阵
121. 图的深度优先搜索类似于树的（ ）次序遍历。
A. 先根 B. 中根 C. 后根 D. 层次
122. 图的广度优先搜索类似于树的（ ）次序遍历。
A. 先根 B. 中根 C. 后根 D. 层次
123. 在用Kruskal算法求解带权连通图的最小（代价）生成树时，通常采用一个（ ）辅助结构，判断一条边的两个端点是否在同一个连通分量上。
A. 位向量 B. 堆 C. 并查集 D. 生成树顶点集合
124. 采用Dijkstra算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是（ ）数。
A. 非零 B. 非整 C. 非负 D. 非正
125. 设有向图有n个顶点和e条边，采用邻接表作为其存储表示，在进行拓扑排序时，总的计算时间为（ ）。
e2
A. O(nlog2e) B. O(n+e) C. O(n) D. O(n)
126. 若待排序对象序列在排序前已基本按排序码递增顺序排列，则采用( )方法比较次数最少。
A. 直接插入排序 B. 快速排序 C. 归并排序 D. 直接选择排序
12
127. 对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是( )。
A. 直接选择排序 B. 直接插入排序 C. 快速排序 D. 起泡排序
128. 对5个不同的数据元素进行直接插入排序，最多需要进行( )次比较。 A. 8 B. 10 C. 15 D. 25
129. 下列排序算法中，( )算法是不稳定的。
A. 起泡排序 B. 直接插入排序 C. 基数排序 D. 快速排序
130. 假设某文件经过内部排序得到100个初始归并段，那么如果要求利用多路平衡归并在3 趟内完成排序，则应取的归并路数至少是( )。
A. 3 B. 4 C. 5 D. 6
131. 在基于排序码比较的排序算法中，( )算法在最坏情况下的时间复杂度不高于O(nlog2n)。
A. 起泡排序 B. 希尔排序 C. 堆排序 D. 快速排序
132. 在下列排序算法中，( )算法使用的附加空间与输入序列的长度及初始排列无关。 A. 锦标赛排序 B. 快速排序 C. 基数排序 D. 归并排序
133. 一个对象序列的排序码为{46, 79, 56, 38, 40, 84}，采用快速排序（以位于最左位置的对象为基准）所得到的第一次划分结果为( )。
A. {38, 46, 79, 56, 40, 84} B. {38, 79, 56, 46, 40, 84} C. {40, 38, 46, 79, 56, 84} D. {38, 46, 56, 79, 40, 84}
134. 如果将所有中国人按照生日（不考虑年份，只考虑月、日）来排序，那么使用下列排序算法中( )算法最快。
A. 归并排序 B. 希尔排序 C. 快速排序 D. 基数排序
135. 设有一个含有200个元素的表待散列存储，用线性探查法解决冲突，按关键码查询时找到一个元素的平均探查次数不能超过1.5，则散列表的长度应至少为（ ）。 （注：平均探查次数的计算公式为Snl={1+1/(1-α)}/2, 其中α为装填因子） A. 400 B. 526 C. 624 D. 676
136. 5阶B树中, 每个结点最多允许有（ ）个关键码。
A. 2 B. 3 C. 4 D. 5
137. 在10阶B树中根结点所包含的关键码个数最少为（ ）。
A. 0 B. 1 C. 3 D. 4
138. 在一棵高度为h的B树中，叶结点处于第（ ）层。（注：树根结点为第0层，B树高
13
度为失败结点所处层数）。
A. h-1 B. h C. h+1 D. h+2
139. 在一棵高度为h的B树中，插入一个新关键码时，为搜索插入位置需读取（ ）个结点。
A. h-1 B. h C. h+1 D. h+2
140. 当对一个线性表R[60] 进行索引顺序搜索（分块搜索）时，若共分成了10个子表，每个子表有6个表项。假定对索引表和数据子表都采用顺序搜索，则搜索每一个表项的平均搜索长度为（ ）。
A. 7 B. 8 C. 9 D. 10
141. 当对一个线性表R[60] 进行索引顺序搜索（分块搜索）时，若共分成了8个子表，每个子表有6个表项。假定对索引表和数据子表都采用顺序搜索，则搜索每一个表项的平均搜索长度为（ ）。
A. 7 B. 8 C. 9 D. 10
142. 既希望较快的搜索又便于线性表动态变化的搜索方法是（ ）。
A. 顺序搜索 B. 折半搜索 C. 散列搜索 D. 索引顺序搜索
143. 散列函数应该有这样的性质，即函数值应当以（ ）概率取其值域范围内的每一个值。 A. 最大 B. 最小 C. 平均 D. 同等
144. 设散列地址空间为0?m-1，k为表项的关键码，散列函数采用除留余数法，即Hash(k)=k%p。为了减少发生冲突的频率，一般取p为（ ）。
A. m B. 小于m的最大质数 C. 大于m的最小质数 D. 小于m的最大合数
145. 在采用开散列法解决冲突时，每一个散列地址所链接的同义词子表中各个表项的（ ）值相同。
A. 关键码 B. 非关键码 C. 散列函数 D. 某个域
146. 解决散列法中出现的冲突问题常采用的方法是（ ）。 A. 数字分析法、除留余数法、平方取中法 B. 数字分析法、除留余数法、线性探查法 C. 数字分析法、线性探查法、双散列法 D. 线性探查法、双散列法、开散列法
147. 在闭散列表中，散列到同一个地址而引起的“堆积”问题是由于（ ）引起的。 A. 同义词之间发生冲突 B. 非同义词之间发生冲突 C. 同义词之间或非同义词之间发生冲突 D. 散列表“溢出”
14
148. 采用线性探查法解决冲突时所产生的一系列后继散列地址（ ）。 A. 必须大于原散列地址 B. 必须小于原散列地址
C. 可以大于或小于原散列地址 D. 不能超过散列表长度的一半
149. 对存储有n个元素的长度为m的散列表进行搜索，平均搜索长度（ ）。 A. 为O(log2n) B. 为O(n) C. 与n/m值有关 D. 与n/m值无关
单选题参考解答
1. A 2. B 3. C 4. D 5. B 6. B 7. B 8. A 9. D 10. D 11. A 12. C 13. C 14. C 15. C 16. A 17. C 18. A 19. C 20. C 21. B 22. A 23. C 24. C 25. A 26. C 27. B 28. A 29. B 30. B 31. D 32. A 33. C 34. D 35. D 36. B 37. C 38. C 39. B 40. B 41. C 42. B 43. A 44. B 45. C 46. A 47. B 48. A 49. D 50. D 51. C 52. A 53. D 54. A 55. D 56. C 57. D 58. C 59. A 60. A 61. D 62. B 63. C 64. C 65. A 66. C 67. D 68. C 69. C 70. C 71. A 72. C 73. A 74. D 75. A 76. D 77. C 78. B 79. A 80. B 81. B 82. B 83. D 84. A 85. C 86. C 87. D 88. C 89. A 90. B 91. A 92. B 93. C 94. B 95. D 96. D 97. C 98. B 99. A 100. C 101. B 102. D 103. A 104. C 105. C 106. A 107. B 108. A 109. D 110. C 111. D 112. C 113. A 114. A 115. C 116. A 117. B 118. B 119. B 120. D 121. A 122. D 123. C 124. C 125. B 126. A 127. C 128. B 129. D 130. C 131. C 132. C 133. C 134. D 135. A 136. C 137. B 138. A 139. B 140.C 141. B 142. D 143. D 144. B 145. C 146. D 147. C 148. C 149. C
数据结构（本科）期末综合练习二（填空与判断题）
填空题
1. 数据是________的载体，它能够被计算机程序识别、存储和加工处理。
2. 数据结构包括逻辑结构、________和数据的运算三个方面。
3. 数据结构的逻辑结构包括线性结构和________结构两大类。
4. 数据结构的存储结构包括顺序、________、索引和散列等四种。
5. 基本数据类型是计算机已经实现了的________。
6. 抽象数据类型的特点是________、信息隐蔽、使用与实现分离。
15