数据结构复习题集（下）第十一次作业-查找9.6假定值A到H存储在一个自组织线性表中，开始按照升序存放，对于9.2小节建议的三种自组织启发式规则，按照下面顺序访问线性表，给出结果线性表和需要的比较总数：ＤＨＨＧＨＥＧＨＧＨＥＣＥＨＧ自组织线性表根据实际的记录访问模式在线性表中修改记录顺利。使用自启发规则决定如何重新排列线性表。1．若在线性表中采用折半查找法查找元素，该线性表应该（C）。A）元素按值有序B）采用顺序存储结构C）元素按值有序，且采用顺序存储结构D）元素按值有序，且采用链式存储结构2．在下列查找方法中，平均查找速度是快的是（B）。A）顺序查找B）折半查找C）分块查找D）二叉排序树查找3．在关键字随机分布的情况下，用二叉排序树的方法进行查找，其查找长度与(B）量级相当。A）顺序查找B）折半查找C）分块查找D）前面都不正确元素ABCDEFGH查找次数DD1ABCEFGH4HD1H1ABCEFG8HD1H2ABCEFG2GH2D1G1ABCEF7HH3D1G1ABCEF1EH3D1G1E1ABCF7GH3G2D1E1ABCF3HH4G2D1E1ABCF1GH4G3D1E1ABCF2HH5G3D1E1ABCF1EH5G3E2D1ABCF4CH5G3E2D1C1ABF7EH5G3E3D1C1ABF3HH6G3E3D1C1ABF1GH6G4E3D1C1ABF2ResultHGEDCABF531.保持一个线性表按照访问频率排序的最显然的方式是为每条记录保存一个访问计数。一直按照这个顺序维护记录，称为计数方法(Count)元素ABCDEFGH查找次数DDABCEFGH4HHDABCEFG8HHDABCEFG1GGHDABCEF8HHGDABCEF2EEHGDABCF7GGEHDABCF3HHGEDABCF3GGHEDABCF2HHGEDABCF2EEHGDABCF3CCEHGDABF7EECHGDABF2HHECGDABF3GGHECDABF4ResultGHECDABF592.如果找到一个记录就将其放在线性表的最前面，而把后面的记录后退一个位置。查找元素ABCDEFGH查找次数DABDCEFGH4HABDCEFHG8HABDCEHFG7GABDCEHGF8HABDCHEGF6EABDCEHGF6GABDCEGHF7HABDCEHGF7GABDCEGHF7HABDCEHGF7EABDECHGF5CABDCEHGF5EABDECHGF5HABDEHCGF6GABDEHGCF7ResultABDEHGCF953.把找到的记录与它在线性表中的前一条记录交换位置，称为转置(transpose)9.13假定把关键码K散列到有n个槽(从0到n-1编号)的散列表中。对于下面的每一个函数h(K)，这个函数作为散列函数可以接受吗?(即对于插入和检索，散列程序能否正常工作)？如果可以的话，它是一个好的散列函数吗？函数Random(n)返回一个0到n-1之间的随机整数(包括这两个数在内)。(a)h(k)=k/n,其中k和n都是整数；(b)h(k)=1；(c)h(k)=(k+Random(n))modn；(d)h(k)=kmodn，其中n是一个素数；答案：(a)不可以。若k大于n平方,那么k/n的值就会超出n,超出范围。(b)可以。但是所有的数据都散列到相同的槽位中(c)不可以。因为采用随机数，那么插进去之后，检索不到，因为不知道此元素是使用了什么数据进行插入的(d)可以9.16使用闭散列，利用双散列的方法解决冲突，把下面的关键码插入到一个有13个槽的散列表中(槽从0到12编号)。使用的散列函数H1和H2在下面定义。给出插入8个关键码值后的散列表。一定要说明如何使用H1和H2进行散列。函数Rew(k)颠倒10进制数k各个位的数字，例如Rew(37)=73,Rew(7)=7。H1(k)=kmod13.H2(k)=(Rew(k+1)mod11).答案：双散列：di=i*Hash2(key)，当通过第一个散列函数得到的地址发生冲突之后，则利用第二个散列函数计算该关键字的地址增量，在双散列中，最多经过m次探测就会遍历表中所有的位置，会到H0的位置。H1：2,8,5,7,6,5,1,1H2：3,9,1,1,2,3,1,5插入过程：2------>2成功8------>8成功31----->5成功20----->7成功19----->6成功18----->5冲突；使用H1()+H2()=5+3=8冲突使用H1+H2+H2=5+3+3=11成功53----->1成功27----->1冲突；使用H1()+H2()=1+5=6冲突,使用H1+H2()+H2()=1+5+5=11冲突使用H1()+H2()+H2()+H2()=(1+5+5+5)%13=3成功1．已知关键字序列{23，13，5，28，14，25}，试构造二叉排序树。2.已知一组关键字为（19，14，23，1，68，20，84，27，55，11，10，79），哈希函数：H(key)=keyMOD13，哈希地址空间为0~12，请构造用链地址法处理冲突的哈希表，并求平均查找长度。0123456782135(2)100378(4)99(5)2045(7)3.已知哈希表地址空间是0..8，哈希函数是H(k)=k%7，采用线性探测再散列处理冲突，将序列{100,20,21,35,3,78,99,45}数据序依次存入此哈希表中，列出插...
