在包含n个元素的字典里进行顺序查找.docVIP

第章 查找1． 在包含n个元素的字典里进行顺序查找，若查找第i个元素的概率为pi，pi如下分布∶p1=1/2，p2=1/4，…，pn-1=1/(2n-1)，pn=1/2n求成功的查找的平均比较次数。2． 设某字典组成如下∶D={016, 087, 154, 170, 275, 426, 503, 509, 512, 612, 653, 677, 703, 765, 897, 908}依次顺序表示在内存中，现用二分法的方法查找字典中是否有元素612，问需要进行多少次比较才能得到结论? 每次选择的比较对象是什么元素?3． 若线性表中各结点的查找概率不等，则可用如下策略提高顺序查找的效率∶若找到指定的结点，则将该结点和其前驱(若存在)结点交换，使得经常被查找的结点是尽量位于表的前端。试对线性表的顺序存储结构和链式存储结构写出实现上述策略的顺序查找算法(查找时必须从表头开始向后扫描)4． 参照线性表的链接表示，设计字典的单链表表示的数据结构和顺序查找算法。5． 对题2所给的字典，设计一种散列表示，取α=0.5，根据选择的散列函数，计算出对应的地址，并统计出碰撞发生的次数。6． 用上题设计的一种散列函数对题2的字典进行存储，用开地址线性探查法解决碰撞，将所有元素都进入散列表后的存储状况画出来。7． 为了正确处理开地址散列表元素的删除，需要对每个字典中元素增加一个删除标志位，试用双散列函数法解决碰撞，散列函数为h1(k)和h2(k)，写一个从散列表中删除一个关键码k的算法。8． 为了利用开地址散列表中被删除的元素空间，需要重新设计开地址散列表中插入和查找的算法，请对上题设计的删除算法设计相应的插入和查找算法。9． 设计一种散列法表示的字典存储方法，适合使用拉链法解决碰撞，给出在这种存储结构中实现字典元素的插入和删除算法。 10． 顺序查找时间为O(n)，二分法查找时间为O(log2n)，散列法为O(1)，为什么有高效率的查找方法而低效率的方法不被放弃?11． 试证明∶二叉排序树中结点的对称序列就是二叉排序树结点按关键码排序的序列。 12． 试编写一算法求出指定结点在给定的二叉排序树中所在的层数。13．试编写一算法，在给定的二叉排序树上找出任意两个不同结点最近的公共祖先(若在两结点A，B中，A是B的祖先，则认为A，B最近的公共祖先就是A)。14．设有以下字典∶{wxw, wxz, wzw, wzy, wzz, yyw, yyx, zww, zwx, zwy, zyw, zyx, zyy, zyz}试画出等权情况下的最佳二叉排序树。15．画出包含六个成员∶K1, K2, K3, K4, K5, K6(K1K2…K6)，权分别为∶p1=3, p2= p3= p4= p5= p6=1，q1= q2= q3= q4= q5= q6=1的最佳二叉排序树。16．从一棵空AVL树开始，将关键码xal, wan, wil, zol, yo, xul, yum, wen, wim, zi, yon, xem, xul, zom逐个插入，画出每插入一个新关键码后得到的AVL树。17．已知元素个数为12的字典，其元素集合为∶{Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec}(1) 试按元素的次序依次插入一棵初始时为空的二叉排序树，请画出插入完成之后的二叉排序树，并求其在等概率情况下查找成功的平均查找长度。(2) 按元素顺序构造一棵AVL树，并求其在等概率情况下查找成功的平均查找长度。18．试给出一个个数最小的关键码序列，使构造AVL树时四种调整平衡操作( LL, LR, RR, RL )各至少执行一次，并画出其构造过程。19．下图是一棵三阶的B树，试画出插入关键码B，L，P，Q，R以后的树形。20．图6.26是一棵3阶的B+树，试分别画出插入关键码30及再删去关键码20的B+树。21．根据6.6.2节的计算，对4096字节的页块，B树最大可以设计为683阶，而B+树可以达到1024阶。请读者计算5层这样的B树和B+树最少各需要多少索引项。22．将（for，case，while，class，protected，virtual，public，private，do，template，const，if，int）中的关键字依次插入初态为空的二叉排序树中，请画出所得到的树T。然后画出删去for之后的二叉排序树T，若再将for插入T中得到的二叉排序树T是否与T相同？最后给出T的前序、中序和后序序列。23．设散列函数为h(key)=key%101，解决冲突的方法为线性探查，表中用-1表示空单元。若删去散列表HT中的304（即令HT[1