【考研类试卷】内部排序及答案解析.doc

《【考研类试卷】内部排序及答案解析.doc》由会员分享，可在线阅读，更多相关《【考研类试卷】内部排序及答案解析.doc（13页珍藏版）》请在麦多课文档分享上搜索。

1、内部排序及答案解析(总分：80.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.下列 4 个序列中，哪一个是堆( )。（分数：2.00）_2.对序列 15，9，7，8，20，-1，4 进行排序，进行一趟后数据的排列变为 4，9，-1，8，20，7，15)；则采用的是( )排序。（分数：2.00）A.选择B.快速C.希尔D.冒泡3.对序列 15，9，7，8，20，-1，4，用希尔排序方法排序，经一趟后序列变为 15，-1，4，8，20，9，7则该次采用的增量是( )。（分数：2.00）A.1B.4C.3D.24.排序方法的稳定性是指( )。（分数：2.00）A.该

2、排序算法不允许有相同的关键字记录B.该排序算法允许有相同的关键字记录C.平均时间为 o(n log n)的排序方法D.以上都不对5.设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有 5 个长度为 2 的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为( )。（分数：2.00）_6.二路归并排序的时间复杂度为( )。（分数：2.00）A.O(n)B.O(n2)C.O(nlog2n)D.O(log2n)7.设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量 d=4 的一趟希尔排序结束后前 4

3、条记录关键字为( )。（分数：2.00）A.40，50，20，95B.15，40，60，20C.15，20，40，45D.45，40，15，208.假定对元素序列(7，3，5，9，1，12)进行堆排序，并且采用小根堆，则由初始数据构成的初始堆为( )。（分数：2.00）A.1，3，5，7，9，12B.1，3，5，9，7，12C.1，5，3，7，9，12D.1，5，3，9，12，79.设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是( )。（分数：2.00）A.F，H，C，D，P，A，M，Q，R，S，Y，XB.P，A，C，S

4、，Q，D，F，X，R，H，M，YC.A，D，C，R，F，Q，M，S，Y，P，H，XD.H，C，Q，P，A，M，S，R，D，F，X，Y10.用直接插入排序方法对下面 4 个序列进行排序(由小到大)，元素比较次数最少的是( )。（分数：2.00）A.94，32，40，90，80，46，21，69B.32，40，21，4669，94，90。80C.21，32，46，40，80，69，90，94D.90，69，80，46，21，32，94，4011.若用冒泡排序对关键字序列 18，16，14，12，10，8，进行从小到大的排序，所需进行的关键字比较总次数是( )。（分数：2.00）_12.一组记录的关

5、键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为( )。（分数：2.00）_13.假定一个初始堆为(1，5，3，9，12，7，15，10)，则进行第一趟堆排序后得到的结果为( )。（分数：2.00）A.3，5，7，9，12，10，15，1B.3，5，9，7，12，10，1 5，1C.3，7，5，9，12，10，15，1D.3，5，7，12，9，10，15，114.数据序列(8，9，10，4，5，6，20，1，2)只能是下列排序算法中( )的两趟排序后的结果。（分数：2.00）_15.对一组数据(84，47，25，15，21)排序，数据的

6、排列次序在排序的过程中的变化为( )。(1)84 47 25 15 21 (2)1 5 47 25 84 21(3)15 21 25 84 47 (4)1 5 21 25 47 84则采用的排序是( )。（分数：2.00）_二、综合应用题(总题数：5，分数：50.00)16.对于一个堆栈，若其入栈序列为 12，3，n，不同的出入栈操作将产生不同的出栈序列。其出栈序列的个数正好等于结点个数为 n 的二叉树的个数，且与不同形态的二叉树一一对应。请简要叙述一种从堆栈输入(固定为 1，2，3n)/输出序列对应一种二叉树形态的方法，并以入栈序列 1，2，3(即 n=3)为例加以说明。（分数：10.00）

7、_17.给出一组关键字 T=(12，2，1630，828，4，10，20，6，18)，写出用下列算法从小到大排序时第一趟结束时的序列：(1)希尔排序(第一趟排序的增量为 5)；(2)快速排序选第一个记录为枢轴(分隔)；(3)链式基数排序(基数为 10)。（分数：10.00）_18.已知待排序的序列为(503，87，512，61908，170，897，275，653，462)，试完成下列各题。(1)根据以上序列建立一个堆(画出第一步和最后堆的结果图)，希望先输出最小值。(2)输出最小值后，如何得到次小值(并画出相应结果图)。（分数：10.00）_19.有 n 个记录存储在带头结点的双向链表中，现

