数据结构习题-chp9-排序

一、单项选择题

1. 采用开放定址法处理散列表的冲突时，其平均查找长度 ( B ) 。
   A．低于链接法处理冲突 B. 高于链接法处理冲突
   C．与链接法处理冲突相同 D．高于二分查找
2. 若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找到A［3］元素经过比较的数组下标依次为 ( D ) 。
   A. 1，2，3 B. 9，5，2，3
   C. 9，5，3 D. 9，4，2，3
3. 对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有 （ D ） 个。
   A．1 B．2 C．3 D．4
4. 查找表是以（ A ）为查找结构。
   A．集合 B．图 C．树 D．文件
5. 在表长为ｎ的链表中进行线性查找，它的平均查找长度为（ B ）。
   Ａ. ASL＝ｎ; Ｂ. ASL＝(n+1)/２;
   Ｃ. ASL＝ ＋１; Ｄ. ASL≈log2ｎ
6. 对线性表进行二分查找时，要求线性表必须 （ D ）。
   A．以顺序方式存储 B．以链接方式存储，且结点按关键字有序排序
   C．以链接方式存储 D．以顺序方式存储，且结点按关键字有序排序
7. 如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用（ A ）查找方法。
   A．分块 B．顺序 C．二分 D．散列
8. 链表适用于（ A ）查找。
   A．顺序 B．二分 C．随机 D．顺序或二分
9. 有一个长度为12的有序表，按二分查找法对其进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（ B ）。
   A．35／12 B．37／12 C．39／12 D．43／12
10. 设哈希表长m=14，哈希函数H（key）=key％11。表中已有4个结点：
    addr(15)=4
    addr(38)=5
    addr(61)=6
    addr(84)=7
    其余地址为空。如用二次探测再散列处理冲突，关键字为49的结点的地址是（ D ）。
    A．8 B．3 C．5 D．9
11. 对包含n个元素的散列表进行查找，平均查找长度为（ D ）。
    A．O(n2) B．O(log2n) C. O(n) D．不直接依赖于n
12. 已知8个元素为{34，76，45，18，26，54，92，65}，按照依次插入结点的方法生成一棵二叉树，最后两层上结点的总数为（ B ）。
    A．1 B．2 C. 3 D．4
13. 不可能生成下图二叉排序树的关键字的序列是（ A ）。
    A． 4 5 3 1 2 B．4 2 5 3 1 C．4 5 2 1 3 D．4 2 3 1 5

14. 动态查找包括（ B ）查找。
    A．顺序表 B. 二叉排序树
    C．有序表 D．索引顺序表

二、填空题

15. 设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较 【 7 】 次就可以断定数据元素X是否在查找表中。
16. 设一组初始记录关键字序列为(20，12，42，31，18，14，28)，则根据这些记录关键字构造的二叉排序树的平均查找长度是 【 19/7 】 。
17. 采用开放定址法处理散列表的冲突时，其平均查找长度【 低于 】链地址法处理冲突。
18. 设散列函数H和键值k1，k2，若k1≠k2，且H（k1）=H（k2），则称这种现象为 【 冲突 】 。
19. 【 散列表 】 查找法的平均查找长度与元素个数n无关。
20. 各结点左右子树深度之差的绝对值至多为 【 1 】 的二叉树称谓平衡二叉树。

三、判断题（下列各题，正确的请在前面的括号内打√；错误的打╳ ）

1. 二分查找法要求待查表的关键字值必须有序。（√）
2. 对有序表而言采用二分查找总比采用顺序查找法速度快。（×）
3. 在二叉排序树中，根结点的值都小于孩子结点的值。（×）
4. 散列存储法的基本思想是由关键字的值决定数据的存储地址。（√）
5. 哈希表是一种将关键字转换为存储地址的存储方法。（√）
6. 选择好的哈希函数就可以避免冲突的发生。（×）
7. 在有序的顺序表和有序的链表上，均可以采用二分查找来提高查找速度。（×）
8. 哈希法的查找效率主要取决于哈希表构造时选取的哈希函数和处理冲突的方法。（√）
9. 在二叉排序树上删除一个结点时，不必移动其它结点，只要将该结点的父结点的相应的指针域置空即可。（×）

四、简答题

1. 假定一组记录为(38,42,55,15,23,44,30,74,48,26)，按次序插入每个结点生成一棵AVL树，画出该AVL树，并求出该AVL树中度为2、度为1和度为0的结点个数。
   
   度为2的结点个数：4
   度为1的结点个数：1
   度为0的结点个数：5
2. 设哈希表的长度m=11，哈希函数为H(K)=K mod m，采用链地址法解决冲突,依次插入的关键码序列为{1,13,12,34,38,33,27,22}。根据构成的哈希表回答：
   (1) 画出链地址法解决冲突时所构造的哈希表
   
   (2) 在等概率的情况下，搜索成功时的平均查找长度；15/8
   (3) 在等概率的情况下，搜索失败时的平均查找长度。11/3
3. 对于给定结点的关键字集合K={1，12，5，8，3，10，7，13，9}，
   （1）试构造一棵二叉排序树；
   （2）在二叉树排序BT中删除“12”后的树结构。
   
4. 画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。
   
   ASL=(1/10) * (1 * 1+2 * 2+3 * 4+4 * 3)=2.9