[考研类试卷]计算机专业基础综合数据结构（排序）历年真题试卷汇编9及答案与解析.doc

1、计算机专业基础综合数据结构（排序）历年真题试卷汇编 9 及答案与解析一、综合题1 如果只要找出一个具有 n 个元素的集合的第 k(1kn)个最小元素，你所学过的排序方法中哪种最适合? 给出实现的思想。 【北方交通大学 1998 六(10 分)】2 设结点个数为 n，请问采用堆排序法进行排序，其时间复杂性是多少?请以大 O形式给出，并给出证明。【上海交通大学 2004 四(10 分)】2 已知待排序的序列为(503，87，512，6l，908， 170，897，275，653，462)，试完成下列各题。3 根据以上序列建立一个堆(画出第一步和最后堆的结果图)，希望先输出最小值。4 输出最小值后，

2、如何得到次小值(并画出相应结果图)。【同济大学 2001 二(10 分)】4 试将关键字序列(56，塾，55，67，46，58，18，88)5 调整成一个初始大顶堆，用二叉树形式说明调整过程；6 简要说明如何从初始大顶堆开始进行排序。【华中科技大学 2007 四、24(10 分)】7 一组记录的关键字为(50，79，8，56，32，41，85)，给出利用重建堆方法建立的初始堆(堆顶最大) ，并给出堆排序的过程。 【吉林大学 2007 二、5(4 分)】8 已知序列503，87，512 ，61，908，170，897，275，653，462)将其调整为堆(大堆顶，即 KiK2i，K iK2i+1

3、)。【中国海洋大学 2006 一、4(8 分)】9 给定关键字序列(20，18，9，86，72，12，27，40)。试将该序列建成小根堆。10 判断下面的每个结点序列是否表示一个堆，如果不是堆，请把它调整成堆。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 分)】11 全国有 10000 人参加物理竞赛，只录取成绩优异的前 10 名，并将他们从高分到低分输出。而对落选的其他考生，不需排出名次，问此种情况下，用何种排序方法速度最快?为什么 ?【北京邮电大学 199

4、6 一、3(4 分)】12 设有 n 个无序元素，按非递减次序排序，但只想得到前面长度为 k 的部分序列，其中 nk，最好采用什么排序方法? 为什么?如果有这样一个序列59，11 ，26 ，34，17，91 ，25)，得到的部分序列是 11，17，25)，对于该例使用所选择的方法实现时，共执行多少次比较?【东北大学 2002 一、4(3 分)】13 写出用堆排序算法对文件 F=(12，3，15，30，9，28)进行排序时，初始堆及以后每挑好一个元素重新调整后堆的状态，并指出这里的堆和败者树的一个主要区别。【东南大学 1998 二(8 分)】13 请回答下列关于堆(Heap)的一些问题。【清华大

5、学 2000 五(12 分)】14 堆的存储表示是顺序的，还是链接的?15 设有一个最小堆，即堆中任意结点的关键字均大于它的左子女和右子女的关键字。其具有最大值的元素可能在什么地方?16 对，1 个元素进行初始建堆的过程中，最多做多少次数据比较(不用大 0 表示法)?二、设计题17 设有一个数组中存放了一个无序的关键序列 K1、K 2、K n。现要求将 Kn 放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过 n。(注：用程序实现。)【南京航空航天大学 1997 六(12 分)】18 借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于 key的记录。

6、设此组记录存放于数组 r1h中。若查找成功，则输出该记录在 r 数组中的位置及其值，否则显示“not find” 信息。请编写出算法并简要说明算法思想。【北京邮电大学 1998 七(1 5 分)】19 编写非递归的快速排序算法。【中科院软件所 1997 三(10 分)】20 设有顺序放置的 n 个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红、白、蓝之一。要求重新安排这些砾石，使得所有红色砾石在前，所有白色砾石居中，所有蓝色砾石居后。重新安排时，对每粒砾石的颜色只能查看一次，并且只允许交换操作来调整砾石的位置。【上海大学 1999 二、2(18 分)】21 编写算法解决荷兰国旗问题，即将仅由红、

7、白、蓝三种颜色的条块序列，在O(n)时间内按红、白、蓝顺序排好。例：给定色彩条块序列蓝、白、红、白、蓝、红、白、白、红、蓝)则要求的结果为：红、红、红、白、白、白、白、蓝、蓝、蓝【东华大学 2003 五(15 分)】【浙江大学 2003 七(10 分)】22 对给定关键字序号 j(1jn)，要求在无序记录 A1n中找到关键字从小到大排在第 j 位上的记录，写一个算法利用快速排序的划分思想实现上述查找 (要求用最少的时间和最少的空间)。例如：给定无序关键字7，5，1，6，2，8，9，3)，当 j=4 时，找到的关键字应是 5。【中科院研究生院 2003 十二(15 分)】【武汉理工大学 2002