8、用双向冒泡排序法对其按升序进行排序，请写出这种排序的算法(注：双向冒泡排序即相邻两趟排序向相反方向起泡)。（分数：10.00）_20.编写算法实现以被分类序列中所有元素的平均值为界值的快速分类方法。（分数：10.00）_内部排序答案解析(总分：80.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.下列 4 个序列中，哪一个是堆( )。（分数：2.00）_解析：堆排序是另一种基于选择的排序方法。n 个元素的序列k 1，k 2，k 3，.k n，当且仅当满足以下关系时，称之为堆：ki=k 2i 或者： k i=k 2i。ki=k 2i+1 ki=k 2i+1其中 i

9、=1，2，n/2。若将同以上序列对应的一维数组看成是一棵完全二叉树，则堆的含义表明：该完全二叉树的所有非终端结点均不大于(或不小于)其左、右孩子结点的值。由此，若k1，k2，kn)是堆，则堆顶元素(或完全二叉树的根结点)必定是该序列 n 个元素中的最小值(或者最大值)。若将堆看成是一棵以 k1为根的完全二叉树，则这棵完全二叉树中的每个非终端结点的值均不大于(或不小于)其左、右孩子结点的值。由此可以看出，若一棵完全二叉树是堆，则根结点一定是这 n 个结点中的最小者(或最大者)。下图给出了两个堆的示例。*从堆的定义可以看出，若将堆用一棵完全二叉树表示则根结点是当前堆中所有结点的最小者(或最大者)。

10、堆排序的基本思想是：首先将待排序的记录序列构造一个堆，此时，选出了堆中所有记录的最小者或最大者，然后将它从堆中移走，并将剩余的记录再调整成堆，这样又找出了次小(或次大)的记录，以此类推，直到堆中只有一个记录为止，每个记录出堆的顺序就是一个有序序列。假设当前要进行筛选的结点编号为 k，堆中最后一个结点的编号为 m，且 ak+1至 am之间的结点都已经满足堆的条件，则调整过程可以描述为：(1)设置两个指针 i 和 j，i 指向当前(要筛选)的结点：|=k；j 指向当前结点的左孩子结点：j=2*i；(2)比较当前结点的左右孩子的关键字值，并用 j 指向关键字值较大的孩子结点。if(jm&ajkeya

11、j+1)key)j+；(3)用当前结点的关键字与 j 所指向的结点关键字值进行比较，根据比较结果采取相应的操作，即结束筛选或交换结点内容并继续进行筛选。实现这个操作的语句为：if(aikeyajkey)break； 结束筛选操作elsetemp=ai；ai=aj；aj=temp； 交换结点内容i=j；j=2*i； 准备继续筛选可以将交换改进为：if(aikeyajkey)break：elseai=aj；i=j；j=2*i；堆排序的筛选算法：void sift(DataType a，int k，int m) i=k；j=2*i；temp=ai；while(j=m)if(jm&ajkeyraj+1

12、key)j+；if(aikeyajkey)break：elseai=aj；i=j；j=2*i；ai=temp；堆排序完整的算法为：void heapsort(DataType a，int n)h=n/2； 最后一个非终端结点的编号for(i=h；i=1；i) 初建堆，从最后一个非终端结点至根结点sift(a，i，n)；for(i=n；i1；i) 重复执行移走堆顶结点及重建堆的操作temp=al；al=aiai=temp；sift(a，1，i-1)；2.对序列 15，9，7，8，20，-1，4 进行排序，进行一趟后数据的排列变为 4，9，-1，8，20，7，15)；则采用的是( )排序。（分数：

13、2.00）A.选择B.快速C.希尔 D.冒泡解析：希尔排序又称“缩小增量排序”，是一种改进的插入排序，在时间效率上有了较大的改进。对直接插入排序来说比较的步长为 1。这种情况下，如果较小的数在序列的较后面部分，则需要一步一步地向前移动，无疑是比较慢的。如果采用步长1 的方法，则可以使较小的数向前推进是“跳跃式”进行，故可以提高排序效率。方法：将整个序列分成若干子序列，对各个子序列进行直接插入排序，得到一趟希尔排序序列；然后缩短步长，重复以上动作，直到步长为 1。具体步骤如下：(1)先取一正整数 d(dn，一般可取 d=*)把所有距离为 d 的倍数的记录编在一组，组成一个子序列，这样将整个待排序

