二叉排序树建立过程_二叉排序树的建立_二叉排序树的建立算法(24)

散列表的这一重要特性反映了负载因子对查找的时间性能的直接影响。因此，在使用中应根据实际问题，对散列函数、解决冲突的方法和负载因子做出恰当、合理的选择，如果选择的好，散列表的平均查找长度可以小于2。9.5 本章小结本章重点介绍了线性表、树形表和散列表的查找方法、算法实现及各种查找方法的时间性能 平均查找长度 分析。本章的重点是顺序查找、折半查找、分块查找，二叉排序树上查找以及散列表上查找的基本思想及算法的实现。本章的难点是二叉排序树的删除算法、L树的旋转及B-树上插入和删除运算。本章的知识点如下：1. 基本概念⑴ 查找、查找结果、静态查找表与动态查找表等概念⑵ 查找算法效率的评判标准2. 线性表的查找⑴ 顺序查找、折半查找和分块查找的基本方法、算法实现和查找效率分析⑵ 顺序查找中哨兵的作用⑶ 折半查找对存储结构及关键字的要求⑷ 通过比较线性表上三种查找方法的优缺点，能根据实际问题的要求和特点，选择出合适的查找方法3. 树形表的查找⑴ 二叉排序树、最佳二叉排序树和L树及平衡因子、平衡旋转等概念⑵ 二叉排序树、最佳二叉排序树和L树以及B-树的特点及用途⑶ 建立一棵二叉排序树的过程实质上是对输入实例的排序过程，输入实例对所建立的二叉排序树形态的影响⑷ 二叉排序树、最佳二叉排序树、L树和B-树的构造方法⑸ 二叉排序树、最佳二叉排序树、L树和B-树的的查找效率4. 散列表的查找⑴ 散列表、散列函数、散列地址、冲突、堆积和负载因子等有关概念⑵ 散列函数的选取原则及产生冲突的原因⑶ 几种常用的散列函数的构造方法⑷ 两类解决冲突的方法及其优缺点⑸ 产生“堆积”现象的原因⑹ 采用线性探查法和拉链法解决冲突时，散列表的建表方法、查找过程以及算法实现和时间分析⑺ 散列表和其它表的本质区别习 题1. 在有n个关键字的线性表中进行顺序查找，若查找第i个关键字的概率为pi，且 。

求出成功的查找的平均查找长度。2. 写出在单链表上进行顺序查找的算法。3. 若在有序表（06, 12, 26, 34, 42, 48, 51, 56, 66, 69, 78, 85）中进行折半查找，试分别画出查找关键字为12、56和75的过程。4. 画出长度为12的有序表进行折半查找的判定树，并求其在等概率情况下查找成功的平均查找长度。5. 为什么对有序的单链表不能进行折半查找？6. 若对表长为n的有序的顺序表和无序的顺序表分别进行顺序查找，试在下列三种情况下分别讨论两者在等概率时的平均查找长度是否相同？⑴ 查找不成功，即表中无关键字等于给定值K的记录；⑵查找成功，且表中只有一个关键字等于给定值K的记录；⑶查找成功，且表中有若干个关键字等于给定值K的记录，一次查找要求找出所有记录。此时的平均查找长度应考虑找到所有记录时所用的比较次数。7. 对于含有256个结点的线性表，若采用分块查找，如何分块才能使效率达到最高？若对索引表也进行顺序查找，则平均查找长度是多少？若每块均含有8个结点，则它的平均查找长度又为多少？8. 对于长度为12的表（Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec），请完成：⑴ 按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率情况下查找成功的平均查找长度。

⑵画出它的最佳二叉排序树，并求其在等概率情况下查找成功的平均查找长度。⑶画出按表中元素的顺序构造一棵L树的过程，并求在等概率情况下查找成功的平均查找长度。9. 写出按图9-7所示的删除方法?'之规定从二叉排序树里删除一个关键字的算法。10. 试证明：二叉排序树结点的对称序序列就是二叉排序树结点的按关键字值排序的序列。11. 对于图9-39所示的一棵3阶B-树，试分别画出在插入65、15、40、30之后B-树的变化。12. 对于图9-40所示的一棵3阶B-树，试分别画出在删除50、40之后B-树的变化。13. 设有一棵B+ 树，其内部结点最多可放100个子树指针，叶结点最多可存储15个记录。对于分别有1, 2, 3, 4, 5层B+ 树，最多能多少个记录，最少能多少个记录？14. 设有关键字集合为 016, 087, 154, 170, 275, 426, 503, 509, 512, 612, 653, 677, 703, 765, 897, 908 。现要按α 0.5把这些关键字存入一个散列表中，试设计两种散列函数，分别算出每个关键字对应的地址，指出有多少次冲突发生。15. 对于上题设计的一种散列函数对上述关键字集合进行存储，用开地址线性探查法解决冲突，将所有关键字都进入散列表后的存储状况画出来，并计算其平均查找长度。

16. 顺序查找的时间为O n ，折半查找的时间为O log2n ，散列法为O 1 ，为什么有高效率的查找方法而低效率的查找方法还不被放弃？266 267 30 1 当 k+1为 2 的幂时；0 当 k+1为其它值时。 k+1 2t k 2t-11≤k ≤n-11≤2t-1≤n-12≤2t≤nlog22≤log22t≤log2n1≤t≤ log2 n1≤k≤n-1且k+1为2的幂

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-26588-24.html