【考研类试卷】计算机学科专业基础综合数据结构-内部排序及答案解析.doc

《【考研类试卷】计算机学科专业基础综合数据结构-内部排序及答案解析.doc》由会员分享，可在线阅读，更多相关《【考研类试卷】计算机学科专业基础综合数据结构-内部排序及答案解析.doc（12页珍藏版）》请在麦多课文档分享上搜索。

1、计算机学科专业基础综合数据结构-内部排序及答案解析(总分：80.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.对序列15，9，7，8，20，-1，4进行排序，进行一趟后数据的排列变为4，9，-1，8，20，7，15)；则采用的是 _ 排序。（分数：2.00）A.选择B.快速C.希尔D.冒泡2.下列 4个序列中，哪一个是堆 _ 。（分数：2.00）A.75，65，30，15，25，45，20，10B.75，65，45，10，30，25，20，15C.75，45，65，30，15，25，20，10D.75，45，65，10，25，30，20，153.一组记录的关键

2、码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为 _ 。（分数：2.00）A.(38，40，46，56，79，84)B.(40，38，46，79，56，84)C.(40，38，46，56，79，84)D.(40，38，46，84，56，79)4.数据序列(8，9，10，4，5，6，20，1，2)只能是下列排序算法中 _ 的两趟排序后的结果。（分数：2.00）A.选择排序B.冒泡排序C.插入排序D.堆排序5.对一组数据(84，47，25，15，21)排序，数据的排列次序在排序的过程中的变化为 _ 。 (1)84 47 25 15 21 (2

3、)1 5 47 25 84 21 (3)15 21 25 84 47 (4)1 5 21 25 47 84 则采用的排序是 _ 。（分数：2.00）A.选择B.冒泡C.快速D.插入6.若用冒泡排序对关键字序列18，16，14，12，10，8，进行从小到大的排序，所需进行的关键字比较总次数是 _ 。（分数：2.00）A.10B.15C.21D.347.设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有 5个长度为 2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为 _ 。（分数：2.00）A.15，25，35，50，20，40