14、序列分成若干组；(2)在各个子序列中进行直接插入排序；(3)取一个新的 d(比原来的要小，一般取原来的 1/2)，(1)、(2)直到 d=1 为止(此时，整个序列变成直接插入排序)。例如：利用希尔排序对下序列进行排序。(72，73，71，23，94，16，15，68)，n=8过程：1第一次分组，取 d=*=4，则对序列分组为：*对每个子序列直接插入排序得(4 组)：72 16 1 5 23 94 73 71 682第二次分组，取 d=2(原来的一半)，对序列分组为：*对每个子序列直接插入排序得(2 组)：15 16 71 23 72 68 94 733第三次分组，取 d=1(原来的一半)，序列

15、为一组，直接插入排序得：15 16 23 68 71 72 73 94排序完成。说明：步长的选择是迄今为止还没有完全解决的。该算法的时间复杂度 O(n。)，是不稳定排序(因为存在着跳跃)。3.对序列 15，9，7，8，20，-1，4，用希尔排序方法排序，经一趟后序列变为 15，-1，4，8，20，9，7则该次采用的增量是( )。（分数：2.00）A.1B.4 C.3D.2解析：解析见 1。4.排序方法的稳定性是指( )。（分数：2.00）A.该排序算法不允许有相同的关键字记录B.该排序算法允许有相同的关键字记录C.平均时间为 o(n log n)的排序方法D.以上都不对 解析：待排序的文件中，

16、若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。注意：排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。下表列出了各种内部排序算法的平均时间、最坏情况、辅助空间、稳定性。排序方法 平均时间 最坏情况 辅助空间 稳定性直接插入排序 O(n 2) O(n 2) O(1) 稳定拆半插入排序 O(n 2) O(n 2) O(1) 稳定起泡排序 O(n 2) O(n 2) O(1) 稳定直

