课程（本科）《数据结构》第七章试题&参考答案.docx

课程（本科）《数据结构》第七章试题&参考答案一、单项选择题1. 若搜索每一个元素的概率相等，则在长度为n的顺序表上搜索到表中任一元素的平均搜索长度为（ ） A. n B. n+1 C. (n-1)/2 D. (n+1)/22. 对长度为10的顺序表进行搜索，若搜索前面5个元素的概率相同，均为1/8，搜索后面5个元素的概率相同，均为3/40，则搜索到表中任一元素的平均搜索长度为（ ） A. 5.5 B. 5 C. 39/8 D. 19/43. 对长度为3的顺序表进行搜索，若搜索第一个元素的概率为1/2，搜索第二个元素的概率为1/3，搜索第三个元素的概率为1/6，则搜索到表中任一元素的平均搜索长度为（ ） A. 5/3 B. 2 C. 7/3 D. 4/34. 对长度为n的有序单链表，若搜索每个元素的概率相等，则顺序搜索到表中任一元素的平均搜索长度为（ ） A. n/2 B. (n+1)/2 C. (n-1)/2 D. n/45. 对于长度为n的有序顺序表，若采用折半搜索，则对所有元素的搜索长度中最大的为（ ）的值的向上取整。

A. log2(n+1) B. log2n C. n/2 D. (n+1)/26. 对于长度为n的有序顺序表，若采用折半搜索，则对所有元素的搜索长度中最大的为（ ）的值的向下取整加一 A. log2(n+1) B. log2n C. n/2 D. (n+1)/27. 对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（ ）的值除以9 A. 20 B. 18 C. 25 D. 228. 对于长度为18的有序顺序表，若采用折半搜索，则搜索第15个元素的搜索长度为（ ） A. 3 B. 4 C. 5 D. 69. 对具有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+111. 从具有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～115. 向一棵AVL树（高度平衡的二叉搜索树）插入元素时，可能引起对最小不平衡子树的调整过程，此调整分为（ ）种旋转类型。

A. 2 B. 3 C. 4 D. 516. 向一棵AVL树（高度平衡的二叉搜索树）插入元素时，可能引起对最小不平衡子树的左单或右单旋转的调整过程，此时需要修改相关（ ）个结点指针域的值 A. 2 B. 3 C. 4 D. 517. 向一棵AVL树（高度平衡的二叉搜索树）插入元素时，可能引起对最小不平衡子树的双向旋转的调整过程，此时需要修改相关（ ）个结点指针域的值 A. 2 B. 3 C. 4 D. 5参考答案： 1. D 2. C 3. A 4. B 5. A 6. B 7. C 8. A 9. D 10. D11. C 12. A 13. B 14. A 15. C16. A 17. C二、填空题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) 2. 3. 20.5 4. O(log2n) 5. 3 6. 19 7. 左子树 8. 右子树 9. 左子树 10. 右子树 11. 插入 12. O(nlog2n) 13. 1 14. 50 15. 先右后左双旋转 16. 右单旋转17. 48 18. O(lon2n) 三、判断题1. 在顺序表中进行顺序搜索时，若各元素的搜索概率不等，则各元素应按照搜索概率的降序排列存放，则可得到最小的平均搜索长度。

2. 进行折半搜索的表必须是顺序存储的有序表3. 能够在链接存储的有序表上进行折半搜索，其时间复杂度与在顺序存储的有序表上相同4. 假定用两个有序单链表表示两个集合，则这两个集合交运算得到的集合单链表，其长度小于参加运算的任一个集合单链表的长度5. 假定用两个有序单链表表示两个集合，则这两个集合的差运算得到的集合单链表，其长度小于参加运算的任一个集合单链表的长度6. 折半搜索所对应的判定树，既是一棵二叉搜索树，又是一棵理想平衡二叉树（它的特点是除最底层结点外其他各层结点数都是满的，最底层的若干结点可能散布在该层各处）7. 对二叉搜索树进行前序遍历得到的结点序列是一个有序序列8. 在由n个元素组成的有序表上进行折半搜索时，对任一个元素进行搜索的长度（即比较次数）都不会大于log2n+19. 根据n个元素建立一棵二叉搜索树的时间复杂度大致为O(log2n)10. 根据n个元素建立一棵二叉搜索树的时间复杂度大致为O(nlog2n)11. 对于同一组记录，若生成二叉搜索树时插入记录的次序不同则得到不同结构的二叉搜索树12. 对于同一组记录，生成二叉搜索树的结构与插入记录的次序无关13. 对于两棵具有相同记录集合而具有不同结构的二叉搜索树，按中序遍历得到的结点序列是相同的。

14. 在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越大的结点离树根越近，则得到的是最优二叉搜索树15. 在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越小的结点离树根越近，则得到的是最优二叉搜索树参考答案： 1. 是 2. 是 3. 否 4. 是 5. 否6. 是 7. 否 8. 是 9. 否 10. 是11. 是 12. 否 13. 是 14. 是 15. 否四、运算题1. 一个一维数组a[10]中存储着一个有序表，该有序表为：(15, 26, 34, 39, 45, 56, 58, 63, 74, 76 )，根据折半搜索所对应的判定树，写出该判定树的广义表表示，并求出在等概率情况下搜索成功的平均搜索长度判定树的广义表表示：_______________________________平均搜索长度：_________________2. 已知一个有序表 ( 15, 26, 34, 39, 45, 56, 58, 63, 74, 76, 83, 94 ) 顺序存储于一维数组a[12]中，根据折半搜索过程填写成功搜索下表中所给元素34, 56, 58, 63, 94时的比较次数。

元素值 比较次数3. 假定一个线性序列为 ( 。