4、，80，85，3670B.15，25，35，50，80，20，85，40，70，36C.15，25，35，50，80，85，20，36，40，70D.15，25，35，50，80，20，36，40，70，858.假定一个初始堆为(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，19.设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序

5、结束后的结果是 _ 。（分数：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，Y10.设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量 d=4的一趟希尔排序结束后前 4条记录关键字为 _ 。（分数：2.00）A.40，50，20，95B.15，40，60，20C.15，20，40，45D.45，40，15，2011.假定对元素序列(7，3，5，9，1，12)进行堆排序，并且采用小根堆，则由初始数据构

6、成的初始堆为 _ 。（分数：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，712.二路归并排序的时间复杂度为 _ 。 A.O(n) B.O(n2) C.O(nlog2n) D.O(log2n)（分数：2.00）A.B.C.D.13.用直接插入排序方法对下面 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

7、，4014.对序列15，9，7，8，20，-1，4，用希尔排序方法排序，经一趟后序列变为15，-1，4，8，20，9，7则该次采用的增量是 _ 。（分数：2.00）A.1B.4C.3D.215.排序方法的稳定性是指 _ 。（分数：2.00）A.该排序算法不允许有相同的关键字记录B.该排序算法允许有相同的关键字记录C.平均时间为 o(n log n)的排序方法D.以上都不对二、综合应用题(总题数：5，分数：50.00)16.对于一个堆栈，若其入栈序列为 12，3，n，不同的出入栈操作将产生不同的出栈序列。其出栈序列的个数正好等于结点个数为 n的二叉树的个数，且与不同形态的二叉树一一对应。请简要叙

8、述一种从堆栈输入(固定为 1，2，3n)/输出序列对应一种二叉树形态的方法，并以入栈序列 1，2，3(即 n=3)为例加以说明。 （分数：10.00）_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)根据以上序列建立一个堆(画出第一步和最后

9、堆的结果图)，希望先输出最小值。 (2)输出最小值后，如何得到次小值(并画出相应结果图)。 （分数：10.00）_19.有 n个记录存储在带头结点的双向链表中，现用双向冒泡排序法对其按升序进行排序，请写出这种排序的算法(注：双向冒泡排序即相邻两趟排序向相反方向起泡)。 （分数：10.00）_20.编写算法实现以被分类序列中所有元素的平均值为界值的快速分类方法。 （分数：10.00）_计算机学科专业基础综合数据结构-内部排序答案解析(总分：80.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.对序列15，9，7，8，20，-1，4进行排序，进行一趟后数据的排列变为

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

11、把所有距离为 d的倍数的记录编在一组，组成一个子序列，这样将整个待排序序列分成若干组； (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 68 2第二次分组，取 d=2(原来的一半)，对序列分组为： 2.下列 4个序列中，哪一个是堆 _ 。（分数

12、：2.00）A.75，65，30，15，25，45，20，10B.75，65，45，10，30，25，20，15C.75，45，65，30，15，25，20，10 D.75，45，65，10，25，30，20，15解析：堆排序是另一种基于选择的排序方法。n 个元素的序列k 1 ，k 2 ，k 3 ，.k n ，当且仅当满足以下关系时，称之为堆： k i =k 2i 或者： k i =k 2i 。 k i =k 2i+1 k i =k 2i+1 其中 i=1，2，n/2。 若将同以上序列对应的一维数组看成是一棵完全二叉树，则堆的含义表明：该完全二叉树的所有非终端结点均不大于(或不小于)其左、右孩

13、子结点的值。由此，若k1，k2，kn)是堆，则堆顶元素(或完全二叉树的根结点)必定是该序列 n个元素中的最小值(或者最大值)。 若将堆看成是一棵以 k 1 为根的完全二叉树，则这棵完全二叉树中的每个非终端结点的值均不大于(或不小于)其左、右孩子结点的值。由此可以看出，若一棵完全二叉树是堆，则根结点一定是这 n个结点中的最小者(或最大者)。下图给出了两个堆的示例。 3.一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为 _ 。（分数：2.00）A.(38，40，46，56，79，84)B.(40，38，46，79，56，84)C

14、.(40，38，46，56，79，84) D.(40，38，46，84，56，79)解析：快速排序是对冒泡排序的一种改进，其基本思想是：通过一趟排序将待排序的记录分成独立的两部分，其中一部分记录的关键字比另一部分的关键字小。然后对这两部分再继续排序，一直达到整个序列有序。 设待排序序列为L.r1，L.r2，L.rn)，首先任意选取一个记录(通常选择第一个记录 L.r1)作为支点(pivot)，然后按照下述原则排列其余记录：将所有关键字比 L.r1key 小的记录都安排在它的位置之前，将所有关键字比 L.r1.key大的记录都安排在它的位置之后。可以发现，在安置的过程中，L.r1的确切位置将被最

15、终确定。设该支点(pivot)最后确定的位置为 i，则将序列分割为左右两部分。这个过程称为一趟快速排序。 设待排序序列用数组 elowhigh保存。设置两个指针 low和 high，分别指向数组的开始位置和终止位置。设支点记录为 elow，并将之暂存于 t。 首先，从 high的位置向前搜索，找到第一个小于 t的记录，将这个记录和 elow的值交换；然后，从low所指向的位置向后搜索，找到第一个值大于 t的记录，将这个记录和 ehigh的值交换。重复以上步骤，直到 low=high。完成一趟排序，low(或者 high)指向的位置就是第一个元素的确切位置(从两边向中间“夹挤”)。 第一趟完成后

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

17、字 97，将之赋给 ehigh，如下： high继续左移(high)，没有找到比 t(49)还小的数，但是由于出现了 high=low的情况，结束左移。如下： 4.数据序列(8，9，10，4，5，6，20，1，2)只能是下列排序算法中 _ 的两趟排序后的结果。（分数：2.00）A.选择排序B.冒泡排序C.插入排序 D.堆排序解析：直接插入排序是一种最基本的排序算法，基本操作为：将一个记录插入到一个已经排好序的有序表中，从而得到一个新的、长度增 1的有序表。 一般情况下，第 i趟的操作为：在含有 i=1个记录的有序子序列 r1i-1中插入一个新记录 ri，变成含有 i个记录的有序序列 rLli。