17、接选择排序 O(n 2) O(n 2) O(1) 不稳定希尔排序 O(n 1.3) O(n 1.3) O(1) 不稳定快速排序 O(nlog 2n) O(n 2) O(log 2n) 不稳定堆排序 O(nlog 2n) O(nlog 2n) O(1) 不稳定2路归并排序 O(nlog 2n) O(nlog 2n) O(n) 稳定基数排序 O(d*(rd+n) O(d*(rd+n) O(rd) 稳定 5.设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有 5 个长度为 2 的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为( )

18、。（分数：2.00）_解析：归并排序是一种另一类排序方法。所谓归并是指将两个或两个以上的有序表合并成一个新的有序表。归并排序的基本思想是将一个具有 n 个待排序记录的序列看成是 n 个长度为 1 的有序序列，然后进行两两归并，得到*个长度为 2 的有序序列，再进行两两归并，得到 n/4 个长度为 4 的有序序列，如此重复，直至得到一个长度为 n 的有序序列为止。假设记录序列被存储在一维数组 a 中，且 asam和 am+1at已经分别有序，现将它们合并为一个有序段，并存入数组 a1 中的 a1sa1t之间。2路归并排序的算法如下：void merge(DataType a，DataType a

19、l，int s，int m，int t)/asm和 am+1at已经分别有序，将它们归并至 a1sa 1t中k=s；i=s；j=m+1；whiie(i=m&j=t) if(ai.key=aj.key)alk+=ai+；else a1k+=aj+；if(i=m) 将剩余记录复制到数组 a1中while(i=m) a 1k+=ai+；if(j=t)while(j=t) a 1k+=aj+；6.二路归并排序的时间复杂度为( )。（分数：2.00）A.O(n)B.O(n2)C.O(nlog2n) D.O(log2n)解析：解析见 15。7.设一组初始记录关键字序列为(50，40，95，20，15，70

20、，60，45)，则以增量 d=4 的一趟希尔排序结束后前 4 条记录关键字为( )。（分数：2.00）A.40，50，20，95B.15，40，60，20 C.15，20，40，45D.45，40，15，20解析：解析见 1。8.假定对元素序列(7，3，5，9，1，12)进行堆排序，并且采用小根堆，则由初始数据构成的初始堆为( )。（分数：2.00）A.1，3，5，7，9，12B.1，3，5，9，7，12 C.1，5，3，7，9，12D.1，5，3，9，12，7解析：解析见 2。9.设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后

21、的结果是( )。（分数：2.00）A.F，H，C，D，P，A，M，Q，R，S，Y，XB.P，A，C，S，Q，D，F，X，R，H，M，YC.A，D，C，R，F，Q，M，S，Y，P，H，XD.H，C，Q，P，A，M，S，R，D，F，X，Y 解析：解析见 6。10.用直接插入排序方法对下面 4 个序列进行排序(由小到大)，元素比较次数最少的是( )。（分数：2.00）A.94，32，40，90，80，46，21，69B.32，40，21，4669，94，90。80C.21，32，46，40，80，69，90，94 D.90，69，80，46，21，32，94，40解析：解析见 4。11.若用冒泡排序

22、对关键字序列 18，16，14，12，10，8，进行从小到大的排序，所需进行的关键字比较总次数是( )。（分数：2.00）_解析：(1)算法基本思想：起泡排序是交换排序中一种简单的排序方法。它的基本思想是对所有相邻记录的关键字值进行比效，如果是逆序(ajaj+1)，则将其交换，最终达到有序化。其处理过程为：将整个待排序的记录序列划分成有序区和无序区，初始状态有序区为空，无序区包括所有待排序的记录。对无序区从前向后依次将相邻记录的关键字进行比较，若逆序则将其交换，从而使得关键字值小的记录向上“飘浮”(左移)，关键字值大的记录好像石块，向下“堕落”(右移)。每经过一趟冒泡排序，都使无序区中关键字值

23、最大的记录进入有序区，对于由 n 个记录组成的记录序列，最多经过 n-1 趟冒泡排序，就可以将这 n 个记录重新按关键字顺序排列。(2)起泡排序算法：原始的冒泡排序算法：对由 n 个记录组成的记录序列，最多经过(n-1)趟冒泡排序，就可以使记录序列成为有序序列，第一趟定位第 n 个记录，此时有序区只有一个记录；第二趟定位第 n=1 个记录，此时有序区有两个记录；以此类推，算法框架为：(假设用数组 a 存储待排序记录)void BubbieSortl(DataType a，int n)for(i=n；i1；i)for(j=1；j=i-l；J+)if(ajkeyaj+1.key)temp=aj；a

24、j=aj+1；aj+1=temp；改进的冒泡排序算法：在冒泡排序过程中，一旦发现某一趟没有进行交换操作，就表明此时待排序记录序列已经成为有序序列，冒泡排序再进行下去已经没有必要，应立即结束排序过程。void BubbleSort2(DataType a，int n)for(i=n；i1；i)exchange=0；for(j=1；j=i-1；j+)if(ajkeyaj+1.key)temp=aj；aj=aj+1；aj+1=temp；exchange=1；if(exchange=0)break；进一步地改进冒泡排序算法：在算法给出的冒泡排序算法的基础上，如果我们同时记录第 i 趟冒泡排序中最后一次

25、发生交换操作的位置 m(m一 n-i)，就会发现从此位置以后的记录均已经有序，即无序区范围缩小在 a1am之间，所以在进行下一趟排序操作时，就不必考虑 am+1an范围内的记录了，而只在 a1am范围内进行。void BubbleSort3(DataType a，int n)last=n-1：for(i-n；i1；i) exchange=0；m=last； 初始将最后进行记录交换的位置设置成 i-1for(j=1；j=m；j+)if(ajkeyaj+1.key)temp=aj；aj=aj+1；aj-i=temp；exchange=1：last=j； 记录每一次发生记录交换的位置)if(exch

26、ange=-0)break：12.一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为( )。（分数：2.00）_解析：快速排序是对冒泡排序的一种改进，其基本思想是：通过一趟排序将待排序的记录分成独立的两部分，其中一部分记录的关键字比另一部分的关键字小。然后对这两部分再继续排序，一直达到整个序列有序。设待排序序列为L.r1，L.r2，L.rn)，首先任意选取一个记录(通常选择第一个记录 L.r1)作为支点(pivot)，然后按照下述原则排列其余记录：将所有关键字比 L.r1key 小的记录都安排在它的位置之前，将所有关键字比 L

