《数据结构》课程教学资源（作业习题）练习题及答案9

一、填空题（每空1分，共24分） 1.大多数排序算法都有两个基本的操作：比较（两个关赞字的大小）和移动（记录或改变指向记录的指 针) 2.在对一组记录(54,38,96,23,15,72,60,45,83)进行直接插入排序时，当把第7个记录60插入到有 序表时，为寻找插入位置至少需比较3次。（可约定为，从后向前比较） 3.在插入和选择排序中，若初始数据基本正序，则选用插入排序（到尾部）若初始数据基本反序，则选 用选择排序 4.在堆排序和快速排序中，若初始记录接近正序或反序，则选用堆挂序：若初始记录基本无序，则最好选 用快速排序 5.对于个记录的集合进行目泡排序，在最坏的情况下所需要的时间是0山一。若对其进行快速排序，在 最坏的情况下所需要的时间是O(凸一· 6.对于n个记录的集合进行归并排序，所需要的平均时间是0logm,所需要的附加空间是Om。 7.【计研题2000】对于■个记录的表进行2路归并排序，整个归并排序需进行10（），共计移 动noe_次记录。 (即移动到新表中的总次数！共Iog2n趟，每趟都要移动n个元素) 8设要将序列(Q,耳C PA.MS.R.D,.X)中的关键码按字母序的升序重新排列，则： 冒泡排序 一通扫猫的结果是 H.C.Q.P.A.M.S.R.D.F.X.Y 初始步长为4的希尔(shell)排序一越的结果是P4CS,QD,EX,RHMY 二路归并排序一趙扫描的结果是HQCY,A.P.M.S,D.R.EX: 快速排序一描扫描的结果是F,H,C,D.P.A.L.O.R.S.Y,X: 堆排序初始建堆的结果是AD,CR,￡Q,MSY,P山X。 9。在堆排序、快速排序和归并排序中， 若只从存储空间考忠，则应首先选取堆排序方法，其次选取快速排序方法，最后选取归并排庄方法： 若只从排序结果的稳定性考感，则应选取归并排庄方法： 若只从平均情况下最快考虑，则应选取快速排庄方法： 若只从最坏情况下最快并且要节省内存考虑，则应选取雄排庄方法。 二、单项选择题（每小题1分，共18分） （C)1.将5个不同的数据进行排序，至多需要比较次。 A.8 B.9 C.10 D.25 （C)2。排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将 其放入已排序序列的正确位置上的方法，称为 A.希尔排序 B.冒泡排序 C.插入排序 D.选择排序 1

1 一、填空题（每空 1 分，共 24 分） 1. 大多数排序算法都有两个基本的操作： 比较（两个关键字的大小） 和 移动（记录或改变指向记录的指 针） 。 2. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第 7 个记录 60 插入到有 序表时，为寻找插入位置至少需比较 3 次。(可约定为，从后向前比较) 3. 在插入和选择排序中，若初始数据基本正序，则选用 插入排序（到尾部） ；若初始数据基本反序，则选 用 选择排序 。 4. 在堆排序和快速排序中，若初始记录接近正序或反序，则选用 堆排序 ；若初始记录基本无序，则最好选 用 快速排序 。 5. 对于 n 个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是 O(n2 ) 。若对其进行快速排序，在 最坏的情况下所需要的时间是 O(n2 ) 。 6. 对于 n 个记录的集合进行归并排序，所需要的平均时间是 O(nlog2n) ，所需要的附加空间是 O(n) 。 7．【计研题 2000】对于 n 个记录的表进行 2 路归并排序，整个归并排序需进行 log2n 趟（遍），共计移 动 n log2n 次记录。 (即移动到新表中的总次数！共 log2n 趟，每趟都要移动 n 个元素) 8.设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则： 冒泡排序一趟扫描的结果是 H, C, Q, P, A, M, S, R, D, F, X ,Y ； 初始步长为 4 的希尔（shell）排序一趟的结果是 P, A, C, S, Q, D, F, X , R, H,M, Y ； 二路归并排序一趟扫描的结果是 H, Q, C, Y，A, P, M, S, D, R, F, X ； 快速排序一趟扫描的结果是 F, H, C, D, P, A, M, Q, R, S, Y，X ； 堆排序初始建堆的结果是 A, D, C, R, F, Q, M, S, Y，P, H, X 。 9. 在堆排序、快速排序和归并排序中， 若只从存储空间考虑，则应首先选取 堆排序 方法，其次选取 快速排序 方法，最后选取 归并排序 方法； 若只从排序结果的稳定性考虑，则应 选取归并排序方法； 若只从平均情况下最快考虑，则应选取快速排序方法； 若只从最坏情况下最快并且要节省内存考虑，则应选取堆排序方法。 二、单项选择题（每小题 1 分，共 18 分） （ C ）1．将 5 个不同的数据进行排序，至多需要比较 次。 Ａ. 8 Ｂ. 9 Ｃ. 10 Ｄ. 25 （ C ）2． 排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将 其放入已排序序列的正确位置上的方法，称为 Ａ. 希尔排序 Ｂ. 冒泡排序 Ｃ. 插入排序 Ｄ. 选择排序

