【中央广播电视大学】【试卷习题】【图的辅导练习题及解答_数据结构】

排序的辅导旅习题及解答 (一)单地择题 1.若对n个元素进行直接插入排序，测进行第1崎排序过程前，有序表中的元素个数 为(). A n B n+1 C n-1 D 1 2若对个元素进行直接插入排序，在违行第1崎带序时，为寻找插入位置最多需要 进行()次元素的比较，假定第0号元素放有特查的健植。 A n B n-1 C n+1 D 1 3若对n个元素进行直接插入排序，在进行第1崎排序时，假定元素r[+1]的插入位 置为[】，则需要移动元素的次数为()： A j-I B i-j-1 c i-j D i-j*1 4.若对个元素进行直接插入排序，（遗行任一语排序的过程中，为寻我福入位置而 需要的时间复杂性为()。 A0(1)B0(n)C0(mD0(1og 点在对个元素进行直接插入排序的过程中，共需要进行()场。 An Bn+1Cn-1D2知 6对■个元素进行直接插入持序到间复杂性为()。 A 0(1)B O(n)C o(n)D O(log-n) 7。在对个元素进行冒泡排序的过程中，第一墙排序至多需要进行()对相邻元素之 间的交换。 A n B n-l C n+l D n/2 &在对个元素进行冒泡排序的过程中，最好情况下的时间复杂性为(》。 A O(1)B O(logn)C o(')D O(n) 9.在对个元素进行冒泡排序的过程中，至少需委《)植完成。 A 1 B n C n-1 D n/2 1Q,在对个元素进行快速排序的过程中，若每次划分得到的左，右两个子区间中元素 的个数相等或只差一个，则整个样序过程得到的含两个或两个元素的区间个数大致为()· A n B n/2 C logan D 2n 11,在对n个元素进行快速排序的过程中，第一次划分最多需要移动《)次元素。包括 1

1 排序的辅导练习题及解答 （一）单项选择题 1. 若对 n 个元素进行直接插入排序，则进行第 i 趟排序过程前，有序表中的元素个数 为（）。 A n B n+1 C n-1 D 1 2. 若对 n 个元素进行直接插入排序，在进行第 i 趟排序时，为寻找插入位置最多需要 进行（）次元素的比较，假定第 0 号元素放有待查的键值。 A n B n-1 C n+1 D 1 3. 若对 n 个元素进行直接插入排序，在进行第 i 趟排序时，假定元素 r[i+1]的插入位 置为 r[j]，则需要移动元素的次数为（）。 A j-I B i-j-1 C i-j D i-j+1 4. 若对 n 个元素进行直接插入排序，则进行任一趟排序的过程中，为寻找插入位置而 需要的时间复杂性为（）。 A O(1) B O(n) C O(n2 ) D O(log2n) 5. 在对 n 个元素进行直接插入排序的过程中，共需要进行（）趟。 A n B n+1 C n-1 D 2n 6. 对 n 个元素进行直接插入排序时间复杂性为（）。 A O(1) B O(n) C O(n2 ) D O(log2n) 7. 在对 n 个元素进行冒泡排序的过程中，第一趟排序至多需要进行（）对相邻元素之 间的交换。 A n B n-1 C n+1 D n/2 8. 在对 n 个元素进行冒泡排序的过程中，最好情况下的时间复杂性为（）。 A O(1) B O(log2n) C O(n2 ) D O(n) 9. 在对 n 个元素进行冒泡排序的过程中，至少需要（）趟完成。 A 1 B n C n-1 D n/2 10. 在对 n 个元素进行快速排序的过程中，若每次划分得到的左、右两个子区间中元素 的个数相等或只差一个，则整个排序过程得到的含两个或两个元素的区间个数大致为（）。 A n B n/2 C log2n D 2n 11. 在对 n 个元素进行快速排序的过程中，第一次划分最多需要移动（）次元素，包括

开始肥基准元素移动到临时变量的一次在内。 A n/2 B n-1 C n D n+l 2.在对·个元素进行快速排序的过程中，最好情况下需要进行()躺. A n B n/2 C logn D 2n 13,在对个元素遗行快逸排序的过程中，最坏情况下需要进行()销。 A n B n-l C n/2 D logan 14.在对n个元素进行快速排序的过程中。平均情况下的时间复杂性为()， A0(1D B O(logn)C O(n) D O(nlogn) 15.在对个元素进行快速排序的过程中，最坏情况下的时间复杂性为()。 A01) B O(logn)C o(n)D O(nlog-n) 16,在对个元素适行快速排序的过程中。平均情况下的空间复杂性为(》。 A O(1)B O(logn)C O(n)D O(nlogn) 17.在对个元素进行快速排序的过程中，最坏情况下的空间复杂性为(》， A O(1)B O(logn)C o(n')D O(nlogn) 18。在对个元素进行直接插入排序的过程中，算法的空间复条性为()。 A O(1)B O(loz:n)C O(')D O(nlog:n) 19.假定对元素序列(3,7,5,9,1)进行快速排序，则进行第一次划分时需要移动 元素的次数为()，假定不包括开始把基准元素移动到：时变量的一次计算在内， A】 B2 C 3 0,对下列四个序列进行快速排序，各以第一个元素为基准进行第一次划分，则在该次 划分过程中需要移动元素次数最多的序列为(》。 A1,35,7,9B9,7,53,1 C5,3,1,7.9D5.7,9.1,3 21.假定对元素序列(7,3,5,9,1,128,15》进行快速排序，则进行第一次划分 后，得到的左区间中元素的个数为()。 A 2 B 3 C4 D5 22.在对个元素送行直接选择排序的过程中，需要进行(》墙选择和交操. A n B e+1 C n-1 D /2 2。在对个元素进行直接选择排序的过程中，在第1婚雷要从()个元素中选择出最 小值元素。A 2

2 开始把基准元素移动到临时变量的一次在内。 A n/2 B n-1 C n D n+1 12. 在对 n 个元素进行快速排序的过程中，最好情况下需要进行（）躺。 A n B n/2 C log2n D 2n 13. 在对 n 个元素进行快速排序的过程中，最坏情况下需要进行（）躺。 A n B n-1 C n/2 D log2n 14. 在对 n 个元素进行快速排序的过程中，平均情况下的时间复杂性为（）。 A O(1) B O(log2n) C O(n2 ) D O(nlog2n) 15. 在对 n 个元素进行快速排序的过程中，最坏情况下的时间复杂性为（）。 A O(1) B O(log2n) C O(n2 ) D O(nlog2n) 16. 在对 n 个元素进行快速排序的过程中，平均情况下的空间复杂性为（）。 A O(1) B O(log2n) C O(n2 ) D O(nlog2n) 17. 在对 n 个元素进行快速排序的过程中，最坏情况下的空间复杂性为（）。 A O(1) B O(log2n) C O(n2 ) D O(nlog2n) 18. 在对 n 个元素进行直接插入排序的过程中，算法的空间复杂性为（）。 A O(1) B O(log2n) C O(n2 ) D O(nlog2n) 19. 假定对元素序列（3, 7, 5, 9, 1）进行快速排序，则进行第一次划分时需要移动 元素的次数为（），假定不包括开始把基准元素移动到临时变量的一次计算在内。 A 1 B 2 C 3 D 4 20. 对下列四个序列进行快速排序，各以第一个元素为基准进行第一次划分，则在该次 划分过程中需要移动元素次数最多的序列为（）。 A 1, 3, 5, 7, 9 B 9, 7, 5, 3, 1 C 5, 3, 1, 7, 9 D 5, 7, 9, 1, 3 21. 假定对元素序列（7, 3, 5, 9, 1, 12, 8, 15）进行快速排序，则进行第一次划分 后，得到的左区间中元素的个数为（）。 A 2 B 3 C 4 D 5 22．在对 n 个元素进行直接选择排序的过程中，需要进行（）趟选择和交换。 A n B n+1 C n-1 D n/2 22．在对 n 个元素进行直接选择排序的过程中，在第 i 趟需要从（）个元素中选择出最 小值元素。A

A n-i+l B n-f C i D i+l 2以.若对·个元素进行直接选择排序，则进行任一墙排序的过程中，为寻找最小值元素 所需要的时间复染性为()。 A O(1)B O(logn)C o(n)D O(n) 24.若对·个元素进行堆排序，则在构成初始堆的过程中需要进行()次篇运算。 A 1 B n/2 C n D n-1 25.若对个元素进行堆排序，则在由初始堆进行每崤排序的的过程中，共需要进行() 次筛运算。 A n+1 B n/2 C n D n-1 25.若对个元素进行堆排序，则每次进行简运算的时间复桑性为0。 A0(1)B0(1ogn)C0(）D0( 7,在对个元素进行堆排序的过程中，时间复杂性为()。 A O(1)B O(logn)C O(n')D O(nlogn) 28.在对个元素进行堆排序的过程中，空间复杂性为()· A O(1)B O(logn)C o(n)D O(nlogn) 29,程定对元素序列(7,3,5,9,1,12》遗行堆排序，并且采用小根堆。则由初始 数据构成的初始堆为()。 A1,3.5,7.9,12B1,3.5.9,7.12 C1.5,3.7,9,12D1,53,9.12,7 30.假定一个初始堆为(1,5,3,9.12,7,15,10)，则进行第一植堆排序后得到的 结果为()。 A3,5.7,9.12,10.15,1B3,5.9,7,12,10.15,1 A3,7.5,9.12,1015,1B3,5.7,12.9,1015,1 31,若对n个元素送行归并排序，则进行归并的墙数为()， A n B n-l C n/2 D [logal 32,若对个元素进行自并排序，则进行每一墙归并的时间复杂性为()。 A0(1)B01oen)C0)D0(m7 33.若一个元素序列基本有序，则选用()方法较快。 A直接插入排序B直接选择排序 C堆持序D快速排序

3 A n-i+1 B n-i C i D i+1 23. 若对 n 个元素进行直接选择排序，则进行任一趟排序的过程中，为寻找最小值元素 所需要的时间复杂性为（）。 A O(1) B O(log2n) C O(n2 ) D O(n) 24. 若对 n 个元素进行堆排序，则在构成初始堆的过程中需要进行（）次筛运算。 A 1 B n/2 C n D n-1 25. 若对 n 个元素进行堆排序，则在由初始堆进行每躺排序的的过程中，共需要进行（） 次筛运算。 A n+1 B n/2 C n D n-1 26. 若对 n 个元素进行堆排序，则每次进行筛运算的时间复杂性为()。 A O(1) B O(log2n) C O(n2 ) D O(n) 27. 在对 n 个元素进行堆排序的过程中，时间复杂性为（）。 A O(1) B O(log2n) C O(n2 ) D O(nlog2n) 28. 在对 n 个元素进行堆排序的过程中，空间复杂性为（）。 A O(1) B O(log2n) C O(n2 ) D O(nlog2n) 29. 假定对元素序列（7, 3, 5, 9, 1, 12）进行堆排序，并且采用小根堆，则由初始 数据构成的初始堆为（）。 A 1, 3, 5, 7, 9, 12 B 1, 3, 5, 9, 7, 12 C 1, 5, 3, 7, 9, 12 D 1, 5, 3, 9, 12, 7 30. 假定一个初始堆为(1, 5, 3, 9, 12, 7, 15, 10)，则进行第一趟堆排序后得到的 结果为（）。 A 3, 5, 7, 9, 12, 10, 15, 1 B 3, 5, 9, 7, 12, 10, 15, 1 A 3, 7, 5, 9, 12, 10, 15, 1 B 3, 5, 7, 12, 9, 10, 15, 1 31. 若对 n 个元素进行归并排序，则进行归并的趟数为（）。 A n B n-1 C n/2 D log2n 32. 若对 n 个元素进行归并排序，则进行每一趟归并的时间复杂性为（）。 A O(1) B O(log2n) C O(n) D O(n2 ) 33. 若一个元素序列基本有序，则选用（）方法较快。 A 直接插入排序 B 直接选择排序 C 堆排序 D 快速排序

34.若要从1000个元素中得到10个最小值元素，最好采用()方法， A直接插入排序B直接透择排序 C堆排序D快速排序 35.若要对1000个元素排序，要求既快又稳定，则最好采用()方法， A直接插入排序B自并排序 C堆排序D快速排序 36,若要对1000个元素排序，要求既快又节省存储空闻，则最好采用()方法。 A直接插入排序B日并排序 C堆排序 D快速排序 37,在下列排序方法中，空间复染性为0(1o)的方法为()。 A直接选择排序B白并排序 C排排序 D快速排序 38,在平均情况下速度最快的排序方法为()。 A直接选择排序B白并排序 C蝶排序 D快速排序 (二)填空题 1,每次从无序子表中取出一个元素，把它括入到有序子表中的适当位置。此种排序方 法叫做持序：每次从无序子表中挑选出一个最小或最大元素，把它交换到有序表的 一端，此种排序方法叫做排序。 2.每次直接或通过基准元素闻接比较两个元素，若出现逆序排判时瓷交换它们的位置， 此种排序方法叫做排序：每次使两个相细的有序表合井成一个有序表的排序方法叫 做排序。 3,在直接透择排序中，记录比较次数的时间复杂性为 ,记录移动次数的时间 复杂性为 4.在堆排序的过程中，对■个记录建立初始堆需要进行 次静运算，由初始堆 到堆排序结束。需要对树根结点进行次筛运算。 5,在堆排序的过程中，对任一分支结.点进行筛运算的时间复杂性为 ,整个堆 排序过程的时间复杂性为 6对■个记录进行冒泡排序时，最少的比较次数为 一，最少的植数为 ?。快速排序在平均情况下的时间复杂性为 ,在最坏情况下的时间复桑性为

4 34. 若要从 1000 个元素中得到 10 个最小值元素，最好采用（）方法。 A 直接插入排序 B 直接选择排序 C 堆排序 D 快速排序 35. 若要对 1000 个元素排序，要求既快又稳定，则最好采用（）方法。 A 直接插入排序 B 归并排序 C 堆排序 D 快速排序 36. 若要对 1000 个元素排序，要求既快又节省存储空间，则最好采用（）方法。 A 直接插入排序 B 归并排序 C 堆排序 D 快速排序 37. 在下列排序方法中，空间复杂性为 O(log2n)的方法为（）。 A 直接选择排序 B 归并排序 C 堆排序 D 快速排序 38. 在平均情况下速度最快的排序方法为（）。 A 直接选择排序 B 归并排序 C 堆排序 D 快速排序 （二）填空题 1．每次从无序子表中取出一个元素，把它插入到有序子表中的适当位置，此种排序方 法叫做________排序；每次从无序子表中挑选出一个最小或最大元素，把它交换到有序表的 一端，此种排序方法叫做________排序。 2．每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交换它们的位置， 此种排序方法叫做________排序；每次使两个相邻的有序表合并成一个有序表的排序方法叫 做________排序。 3．在直接选择排序中，记录比较次数的时间复杂性为________，记录移动次数的时间 复杂性为________。 4. 在堆排序的过程中，对 n 个记录建立初始堆需要进行________次筛运算，由初始堆 到堆排序结束，需要对树根结点进行_______次筛运算。 5．在堆排序的过程中，对任一分支结点进行筛运算的时间复杂性为________，整个堆 排序过程的时间复杂性为________。 6. 对 n 个记录进行冒泡排序时，最少的比较次数为________，最少的趟数为_______。 7. 快速排序在平均情况下的时间复杂性为________，在最坏情况下的时间复杂性为

8。快速情序在平均情况下的空间复杂性为 一·在最坏情况下的空间复桑性为 9.在二路归并排序中，对■个记录进行归并的随数为 1Q,在白并持序中，透行每墙归并的时间复杂性为 整个排序过程的时间复染 性为一，空间复杂性为一· 11,对20个记录进行归并排序时。共需要进行 墙归并，在第三墙自并时是把 长度为的有序表两两归并为长度为的有序表。 12.若对一组记录(46.79,56.38,0.80,35,50,74)进行直接插入排序，当把第8个记录 辅入到前面己排序的有序表时，为寻找插入位置需比较次， 13,若对一组记承(4679,56,38,40.80,35,50,74)进行直接选择排序，用k表示最小值 元素的下标，进行第一趋时k的初值为1，则在第一通选择最小值的过程中，k的值被修成 次。 14.若对一组记录(7638,62,53,80,74,83,65,85)进行堆排序，已知除第一个元素外， 以其象元素为根的结点都已是堆，则对第一个元素进行第运算时，它将最终被简到下标为 的位置。 15.假定一组记录为(6.79,56.38,0,8)，则利用堆排序方法建立的初始小根堆为 16.假定一个堆为(38.40,56.79,6,8)，则利用堆排序方法进行第一籁交换和对根结 点筛运算后得到的结果为 17.假定一组记录为(46,79,56,38.40,8)，在冒泡排序的过程中进行第一墙排序后的 结果为 18.假定一组记录为(46,79,56,64,38,0,8443)，在冒泡排序的过程中进行第一槽样 序时，元素9将最终下沉到其后第一个元素的位置。 19,假定一组记录为(469,5638,40,80)，对其进行快速排序的过程中，共需要 胡排序。 20.假定一组记录为(46,79,6,38,40,80)，对其进行快速排序的过程中，含有两个或 两个以上元素的排序区间的个数为个。 21.型定一组记录为(46,79,56,25,76,38,40,80)，对其选行快速排序的第一次划分后， 右区阿内元需的个数为 5

5 ________。 8．快速排序在平均情况下的空间复杂性为________，在最坏情况下的空间复杂性为 ________。 9．在二路归并排序中，对 n 个记录进行归并的趟数为________。 10. 在归并排序中，进行每趟归并的时间复杂性为________，整个排序过程的时间复杂 性为________，空间复杂性为________。 11．对 20 个记录进行归并排序时，共需要进行________趟归并，在第三趟归并时是把 长度为________的有序表两两归并为长度为________的有序表。 12. 若对一组记录(46,79,56,38,40,80,35,50,74)进行直接插入排序，当把第 8 个记录 插入到前面已排序的有序表时，为寻找插入位置需比较________次。 13. 若对一组记录(46,79,56,38,40,80,35,50,74)进行直接选择排序，用 k 表示最小值 元素的下标，进行第一趟时 k 的初值为 1，则在第一趟选择最小值的过程中，k 的值被修改 ________次。 14．若对一组记录(76,38,62,53,80,74,83,65,85)进行堆排序，已知除第一个元素外， 以其余元素为根的结点都已是堆，则对第一个元素进行筛运算时，它将最终被筛到下标为 ________的位置。 15．假定一组记录为(46,79,56,38,40,84)，则利用堆排序方法建立的初始小根堆为 ____________________。 16．假定一个堆为(38,40,56,79,46,84)，则利用堆排序方法进行第一躺交换和对根结 点筛运算后得到的结果为____________________。 17. 假定一组记录为(46,79,56,38,40,84)，在冒泡排序的过程中进行第一趟排序后的 结果为____________________。 18. 假定一组记录为(46,79,56,64,38,40,84,43)，在冒泡排序的过程中进行第一趟排 序时，元素 79 将最终下沉到其后第_______个元素的位置。 19. 假定一组记录为(46,79,56,38,40,80)，对其进行快速排序的过程中，共需要 ________趟排序。 20. 假定一组记录为(46,79,56,38,40,80)，对其进行快速排序的过程中，含有两个或 两个以上元素的排序区间的个数为________个。 21. 假定一组记录为(46,79,56,25,76,38,40,80)，对其进行快速排序的第一次划分后， 右区间内元素的个数为__________

22.假一组记承为(46,9,6,38.40)，对其进行快速排序的第一次划分后的结果 为 2公.程定一组记录为(46,79,56,38.40,80,4675)，对其进行归并排序的过程中，第二 墙归并后的第2个子表为 24.假定一组记录为(46,79,56,38.40,80.46,75,28,46)，对其进行力并排序的过程中， 第二墙归并后的子表个数为 25.假定一组记录为(6,79,56,38.40,80,46,75,28,46)，对其进行归并排序的过程中， 第三植归并后的第2个子表为 26.假定一组记录为(46,79,56,38.40,8046,75,2846)，对其法行月并推序的过程中， 供需要 崎完成。 27.假定一组记录为(46,79,56,38,40,80)，对其进行归并排序的过程中，第二随归并 后的结果为 8。在时间复桑性为0(loen)的所有持序方法中，伟序方法是稳定的。 29。在时间复杂性为0()的所有排序方法中，排序方法是不稳定的。 30。在所有排序方法中， 排序方法采用的是二分法的思想。 31.在所有持序方法中， 方法使数据的组织采用的是完全二叉树的结构： 32.在所有排序方法中， 方法采用的是两两有序表合并的思想。 33. 作序方法使健值大的记录递渐下沉，使健值小的记录还渐上浮。 3. 排序方法能够每次使无序表中的第一个记录插入到有序表中。 35. 排序方法能够每次从无序表中顺序查找出一个最小值。 (三)应用题 1.已知一组记录为(46,74,53,14,2638,86,65,27.30，给出采用直接插入排序法进行 排序时每一崎的排序结果。 2已知一组记录为(46,74,5队，14,26,38,86,65,27,34)，给出果用冒泡排序法送行排序 时每一趟的排序结果。 3己知一组记录为(46,74，忍，14,2838,8服，65,27,34)，给出采用快速排序法进行挂序 时每一墙的排序结果。 4.已知一组记录为(46,74,53,14,26.3褐，86,65,27.30，给出采用直接选择排序法进行 排序时每一墙的排序结果。 5己知一组记录为(46,74,53,14,2538,8665,27,34)，给出采用堆排序法进行排序到

6 22. 假定一组记录为(46,79,56,38,40,80)，对其进行快速排序的第一次划分后的结果 为____________________。 23．假定一组记录为(46,79,56,38,40,80,46,75)，对其进行归并排序的过程中，第二 趟归并后的第 2 个子表为________________。 24．假定一组记录为(46,79,56,38,40,80,46,75,28,46)，对其进行归并排序的过程中， 第二趟归并后的子表个数为________________。 25．假定一组记录为(46,79,56,38,40,80,46,75,28,46)，对其进行归并排序的过程中， 第三趟归并后的第 2 个子表为________________。 26．假定一组记录为(46,79,56,38,40,80,46,75,28,46)，对其进行归并排序的过程中， 供需要__________趟完成。 27．假定一组记录为(46,79,56,38,40,80)，对其进行归并排序的过程中，第二趟归并 后的结果为________________。 28. 在时间复杂性为 O(nlog2n)的所有排序方法中，________排序方法是稳定的。 29．在时间复杂性为 O(n2 )的所有排序方法中，________排序方法是不稳定的。 30．在所有排序方法中，________排序方法采用的是二分法的思想。 31．在所有排序方法中，________方法使数据的组织采用的是完全二叉树的结构。 32．在所有排序方法中，________方法采用的是两两有序表合并的思想。 33．________排序方法使键值大的记录逐渐下沉，使键值小的记录逐渐上浮。 34．________排序方法能够每次使无序表中的第一个记录插入到有序表中。 35．________排序方法能够每次从无序表中顺序查找出一个最小值。 （三）应用题 1. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用直接插入排序法进行 排序时每一趟的排序结果。 2. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用冒泡排序法进行排序 时每一趟的排序结果。 3. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用快速排序法进行排序 时每一趟的排序结果。 4. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用直接选择排序法进行 排序时每一趟的排序结果。 5. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用堆排序法进行排序时

每一墙的排序结果。 6已知一组记录为(46,74,5314,26.38,86,65,27,30，给出采用归并排序法进行排序 时每一墙的排序结果。 (四)算法设计题 1.已知奇钙转换排序方法如下所述：第一墙对所有奇数i,将a[i]和a[i+1]进行比较， 第二墙对所有偶数1，将a【1们和a[1+1]进行比较。每次比较时若a[们>a[1+1】,则将两者交 换，重复以上过程，直到整个爱组有序。 (》试月：排序结束的条件是什么？ 2)编写一个实现上述排序过程的算法：voi D oesort(inta0,int)。 2一个线性表中的元素的正整数或负整要，设计一个算法，将正整数和负整要分开， 使线性表的前部为负整数，后部为正整数，不要求对它们排序，但要求尽量减少交换次数。 3。编写一个直接桶入排序算法，使得查找插入位置时不是采用顺序的方法而是采用 二分的方法。 4.编写一个对整型数组A[+I]中的A[1]至A[]元素进行选释排序的算法，使得首先 从特排序区阿中选择出一个最小值并同第一个元素交换，再从特排序区间中选择出一个最大 值并同最后一个元素交换，反复进行直到待排序区间中元素的个数不超过1为止。 7

7 每一趟的排序结果。 6. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用归并排序法进行排序 时每一趟的排序结果。 （四）算法设计题 1. 已知奇偶转换排序方法如下所述：第一趟对所有奇数 i，将 a[i]和 a[i+1]进行比较， 第二趟对所有偶数 i，将 a[i]和 a[i+1]进行比较，每次比较时若 a[i]>a[i+1]，则将两者交 换，重复以上过程，直到整个数组有序。 (1) 试问：排序结束的条件是什么？ (2) 编写一个实现上述排序过程的算法：voi D oesort(int a[], int n)。 2. 一个线性表中的元素的正整数或负整数，设计一个算法，将正整数和负整数分开， 使线性表的前部为负整数，后部为正整数，不要求对它们排序，但要求尽量减少交换次数。 3．编写一个直接插入排序算法，使得查找插入位置时不是采用顺序的方法而是采用 二分的方法。 4．编写一个对整型数组 A[n+1]中的 A[1]至 A[n]元素进行选择排序的算法，使得首先 从待排序区间中选择出一个最小值并同第一个元素交换，再从待排序区间中选择出一个最大 值并同最后一个元素交换，反复进行直到待排序区间中元素的个数不超过 1 为止

陈习愿参考解答 (一)单适择题 1.A 2.C 3.D 4.B 5.C 6.C 7.B8D9.A10.B1L.D12.C 13.B14,D15.C16B17.C18.A 19.B20.D21.B22.C23.D24.B 25.D268.B27.D28A29.B30.A 31.D32.C33A34.B35.B36.C 37.D38.D (二)填空题 1,插入选择2.快速归井 3.0r)0n叫4./2n-l1 5.0logw0 nlog:n)6.-】1 7.O(nlogn)O(n)8.O(logzn)O(n) 9.Tloginl 10.O(n)O(nlogn)O(n) 11.54812.4 13.214.8 15.(3840,5679,4684016.(40,46,6679,84.38) 17.(46,56,38.40,79.84018.4 19.3204 21.422.【4038]46[567980] 23.4046758024.3 25.[2846]26.4 27.[38465679][4080】28.归并 29.直接选择30，快速 31.堆排序32归并排序 33.冒泡34.直接插入 35.直接遗择 (三)应用题 8

8 练习题参考解答 （一）单项选择题 1. A 2. C 3. D 4. B 5. C 6. C 7. B 8. D 9. A 10. B 11. D 12. C 13. B 14. D 15. C 16. B 17. C 18. A 19. B 20. D 21. B 22. C 23. D 24. B 25. D 26. B 27. D 28. A 29. B 30. A 31. D 32. C 33. A 34. B 35. B 36. C 37. D 38. D （二）填空题 1．插入 选择 2．快速 归并 3．O(n2 ) O(n) 4．n/2 n-1 5．O(log2n) O(nlog2n) 6．n-1 1 7．O(nlog2n) O(n2 ) 8. O(log2n) O(n) 9．log2n 10．O(n) O(nlog2n) O(n) 11．5 4 8 12．4 13．2 14．8 15. (38,40,56,79,46,84) 16. (40,46,56,79,84,38) 17. (46,56,38,40,79,84) 18. 4 19. 3 20. 4 21. 4 22．[40 38]46[56 79 80] 23．[40 46 75 80] 24．3 25. [28 46] 26. 4 27. [38 46 56 79][40 80] 28. 归并 29. 直接选择 30. 快速 31. 堆排序 32. 归并排序 33. 冒泡 34. 直接插入 35. 直接选择 （三）应用题 1

0[46】745314283886652734 (1)[4674]5314283886652734 2[465374]14253886652734 3)[144653741283886652734 (40[1428465374】3886652734 5[142638 465374)86652734 (6[14263846537486]652734 (7[1426384653657486]2734 8)[142827384653657486】34 9)[14262734384653657486] 2 0)【467453142838866527341 (1)[465314263874652734186 (2)[46142638536527340]7486 3)[14283846532734】657486 (40[142638462734]53657486 局【1428 38 27 34】465365748% (6)[142627341384653657486 (7)[142627341384653657486 3 0[46745314263886652734】 (1)[3427381426]46【8665 5374] 2)[252714】343846【746553】86 (3)142827343846【6365】7486 (4014262734384653657486 4 0)[467453142638866527341 (1)14[745346263886652734] (2)1428[5346743886652734】 (3142627【467438866553341

9 (0) [46] 74 53 14 26 38 86 65 27 34 (1) [46 74] 53 14 26 38 86 65 27 34 (2) [46 53 74] 14 26 38 86 65 27 34 (3) [14 46 53 74] 26 38 86 65 27 34 (4) [14 26 46 53 74] 38 86 65 27 34 (5) [14 26 38 46 53 74] 86 65 27 34 (6) [14 26 38 46 53 74 86] 65 27 34 (7) [14 26 38 46 53 65 74 86] 27 34 (8) [14 26 27 38 46 53 65 74 86] 34 (9) [14 26 27 34 38 46 53 65 74 86] 2. (0) [46 74 53 14 26 38 86 65 27 34] (1) [46 53 14 26 38 74 65 27 34] 86 (2) [46 14 26 38 53 65 27 34] 74 86 (3) [14 26 38 46 53 27 34] 65 74 86 (4) [14 26 38 46 27 34] 53 65 74 86 (5) [14 26 38 27 34] 46 53 65 74 86 (6) [14 26 27 34] 38 46 53 65 74 86 (7) [14 26 27 34] 38 46 53 65 74 86 3. (0) [46 74 53 14 26 38 86 65 27 34] (1) [34 27 38 14 26] 46 [86 65 53 74] (2) [26 27 14] 34 38 46 [74 65 53] 86 (3) 14 26 27 34 38 46 [53 65] 74 86 (4) 14 26 27 34 38 46 53 65 74 86 4. (0) [46 74 53 14 26 38 86 65 27 34] (1) 14 [74 53 46 26 38 86 65 27 34] (2) 14 26 [53 46 74 38 86 65 27 34] (3) 14 26 27 [46 74 38 86 65 53 34]

(4014282734[743886656346】 (5)1426273438[7486655346] 6142627343846【866553741 (7)14282734384653[658674] (8)1426273438465365[8674] 9142827343846536574【86】 5 构成初始堆（即建堆）的过程： 12345678910 0)4674531425388665273别 (1)46745314263886652734 2)46745314283886652734 (3)46743814265386652734 (4046143827265386657434 5)142838273456386657446 进行堆排序的过程： 0)14283827345386657448 (1)252738463453866574[14] 2)2734384674538665[25141 334463865745386[272614】 (4)38465365 85【34272614】 5)4665538674[3834272614] (6)53657486【463834272614] (7658674[53463834272614] 8)7486[6553463834272614】 (9)86[746553463834272614] 6 (0)[46[74][53][141[26][38][86][65][27][34] (1)【4674][1453[2638][6586][2734] 2)[144653741[28386686][2734] 10

10 (4) 14 26 27 34 [74 38 86 65 53 46] (5) 14 26 27 34 38 [74 86 65 53 46] (6) 14 26 27 34 38 46 [86 65 53 74] (7) 14 26 27 34 38 46 53 [65 86 74] (8) 14 26 27 34 38 46 53 65 [86 74] (9) 14 26 27 34 38 46 53 65 74 [86] 5. 构成初始堆（即建堆）的过程： 1 2 3 4 5 6 7 8 9 10 (0) 46 74 53 14 26 38 86 65 27 34 (1) 46 74 53 14 26 38 86 65 27 34 (2) 46 74 53 14 26 38 86 65 27 34 (3) 46 74 38 14 26 53 86 65 27 34 (4) 46 14 38 27 26 53 86 65 74 34 (5) 14 26 38 27 34 53 86 65 74 46 进行堆排序的过程： (0) 14 26 38 27 34 53 86 65 74 46 (1) 26 27 38 46 34 53 86 65 74 [14] (2) 27 34 38 46 74 53 86 65 [26 14] (3) 34 46 38 65 74 53 86 [27 26 14] (4) 38 46 53 65 74 86 [34 27 26 14] (5) 46 65 53 86 74 [38 34 27 26 14] (6) 53 65 74 86 [46 38 34 27 26 14] (7) 65 86 74 [53 46 38 34 27 26 14] (8) 74 86 [65 53 46 38 34 27 26 14] (9) 86 [74 65 53 46 38 34 27 26 14] 6. (0) [46][74][53][14][26][38][86][65][27][34] (1) [46 74][14 53][26 38][65 86][27 34] (2) [14 46 53 74][26 38 65 86][27 34]