你可能喜欢
问答题
本题给出一个施加于链表的选择排序的算法。算法中用到一个临时的表头结点 head,作为结果链表的表头结点,每次从first链上摘下值最大的结点current链入 head之后。算法结束前,将 head删除。
(1)请将缺失的语句部分补上;
(2)设待排序的对象个数 n = 7,当排序前各对象排序码的初始链接顺序为40, 20, 60, 30, 70, 50, 80,试根据上述算法,画出每一趟排序时各结点指针的变化。
问答题
如果某个文件经内排序得到80个初始归并段,试问:
(1)若使用多路归并执行3趟完成排序,那么应取的归并路数至少应为多少?
(2)如果操作系统要求一个程序同时可用的输入/输出文件的总数不超过15个,则按多路归并至少需要几趟可以完成排序?如果限定这个趟数,可取的最低路数是多少?
问答题
假设文件有4500个记录,在磁盘上每个页块可放75个记录。计算机中用于排序的内存区可容纳450个记录。试问:
(1)可建立多少个初始归并段?每个初始归并段有多少记录?存放于多少个页块中?
(2)应采用几路归并?请写出归并过程及每趟需要读写磁盘的页块数。
问答题
问答题
问答题
问答题
在不要求完全排序时,堆排序是一种高效的算法。这种算法的过程是:
(Heapification)把待排序序列看作一棵完全二叉树,通过反复筛选将其调整为堆;
(Re-heapification)依次取出堆顶,然后将剩余的记录重新调整为堆。
现考虑序列A = { 23,41,7,5,56 }:
(1)给出对应于序列A的最小堆HA(以线性数组表示);
(2)给出第一次取出堆顶后,重新调整HA后的结果(以线性数组表示);
(3)给出第二次取出堆顶后,重新调整HA后的结果(以线性数组表示)。