第九章 查找（答案版）

第九章 查找 一、填空题 1、 在数据的存放无规律的线性表中进行查找的有效方法是 顺序查找 。 2、线性有序表（a1，a2，a3，…，a256)是从小到大顺序保存的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索 8 次。 3、假设在有序线性表a[20]上进行折半查找，则比较1次查找成功的结点数为 1 ，比较2次查找成功的结点数为 2 ，比较5次查找成功的结点数为 8 ，平均查找长度为 3.7 。 4、折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28,6,12,20 比较大小。 5、 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 散列查找 。 6、散列法存储的基本思想是由 关键字的值 决定数据的存储地址。 7、有一个表长为m的散列表，初始状态为空，现将n（n<m）个不同的关键码插入到散列表中，解决冲突的方法是用线性探测法。如果这n个关键码的散列地址都相同，则在该哈希表上查找全部数据需要的总次数是 n(n-1)/2 （ 1＋2 ＋…＋n-1） 。 8、给定关键字序列6，11，78，10，1，3，9，2，4，21试分别用二分查找（假设已排序）、二叉排序树查找、散列查找(用线性探查法（模取11的HASH函数）和链地址法（模取7的HASH函数）)来实现查找的平均查找长度， 则二分查找 (1*1+2*2+4*3+3*4)/10 = 2.9 ， 二叉排序树查找 ( 1*1+2*2+4*3+3*4)/10 = 2.9 ， 线性探查法 (6*1+2*2+1*3+1*9)/10 = 2.2 ， 链地址法 (8*1+2*2)/10 = 1.2 。 9、折半搜索与二叉搜索树的时间性能 有时不相同 。 10、散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。则元素59存放在散列表中的地址是 11 。 二、简答题 1、在本章的9.4.1中，曾提到“散列函数为：hash(Key)=key，当然，这种存储现实中几乎是不可能的”请回答具体有哪些原因 答：1. 无论哈希函数设计有多么精细，都会产生冲突现象，也就是2个关键字处理函数的结果映射在了同一位置上，因此，有一些方法可以避免冲突。 2.因为存储的信息不可能只是数字，有可能是一些复杂的结构体，而散列函数的存储方式是通过地址存储。 2、折半查找适不适合链表结构的序列，为什么？用二分查找的查找速度必然比线性查找的速度快，这种说法对吗？ 答：不适合！虽然有序的单链表的结点是按从小到大（或从大到小）顺序排列，但因其存储结构为单链表，查找结点时只能从头指针开始逐步搜索，故不能进行折半查找。 二分查找的速度在一般情况下是快些，但在特殊情况下未必快。例如所查数据位于首位时，则线性查找快；而二分查找则慢得多。 3、假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试画出描述折半查找过程的判定树。 答： 4、设哈希（Hash）表的地址范围为0～17，哈希函数为：H（K）＝K MOD 16。用线性探测法再散列法处理冲突，输入元素序列为（10，24，32，17，31，30，46，47，40，63，49）画出哈希表的示意图,假定每个元素的查找概率相等，求平均查找长度。 答：示意图： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 32 17 63 49 24 40 10 30 31 46 47 ASL=1/11*(6+2+3*3)=17/11=1.55 5、从时间效率出发，分析比较查找、排序的各自特点，并解释为什么查找比排序效率高一个量级O(n) 提示：排序和查找都有比较的过程，但排序多了移动数据的步骤 6、已知如下所示长度为12的表： （Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec） 试按表中元素的顺序依次插入一棵初始为空的二叉排序树。 1）画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。 2）若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。 3）按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。