8、 四、3(353 分)】23 若待排序列用单链表存储，试给出其快速排序算法。【北京邮电大学 2000 七(15 分)】24 已知关键字序列(K 1,K2,K3,，K n-1)是大根堆。(1)试写出一算法将(K1,K2,K3,，K n-1，K n)调整为大根堆；(2)利用(1)的算法写一个建大根堆的算法。【中科院软件所 1999 七、2(7 分)】25 已知由 n 一 1 个关键字组成的序列(K 1,K2,K3Kn-1)是大顶堆，现在再增加一个关键字 Kn，要求将关键字序列(K 1,K2,K3,，K n-1，K n)重新调整为大顶堆。请完成以下要求： (1)编写满足上述要求的算法。 (2) 简述

9、你所编写的算法的基本思想。 (3)分析你所编写的算法的时间复杂度。 【南京航空航天大学 2006 7(5 分)】【江苏大学 2006 四、1(12 分) 】26 试设计一个 Heaplnsert(r，key)算法，将关键字 key 插入到堆 R 中去，并保证插入后 R 仍是堆。并分析你的算法的时间复杂性。【哈尔滨工业大学 2005 五、1(15分)】27 有关堆排序：(1)给出堆的定义及其数据结构定义；(2)给出堆排序算法的基本思想，并以图例予以说明(要求不少于 6 个待排序元素)；(3)用伪语言描述该算法；(4)给出算法在最坏情况下的时间复杂性分析。【中南大学 2005 五、1(20 分)】

10、28 设有一大批需实时处理的数据元素组成集合 S，实时处理开始后，每隔一极短的时间间隔便收到一个新的数据元素加入 S。现要求在每次接收一个新元素之前，找出 S 中现有的最小元素并将其输出(从 S 中删除)。试选择或构造一种适当的数据结构并设计一个算法，尽可能高效地完成上述任务(只要求用文字说明算法的基本设计思想)。【同济大学 2005 三、1(7 分)】【中国海洋大学 2004 七(20 分)】计算机专业基础综合数据结构（排序）历年真题试卷汇编 9 答案与解析一、综合题1 【正确答案】 在具有 n 个元素的集合中找第 k(1kn)个最小元素，应使用快速排序方法。其基本思想如下：设 n 个元素的

11、集合用一维数组表示，其第一个元素的下标为 1，最后一个元素的下标为 n。以第一个元素为“枢轴” ，经过快速排序的一次划分，找到“ 枢轴” 的位置 i，若 i=k，则该位置的元素即：为所求；若 ik，则在 1 至 i 一 1 间继续进行快速排序的划分；若 i58，46，55，18，56，因篇幅所限，建堆过程略。6 【正确答案】 堆排序过程。待排序元素在一维数组中，建成堆后，堆顶元素(下标 0)和最后一个元素( 下标 n 一 1，本例下标 7)交换。这时最后一个元素(本例 88)到位，不再参与以后的调堆。从堆顶调堆至堆底(下标 n 一 2)，又建成大顶堆。再将堆顶元素和最后一个元素(下标 n 一

12、2)交换，得到次大元素 67。如此下去，直至堆中只剩一个元素，得到元素的升序序列。7 【正确答案】 结果的大根堆为：85，79，50，56，32，41，8。建堆过程可以描述如下。首先按序列顺序画 n(待排序元素个数)个结点的完全二叉树。定义叶子结点已经是堆。从最后一个分支结点(下标 n21，第 1 个元素下标 0)开始调堆，直至最后将第 1 个元素调整到符合堆的定义。结合本例说明如下：叶子56，32，41 和 85 已经是堆，最后一个分支结点元素 8 不符合堆的定义，将 85 与8 交换。元素 79 符合堆的定义，不需调整。元素 50 不符合堆的定义，沿元素大的右分支向下筛选(因为建大根堆)，

13、将 85 调到堆顶。将 50 放在原 85 的位置已满足堆的定义，否则还要继续向下筛选，直至满足堆的定义找到 50 的位置。8 【正确答案】 结果的大堆为：908，653，897，503，462，170，512，275，61，879 【正确答案】 小根堆为：9，1 8，12，40，72，20，27，8610 【正确答案】 是堆 不是堆，调成大堆100，90，80，25，85，75，60，20，10，70，65，5011 【正确答案】 在内部排序方法中，一趟排序后只有简单选择排序和冒泡排序可以选出一个最大(或最小) 元素，并加入已有的有序子序列中，但要比较 n 一 1 次。选次大元素要再比较 n

14、 一 2 次，其时间复杂度是 O(n2)。从 10 000 个元素中选 10个元素不能使用这种方法。而插入排序及希尔排序、快速排序、归并排序、基数排序等时间性能好的排序，都要等到最后才能确定各元素位置。只有堆排序，在未结束全部排序前，可以有部分排序结果。建立堆后，堆顶元素就是最大(或最小，视大堆或小堆而定)元素，然后，调堆又选出次大(小)元素。凡要求在 n 个元素中选出k(k2)个最大(或最小)元素，一般均使用堆排序。因为堆排序建堆比较次数至多不超过 4n，对深度为 k 的堆，在调堆算法中进行的关键字的比较次数至多为 2(k-1)次，且辅助空间为 O(1)。因快速排序会出现最差情况，时间复杂度