27、.r1.key 大的记录都安排在它的位置之后。可以发现，在安置的过程中，L.r1的确切位置将被最终确定。设该支点(pivot)最后确定的位置为 i，则将序列分割为左右两部分。这个过程称为一趟快速排序。设待排序序列用数组 elowhigh保存。设置两个指针 low 和 high，分别指向数组的开始位置和终止位置。设支点记录为 elow，并将之暂存于 t。首先，从 high 的位置向前搜索，找到第一个小于 t 的记录，将这个记录和 elow的值交换；然后，从low 所指向的位置向后搜索，找到第一个值大于 t 的记录，将这个记录和 ehigh的值交换。重复以上步骤，直到 low=high。完成一趟排

28、序，low(或者 high)指向的位置就是第一个元素的确切位置(从两边向中间“夹挤”)。第一趟完成后，确定了第一个元素的确切位置，同时生成了两个子序列，然后再对这两个序列使用同样的办法，最终实现整个序列的有序。举例：利用快速排序法对以下序列进行排序：(49，38，65，97，76，13，27，49)过程如下：初始状态：*high 向左移动(high)，直到找到小于 t(49)的关键字 27，将 27 的值赋给 elow，如下：*接着 low 开始向右移动(low+)，直到找到大于 t(49)的关键字 65，将 65 的值赋给 ehigh，如下：high 继续左移(high)，直到找到一个小于

29、t 的数 13，将之赋给 elow，如下：*low 继续右移(low+)，直到找到大于 t(49)的关键字 97，将之赋给 ehigh，如下：*high 继续左移(high)，没有找到比 t(49)还小的数，但是由于出现了 high=low 的情况，结束左移。如下：*此时 low(或者 high)指向的位置就是第一个元素的确定位置：elow=t；经过以上一趟快速排序，可将原序列分为两个序列，同时确定关键字 49 的确切位置，如下：27，38，13 49 76，97，65，49下面再分别对两个子类进行快速排序，得最终结果：13)2738 49 49， 65 76 9749 6513.假定一个初始

30、堆为(1，5，3，9，12，7，15，10)，则进行第一趟堆排序后得到的结果为( )。（分数：2.00）A.3，5，7，9，12，10，15，1 B.3，5，9，7，12，10，1 5，1C.3，7，5，9，12，10，15，1D.3，5，7，12，9，10，15，1解析：解析见 2。14.数据序列(8，9，10，4，5，6，20，1，2)只能是下列排序算法中( )的两趟排序后的结果。（分数：2.00）_解析：直接插入排序是一种最基本的排序算法，基本操作为：将一个记录插入到一个已经排好序的有序表中，从而得到一个新的、长度增 1 的有序表。一般情况下，第 i 趟的操作为：在含有 i=1 个记录的

31、有序子序列 r1i-1中插入一个新记录 ri，变成含有 i 个记录的有序序列 rLli。设置 r0为空值，从 r1开始保存信息，可首先将待插入的记录 ri复制到 r0中，如下所示：*可把 r0看成是 ri的备份，以后从 r1ri-1查找插入位置时可直接同 r0比较，而且 ri也可被覆盖了。因为 ri复制到 r0后，可认为已经空出了 ri。考虑从后向前比较，只要 ri-1ri，则 ri的位置不必改变，否则(即 ri-1ri)，则将 ri-1移动到 ri处，然后再比较 ri-2和 r0，依次等等。当最后找到一个比 r0小的关键字时，将 r0复制到此关键字后面的一个位置，结束。具体算法为：void

32、InsertSort(SqList&L)for(i=2；i=L.length；+i)第一个元素认为本身有序，所以从第二个元素开始即可if(L.ri：keyL.ri-1key)当 ri小于 ri-1时，需排序，否则无需排序L.r0=L.rLi；复制 L.ri至 L.r0，保证下面的 for 循环肯定能正常结束foi(j=i-1；L.r0.keyrL.rj.keyr；j)L.rj+1=L.rj；记录后移L.rj+1=L.r0；插入到第一个小于 L.r0的元素 L.rj的后面15.对一组数据(84，47，25，15，21)排序，数据的排列次序在排序的过程中的变化为( )。(1)84 47 25 15

33、 21 (2)1 5 47 25 84 21(3)15 21 25 84 47 (4)1 5 21 25 47 84则采用的排序是( )。（分数：2.00）_解析：简单选择排序的基本思想是：每一趟在 n-i+1(i=1，2，3，n-1)个记录中选取关键字最小的记录作为有序序列中的第 i 个记录。它的具体实现过程为：(1)将整个记录序列划分为有序区域和无序区域，有序区域位于最左端，无序区域位于右端，初始状态有序区域为空，无序区域含有待排序的所有 n 个记录。(2)设置一个整型变量 index，用于记录在一趟的比较过程中，当前关键字值最小的记录位置。开始将它设定为当前无序区域的第一个位置，即假设这

