1、计算机专业基础综合数据结构（排序）历年真题试卷汇编 8 及答案解析(总分：56.00，做题时间：90 分钟)一、综合题(总题数：12，分数：32.00)1.如果只要找出一个具有 n 个元素的集合的第 k(1kn)个最小元素，你所学过的排序方法中哪种最适合?给出实现的思想。【北方交通大学 1998 六(10 分)】（分数：2.00）_2.设结点个数为 n，请问采用堆排序法进行排序，其时间复杂性是多少?请以大 O 形式给出，并给出证明。【上海交通大学 2004 四(10 分)】（分数：2.00）_已知待排序的序列为(503，87，512，6l，908，170，897，275，653，462)，试完
2、成下列各题。（分数：4.00）(1).根据以上序列建立一个堆(画出第一步和最后堆的结果图)，希望先输出最小值。（分数：2.00）_(2).输出最小值后，如何得到次小值(并画出相应结果图)。【同济大学 2001 二(10 分)】（分数：2.00）_试将关键字序列(56，塾，55，67，46，58，18，88)（分数：4.00）(1).调整成一个初始大顶堆，用二叉树形式说明调整过程；（分数：2.00）_(2).简要说明如何从初始大顶堆开始进行排序。【华中科技大学 2007 四、24(10 分)】（分数：2.00）_3.一组记录的关键字为(50，79，8，56，32，41，85)，给出利用重建堆方法
3、建立的初始堆(堆顶最大)，并给出堆排序的过程。 【吉林大学 2007 二、5(4 分)】（分数：2.00）_4.已知序列503，87，512，61，908，170，897，275，653，462)将其调整为堆(大堆顶，即 K i K 2i ，K i K 2i+1 )。【中国海洋大学 2006 一、4(8 分)】（分数：2.00）_5.给定关键字序列(20，18，9，86，72，12，27，40)。试将该序列建成小根堆。（分数：2.00）_6.判断下面的每个结点序列是否表示一个堆，如果不是堆，请把它调整成堆。100，90，80，60，85，75，20，25，10，70，65，50100，70，5
4、0，20，90，75，60，25，10，85，65，80【复旦大学 1997 二(8 分)】（分数：2.00）_7.全国有 10000 人参加物理竞赛，只录取成绩优异的前 10 名，并将他们从高分到低分输出。而对落选的其他考生，不需排出名次，问此种情况下，用何种排序方法速度最快?为什么?【北京邮电大学 1996 一、3(4 分)】（分数：2.00）_8.设有 n 个无序元素，按非递减次序排序，但只想得到前面长度为 k 的部分序列，其中 nk，最好采用什么排序方法?为什么?如果有这样一个序列59，11，26，34，17，91，25)，得到的部分序列是11，17，25)，对于该例使用所选择的方法实
5、现时，共执行多少次比较?【东北大学 2002 一、4(3 分)】（分数：2.00）_9.写出用堆排序算法对文件 F=(12，3，15，30，9，28)进行排序时，初始堆及以后每挑好一个元素重新调整后堆的状态，并指出这里的堆和败者树的一个主要区别。【东南大学 1998 二(8 分)】（分数：2.00）_请回答下列关于堆(Heap)的一些问题。【清华大学 2000 五(12 分)】（分数：6.00）(1).堆的存储表示是顺序的，还是链接的?（分数：2.00）_(2).设有一个最小堆，即堆中任意结点的关键字均大于它的左子女和右子女的关键字。其具有最大值的元素可能在什么地方?（分数：2.00）_(3)
6、.对，1 个元素进行初始建堆的过程中，最多做多少次数据比较(不用大 0 表示法)?（分数：2.00）_二、设计题(总题数：12，分数：24.00)10.设有一个数组中存放了一个无序的关键序列 K 1 、K 2 、K n 。现要求将 K n 放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过 n。(注：用程序实现。)【南京航空航天大学 1997 六(12 分)】（分数：2.00）_11.借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于 key 的记录。设此组记录存放于数组 r1h中。若查找成功，则输出该记录在 r 数组中的位置及其值，否则显示“not
7、 find”信息。请编写出算法并简要说明算法思想。【北京邮电大学 1998 七(1 5 分)】（分数：2.00）_12.编写非递归的快速排序算法。【中科院软件所 1997 三(10 分)】（分数：2.00）_13.设有顺序放置的 n 个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红、白、蓝之一。要求重新安排这些砾石，使得所有红色砾石在前，所有白色砾石居中，所有蓝色砾石居后。重新安排时，对每粒砾石的颜色只能查看一次，并且只允许交换操作来调整砾石的位置。【上海大学 1999 二、2(18 分)】（分数：2.00）_14.编写算法解决荷兰国旗问题，即将仅由红、白、蓝三种颜色的条块序列，在 O(n)时间
8、内按红、白、蓝顺序排好。例：给定色彩条块序列蓝、白、红、白、蓝、红、白、白、红、蓝)则要求的结果为：红、红、红、白、白、白、白、蓝、蓝、蓝【东华大学 2003 五(15 分)】【浙江大学 2003 七(10 分)】（分数：2.00）_15.对给定关键字序号 j(1jn)，要求在无序记录 A1n中找到关键字从小到大排在第 j 位上的记录，写一个算法利用快速排序的划分思想实现上述查找(要求用最少的时间和最少的空间)。例如：给定无序关键字7，5，1，6，2，8，9，3)，当 j=4 时，找到的关键字应是 5。【中科院研究生院 2003 十二(15 分)】【武汉理工大学 2002 四、3(353 分)
9、】（分数：2.00）_16.若待排序列用单链表存储，试给出其快速排序算法。【北京邮电大学 2000 七(15 分)】（分数：2.00）_17.已知关键字序列(K 1 ,K 2 ,K 3 ,，K n-1 )是大根堆。(1)试写出一算法将(K 1 ,K 2 ,K 3 ,，K n-1 ，K n )调整为大根堆；(2)利用(1)的算法写一个建大根堆的算法。【中科院软件所 1999 七、2(7 分)】（分数：2.00）_18.已知由 n 一 1 个关键字组成的序列(K 1 ,K 2 ,K 3 K n-1 )是大顶堆，现在再增加一个关键字 K n ，要求将关键字序列(K 1 ,K 2 ,K 3 ,，K n
10、-1 ，K n )重新调整为大顶堆。请完成以下要求： (1)编写满足上述要求的算法。 (2)简述你所编写的算法的基本思想。 (3)分析你所编写的算法的时间复杂度。 【南京航空航天大学 2006 7(5 分)】【江苏大学 2006 四、1(12 分)】（分数：2.00）_19.试设计一个 Heaplnsert(r，key)算法，将关键字 key 插入到堆 R 中去，并保证插入后 R 仍是堆。并分析你的算法的时间复杂性。【哈尔滨工业大学 2005 五、1(15 分)】（分数：2.00）_20.有关堆排序：(1)给出堆的定义及其数据结构定义；(2)给出堆排序算法的基本思想，并以图例予以说明(要求不少
11、于 6 个待排序元素)；(3)用伪语言描述该算法；(4)给出算法在最坏情况下的时间复杂性分析。【中南大学 2005 五、1(20 分)】（分数：2.00）_21.设有一大批需实时处理的数据元素组成集合 S，实时处理开始后，每隔一极短的时间间隔便收到一个新的数据元素加入 S。现要求在每次接收一个新元素之前，找出 S 中现有的最小元素并将其输出(从 S 中删除)。试选择或构造一种适当的数据结构并设计一个算法，尽可能高效地完成上述任务(只要求用文字说明算法的基本设计思想)。【同济大学 2005 三、1(7 分)】【中国海洋大学 2004 七(20 分)】（分数：2.00）_计算机专业基础综合数据结构
12、（排序）历年真题试卷汇编 8 答案解析(总分：56.00，做题时间：90 分钟)一、综合题(总题数：12，分数：32.00)1.如果只要找出一个具有 n 个元素的集合的第 k(1kn)个最小元素，你所学过的排序方法中哪种最适合?给出实现的思想。【北方交通大学 1998 六(10 分)】（分数：2.00）_正确答案：(正确答案：在具有 n 个元素的集合中找第 k(1kn)个最小元素，应使用快速排序方法。其基本思想如下：设 n 个元素的集合用一维数组表示，其第一个元素的下标为 1，最后一个元素的下标为n。以第一个元素为“枢轴”，经过快速排序的一次划分，找到“枢轴”的位置 i，若 i=k，则该位置的
13、元素即：为所求；若 ik，则在 1 至 i 一 1 间继续进行快速排序的划分；若 i解析：2.设结点个数为 n，请问采用堆排序法进行排序，其时间复杂性是多少?请以大 O 形式给出，并给出证明。【上海交通大学 2004 四(10 分)】（分数：2.00）_正确答案：(正确答案：堆排序的时间由建堆和反复筛选两部分时间构成。对深度为 h 的堆，“筛选”所需进行的关键字比较的次数至多为 2(h 一 1)；对 n 个关键字，建成深度为 h=log 2 n+1 的堆，所需进行的关键字比较的次数至多为 C(n)，它满足下式： )解析：已知待排序的序列为(503，87，512，6l，908，170，897，2
14、75，653，462)，试完成下列各题。（分数：4.00）(1).根据以上序列建立一个堆(画出第一步和最后堆的结果图)，希望先输出最小值。（分数：2.00）_正确答案：(正确答案：建小堆 )解析：(2).输出最小值后，如何得到次小值(并画出相应结果图)。【同济大学 2001 二(10 分)】（分数：2.00）_正确答案：(正确答案：求次小值 )解析：试将关键字序列(56，塾，55，67，46，58，18，88)（分数：4.00）(1).调整成一个初始大顶堆，用二叉树形式说明调整过程；（分数：2.00）_正确答案：(正确答案：大顶堆：88，67，58， 58 ，46，55，18，56，因篇幅所限
15、，建堆过程略。)解析：(2).简要说明如何从初始大顶堆开始进行排序。【华中科技大学 2007 四、24(10 分)】（分数：2.00）_正确答案：(正确答案：堆排序过程。待排序元素在一维数组中，建成堆后，堆顶元素(下标 0)和最后一个元素(下标 n 一 1，本例下标 7)交换。这时最后一个元素(本例 88)到位，不再参与以后的调堆。从堆顶调堆至堆底(下标 n 一 2)，又建成大顶堆。再将堆顶元素和最后一个元素(下标 n 一 2)交换，得到次大元素 67。如此下去，直至堆中只剩一个元素，得到元素的升序序列。)解析：3.一组记录的关键字为(50，79，8，56，32，41，85)，给出利用重建堆方
16、法建立的初始堆(堆顶最大)，并给出堆排序的过程。 【吉林大学 2007 二、5(4 分)】（分数：2.00）_正确答案：(正确答案：结果的大根堆为：85，79，50，56，32，41，8。建堆过程可以描述如下。首先按序列顺序画 n(待排序元素个数)个结点的完全二叉树。定义叶子结点已经是堆。从最后一个分支结点(下标 n21，第 1 个元素下标 0)开始调堆，直至最后将第 1 个元素调整到符合堆的定义。结合本例说明如下：叶子 56，32，41 和 85 已经是堆，最后一个分支结点元素 8 不符合堆的定义，将 85 与 8 交换。元素79 符合堆的定义，不需调整。元素 50 不符合堆的定义，沿元素大
17、的右分支向下筛选(因为建大根堆)，将85 调到堆顶。将 50 放在原 85 的位置已满足堆的定义，否则还要继续向下筛选，直至满足堆的定义找到50 的位置。)解析：4.已知序列503，87，512，61，908，170，897，275，653，462)将其调整为堆(大堆顶，即 K i K 2i ，K i K 2i+1 )。【中国海洋大学 2006 一、4(8 分)】（分数：2.00）_正确答案：(正确答案：结果的大堆为：908，653，897，503，462，170，512，275，61，87)解析：5.给定关键字序列(20，18，9，86，72，12，27，40)。试将该序列建成小根堆。（分数
18、：2.00）_正确答案：(正确答案：小根堆为：9，1 8，12，40，72，20，27，86)解析：6.判断下面的每个结点序列是否表示一个堆，如果不是堆，请把它调整成堆。100，90，80，60，85，75，20，25，10，70，65，50100，70，50，20，90，75，60，25，10，85，65，80【复旦大学 1997 二(8 分)】（分数：2.00）_正确答案：(正确答案：是堆不是堆，调成大堆100，90，80，25，85，75，60，20，10，70，65，50)解析：7.全国有 10000 人参加物理竞赛，只录取成绩优异的前 10 名，并将他们从高分到低分输出。而对落选的其
19、他考生，不需排出名次，问此种情况下，用何种排序方法速度最快?为什么?【北京邮电大学 1996 一、3(4 分)】（分数：2.00）_正确答案：(正确答案：在内部排序方法中，一趟排序后只有简单选择排序和冒泡排序可以选出一个最大(或最小)元素，并加入已有的有序子序列中，但要比较 n 一 1 次。选次大元素要再比较 n 一 2 次，其时间复杂度是 O(n 2 )。从 10 000 个元素中选 10 个元素不能使用这种方法。而插入排序及希尔排序、快速排序、归并排序、基数排序等时间性能好的排序，都要等到最后才能确定各元素位置。只有堆排序，在未结束全部排序前，可以有部分排序结果。建立堆后，堆顶元素就是最大
20、(或最小，视大堆或小堆而定)元素，然后，调堆又选出次大(小)元素。凡要求在 n 个元素中选出 k(k 2)个最大(或最小)元素，一般均使用堆排序。因为堆排序建堆比较次数至多不超过 4n，对深度为 k 的堆，在调堆算法中进行的关键字的比较次数至多为 2(k-1)次，且辅助空间为 O(1)。因快速排序会出现最差情况，时间复杂度为 O(n2)，所以，这里不采用快速排序。)解析：8.设有 n 个无序元素，按非递减次序排序，但只想得到前面长度为 k 的部分序列，其中 nk，最好采用什么排序方法?为什么?如果有这样一个序列59，11，26，34，17，91，25)，得到的部分序列是11，17，25)，对于
21、该例使用所选择的方法实现时，共执行多少次比较?【东北大学 2002 一、4(3 分)】（分数：2.00）_正确答案：(正确答案：从序列59，11，26，34，17，91，25得到11，17，25共用 14 次比较。其中建堆输出 11 比较了 8 次，调堆输出 1 7 和 25 各需要比较 4 次和 2 次：上面已经说明，堆排序适合数据量较大的情况，题中 7 个数据反映不出堆排序的优越性。)解析：9.写出用堆排序算法对文件 F=(12，3，15，30，9，28)进行排序时，初始堆及以后每挑好一个元素重新调整后堆的状态，并指出这里的堆和败者树的一个主要区别。【东南大学 1998 二(8 分)】（分
22、数：2.00）_正确答案：(正确答案：对具体例子的手工堆排序略。堆与败者树的区别：堆是 n 个元素的序列，在向量中存储，具有如下性质： )解析：请回答下列关于堆(Heap)的一些问题。【清华大学 2000 五(12 分)】（分数：6.00）(1).堆的存储表示是顺序的，还是链接的?（分数：2.00）_正确答案：(正确答案：堆的存储是顺序的。)解析：(2).设有一个最小堆，即堆中任意结点的关键字均大于它的左子女和右子女的关键字。其具有最大值的元素可能在什么地方?（分数：2.00）_正确答案：(正确答案：最大值元素一定是叶子结点，可以在n2+1n 间的任何位置上。说明：原题“设有一个最小堆，即堆中
23、任意结点的关键码均 大于 它的左子女和右子女的关键码。其具有最大值的元素可能在什么地方”的叙述有误，应将“大于”改为“小于”。最大值元素一定是叶子结点。)解析：(3).对，1 个元素进行初始建堆的过程中，最多做多少次数据比较(不用大 0 表示法)?（分数：2.00）_正确答案：(正确答案：在建含有 n 个元素、深度为 h 的堆时，其比较次数不超过 4n，推导如下：由于第i 层上的结点数至多是 2 r-1 ，以它为根的二叉树的深度为 h 一 i+1，则调用n2次筛选算法时总共进行的关键字比较次数不超过下式之值： )解析：二、设计题(总题数：12，分数：24.00)10.设有一个数组中存放了一个无
24、序的关键序列 K 1 、K 2 、K n 。现要求将 K n 放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过 n。(注：用程序实现。)【南京航空航天大学 1997 六(12 分)】（分数：2.00）_正确答案：(正确答案：以 K n 为枢轴的一趟快速排序。暂存 K n ，先 i(初值 1)从前向后，再 i(初值n1)从后向前地和枢轴 K n 比较，寻找 K n 的最终位置。请参见第 17 题。)解析：11.借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于 key 的记录。设此组记录存放于数组 r1h中。若查找成功，则输出该记录在 r 数组中的位
25、置及其值，否则显示“not find”信息。请编写出算法并简要说明算法思想。【北京邮电大学 1998 七(1 5 分)】（分数：2.00）_正确答案：(正确答案：可把待查记录看作枢轴，先由后向前依次比较，若小于枢轴，则从前向后，直到查找成功 返回其位置或失败返回 0 为止。)解析：12.编写非递归的快速排序算法。【中科院软件所 1997 三(10 分)】（分数：2.00）_正确答案：(正确答案：快速排序的非递归算法的核心语句段如下： typedef structint low，high；)node node sn+1； int quickpass(rectype r，int，int)； 函数声
26、明 int top=1；stoplow=1； stophigh=n； top 是栈顶指针 while(top0) (ss=stoplow；tt=stophigh；top 一一； if(ssI)s+toplow=SSj stophigh=k 一 1； 枢轴左边进栈 if(ttk1)s+toplow=k+1； stophigh=tt ； 枢轴右边进栈 )解析：13.设有顺序放置的 n 个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红、白、蓝之一。要求重新安排这些砾石，使得所有红色砾石在前，所有白色砾石居中，所有蓝色砾石居后。重新安排时，对每粒砾石的颜色只能查看一次，并且只允许交换操作来调整砾石的位置
27、。【上海大学 1999 二、2(18 分)】（分数：2.00）_正确答案：(正确答案：一趟快速排序可以将序列划分成两部分，这里要求一趟排序将序列分成三部分。设 3 个指针 i、j 和 k，将 r1j 一 1作为红色，r，k-1为白色，rk.n为蓝色。为方便处理，将三种砾石的颜色用整数 1、2 和 3 表示。核心语句段如下： int i=1，j=1，k=n，temp； while(jnext； p 为工作指针 while(flag) 进行一趟快速排序，flag 是结束排序的标志，初值为 0 if(p 一datadata) 结点插入前一半 endl 一next=p-next； 保留后继结点 if(
28、p：=end)flag=0； 一趟快速排序结束 if(start=end1) end0=p； end0 是遍历遇到的第一个小于枢轴的结点，将为前半的尾结点 pnext=start； start=p； 修改左半部链表头指针 p=end1 一next； 恢复当前待处理结点 else 处理右半部链表 if(p=end)flag=0； 已到链表尾 endl 一next=p；endlip； endl和 P 是前驱和后继关系 p=p 一next； else while LinkQuickSort(start，end0)； 对枢轴元素最终位置前的单链表快速排序 LinkQuicksort(start1 一n
29、ext，end1)； 对枢轴元素最终位置后的单链表快速排序)解析：17.已知关键字序列(K 1 ,K 2 ,K 3 ,，K n-1 )是大根堆。(1)试写出一算法将(K 1 ,K 2 ,K 3 ,，K n-1 ，K n )调整为大根堆；(2)利用(1)的算法写一个建大根堆的算法。【中科院软件所 1999 七、2(7 分)】（分数：2.00）_正确答案：(正确答案：(1)因为前 n 一 1 个元素已经是堆，所以从第 n 个记录开始依次与其双亲(n2)比较，若大于双亲则交换，继而与其双亲的双亲比较，直至满足堆的定义(最多类推到根)。核心语句段如下：j=n；R0=Rj； for(i=n2；i=1ji
30、=i12) if(R0keyRikey)Rj=Ri; j=i; else break； Rj=R0; (2)void HeapBuilder(RecType R，int n) for(i=2；i=1ji=i12) if(R0keyRikey)Rj=Ri; j=i; else break； Rj=R0; (2)void HeapBuilder(RecType R，int n) for(i=2；i=1ji=i12) if(R0keyRikey)Rj=Ri; j=i; else break； Rj=R0; (2)void HeapBuilder(RecType R，int n) for(i=2；i1
31、； i 一一)(R1Ri；Sift(R，1，i 一 1)；)for HeapSort)解析：21.设有一大批需实时处理的数据元素组成集合 S，实时处理开始后，每隔一极短的时间间隔便收到一个新的数据元素加入 S。现要求在每次接收一个新元素之前，找出 S 中现有的最小元素并将其输出(从 S 中删除)。试选择或构造一种适当的数据结构并设计一个算法，尽可能高效地完成上述任务(只要求用文字说明算法的基本设计思想)。【同济大学 2005 三、1(7 分)】【中国海洋大学 2004 七(20 分)】（分数：2.00）_正确答案：(正确答案：这是堆排序问题，先将集合 S 中的元素建成小堆，并输出堆顶最小元素。再将每隔一极短的时间间隔收到的新数据元素放到堆顶，进行调堆，再输出堆顶元素，如此反复进行。请参考上面第 34 题堆排序算法。)解析：