15、为 O(n2)，所以，这里不采用快速排序。12 【正确答案】 从序列59，11，26，34，17，91，25 得到11，17，25共用 14次比较。其中建堆输出 11 比较了 8 次，调堆输出 1 7 和 25 各需要比较 4 次和 2 次：上面已经说明，堆排序适合数据量较大的情况，题中 7 个数据反映不出堆排序的优越性。13 【正确答案】 对具体例子的手工堆排序略。堆与败者树的区别：堆是 n 个元素的序列，在向量中存储，具有如下性质：由于堆的这个性质中下标 i 和2i、2i+1 的关系，恰好和完全二叉树中第 i 个结点和其子树结点的序号间的关系一致，所以堆可以看作是 n 个结点的完全二叉树。

16、而败者树是由参加比赛的 n 个元素作叶子结点而得到的完全二叉树。每个非叶(双亲)结点中存放的是两个子结点中的败者数据，而让胜者去参加更高一级的比赛。另外，还需增加一个结点，即结点0，存放比赛的全局获胜者。14 【正确答案】 堆的存储是顺序的。15 【正确答案】 最大值元素一定是叶子结点，可以在n2+1n 间的任何位置上。说明：原题“ 设有一个最小堆，即堆中任意结点的关键码均大于 它的左子女和右子女的关键码。其具有最大值的元素可能在什么地方”的叙述有误，应将“ 大于”改为“小于”。最大值元素一定是叶子结点。16 【正确答案】 在建含有 n 个元素、深度为 h 的堆时，其比较次数不超过 4n，推导

17、如下：由于第 i 层上的结点数至多是 2r-1，以它为根的二叉树的深度为 h 一 i+1，则调用n 2次筛选算法时总共进行的关键字比较次数不超过下式之值：二、设计题17 【正确答案】 以 Kn 为枢轴的一趟快速排序。暂存 Kn，先 i(初值 1)从前向后，再 i(初值 n1)从后向前地和枢轴 Kn 比较，寻找 Kn 的最终位置。请参见第 17 题。18 【正确答案】 可把待查记录看作枢轴，先由后向前依次比较，若小于枢轴，则从前向后，直到查找成功 返回其位置或失败返回 0 为止。19 【正确答案】 快速排序的非递归算法的核心语句段如下：typedef structint low，high；)no

18、denode sn+1；int quickpass(rectype r，int，int)； 函数声明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 ； 枢轴右边进栈20 【正确答案】 一趟快速排序可以将序列划分成两部分，这里要求一趟排序将序列分成三部分。设 3 个指针 i、j 和 k，将 r1j 一 1作为红色，r，k-1为

19、白色，rk.n为蓝色。为方便处理，将三种砾石的颜色用整数 1、2 和 3 表示。核心语句段如下：int i=1，j=1，k=n，temp；while(jnext； p 为工作指针while(flag) 进行一趟快速排序， flag 是结束排序的标志，初值为 0if(p 一datadata) 结点插入前一半endl 一next=p-next； 保留后继结点if(p：=end)flag=0； 一趟快速排序结束if(start=end1)end0=p； end0 是遍历遇到的第一个小于枢轴的结点，将为前半的尾结点pnext=start； start=p ； 修改左半部链表头指针p=end1 一nex

20、t； 恢复当前待处理结点else 处理右半部链表if(p=end)flag=0； 已到链表尾endl 一next=p ；endlip； endl 和 P 是前驱和后继关系p=p 一next； else whileLinkQuickSort(start，end0)； 对枢轴元素最终位置前的单链表快速排序LinkQuicksort(start1 一next，end1) ； 对枢轴元素最终位置后的单链表快速排序24 【正确答案】 (1)因为前 n 一 1 个元素已经是堆，所以从第 n 个记录开始依次与其双亲(n 2)比较，若大于双亲则交换，继而与其双亲的双亲比较，直至满足堆的定义(最多类推到根) 。

21、核心语句段如下：j=n； R0=Rj；for(i=n2；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；i=1ji=i12)if(R0keyRikey)Rj=Ri; j=i;else break；Rj=R0;(2)void HeapBuilder(RecType R，int n)for(i=2；i0;i-) Sift(R，i，n)；for(i=n； i1； i 一一)(R1Ri；Sift(R， 1，i 一 1)；)for HeapSort28 【正确答案】 这是堆排序问题，先将集合 S 中的元素建成小堆，并输出堆顶最小元素。再将每隔一极短的时间间隔收到的新数据元素放到堆顶，进行调堆，再输出堆顶元素，如此反复进行。请参考上面第 34 题堆排序算法。