（D)3.排序方法中，从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方 法，称为 A.希尔排序 B.归并排序 C.插入排序 D.选择排序 (C）4.对个不同的排序码进行目泡排序，在下列哪种情况下比较的次数最多。 A.从小到大排列好的B。从大到小排列好的C.元素无序D.元素基本有序 （D)5,对个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为 A.叶 B.n C.n-1 D.n(n-1)/2 前3个答案都太小了 （C)6.快速排序在下列哪种情况下最易发挥其长处。 .被排序的数据中含有多个相同排序码B.被排序的数据已基本有序 c. 排序的教据完全无序 D.被排序的数据中的最大值和最小值相差悬殊 (B)7. 【计研题201】对有■个记录的表作快速排序，在最坏情况下，算法的时间复杂度是 A.0n) B.O(n2) C.O(nlogzn) D.O(n) （C)8.若一组记录的排序码为(46,79,56,38,40,84)，则利用快速排序的方法，以第一个记录为基准得 到的一次划分结果为 A.38,40,46,56,79,84 B.40,38.46,79,56.84 C.40,38,46,56,79,84D.40,38,46,84,5679 （A&D)9.【计研题2001】在最好情况下，下列排序算法中 排序算法所需比较关键字次数最少。 A.泡 B.归并 C.快速 D.直接插入 (仅n一次！) （C)10.【计研题2001】置换选择排序的功能是 。（置换选择排序=简单选择排序？）】 A.选出最大的元素B.产生初始归并段C.产生有序文件D.置换某个记录 （(A)1山.将5个不同的数据进行排序，至少需要比较次。 A.4 B.5 c.6 D.7 （D)12.下列关学序列中， 是堆。 A.16,72,31,23,94,53B.94,23,31,72,16,53 C.16,53,23,94,31,72 D.16,23,53,31,94,72 (B)13.堆是一种排序。 A.插入 B选择 C.交换 D.归并 （C)14.堆的形状是一棵 A.二叉排序树 B满二叉树 C.完全二叉树D.平衡二叉树 （B)15.若一组记录的排序码为(46,79,56,3840,84)，则利用堆排序的方法建立的初始堆为 A.79,46,56,38,40,84 B.84,79,56,38,40,46

