精品文档
数据结构课程（本科）第七章试题
一、单项选择题
1. 若搜索每一个元素的概率相等，则在长度为n的顺序表上搜索到表中任一元素的平均搜索长度为
（ ）。 A. n
B. n+1
C. (n-1)/2
D. (n+1)/2
2. 对长度为10的顺序表进行搜索，若搜索前面5个元素的概率相同，均为1/8，搜索后面5个元素的概
率相同，均为3/40，则搜索到表中任一元素的平均搜索长度为（ ）。 A. 5.5
B. 5
C. 39/8
D. 19/4
3. 对长度为3的顺序表进行搜索，若搜索第一个元素的概率为1/2，搜索第二个元素的概率为1/3，搜索
第三个元素的概率为1/6，则搜索到表中任一元素的平均搜索长度为（ ）。 A. 5/3
B. 2
C. 7/3
D. 4/3
4. 对长度为n的有序单链表，若搜索每个元素的概率相等，则顺序搜索到表中任一元素的平均搜索长度
为（ ）。 A. n/2
B. (n+1)/2
C. (n-1)/2
D. n/4
5. 对于长度为n的有序顺序表，若采用折半搜索，则对所有元素的搜索长度中最大的为（ ）的值
的向上取整。 A. log2(n+1)
B. log2n
C. n/2
D. (n+1)/2
6. 对于长度为n的有序顺序表，若采用折半搜索，则对所有元素的搜索长度中最大的为（ ）的值
的向下取整加一。
A. log2(n+1) B. log2n
C. n/2
D. (n+1)/2
7. 对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（ ）
的值除以9。 A. 20
B. 18
C. 25
D. 22
8. 对于长度为18的有序顺序表，若采用折半搜索，则搜索第15个元素的搜索长度为（ ）。 A. 3
B. 4
C. 5
D. 6
9. 对具有n个元素的有序顺序表进行折半搜索，则搜索任一元素的时间复杂度为（ ）。
A. O(n)
B. O(n2)
C. O(1)
D. O(log2n)
10. 在一棵高度为h的具有n个元素的二叉搜索树中，搜索所有元素的搜索长度中最大的为（ ）。
A. n
B. log2n
C. (h+1)/2
D. h+1
11. 从具有n个结点的二叉搜索树中搜索一个元素时，在等概率情况下进行成功搜索的时间复杂度大致为
（ ）。
A. O(n)
精品文档
B. O(1)
C. O(log2n) D. O(n2)
精品文档
12. 从具有n个结点的二叉搜索树中搜索一个元素时，在最坏情况下进行成功搜索的时间复杂度为
（ ）。 A. O(n)
B. O(1)
C. O(log2n) D. O(n2)
13. 向具有n个结点的二叉搜索树中插入一个元素时，其时间复杂度大致为（ ）。 A. O(1)
B. O(log2n ) C. O(n)
D. O(nlog2n)
14. 在一棵AVL树（高度平衡的二叉搜索树）中，每个结点的平衡因子的取值范围是（ ）。 A. -1～1
B. -2～2 C. 1～2
D. 0～1
15. 向一棵AVL树（高度平衡的二叉搜索树）插入元素时，可能引起对最小不平衡子树的调整过程，此调
整分为（ ）种旋转类型。 A. 2
B. 3
C. 4
D. 5
16. 向一棵AVL树（高度平衡的二叉搜索树）插入元素时，可能引起对最小不平衡子树的左单或右单旋转
的调整过程，此时需要修改相关（ ）个结点指针域的值。 A. 2
B. 3
C. 4
D. 5
17. 向一棵AVL树（高度平衡的二叉搜索树）插入元素时，可能引起对最小不平衡子树的双向旋转的调整
过程，此时需要修改相关（ ）个结点指针域的值。 A. 2
参考答案： 1. D
6. B 11. C 16. A
B. 3 2. C 7. C 12. A 17. C
C. 4
4. B 9. D 14. A
D. 5
5. A 10. D 15. C
3. A 8. A 13. B
二、填空题
1. 以顺序搜索方法从长度为n的顺序表或单链表中搜索一个元素时，其时间复杂度为________。
2. 对长度为n的搜索表进行搜索时，假定搜索第i个元素的概率为pi，搜索长度（即在搜索过程中依次
同有关元素比较的总次数）为ci，则在搜索成功情况下的平均搜索长度的计算公式为________。
3. 假定一个顺序表的长度为40，并假定搜索每个元素的概率都相同，则在搜索成功情况下的平均搜索长
度为________。
4. 以折半搜索方法从长度为n的有序表中搜索一个元素时，时间复杂度为________。
5. 从有序表 (12, 18, 30, 43, 56, 78, 82, 95) 中折半搜索元素56时，其搜索长度为________。
6. 假定对长度n = 50的有序表进行折半搜索，则对应的判定树中最后一层的结点数为______个。
精品文档
精品文档
7. 从一棵二叉搜索树中搜索一个元素时，若给定值小于根结点的值，则需要向________继续搜索。
8. 从一棵二叉搜索树中搜索一个元素时，若给定值大于根结点的值，则需要向________继续搜索。
9. 向一棵二叉搜索树中插入一个新元素时，若该新元素的值小于根结点的值，则应把它插入到根结点的
________上。
10. 向一棵二叉搜索树中插入一个新元素时，若该新元素的值大于根结点的值，则应把它插入到根结点的
________上。
11. 向一棵二叉搜索树________一个元素时，若查找到的根结点为空值，则应把该元素结点链接到这个空
指针位置上。
12. 根据n个元素建立一棵二叉搜索树的时间复杂度性大致为_____________。
13. 在一棵AVL树（高度平衡的二叉搜索树）中，每个结点的左子树高度与右子树高度之差的绝对值不
超过________。
14. 根据一组记录 ( 56, 42, 50, 64, 48 ) 依次插入结点生成一棵AVL树（高度平衡的二叉搜索树）时，当
插入到值为_______的结点时需要进行旋转调整。
15. 根据一组记录 ( 56, 74, 63, 64, 48 ) 依次插入结点生成一棵AVL树（高度平衡的二叉搜索树）时，当
插入到值为63的结点时需要进行________________调整。
16. 根据一组记录 ( 56, 42, 38, 64, 48 ) 依次插入结点生成一棵AVL树（高度平衡的二叉搜索树）时，当
插入到值为38的结点时需要进行____________调整。
17. 根据一组记录 ( 56, 42, 73, 50, 64, 48, 22 ) 依次插入结点生成一棵AVL树（高度平衡的二叉搜索树）
时，当插入到值为_______的结点时才出现不平衡，需要进行旋转调整。
18. 在一棵AVL树（高度平衡的二叉搜索树）上进行插入或删除元素时，所需的时间复杂度为_________。
参考答案： 1. O(n)
5. 3 13. 1
2.
n?1i?0?pc
ii
3. 20.5 7. 左子树 11. 插入
4. O(log2n) 8. 右子树 12. O(nlog2n)
6. 19
9. 左子树 17. 48
10. 右子树 14. 50 18. O(lon2n)
15. 先右后左双旋转 16. 右单旋转
三、判断题
1. 在顺序表中进行顺序搜索时，若各元素的搜索概率不等，则各元素应按照搜索概率的降序排列存放，
则可得到最小的平均搜索长度。 精品文档
最新《数据结构》习题汇编08-第八章-查找-试题
