发布时间 : 星期六 文章数据结构考研试题精选及答案第10章 排序更新完毕开始阅读f23476232f60ddccda38a060
END;
PROCEDURE mergesort(VAR r,r1:listtype;s,t:integer); BEGIN
IF s=t THEN r1[s]:=r[s] ELSE BEGIN
MERGESORT(r,r2,s,(s+t)DIV 2); MERGESORT(r,r2,(S+t)DIV 2+1,t); MERGE(r2,s,(s+t)DIV 2,t,rl) END END;
若对下列关键字序列进行快速排序和归并排序，分别写出三次调用过程qkpass和过程merge后的结果。
（98，36，77，42，23，65，84，10，59，37，61，18）。 【清华大学 1996 六 】
38．已知一关键码序列为：3，87，12，61，70，97，26，45。试根据堆排序原理，填写完整下示各步骤结果。【首都经贸大学 1998 二、7 （10分）】
建立堆结构：_____________ 交换与调整：
（1）87 70 26 61 45 12 3 97;（2）____________________; （3）61 45 26 3 12 70 87 97;（4）____________________; （5）26 12 3 45 61 70 87 97;（6）____________________; （7）3 12 26 45 61 70 87 97;
39．判断下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，请将它们调整为堆）。 （1）100，85，98，77，80，60，82，40，20，10，66 （2）100，98，85，82，80，77，66，60，40，20，10 （3）100，85，40，77，80，60，66，98，82，10，20
（4）10，20，40，60，66，77，80， 82，85，98，100
【山东大学 1998 四 (5分)】 【山东工业大学 2000 四 （5分）】 类似本题的另外叙述有：
(1) 判别以下序列是否是堆（大顶堆），如果不是，则把它调整为堆。 （12 ，70，33，65，24，56，48，92，86，33）【燕山大学 2001 四、1 （8分）】 (2) 判断下面的每个结点序列是否表示一个堆，如果不是堆，请把它调整成堆。 ①100，90，80，60，85，75，20，25，10，70，65，50
②100，70，50，20，90，75，60，25，10，85，65，80 【复旦大学 1997 二 （8分）】
(3) 判别下列两个序列是否为堆，若不是，按照对序列建堆的思想把它调整为堆，用图表示建堆的过程。【厦门大学 2001 二、1 （24%/3分）】
①（1，5，7，20，18，8，8，40） ②（18，9，5，8，4，17，21，6）
(4）根据给定的关键字集合（20，15，40，35，45，25，50，30，10）顺序输入 ①构造一棵完全二叉树；②画出整理好的一棵堆树；③画出一棵输出一个排序记录后的二叉树；
④画出重新调整好的堆树。 【大连海事大学 2001 六 (5分)】
40．全国有10000人参加物理竞赛，只录取成绩优异的前10名，并将他们从高分到低分输出。而对落选的其他考生，不需排出名次，问此种情况下，用何种排序方法速度最快？为什么？
【北京邮电大学 1996 一、3 （4分）】 类似本题的另外叙述有：
（1）如果在1000000个记录中找出2 个最小的记录，你认为采用什么样的排序方法所需的关键字比较次数最少？共计多少次？ 【厦门大学 1999 三、4】
41．已知待排序的序列为（503，87，512，61，908，170，897，275，653，462），试完成下列各题。
(1) 根据以上序列建立一个堆（画出第一步和最后堆的结果图），希望先输出最小值。 (2) 输出最小值后，如何得到次小值。（并画出相应结果图）【同济大学 2001 二 (10分)】 类似本题的另外叙述有：
(1) 对于输入关键字序列48，70，65，33，24，56，12，92进行： ① 建立堆排序的初始堆（小顶堆），要求画出主要过程。
② 建一棵平衡二叉树，画出过程（至少每次调整有一张，标出最小不平衡子树的根）。 【北京工业大学 2001 二、5 (6分)】
(2) 简要叙述堆排序的算法思想。并对如下关键字序列（3，8，85，12，37，50）按堆排序算法进行从小到大排序，要求画出排序全过程的示意图。 【南京航空航天大学 1997 五 （10分）】
(3) 设记录关键字集合K={28，17，85，96，75，8，42，65，04}
① 写出对K进行“二路归并”且按关键字递增次序排序时，各趟排序的结果；
② 如何将K建成一个完全二叉树形式的最小堆； 【北京科技大学 1997 七（10分）】 42．设有n个无序元素，按非递减次序排序，但只想得到前面长度为k的部分序列，其中n>>k，最好采用什么排序方法？为什么？如果有这样一个序列{59，11，26，34，17，91，25}，得到的部分序列是：{11，17，25}，对于该例使用所选择的方法实现时，共执行多少次比较？【东北大学 2002 一、4(3分)】 类似本题的另外叙述有：
(1) 如果只想得到一个序列中第K个最小元素之前的部分排序序列，那么最好应采用哪种排序算法？为什么？如由这样一个序列：57, 40, 38, 11, 13, 34, 48, 75, 25, 6, 19, 9, 7 得到其第四个最小元素之前的部分排序序列：6,7,9,11,? 用你选用算法实现时，共执行多少次比较？
【北方交通大学 1994 七（16分）】
43．写出用堆排序算法对文件F=（12，3，15，30，9，28）进行排序时，初始堆及以后每挑好一个元素重新调整后堆的状态，并指出这里的堆和败者树的一个主要区别。【东南大学 1998 二（8分）】
44．请回答下列关于堆(Heap)的一些问题：【清华大学 2000 五 （12分）】
(1)(4分) 堆的存储表示是顺序的，还是链接的? (2)(4分) 设有一个最小堆，即堆中任意结点的关键码均大于它的左子女和右子女的关键码。其具有最大值的元素可能在什么地方?
(3)(4分)对n个元素进行初始建堆的过程中，最多做多少次数据比较（不用大O表示法）? 45．解答问题
(1)（6分）设某文件中待排序记录的排序码为72，73，71，23，94，16，05，68，试画图表示出树形选择排序（增序）过程的前三步。 (2)（4分） 试说明树形选择排序的基本思想。
(3)（2分） 树形选择排序与直接选择排序相比较，优缺点是什么？ (4)（3分） 堆排序是如何改进树形排序方法的？优点是什么？
【山东大学 1999 五（15分）】 【山东工业大学 1999 五 （15分）】
46. 若有N个元素已构成一个小根堆, 那么如果增加一个元素为Kn+1,请用文字简要说明你如何在log2n 的时间内将其重新调整为一个堆? 【中科院计算所 1999 三、2 （5分）】 47．填空并回答相关问题
(1)下面是将任意序列调整为最大堆（MAX HEAP）的算法，请将空白部分填上：
将任意序列调整为最大堆通过不断调用adjust函数，即：FOR（i=n/2；i >0；i- -）adjust（list，i，n）；其中list为待调整序列所在数组（从下标1开始），n为序列元素个数，adjust函数为：
void adjust（int list[]，int root，int n） /*将以root为下标的对应元素作为待调整堆的根，待调整元素放在list数组中，最大元素下标为n*/
{int child,rootkey; rootkey=list[root]; child=2*root; while(child<=n)
{if((child if(rootkey>list[child]) break; else{List[(2) ]=list[child]; child*=2; } } list[child/2]=rootkey; } (2)．判断下列序列能否构成最大堆：（12，70，33，65，24，56，48，92，86，33）；若不能按上述算法将其调整为堆，调整后的结果为：（ ）。 【浙江大学 1998 七 (11分)】 48．回答问题：(1) 设待排序的结点个数是n。试问堆排序算法在完成一次sift建堆，并且取走找到的最小关键码后，是否还需要对于n-1个关键码从头开始建堆？为什么？ (2) 假定采用sift建堆算法。试问堆排序算法采用了怎样的节省存储空间的措施？堆排序完成后，heap中保存了关键码值的升序排列还是降序排列？ 【山东工业大学 1996 三、3 （8分）】 49．在多关键字排序时，LSD和MSD两种方法的特点是什么？【北京邮电大学 2001 三、3 （5分）】 50．内排序的过程中，通常需要对待排序的关键字集合进行多遍扫描。采用不同排序方法，会产生不同的中间结果。设要将序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的关键字按字母序的升序重新排列，请分别给出对该序列进行冒泡排序，初始步长为4的希尔排序，二路归并排序及以第一个元素为分界元素的快速排序的第一趟扫描的结果，并给出对该序列作堆排序时初始建堆的结果。【长沙铁道学院 1998 四、5(6分)】 51．给出一组关键字T=(12,2,16,30,8,28,4,10,20,6,18),写出用下列算法从小到大排序时第一趟结束时的序列； (1) 希尔排序（第一趟排序的增量为5） (2) 快速排序（选第一个记录为枢轴（分隔）） (3) 链式基数排序（基数为10） 【上海交通大学 1999 八 （9分）】 52. 给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进 行排序时的变化过程：【南开大学 1998 八 (12分)】 (1) 归并排序 每归并一次书写一个次序。 (2) 快速排序 每划分一次书写一个次序。 (3) 堆排序 先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。 类似本题的另外叙述有： (1) 对关键字/权值序列{9，4，3，8，10，7，6，5} ① 设序列是初始归并段的长度，画出最佳归并树，并计算其对应归并排序的I/O 次数（假设每次I/O读写一个记录）。 ② 设序列是关键字输入次序，画出得到的二叉排序树。 ③ 画出构造初始小根堆的过程。 ④ 画出快速排序第一趟的过程。 ⑤ 画出步长为2的一趟希尔排序结果。【华南师范大学2000 二 (20分)】 53. （1） 判定起泡排序的结束条件是什么？ （2） 请简单叙述希尔排序的基本思想。 （3） 将下列序列调整成堆（堆顶为最小值） 1 2 3 4 5 6 7 8 9 10 112 70 33 65 24 56 48 92 80 13 （4）在16个关键字中选出最小的关键字至少要多少次比较？再选出次小的关键字至少要多少次比较？请简要说明选择的方法和过程。 【燕山大学 1999 九（14分）】 54．给出如下关键字序列321，156，57，46，28，7，331，33，34，63试按链式基数排序方法，列出一趟分配和收集的过程。 【北京轻工业学院 1999 九 （10分）】 类似本题的另外叙述有： (1) 已知整数数组a的10个元素为326，129，167，588，212，95，980，725，443，601，用以下排序方法进行由小到大排序。 【西南交通大学 2000 二、6】 ① 用基数排序算法时，试写出第一次分配和收集后数组a中的结果。 ② 用堆排序时，试写出将第一个选出的数据放在数组a的最后位置上，将a调整为堆之后的a中的结果。 55．请写出应填入下列叙述中（ ）内的正确答案。 【上海大学 2002 一（8分）】 排序有各种方法，如插入排序、快速排序、堆排序等。 设一数组中原有数据如下：15，13，20，18，12，60。下面是一组由不同排序方法进行一遍排序后的结果。 （ ）排序的结果为：12，13，15，18，20，60 （ ）排序的结果为：13，15，18，12，20，60 （ ）排序的结果为：13，15，20，18，12，60 （ ）排序的结果为：12，13，20，18，15，60 56．图： k←0 i←1 m←n