2 （ D ）3． 排序方法中，从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方 法，称为 Ａ. 希尔排序 Ｂ. 归并排序 Ｃ. 插入排序 Ｄ. 选择排序 （ C ）4．对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。 Ａ. 从小到大排列好的 Ｂ. 从大到小排列好的 Ｃ. 元素无序 Ｄ. 元素基本有序 （ D ）5．对ｎ个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为 Ａ. n+1 Ｂ. n Ｃ. n-1 Ｄ. n(n-1)/2 (前 3 个答案都太小了) （ C ）6．快速排序在下列哪种情况下最易发挥其长处。 Ａ. 被排序的数据中含有多个相同排序码 Ｂ. 被排序的数据已基本有序 Ｃ. 被排序的数据完全无序 Ｄ. 被排序的数据中的最大值和最小值相差悬殊 （ B ）7． 【计研题 2001】对有 n 个记录的表作快速排序，在最坏情况下，算法的时间复杂度是 A．O(n) B．O(n2 ) C．O(nlog2n) D．O(n3 ) （ C ）8．若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用快速排序的方法，以第一个记录为基准得 到的一次划分结果为 Ａ. 38, 40, 46, 56, 79, 84 Ｂ. 40,38, 46 , 79, 56, 84 Ｃ. 40, 38，46, 56, 79, 84 Ｄ. 40, 38,46, 84, 56, 79 （ A&D ）9．【计研题 2001】在最好情况下，下列排序算法中 排序算法所需比较关键字次数最少。 A．冒泡 B．归并 C．快速 D．直接插入 (仅 n—1 次！) （ C ）10． 【计研题 2001】置换选择排序的功能是 。 （置换选择排序＝简单选择排序？） A．选出最大的元素 B．产生初始归并段 C．产生有序文件 D．置换某个记录 （ A ）11．将 5 个不同的数据进行排序，至少需要比较 次。 Ａ. 4 Ｂ. 5 Ｃ. 6 Ｄ. 7 （ D ）12．下列关键字序列中， 是堆。 Ａ. 16,72,31,23,94,53 Ｂ. 94,23, 31, 72, 16, 53 Ｃ. 16, 53, 23,94,31, 72 Ｄ. 16, 23, 53,31, 94, 72 （ B ）13．堆是一种 排序。 Ａ. 插入 Ｂ.选择 Ｃ. 交换 Ｄ. 归并 （ C ）14．堆的形状是一棵 Ａ. 二叉排序树 Ｂ.满二叉树 Ｃ. 完全二叉树 Ｄ. 平衡二叉树 （ B ）15．若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用堆排序的方法建立的初始堆为 Ａ. 79, 46, 56, 38, 40, 84 Ｂ. 84, 79, 56, 38, 40, 46