34、个位置的关键字最小，然后用它与无序区域中其他记录进行比较，若发现有比它的关键字还小的记录，就将 index 改为这个新的最小记录位置，随后再用 aindex.key 与后面的记录进行比较，并根据比较结果，随时修改 index 的值，一趟结束后 index 中保留的就是本趟选择的关键字最小的记录位置。(3)将 index 位置的记录交换到无序区域的第一个位置，使得有序区域扩展了一个记录，而无序区域减少了一个记录。不断重复(2)、(3)，直到无序区域剩下一个记录为止。此时所有的记录已经按关键字从小到大的顺序排列就位。算法如下：void selecsort(DataType a，int n)for(

35、i=1；in；i+) 对 n 个记录进行 n-1 趟的简单选择排序index=i； 初始化第 i 趟简单选择排序的最小记录指针for(j=i+1；j=n；j+)搜索关键字最小的记录位置if(ajkeyai.key)index=j；if(index!=i)temp=ai；ai=aindex；aindex=temp；二、综合应用题(总题数：5，分数：50.00)16.对于一个堆栈，若其入栈序列为 12，3，n，不同的出入栈操作将产生不同的出栈序列。其出栈序列的个数正好等于结点个数为 n 的二叉树的个数，且与不同形态的二叉树一一对应。请简要叙述一种从堆栈输入(固定为 1，2，3n)/输出序列对应一种

36、二叉树形态的方法，并以入栈序列 1，2，3(即 n=3)为例加以说明。（分数：10.00）_正确答案：(由于二叉树前序遍历序列和中序遍历序列可唯一确定一棵二叉树，因此，若入栈序列为1，2，3，n，相当于前序遍历序列是 1，2，3，n，出栈序列就是该前序遍历对应的二叉树的中序序列的数目。因为中序遍历的实质就是一个结点进栈和出栈的过程，所以二叉树的形态确定了结点进栈和出栈的顺序，也就确定了结点的中序序列。下图以入栈序列 1，2，3，(解释为二叉树的前序序列)为例，说明不同形态的二叉树在中序遍历时栈的状态和访问结点次序的关系：*)解析：17.给出一组关键字 T=(12，2，1630，828，4，10

37、，20，6，18)，写出用下列算法从小到大排序时第一趟结束时的序列：(1)希尔排序(第一趟排序的增量为 5)；(2)快速排序选第一个记录为枢轴(分隔)；(3)链式基数排序(基数为 10)。（分数：10.00）_正确答案：(1)一趟希尔排序：12，2，10，20，6，18，4，16，30，8，28(D=5)(2)一趟快速排序：6，2，10，4，8，12，28，30，20，16，18(3)链式基数排序*)解析：18.已知待排序的序列为(503，87，512，61908，170，897，275，653，462)，试完成下列各题。(1)根据以上序列建立一个堆(画出第一步和最后堆的结果图)，希望先输出最

38、小值。(2)输出最小值后，如何得到次小值(并画出相应结果图)。（分数：10.00）_正确答案：(1)建小堆*(2)求次小值*)解析：19.有 n 个记录存储在带头结点的双向链表中，现用双向冒泡排序法对其按升序进行排序，请写出这种排序的算法(注：双向冒泡排序即相邻两趟排序向相反方向起泡)。（分数：10.00）_解析：20.编写算法实现以被分类序列中所有元素的平均值为界值的快速分类方法。（分数：10.00）_正确答案：(取平均值，将所有关键字与平均值进行比较，若小于平均值则属于左半部；否则就属于右半部。int Partition(RecType r，int l，h)int i=l，j=h，avg=0；for(；i=h；i+)avg+=Ri.key；i=l：avg=avg/(h-1+1)；求得平均值while(ij)while(ij&Rjkey=avg)大于平均值j；if(ij)Ri=Rj；while(ij&Rikey=avg)小于平均值i+：if(ij)Rj=Ri；if(Rikey=avg)return i；elsereturn i-1；void quicksort(RecType R，int S，T)；if(ST)k=partition(R，S，T)；quicksort(R，S，k)；quicksort(R，k+1，T)；)解析：