18、设置 r0为空值，从 r1开始保存信息，可首先将待插入的记录 ri复制到 r0中，如下所示： 5.对一组数据(84，47，25，15，21)排序，数据的排列次序在排序的过程中的变化为 _ 。 (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）A.选择 B.冒泡C.快速D.插入解析：简单选择排序的基本思想是：每一趟在 n-i+1(i=1，2，3，n-1)个记录中选取关键字最小的记录作为有序序列中的第 i个记录。它的具体实现过程为： (1)将整个记录序列划分为有

19、序区域和无序区域，有序区域位于最左端，无序区域位于右端，初始状态有序区域为空，无序区域含有待排序的所有 n个记录。 (2)设置一个整型变量 index，用于记录在一趟的比较过程中，当前关键字值最小的记录位置。开始将它设定为当前无序区域的第一个位置，即假设这个位置的关键字最小，然后用它与无序区域中其他记录进行比较，若发现有比它的关键字还小的记录，就将 index改为这个新的最小记录位置，随后再用 aindex.key与后面的记录进行比较，并根据比较结果，随时修改 index的值，一趟结束后 index中保留的就是本趟选择的关键字最小的记录位置。 (3)将 index位置的记录交换到无序区域的第一

20、个位置，使得有序区域扩展了一个记录，而无序区域减少了一个记录。 不断重复(2)、(3)，直到无序区域剩下一个记录为止。此时所有的记录已经按关键字从小到大的顺序排列就位。 算法如下： void selecsort(DataType a，int n) for(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； 简单选择排序算法简单，但

21、是速度较慢，并且是一种不稳定的排序方法，但在排序过程中只需要一个用来交换记录的暂存单元。其时间复杂度为 O(n 2 )。 举例：利用简单选择排序算法对以下序列排序： (72，73，71，23，94，16，5，68) 过程： 第一趟：5，73，71，23，94，16，72，68 第二趟：5，16，71，23，94，73，72，68 第三趟：5，16，23，71，94，73，72，68 第四趟：5，16，23，68，94，73，72，71 第五趟：5，16，23，68，71，73，72，94 第六趟：5，16，23，68，71，72，73，94 第七趟：5，16，23，68，71，72，73，94

22、 完成6.若用冒泡排序对关键字序列18，16，14，12，10，8，进行从小到大的排序，所需进行的关键字比较总次数是 _ 。（分数：2.00）A.10B.15 C.21D.34解析：(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+)

24、 if(ajkeyaj+1.key) temp=aj；aj=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； 进一步地改进冒泡排序算法：在算

25、法给出的冒泡排序算法的基础上，如果我们同时记录第 i趟冒泡排序中最后一次发生交换操作的位置 m(m void BubbleSort3(DataType a，int n) last=n-1： for(i-n；i1；i) exchange=0； m=last； 初始将最后进行记录交换的位置设置成 i-1 for(j=1；j=m；j+) if(ajkeyaj+1.key) temp=aj；aj=aj+1；aj-i=temp； exchange=1： last=j； 记录每一次发生记录交换的位置 ) if(exchange=-0)break： 冒泡排序比较简单，当初始序列基本有序时，冒泡排序有较高的效

26、率，反之效率较低；冒泡排序只需要一个记录的辅助空间，用来作为记录交换的中间暂存单元；冒泡排序是一种稳定的排序方法。 举例：利用冒泡法对以下序列进行排序。 (49，38，65，97，76，13，27，49)n=8 第一趟：38 49 65 76 13 27 49 97 第二趟：38 49 65 13 27 49 76 97 第三趟：38 49 13 27 49 65 76 97 第四趟：38 13 27 49 49 65 76 97 第五趟：13 g7 38 49 49 65 76 97 第六趟：13 27 38 49 49 65 76 97 第七趟：没有必要再比了，因为上一趟(第六趟)没有发生

27、交换，这说明已经排序完毕。 该算法的时间复杂度为 O(n 2 )，属于稳定排序。7.设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有 5个长度为 2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为 _ 。（分数：2.00）A.15，25，35，50，20，40，80，85，3670 B.15，25，35，50，80，20，85，40，70，36C.15，25，35，50，80，85，20，36，40，70D.15，25，35，50，80，20，36，40，70，85解析：归并排序是一种另一类排序方法。所谓归并是指将两个或两

28、个以上的有序表合并成一个新的有序表。归并排序的基本思想是将一个具有 n个待排序记录的序列看成是 n个长度为 1的有序序列，然后进行两两归并，得到 8.假定一个初始堆为(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。9.设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是 _ 。（分数：2.00）A

29、.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.设一组初始记录关键字序列为(50，40，95，20，15，70，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。11.假定对元素序列(7，3，5，9，1，12)进行堆排序，并且采用小根堆，则由初始数据构成

30、的初始堆为 _ 。（分数：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。12.二路归并排序的时间复杂度为 _ 。 A.O(n) B.O(n2) C.O(nlog2n) D.O(log2n)（分数：2.00）A.B.C. D.解析：解析见 15。13.用直接插入排序方法对下面 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

31、.90，69，80，46，21，32，94，40解析：解析见 4。14.对序列15，9，7，8，20，-1，4，用希尔排序方法排序，经一趟后序列变为15，-1，4，8，20，9，7则该次采用的增量是 _ 。（分数：2.00）A.1B.4 C.3D.2解析：解析见 1。15.排序方法的稳定性是指 _ 。（分数：2.00）A.该排序算法不允许有相同的关键字记录B.该排序算法允许有相同的关键字记录C.平均时间为 o(n log n)的排序方法D.以上都不对 解析：待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则该排序方法是稳定的；若具有相同关键

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

33、 1.3 ) O(1) 不稳定 快速排序 O(nlog 2 n) O(n 2 ) O(log 2 n) 不稳定 堆排序 O(nlog 2 n) O(nlog 2 n) O(1) 不稳定 2路归并排序 O(nlog 2 n) O(nlog 2 n) O(n) 稳定 基数排序 O(d*(rd+n) O(d*(rd+n) O(rd) 稳定 二、综合应用题(总题数：5，分数：50.00)16.对于一个堆栈，若其入栈序列为 12，3，n，不同的出入栈操作将产生不同的出栈序列。其出栈序列的个数正好等于结点个数为 n的二叉树的个数，且与不同形态的二叉树一一对应。请简要叙述一种从堆栈输入(固定为 1，2，3n

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

35、630，828，4，10，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)根据以上序列建立一个堆(画

36、出第一步和最后堆的结果图)，希望先输出最小值。 (2)输出最小值后，如何得到次小值(并画出相应结果图)。 （分数：10.00）_正确答案：()解析：(1)建小堆 (2)求次小值 19.有 n个记录存储在带头结点的双向链表中，现用双向冒泡排序法对其按升序进行排序，请写出这种排序的算法(注：双向冒泡排序即相邻两趟排序向相反方向起泡)。 （分数：10.00）_正确答案：()解析：typedef struct node ElemType data； struct node*prior，*next； )node，*DLinkedList； void TwoWayBubbleSort(DLinkedLis

37、t la) 对存储在带头结点的双向链表 la中的元素进行双向起泡排序。 int exchange=1； 设标记 DLinkedList p，temp，tail； head=la 双向链表头，算法过程中是向下起泡的开始结点 tail=null； 双向链表尾，算法过程中是向上起泡的开始结点 while(exchange) P=head-next； P 是工作指针，指向当前结点 exchange=0； 假定本趟无交换 while(p-next!=tail) 向下(右)起泡，一趟有一最大元素沉底 if(pdatapnextdata) 交换两结点指针，涉及 6条链 temp=pnext；exchange

38、=1； 有交换 pnext=tempnext；tempnextprior=p；先将结点从链 表上摘下 tempnext=P；ppriornext=temp； 将 temp插到 P结点前 tempprior=pprior；prior=temp； else ppEnext； 无交换，指针后移 tail=p； 准备向上起泡 P=tailprior： while(exchange&pprior!=head) 向上(左)起泡，一趟有一最小元素冒出 if(pdatap)priordata) 交换两结点指针，涉及 6条链 temp=pprior；exchange=1； 有交换 pprior=tempprio

39、r；temppriornext=p； 先将 temp结点从链表上摘下 tempprior=P；pnextprior=temp； 将 temp插到 P结点后(右) tempnext=pnext；pnext=temp； else p=pprior； 无交换，指针前移 head=P； 准备向下起泡 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； else return 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)；