C.84.79.56.46.40.38 D.84.56.79.40.46.38 (B)16.下述几种排序方法中，平均查找长度(ASL)最小的是 A.插入排序 B.快速排序 C.归并排序 D,选择排序 （C)17.下述几种排序方法中，要求内存最大的是 A.插入排序 B.快速排序 C.归并排序 D.洗择排序 (B)18,目前以比较为基础的内部排序方法中，其比较次数与待排序的记录的初始排列状态无关的是 A.袖入排抒 B,二分插入排序 C,快速排 D.目泡排序 三、简答题（每小题4分，共36分） 【。【全国专升本题】已知序列本有序。对此序列最快的排序方法是多少，此时平均复杂度是多少2 答：插入并序和目泡应该是最快的。因为只有比较动作，无需移动元素。此时平均时间复杂度为0（回 2.设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好采用哪种排序方法？ 答：用堆排序或锦标赛排序最合适，因为不必等全部元素排完就能得到所需结果，时间效率为O(g):若 用目泡排序则需时n(a-l0g 3.用某种排序方法对线性表(25,84,21,47,15,27,68,35,20)进行排序时，元素序列的变化情况如下： 25,84,21,47,15,27,68,35,20+20,15,21,25,47,27,68.35,84→15,20,21,25,35,27,47,68,84→ 15,20,21,25,27,35.47,68,84, 问采用的是什么排胖方法？ 答：用的是快速排序方法。注意每一越要振满完全部元素才算一个中间结果， 4.对于整数序列100,9998，.3,2,1，如果将它完全倒过来，分别用目泡排序和快速排序法，它们的比较 次数和交换次数各是多少？ 答：冒泡排序的比较和交换次数将最大，都是1+2+.+n-1=n(m-1)2=50×99-4545次 快速排序则看按什么数据来分子表。 如果按100来分，则很惨，也会是(m-)21 若按中间数据50或51来分表，则： 第1轮能确定1个元素，即在1个子表中比较和交换了n一1个元素：n一(2.1) 第2轮能再确定2个元素，即在2个子表中比较和交换了■ 3个元素-(22.1) 第3轮能再确定4个元素，即在4个子表中比较和交换了n一7个元素：一(2以1) 第4轮能再确定8个元素，即在8个子表中比较和交换了n一15个元素：1一(21) 第6轮能再确定32个元素，即在32个子表中比较和交换了n一65个元素：n一(261) 第7轮则能全部确定，（因为2=128） 在100个子表中比较和交换了n-(10-1)个元素 比较和交换总次数为：7m一(2-1+2 -1+2 .+2-1+100-)=7m+7-(1+2+4+ +64+100)-7 -(8+16+32+164)=700-220=480次 若从中间选择初始元素，则ASL=(n+1)og2n一(2+22+25+.十2m=nlog:n+og:n-一(2+22+25+十n) O(nlogn) 5.【全国专升本试愿】【严题集10.15④】设有n个值不同的元素存于顺序结构中，试问能否用比23少的比较

3 Ｃ. 84, 79, 56, 46, 40, 38 Ｄ. 84, 56, 79, 40, 46, 38 （ B ）16． 下述几种排序方法中，平均查找长度（ASL）最小的是 Ａ. 插入排序 Ｂ.快速排序 Ｃ. 归并排序 Ｄ. 选择排序 （ C ）17． 下述几种排序方法中，要求内存最大的是 Ａ. 插入排序 Ｂ.快速排序 Ｃ. 归并排序 Ｄ. 选择排序 （ B ）18．目前以比较为基础的内部排序方法中，其比较次数与待排序的记录的初始排列状态无关的是 Ａ. 插入排序 Ｂ. 二分插入排序 Ｃ. 快速排序 Ｄ. 冒泡排序 三、简答题（每小题 4 分，共 36 分） 1. 【全国专升本题】已知序列基本有序，问对此序列最快的排序方法是多少，此时平均复杂度是多少？ 答：插入排序和冒泡应该是最快的。因为只有比较动作，无需移动元素。此时平均时间复杂度为 O(n) 2. 设有 1000 个无序的元素，希望用最快的速度挑选出其中前 10 个最大的元素，最好采用哪种排序方法？ 答：用堆排序或锦标赛排序最合适，因为不必等全部元素排完就能得到所需结果，时间效率为 O(nlog2n)；若 用冒泡排序则需时 n!/(n-10)! 3. 用某种排序方法对线性表（25, 84，21,47,15,27,68,35,20）进行排序时，元素序列的变化情况如下： 25, 84，21,47,15,27,68,35,20 → 20, 15, 21, 25，47, 27,68,35, 84 → 15, 20, 21, 25，35, 27, 47, 68, 84→ 15, 20, 21, 25，27, 35, 47, 68, 84， 问采用的是什么排序方法？ 答：用的是快速排序方法。注意每一趟要振荡完全部元素才算一个中间结果。 4. 对于整数序列 100，99，98，.3，2，1，如果将它完全倒过来，分别用冒泡排序和快速排序法，它们的比较 次数和交换次数各是多少？ 答：冒泡排序的比较和交换次数将最大，都是 1+2+.+n-1=n(n-1)/2＝50×99=4545 次 快速排序则看按什么数据来分子表。 如果按 100 来分，则很惨，也会是 n(n-1)/2！ 若按中间数据 50 或 51 来分表，则： 第 1 轮能确定 1 个元素，即在 1 个子表中比较和交换了 n－1 个元素；n－（2 1 -1） 第 2 轮能再确定 2 个元素，即在 2 个子表中比较和交换了 n－3 个元素；n－（2 2 -1） 第 3 轮能再确定 4 个元素，即在 4 个子表中比较和交换了 n－7 个元素；n－（2 3 -1） 第 4 轮能再确定 8 个元素，即在 8 个子表中比较和交换了 n－15 个元素；n－（2 4 -1） . 第 6 轮能再确定 32 个元素，即在 32 个子表中比较和交换了 n－65 个元素；n－（2 6 -1） 第 7 轮则能全部确定，（因为 2 7=128）， 在 100 个子表中比较和交换了 n－（100－1）个元素； 比较和交换总次数为：7n－(21－1＋2 2－1＋2 3－1.＋2 6－1＋100－1) ＝7n+7－(1＋2＋4＋.＋64+100)=7n －(8+16+32+164)=700-220=480 次 若从中间选择初始元素，则 ASL=（n+1）log2n－(2 1＋2 2＋2 3+.＋2 m)= nlog2n+log2n－(2 1＋2 2＋2 3+.＋n) ≈O（nlog2n） 5.【全国专升本试题】【严题集 10.15④】设有 n 个值不同的元素存于顺序结构中，试问能否用比 2n-3 少的比较

次数选出这·个元素中的最大值和最小值？若能请说明如何实现（不需写算法）。在最坏情况下至少需进行多少 次比较。（或问：对含有■个互不相同元素的集合，同时找最大元和最小元至少需进行多少次比较：） 答：若用目泡排序法，求最大值需m1次比较：第二越改为从1开始求最小值，需2次比较，合计2血3次。 显然本题意图是放弃冒泡排序，寻找其他方法。 法1：一个筒单的办法是，在一越比较时，将头两个元素分别作为最大和最小值的暂存内容，将其余-2个元 素与其相比，具体可设计为： 第1步：a1a2?VES则直接替换a2,N0则再比较al, 1~2次 第3步：a42?YES则直接替换a2,N0则再比较a1 1~2次： 第m-1步：a心a2?YES则直接替换a2,N0则再比较al, 12次： 合计：(m-2)×(1~2)十1m-l)2n-3)≤2m3 最好情况至少需要-1次比较，最坏情况需2知-3次。 法2：借用快速排第一思想：以1为支点，将序列分成两个子表。这一需要-1次比较 然后，在左边的子表中求最小值，目泡一越需要y1次： 在右边的子表中求最大值，冒泡一越需要x1次： 合计需要(n-1)+Hy1)HI)=n+y+-3 因为y+z+1=n,所以总次数=2n一4≤2n一3： 但最坏情况下仍为为2-3次，即一趟完毕后仍为单子表的情况。怎么办？有无更好的办法？ 法3：能否用锦标赛排序思路？求最大值等于求冠军，需要一1次比较：但接着求最小值，等于在2个叶子 中比较即可。 编程也不复杂：可设计为， 第一越：■个数据两两比较（共2次），小者放偶数位，大者放奇数位： 第二越：对奇数位元素继续两两比较(n/4次)：对偶数位元素也两两比较(/4次)；合计n/2次： 第三越：对奇数位元素继续两两比较(m/2次)，对偶数位元素也两两比较(2次)：合计2次 第四越：对奇数位元素继续两两比较(/2次)：对偶数位元素也两两比较(2次)：合计/2次 第1og2n越：对奇数位元素继续两两比较(n/2e2n次=1)：对偶数位元素也两两比较(1次)：合计2次： 全部比较次数为：2+4+8+.十n2次≤2n-3(n>1) 用二进制性质即可证明？因为2+2+.2-2+241<2，即2+.2-+241<2一1<24一1+2一2 (m=25,当k=1,即=2时为极端情况，1=1： n=3时，1.5<3 k-2时，即m-4时，2<5 6。【成教考题】将两个长度为n的有序表归并为一个长度为2血的有序表，最小需要比较次，最多需要比较 2-1次，请说明这两种情况发生时，两个被归并的表有何特征？

4 次数选出这 n 个元素中的最大值和最小值？若能请说明如何实现（不需写算法）。在最坏情况下至少需进行多少 次比较。（或问：对含有 n 个互不相同元素的集合，同时找最大元和最小元至少需进行多少次比较?） 答：若用冒泡排序法，求最大值需 n-1 次比较；第二趟改为从 n-1 开始求最小值，需 n-2 次比较，合计 2n-3 次。 显然本题意图是放弃冒泡排序，寻找其他方法。 法 1 ：一个简单的办法是，在一趟比较时，将头两个元素分别作为最大和最小值的暂存内容，将其余 n-2 个元 素与其相比，具体可设计为： 第 1 步：a1a2? YES 则直接替换 a2，NO 则再比较 a1， 1～2 次； 第 3 步：a4>a2? YES 则直接替换 a2，NO 则再比较 a1， 1～2 次； . 第 n-1 步：an>a2? YES 则直接替换 a2，NO 则再比较 a1， 1～2 次； 合计：（n-2）×（1～2）＋1=(n-1)~(2n-3 )≤2n-3 最好情况至少需要 n-1 次比较，最坏情况需 2n-3 次。 法 2 ：借用快速排序第一趟思想：以 a1 为支点，将序列分成两个子表。这一趟需要 n-1 次比较； 然后，在左边的子表中求最小值，冒泡一趟需要 y-1 次； 在右边的子表中求最大值，冒泡一趟需要 z-1 次； 合计需要(n-1)+( y-1)+( z-1)=n+y+z-3 因为 y+z+1=n, 所以总次数＝2n－4≤2n－3!!!!!!!!!!! 但最坏情况下仍为为 2n-3 次，即一趟完毕后仍为单子表的情况。怎么办？有无更好的办法？ 法 3 ：能否用锦标赛排序思路？求最大值等于求冠军，需要 n—1 次比较；但接着求最小值，等于在 n/2 个叶子 中比较即可。 编程也不复杂：可设计为， 第一趟：n 个数据两两比较（共 n/2 次），小者放偶数位，大者放奇数位； 第二趟：对奇数位元素继续两两比较（n/4 次）；对偶数位元素也两两比较（n/4 次）；合计 n/2 次； 第三趟：对奇数位元素继续两两比较（n/2 3 次）；对偶数位元素也两两比较（n/2 3 次）；合计 n/22 次； 第四趟：对奇数位元素继续两两比较（n/2 4 次）；对偶数位元素也两两比较（n/2 4 次）；合计 n/23 次； . 第 log2n 趟：对奇数位元素继续两两比较（n/2 log2n次＝1）；对偶数位元素也两两比较（1 次）；合计 2 次； 全部比较次数为：2+4+8+.＋n/2 次≤2n-3 （n>1） 用二进制性质即可证明？ 因为 2 0+2 1+.2 k-2+2 k-1<2k ，即 2 1+.2 k-2+2 k-1<2k —1 < 2 k —1 +2k —2 (n=2k , 当 k＝1，即 n=2 时为极端情况，1＝1; n=3 时，1.5<3 k=2 时，即 n=4 时，2<5 6. 【成教考题】将两个长度为 n 的有序表归并为一个长度为 2n 的有序表，最小需要比较 n 次，最多需要比较 2n-1 次，请说明这两种情况发生时，两个被归并的表有何特征?

答：最少的比较次数是这样一种情况：若A表所有元素都小于（或大于）B表元素，则A1比较完B1一Bm之后， 直接拼接即可。 最多比较次数的情况应该是A、B两表互相交错，此时需要穿插重排。则A表的每个元素都要与B表元素相比， A1与B1相比，能确定其中一个元素的位置：剩下一个还要与另一表中下一元素再比较一次， 即：在表A成表B的n个元素中，除了最后一个元素外，年个元意都要比较2次1最坏情况总共为2m一1次 四、【全国专升本类似题】【类严题集10.1①】以关键字序列(256,301,751,129,937,863,742 694,076,438)为例，分别写出执行以下算法的各趟排序结束时，关键字序列的状态，并说明这 些排序方法中，哪些易于在链表（包括各种单、双、循环链表）上实现？ ①直接插入排序②希尔排序③冒泡排序④快速排序 ⑤直接选择排序⑧堆排序 )归并排序⑧基数排序 (8分) ①⑤⑦⑧皆易于在链表上实现。 排序的中间过程如下 ② 希尔排序的中间过程如下 第-趙：(256,301)，751.129,937,863,742,694,076,438 第二插：(256.301,751)，129.937.863,74,694.076.438 (2)希尔推序（取d✉15,3,1） 第三趟：(129,256,301,751)，937.863.742：694.076.438 第-塘：256,301,694,076.438,863,742.751.129.937 第四趟：(129,256.301.751.937).863,742.694,076.438 第二趟：076,301,129,256,438.694.742.751,863.937 第五：(129.256.301,751,863.937)，742.6 4,076.438 第三t趟：076.129,256,301,438,694,742,751,863,97 墙：(129,256,301,742,751,863,937).694.076.438 第七趟：(129,256,301,694,742,751,863,937)，06,438 第八墙：(076.129,256.301,694,742.751,863.937,438 第九趟：(076.129,256.301,438,694.742,751.63.937 ③冒泡排序的中间过程如下 ④快速排序的中间过程如下： 26301,751,12.9g7,863,742,694.06.48 256.301,751.129,937,863.742.694,076,438千6 第-ǚ：256,301,129,751,863,742,694,0m6,438.937第-趙：(076.129)，256.(751.937.863.742.64.301,439) 第二趟：256,129.301,751,742,694,076.438.863,937 第=趟：076.129,256.(438,301.694,742)，751，(863,937) 第三趟：129.256.301,742,694,076.438,751,863,937 29.256.301.694.076.438.742,751 第三：076.129,256,301,438.(694.742).751，(863,937) ,937 第五趟：129.256.301,076,438,694,742,751,863,937 第四：076,29,26.301.438,64,742,751 (863.937 第五趟 第六趋：129.256,076.301,438.694.742.751.863.937 076,129,256301,438,694,742,75,863,937 第七趟：129,076,256,301,438.694,742.751.863.937 第八：076.129.256.301.438.694.742.751.863.937 第九趟：076.129.256,301.438.64,742,751,863,937 同直接选择排序的中间过程如下： ⑥堆排序（大根堆）的中间过程如下：

5 答：最少的比较次数是这样一种情况：若 A 表所有元素都小于（或大于）B 表元素，则 A1 比较完 B1～Bn 之后， 直接拼接即可。 最多比较次数的情况应该是 A、B 两表互相交错，此时需要穿插重排。则 A 表的每个元素都要与 B 表元素相比， A1 与 B1 相比，能确定其中一个元素的位置；剩下一个还要与另一表中下一元素再比较一次， 即：在表 A 或表 B 的 n 个元素中，除了最后一个元素外，每个元素都要比较 2 次！最坏情况总共为 2n—1 次。 四、【全国专升本类似题】【类严题集 10.1①】以关键字序列（256，301，751，129，937，863，742， 694，076，438）为例，分别写出执行以下算法的各趟排序结束时，关键字序列的状态，并说明这 些排序方法中，哪些易于在链表（包括各种单、双、循环链表）上实现？ ① 直接插入排序 ② 希尔排序 ③冒泡排序 ④快速排序 ⑤直接选择排序 ⑥ 堆排序 ⑦ 归并排序 ⑧ 基数排序 （8 分） 解：先回答第 2 问： ① ⑤ ⑦ ⑧皆易于在链表上实现。 ① 直接插入排序的中间过程如下： ② 希尔排序的中间过程如下： ③ 冒泡排序的中间过程如下： ④快速排序的中间过程如下： ⑤ 直接选择排序的中间过程如下： ⑥堆排序（大根堆）的中间过程如下：

256.301.751.129.937.863.742.694.0m6.438 第-趟：(256.301)，751,129,937,863,742,694,076.438 第二趙：(256,301.751)，129.937.863.742.694.076.438 第-趙：(937,6,863.256.438.751,742.129.076,301) 第三趟：(129.256.301,751)，937,863,742.694,076.438 第二（863.694,751.256.438.301,742.129,076).937 第四：(129,256,301,751.937)，863.742.694.076.438 第三：(751,694,742,256,438,301,076,129).863.927 第7i：(129.256.301.751.863.937).742.694.0m6.438 第四趟：(742,64,301,256,438.129,076).751.863.937 第六通：(129.256.301,742.751.863.937).694.076.438 第五趙：(694.438.301,256,076.129)，742.751.863.937 第七越：(129,256,301.64,742,751.863937).076.438 第六通：(438,256,301,129.076)，694,742.751：863.937 第八：(076,129.256,301,694,742,751,863,937438 第七：(301,256.076.129).438.694,742,751,863.937 第九趙：(076,129,256.301,438.694.742,751,863,937) 第八墙：(256.129.076)，301.438,694,742.751,863,937 第九挡：076,129.256,301,438,694,742.751,863,937 ⑦归并排序排序的中间过程如下： 256,301,751,129,937,863.742,694,076.438 第-：[2561，301].[751].129]，[9371.[8631，[7421，[6941，[076]，{438] 第-描：256,3011，129,751.363,937j.[694.721.076,4381 第三描：[129.256,301,7511，[694.742,863.37，[076,438 第四趟：[076.129,256.301,438,694,742,751,868,937] ⑧基数排序的中间过程如下： 236,301,751,12四.97.863,742,694.076,438 第一趙：301,751.742,863,694,256,076,937,438,129 第二趙：301,129.937,438,742,751,256.863,076.694 第三：076.129,256,301.438.694,742,751.863.937

6 ⑦ 归并排序排序的中间过程如下： ⑧ 基数排序的中间过程如下：