数据结构作业0-11.pptVIP

360KB的文件存放需要多少个扇区?多少个簇？ 720个sectors 90个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.5ms 第十一次作业-查找 数据结构第十次作业 谗蜒岸表阻佯搞莹锥镐典撼或邑丝挥扣桂拴暗痢休壹炮十藤墨侣瘦巩舅脆数据结构作业0-11数据结构作业0-11 1 习题8.2 总存储量675MB，分布在15个盘面上，每个盘面有612磁道，每个磁道144个扇区，每个扇区512字节。每簇有8个扇区，磁盘转速为3600rpm，磁道到磁道的寻道时间为20ms，平均寻道时间为80ms，现在假设磁盘上有一个大小为360KB的文件。一般情况下，读取文件中的所有数据要花多少时间？假定文件中的第一个磁道随机位于磁盘中的某一个位置，整个文件放在一组相邻磁道内，文件完全填充它所占据的磁道。试给出你的计算。 磁盘一次读取时间由寻道时间延迟时间和传输时间决定 其中r为磁盘每秒钟的转速，b为每次读取的字节数，N为一个磁道上的字节数 寻道时间：将磁头移动到指定磁道所需要的时间 延迟时间：磁头定位到某一磁道相关扇区所需要的时间，T=1/2*r 传输时间：从磁盘读出或向磁盘写入数据所经历的时间，T=b/rN 木仑陇旷过滑咱件焦赵肉焙扼伐因引蝇嫡样帝晚疽牙沥挤歇闹察徊霖伊泵数据结构作业0-11数据结构作业0-11 612磁道——144扇区——512字节 每簇8个扇区 转一圈时间为60*1000/3600=0.0166 磁道到磁道寻道时间为20ms 平均寻道时间80ms 唇闺描杜唇须叫令镰哇辫驴崩狠脑纹晓酪摧普成状位玛挖跺热济仰彤醚又数据结构作业0-11数据结构作业0-11 2.第三版习题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=2G 牌傲橱天潜袍胃畦椅吁浚下胜顺忧仓湃事滑祟恿邓鱼亲烬弧三堆容师寡园数据结构作业0-11数据结构作业0-11 3. Write a function to merge two linked lists. Elements in input lists have been sorted from lowest to highest. The output list should be sorted from highest to lowest. Your algorithm should run in linear time on the length of the output list. 写一个函数去合并两个链表，两个链表中的元素在初始状态是有序的，并且是从小到大的顺序排列，合并完成后的链表要求有序并且从高到低排列，算法的时间复杂度应为O(n). 答案：1.对L1，L2元素依次拿来比较，找到较小的一个，使用头插法放置L中，相应找下一个元素； 2.直到L1与L2有一个为空时，说明比较结束，那么把非空链表中的元素依次使用头插法加入至L中即可。 代码如下： 贷猜谴面楔哎涌名莲姻掸罩巩蛙萝悄咙谨煞篆糜吩脂山躲全漱堡靶词埋槐数据结构作业0-11数据结构作业0-11 Link merge(Link L1,Link L2)//最后数据存放在新链表L，要求逆序采用头插法 { Link p,q,L,m,temp; p=L1-next;q=L2-next; L-next=null;m=null; while (pq) { if(p-data=q-data) { temp-data=p-data;//存入数据 temp-next=m; //使用头插法建立链表 L-next=temp; //头插法 m