第9章集合 选择题 C|2.A3.1D|3.2C 12.1C12.2c13.1C13.2D d 5.B6.D7.D8.c9.A|10.D11.B 3G13.4H14.1E|14.2B14.3E14.4B14.5B15.1B 15.2A16.A17.C18.c19.C20.D21.B22.C23.B24.C25.1B25.2F 25.3I26.A|27.D28.C29.1A29.2C30.B31.D32.D33.C|34.D35.1D 判断题 1.√|2.√3.x4.x15.×|6.√7.√|8.×|9.×|10.11.|12. 18 19 21 24. 部分答案解释如下。 4.不能说哪种哈希函数的选取方法最好,各种选取方法有自己的适用范围 8.哈希表的结点中可以包括指针,指向其元素 11.单链表不能使用折半查找方法。 20.按插入后中序遍历是递增序列的原则,若某结点只有右子树,而插入元素的关键字小于 该结点的关键字,则会插入到该结点的左侧,成为其左孩子。这种插入就不是插入到叶子下 21.从平衡因子定义看,完全二叉树任一结点的平衡因子的绝对值确实是小于等于1。但是, 平衡二叉树本质上是二叉排序树,完全二叉树不一定是排序树。故不能说完全二叉树是平衡 二叉树 23.某结点的左子树根结点不一定是它的中序前驱,其右子树根结点也不一定是它的中序后 继 24.在等概率下,查找成功时的平均查找长度相同,查找失败时的平均查找长度不相同 26.只有被删除结点是叶子结点时命题才正确。 填空题 1.nn+1 3.6,9,11,12 5.26(第4层是叶子结点,每个结点两个关键字) 6.1,3,6,8,11,13,16,19 7.5,96 8.m-1,「m/2+1 10.(1)哈希函数(2)解决冲突的方法(3)选择好的哈希函数(4)处理冲突的方法(5)均匀(6) 简单 11.AⅥL树(高度平衡树,高度平衡的二叉排序树),或为空二叉树,或二叉树中任意结点 左子树高度与右子树高度差的绝对值小于等于1 2.小于等于表长的最大素数或不包含小于20的质因子的合数13.1614.Llg 15.(1)45(2)45(3)46(块内顺序查找)16.k(k+1)/217.30,31.5(块内顺序查 找) 18.(1)顺序存储或链式存储(②2)顺序存储且有序(3)块内顺序存储,块间有序(4)散列 存储第 9 章 集合 一．选择题 1.C 2.A 3.1D 3.2C 4.D 5.B 6.D 7.D 8.C 9.A 10.D 11.B 12.1C 12.2C 13.1C 13.2D 13.3G 13.4H 14.1E 14.2B 14.3E 14.4B 14.5B 15.1B 15.2A 16.A 17.C 18.C 19.C 20.D 21.B 22.C 23.B 24.C 25.1B 25.2F 25.3I 26.A 27.D 28.C 29.1A 29.2C 30.B 31.D 32.D 33.C 34.D 35.1D 35.2C 36.C 二．判断题 1.√ 2.√ 3.× 4.× 5.× 6.√ 7.√ 8.× 9.× 10. × 11. × 12. √ 13. √ 14. × 15. × 16. × 17. √ 18. × 19. √ 20. × 21. × 22. × 23. × 24. × 25. √ 26. × 27. × 28. √ 29. √ 30. × 31. × 32. √ 33. √ 34. × 35. √ 36. √ 部分答案解释如下。 4．不能说哪种哈希函数的选取方法最好，各种选取方法有自己的适用范围。 8．哈希表的结点中可以包括指针，指向其元素。 11．单链表不能使用折半查找方法。 20．按插入后中序遍历是递增序列的原则，若某结点只有右子树，而插入元素的关键字小于 该结点的关键字，则会插入到该结点的左侧，成为其左孩子。这种插入就不是插入到叶子下 面。 21．从平衡因子定义看，完全二叉树任一结点的平衡因子的绝对值确实是小于等于 1。但是， 平衡二叉树本质上是二叉排序树，完全二叉树不一定是排序树。故不能说完全二叉树是平衡 二叉树。 23．某结点的左子树根结点不一定是它的中序前驱，其右子树根结点也不一定是它的中序后 继。 24．在等概率下，查找成功时的平均查找长度相同，查找失败时的平均查找长度不相同。 26．只有被删除结点是叶子结点时命题才正确。 三．填空题 1．n n+1 2．4 3．6,9,11,12 4．5 5．26（第 4 层是叶子结点，每个结点两个关键字） 6．1,3,6,8,11,13,16,19 7．5,96 8．m-1,「m/2-1 9．2,4,3 10．(1)哈希函数(2)解决冲突的方法 (3)选择好的哈希函数 (4)处理冲突的方法 (5)均匀(6) 简单 11．AVL 树（高度平衡树，高度平衡的二叉排序树），或为空二叉树，或二叉树中任意结点 左子树高度与右子树高度差的绝对值小于等于 1。 12．小于等于表长的最大素数或不包含小于 20 的质因子的合数 13．16 14． ㏒ 2 n」+1 15．(1)45 (2)45 (3)46（块内顺序查找） 16．k(k+1)/2 17．30，31.5（块内顺序查 找） 18．(1)顺序存储或链式存储 (2)顺序存储且有序 (3)块内顺序存储，块间有序 (4) 散列 存储