搜索
数据结构第十次作业1习题8.2总存储量675MB，分布在15个盘面上，每个盘面有612磁道，每个磁道144个扇区，每个扇区512字节。每簇有8个扇区，磁盘转速为3600rpm，磁道到磁道的寻道时间为20ms，平均寻道时间为80ms，现在假设磁盘上有一个大小为360KB的文件。一般情况下，读取文件中的所有数据要花多少时间？假定文件中的第一个磁道随机位于磁盘中的某一个位置，整个文件放在一组相邻磁道内，文件完全填充它所占据的磁道。试给出你的计算。磁盘一次读取时间由寻道时间延迟时间和传输时间决定其中r为磁盘每秒钟的转速，b为每次读取的字节数，N为一个磁道上的字节数寻道时间：将磁头移动到指定磁道所需要的时间延迟时间：磁头定位到某一磁道相关扇区所需要的时间，T=1/2*r传输时间：从磁盘读出或向磁盘写入数据所经历的时间，T=b/rN•360KB的文件存放需要多少个扇区?多少个簇？720个sectors90个cluster•一般情况90*80ms+90*（1/2+8/144）*0.0166s=7288.18ms•连续存放•360KB文件放多少个track？•720/144=5•第一个磁道：80ms+（1/2+1/1）*0.0166s=104.9ms•后面4个磁道：20ms+1.5*0.0166s=44.9ms•总时间：104.9+44.9*4=284.5ms612磁道——144扇区——512字节每簇8个扇区转一圈时间为60*1000/3600=0.0166磁道到磁道寻道时间为20ms平均寻道时间80ms2.第三版习题8.17假设一条记录长为32个字节，一个块长为1024个字节(因此每个块共有32条记录)，工作主存是1MB(还有用于I/O缓冲区、程序变量等的额外存储空间)。对于使用置换选择方法和一趟扫描多路归并的最大的文件，预计的大小是多少？解释你是怎么得到这个结果的。答案：工作主存是1MB，块长是1KB，因此工作内存有1024块。在平均情况下，如果工作内存的大小为M，使用置换选择可以创建长度为2M的顺串，即使用置换选择方法文件最大为2MB(见第二版课本P185);假定为置换选择方法分配B个块，（顺串平均长度就是2B个块），接下来，进行一个B路归并，在一次多路归并中，平均可以处理具有2B2个块的文件，在一趟二路归并中，平均可以处理具有2B(2+1)个块大小的文件，即为2*10243B=2*210*3=2*230=2G3.Writeafunctiontomergetwolinkedlists.Elementsininputlistshavebeensortedfromlowesttohighest.Theoutputlistshouldbesortedfromhighesttolowest.Youralgorithmshouldruninlineartimeonthelengthoftheoutputlist.写一个函数去合并两个链表，两个链表中的元素在初始状态是有序的，并且是从小到大的顺序排列，合并完成后的链表要求有序并且从高到低排列，算法的时间复杂度应为O(n).答案：1.对L1，L2元素依次拿来比较，找到较小的一个，使用头插法放置L中，相应找下一个元素；2.直到L1与L2有一个为空时，说明比较结束，那么把非空链表中的元素依次使用头插法加入至L中即可。代码如下：Linkmerge(LinkL1,LinkL2)//最后数据存放在新链表L，要求逆序采用头插法{Linkp,q,L,m,temp;p=L1-next;q=L2-next;L-next=null;m=null;while(p&&q){if(p-data=q-data){temp-data=p-data;//存入数据temp-next=m;//使用头插法建立链表L-next=temp;//头插法m=temp;//头插法p=p-next;}else{temp-data=q-data;//存入数据temp-next=m;L-next=temp;m=temp;q=q-next;}}//whilewhile(p){temp-data=p-data;//存入数据temp-next=m;L-next=temp;m=temp;p=p-next;}while(q){temp-data=q-data;//存入数据temp-next=m;L-next=temp;m=temp;q=q-next;}returnL;};4.两个单链表L1和L2中的元素类型相同，要求从L1中删除那些同时在L2中出现的元素。若L1中有重复元素，要求只保留一个。分析所设计的算法的时间复杂度。Linkmerge(LinkL1,LinkL2){Linkp,q,temp,pre;p=L1-next;temp=p-next;pre=L1;//从L1的第二个元素开始比较while(p)//对L1依次遍历，删除相同元素{while(temp)if(p-data!=temp-data)temp=temp-next;else{pre-next=pre-next-next;break;}pre=p;p=p-next;//记录当前节点的前驱节点便于删除}pre=L1;p=L1-next;temp=L2-next;//从L2的第一个元素开始比较while(p)//对L1中的元素，依次与L2中比较，删除相同元素{while(temp)if(p-data!=temp-data)temp=temp-next;else{p-next=p-next-next;break;}pre=p;p=p-next;//记录当前节点的前驱节点便于删除}returnL1；};时间复杂度为O(n2)(假设链表L1与L2的规模均为n)第十一次作业-查找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.14假定一个有7个槽的散列表(槽从0到6编号)。如果将散列函数h(k)=kmod7和线性探测用于一组数字3，12，9，2，给出最后的结果散列表。在插入值为2的关键码之后，列出每一个空槽作为下一个被填充槽的概率。插入元素01234563312312993122932129.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的位置。Hi=（H（key）+di）%mH1：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}，试构造二叉排序树。23/\1328/\/514252.已知一组关键字为（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}数据序依次存入此哈希表中，列出插入时的比较次数，并求出在等概率下的平均查找长度。平均查找长度L=(4*1+2+4+5+7)/8=2.754．已知关键字序列{12,26,38,89,56}，试构造平衡二叉树。