数据结构习题汇编09第九章排序试题
数据结构课程（本科）第九章试题
下列算法中（ ）算法不具有这样的特
性：
对某些输入序列，可能不需要移动数据对象即可完成
排序。
A. 起泡排序
B. 希尔排序
C. 快速排序
D.
直接选择排序 1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
单项选择题 若待排序对象序列在排序前已按其排序码递增顺序排列，则采用（ A. 直接插入排序 B. 快速排序 C. 归并排序 D. 直接选择排序 如果只想得到 1024 个元素组成的序列中的前 5 个最小元素，那么用（ A. 起泡排序 B. 快速排序 C. 直接选择排序 D. 堆排序 ）方法比较次数最少。 ）方法最快。 对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作， 直到子序列为空或只剩一个元素为止。这样的排序方法是（ ）。 A. 直接选择排序 B. 直接插入排序 C. 快速排序 D. 起泡排序 对 5 个不同的数据元素进行直接插入排序，最多需要进行（ A. 8 B. 10 ）次比较？ C. 15 D. 25 如果输入序列是已经排好顺序的，则下列算法中（ ）算法最快结束？ A. 起泡排序 B. 直接插入排序 C. 直接选择排序 D. 快速排序 如果输入序列是已经排好顺序的，则下列算法中（ ）算法最慢结束？ A. 起泡排序
B. 直接插入排序
C. 直接选择排序
D. 快速排序
下列排序算法中（ ）算法是不稳定的。 A. 起泡排序 B. 直接插入排序 C. 基数排序 D. 快速排序 假设某文件经过内部排序得到 100 个初始归并段， 那么如果要求利用多路平衡归并在 3 趟内完成排序， 则应取的归并路数至少是（ ）。 A. 3 B. 4 C. 5 D. 6 采用任何基于排序码比较的算法，对 5 个互异的整数进行排序，至少需要（ ）次比较。 A. 5
B. 6
C. 7
D. 8
准而)得到的第一次划分结果为：
15. 如果将所有中国人按照生日 (不考虑年份， 只考虑月、 日)来排序， 那么使用下列排序算法中 (
)
算法最快。
A. 归并排序
B. 希尔排序
C. 快速排序
D. 基数排序
参考答案：
1. A
2. D
3. C
4. B
5. A
6. D
7. D
8. C
9. C 10. C
11. D
12. C
13. C
14. C
15. D
、填空题
1.
第i(i = 1,2
，…,n -1)趟从参加排序的序列中取出第
元素组成的有序表中适当的位置，此种排序方法叫做 _ 2.
第i (i = 0, 1, …,n -2)趟从参加排序的序列中第
素，把它交换到第 i 个位置，此种排序方法叫做 __ 3.
每次直接或通过基准元素间接比较两个元素，若出现逆序排列，就交换它们的位置，这种排序方法叫 做 排序。 4. 每次使两个相邻的有序表合并成一个有序表，这种排序方法叫做
________ 排序。
5.
在直接选择排序中，排序码比较次数的时间复杂度为 O( ____________ ) 。
11. 使用递归的归并排序算法时， 为了保证排序过程的时间复杂度不超过
O(nlog 2n) ，必须做到 ( )。
A. 每次序列的划分应该在线性时间内完成
B. 每次归并的两个子序列长度接近
C. 每次归并在线性时间内完成
D. 以上全是
12. 在基于 排序码 比较的排序算法中， (
A. 起泡排序 C. 归并排序
)算法的最坏情况下的时间复杂度不 高于0(nlog 2n)。
B. 希尔排序 D. 快速排序
13. 在下列排序算法中， ( A.
锦标赛排序 C. 基数排序
)算法使用的附加空间与输入序列的长度及初始排列无关。
B. 快速排序 D. 归并排序
14. 一个对象序列的排序码为 { 46, 79, 56, 38, 40, 84
} ，采用快速排序(以位于最左位置的对象为基 A. { 38, 46, 79, 56, 40, 84 } C. { 40, 38, 46, 79, 56, 84 }
B. { 38, 79, 56, 46, 40, 84 } D. { 38, 46, 56, 79, 40, 84 }
i 个元素，把它插入到由第
0个?第i-1个
___排序。
i 个?第 n-1 个元素中挑选出一个最小(大)元
___排序。
6. 在直接选择排序中，数据对象移动次数的时间复杂度为O( ____________ )。
7. 在堆排序中，对n 个对象建立初始堆需要调用___________ 次调整算法。
8. 在堆排序中，如果n 个对象的初始堆已经建好，那么到排序结束，还需要从堆顶结点出发调用次调整算法。
9. 在堆排序中，对任一个分支结点进行调整运算的时间复杂度为O( _____________ ) 。
10. 对n 个数据对象进行堆排序，总的时间复杂度为O( ___________ )。
11. 给定一组数据对象的排序码为{ 46, 79, 56, 38, 40, 84 } ，则利用堆排序方法建立的初始堆
堆) 为_______ 。
12. 快速排序在平均情况下的时间复杂度为
13. 快速排序在最坏情况下的时间复杂度为
14. 快速排序在平均情况下的空间复杂度为
15. 快速排序在最坏情况下的空间复杂度为
16. 给定一组数据对象的排序码为{46, 79, 56, 38, 40, 84} ，对其进行一趟快速排序，结果为
17.在n 个数据对象的二路归并排序中，每趟归并的时间复杂度为O(__
_____ ) 。
18.在n
个数据对象的二路归并排序
中，
整个归并的时间复杂度为
O(__
__) 。
参考答案： 1. 插入 2. 直接选择 3.交换
4. 两路归并
5. n 2
6.n
7. ?n/2?8. n-19.log 2n
10. nlog 2n11. 84, 79, 56, 38, 40, 4612.nlog 2n
13. n 214. log 2n1
5. n
16. [40 38] 46 [79 56 84]17. n18.nlog 2n
三、判断题
1. 直接选择排序是一种稳定的排序方法。
2. 若将一批杂乱无章的数据按堆结构组织起来, 则堆中各数据是否必然按自小到大的顺序排列起来。
3. 当输入序列已经有序时，起泡排序需要的排序码比较次数比快速排序要少。
4. 在任何情况下，快速排序需要进行的排序码比较的次数都是O(nlog 2n) 。
5. 在2048 个互不相同的排序码中选择最小的5 个排序码，用堆排序比用锦标赛排序更快。
6. 若用m个初始归并段参加k路平衡归并排序，则归并趟数应为？log 2m?。
最大
7. 堆排序是一种稳定的排序算法。
8. 对于某些输入序列，起泡排序算法可以通过线性次数的排序码比较且无需移动数据对象就可以完成排序。
9. 如果输入序列已经排好序，则快速排序算法无需移动任何数据对象就可以完成排序。
10. 希尔排序的最后一趟就是起泡排序。
11. 任何基于排序码比较的算法，对n 个数据对象进行排序时，最坏情况下的时间复杂度不会低于O(nlog 2n) 。
12. 不存在这样一个基于排序码比较的算法：它只通过不超过
9 次排序码的比较，就可以对任何6 个排序
码互异的数据对象实现排序。
参考答案： 1. 否 2. 否 3. 是 4. 否 5. 否
6. 否
7. 否
8. 是
9. 否10. 是
11. 是12. 是
四、运算题
1. 判断以下序列是否是最小堆？如果不是, 将它调整为最小堆。
(1) { 100, 86, 48, 73, 35, 39, 42, 57, 66, 21 }
(2) { 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 } 。
2. 在不要求完全排序时，堆排序是一种高效的算法。这种算法的过程是：
( Heapification )把待排序序列看作一棵完全二叉树，通过反复筛选将其调整为堆；
( Re-heapification )依次取出堆顶，然后将剩余的记录重新调整为堆。现考虑序列 A = { 23，41，7，5，
56 } ：
(1) 给出对应于序列A的最小堆H A (以线性数组表示)；
(2) 给出第一次取出堆顶后，重新调整W后的结果(以线性数组表示)；
(3) 给出第二次取出堆顶后，重新调整H A后的结果(以线性数组表示)。
3. 希尔排序、直接选择排序、快速排序和堆排序是不稳定的排序方法, 试举例说明。
4. 给出12 个初始归并段，其长度分别为19, 22, 17, 16, 11, 10, 12, 32, 26, 20, 28, 07 。现要做4 路外归
并排序，试画出表示归并过程的最佳归并树，并计算该归并树的带权路径长度WPL。
5. 设输入文件包含以下数据对象的排序码：14, 22, 7, 16, 11, 10, 12, 90, 26, 30, 28, 110 。现采
用置换—选择方法生成初始归并段，并假设内存工作区可同时容纳 5 个数据对象，请画出生成初始归并段的过程。
6. 在利用置换—选择方法生成初始归并段时，可另开辟一个与工作区容量相同的辅助存储区(称为储备
库)。当输入对象排序码小于刚输出的门槛LastKey对象的排序码时，不将它存入工作区，而暂存于
储备库中，接着输入下一对象的排序码，依次类推，直到储备库满时不再进行输入，而只是从工作区中选择对象输出直至工作区空为止，由此得到一个初始归并段。然后再将储备库中的对象传送至工作区，重新开始置换一选择。
数据结构第九章排序习题与答案
习题九排序 一、单项选择题 1．下列内部排序算法中： A．快速排序 B.直接插入排序 C. 二路归并排序 D.简单选择排序 E. 起泡排序 F.堆排序 （1）其比较次数与序列初态无关的算法是（） （2）不稳定的排序算法是（） （3）在初始序列已基本有序（除去n 个元素中的某 k 个元素后即呈有序， k< 数据结构课程（本科）第九章试题 一、单项选择题 1.若待排序对象序列在排序前已按其排序码递增顺序排列，则采用（）方法比较次数最少。 A. 直接插入排序 B. 快速排序 C. 归并排序 D. 直接选择排序 2.如果只想得到1024个元素组成的序列中的前5个最小元素，那么用（）方法最快。 A. 起泡排序 B. 快速排序 C. 直接选择排序 D. 堆排序 3.对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作， 直到子序列为空或只剩一个元素为止。这样的排序方法是（）。 A. 直接选择排序 B. 直接插入排序 C. 快速排序 D. 起泡排序 4.对5个不同的数据元素进行直接插入排序，最多需要进行（）次比较？ A. 8 B. 10 C. 15 D. 25 5.如果输入序列是已经排好顺序的，则下列算法中（）算法最快结束？ A. 起泡排序 B. 直接插入排序 C. 直接选择排序 D. 快速排序 6.如果输入序列是已经排好顺序的，则下列算法中（）算法最慢结束？ A. 起泡排序 B. 直接插入排序 C. 直接选择排序 D. 快速排序 7.下列排序算法中（）算法是不稳定的。 A. 起泡排序 B. 直接插入排序 C. 基数排序 D. 快速排序 8.假设某文件经过内部排序得到100个初始归并段，那么如果要求利用多路平衡归并在3 趟内完成排 序，则应取的归并路数至少是（）。 A. 3 B. 4 C. 5 D. 6 9.采用任何基于排序码比较的算法，对5个互异的整数进行排序，至少需要（）次比较。 A. 5 B. 6 C. 7 D. 8 10.下列算法中（）算法不具有这样的特性：对某些输入序列，可能不需要移动数据对象即可完成 排序。 A. 起泡排序 B. 希尔排序 C. 快速排序 D. 直接选择排序 11.使用递归的归并排序算法时，为了保证排序过程的时间复杂度不超过O(nlog2n)，必须做到（）。 数据结构各种排序算法总结 2009-08-19 11:09 计算机排序与人进行排序的不同：计算机程序不能象人一样通览所有的数据，只能根据计算机的"比较"原理，在同一时间内对两个队员进行比较，这是算法的一种"短视"。 1. 冒泡排序 BubbleSort 最简单的一个 public void bubbleSort() { int out, in; for(out=nElems-1; out>0; out--) // outer loop (backward) for(in=0; in swap(out, min); // swap them } // end for(out) } // end selectionSort() 效率：O(N2) 3. 插入排序 insertSort 在插入排序中，一组数据在某个时刻实局部有序的，为在冒泡和选择排序中实完全有序的。 public void insertionSort() { int in, out; for(out=1; out 1．下列排序算法中，其中（）是稳定的。 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序 2．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。 A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序3．排序趟数与序列的原始状态有关的排序方法是( )排序法。 A．插入 B. 选择 C. 冒泡 D. 快速4．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中 的变化为（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47 （4） 15 21 25 47 84 则采用的排序是( )。 A. 选择 B. 冒泡 C. 快速 D. 插入5．对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（）排序。 A. 选择 B. 快速 C. 希尔 D. 冒泡6．若上题的数据经一趟排序后的排列为{9，15，7，8，20，-1，4}，则采用的 是（）排序。 A．选择 B. 堆 C. 直接插入 D. 冒泡 7．在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（）A．直接插入排序B．冒泡排序C．简单选择排序 8．下列排序算法中，（）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。 A. 堆排序 B. 冒泡排序 C. 快速排序 D. 插入排序 9. 下列排序算法中，占用辅助空间最多的是：( ) A. 归并排序 B. 快速排序 C. 希尔排序 D. 堆排序10．用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数 最少的是（）。 A．94,32,40,90,80,46,21,69 B．32,40,21,46,69,94,90,80 C．21,32,46,40,80,69,90,94 D．90,69,80,46,21,32,94,40 11. 若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（）次比较。 A. 3 B. 10 C. 15 D. 25 12．对n个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确 第10章内部排序习题练习答案 1.以关键字序列(265，301，751，129，937，863，742，694，076，438)为例，分别写出执行以下排序算法的各趟排序结束时，关键字序列的状态。 (1) 直接插入排序(2)希尔排序(3)冒泡排序(4)快速排序 (5) 直接选择排序(6) 堆排序(7) 归并排序(8)基数排序 上述方法中，哪些是稳定的排序?哪些是非稳定的排序?对不稳定的排序试举出一个不稳定的实例。 答： (1)直接插入排序:(方括号表示无序区) 初始态: 265[301 751 129 937 863 742 694 076 438] 第一趟：265 301[751 129 937 863 742 694 076 438] 第二趟：265 301 751[129 937 863 742 694 076 438] 第三趟：129 265 301 751[937 863 742 694 076 438] 第四趟：129 265 301 751 937[863 742 694 076 438] 第五趟：129 265 301 751 863 937[742 694 076 438] 第六趟：129 265 301 742 751 863 937[694 076 438] 第七趟：129 265 301 694 742 751 863 937[076 438] 第八趟：076 129 265 301 694 742 751 863 937[438] 第九趟：076 129 265 301 438 694 742 751 863 937 (2)希尔排序(增量为5，3，1) 初始态: 265 301 751 129 937 863 742 694 076 438 第一趟：265 301 694 076 438 863 742 751 129 937 第二趟：076 301 129 265 438 694 742 751 863 937 第三趟：076 129 265 301 438 694 742 751 863 937 (3)冒泡排序(方括号为无序区) 初始态[265 301 751 129 937 863 742 694 076 438] 第一趟：076 [265 301 751 129 937 863 742 694 438] 第二趟：076 129 [265 301 751 438 937 863 742 694] 第三趟：076 129 265 [301 438 694 751 937 863 742] 第四趟：076 129 265 301 [438 694 742 751 937 863] 第五趟：076 129 265 301 438 [694 742 751 863 937] 第六趟：076 129 265 301 438 694 742 751 863 937 (4)快速排序：（方括号表示无序区，层表示对应的递归树的层数） 数据结构-各类排序算法总结 原文转自： https://www.docsj.com/doc/b012663968.html,/zjf280441589/article/details/38387103各类排序算法总结 一. 排序的基本概念 排序(Sorting)是计算机程序设计中的一种重要操作，其功能是对一个数据元素集合或序列重新排列成一个按数据元素 某个项值有序的序列。 有n 个记录的序列{R1，R2，…，Rn}，其相应关键字的序列是{K1，K2，…，Kn}，相应的下标序列为1，2，…，n。通过排序，要求找出当前下标序列1，2，…，n 的一种排列p1，p2，…，pn，使得相应关键字满足如下的非递减（或非递增）关系，即：Kp1≤Kp2≤…≤Kpn，这样就得到一个按关键字有序的记录序列{Rp1，Rp2，…，Rpn}。 作为排序依据的数据项称为“排序码”，也即数据元素的关键码。若关键码是主关键码，则对于任意待排序序列，经排序后得到的结果是唯一的；若关键码是次关键码，排序结果可 能不唯一。实现排序的基本操作有两个： （1）“比较”序列中两个关键字的大小； （2）“移动”记录。 若对任意的数据元素序列，使用某个排序方法，对它按关键码进行排序：若相同关键码元素间的位置关系，排序前与排序后保持一致，称此排序方法是稳定的；而不能保持一致的排序方法则称为不稳定的。 二.插入类排序 1.直接插入排序直接插入排序是最简单的插入类排序。仅有一个记录的表总是有序的，因此，对n 个记录的表，可从第二个记录开始直到第n 个记录，逐个向有序表中进行插入操作，从而得到n个记录按关键码有序的表。它是利用顺序查找实现“在R[1..i-1]中查找R[i]的插入位置”的插入排序。 一、插入排序(Insertion Sort) 1. 基本思想： 每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。 2. 排序过程： 【示例】： [初始关键字] [49] 38 65 97 76 13 27 49 J=2(38) [38 49] 65 97 76 13 27 49 J=3(65) [38 49 65] 97 76 13 27 49 J=4(97) [38 49 65 97] 76 13 27 49 J=5(76) [38 49 65 76 97] 13 27 49 J=6(13) [13 38 49 65 76 97] 27 49 J=7(27) [13 27 38 49 65 76 97] 49 J=8(49) [13 27 38 49 49 65 76 97] 1 2Procedure InsertSort(Var R : FileType); 3//对R[1..N]按递增序进行插入排序, R[0]是监视哨// 4 Begin 5 for I := 2 To N Do //依次插入R[2],...,R[n]// 6 begin 7 R[0] := R; J := I - 1; 8 While R[0] < R[J] Do //查找R的插入位置// 9 begin 10 R[J+1] := R[J]; //将大于R的元素后移// 11 J := J - 1 12 end 13 R[J + 1] := R[0] ; //插入R // 14 end 15 End; //InsertSort // 复制代码 排序算法操作 课程名称：数据结构研究 论文题目：排序算法操作 院系： 学生姓名： 学号： 专业班级： 年月日 数据结构之排序算法操作 摘要：本文通过对数据结构中排序算法深入研究,实现了排序算法中的直接插入排序、快速排序和简单选择排序操作，进一步加深了对数据结构中排序算法的理解，得到的算法可以应用到以后的编程实践中。 关键词：排序时间复杂度空间复杂度稳定性 1.引言 排序是日常生活和工作中的一个常见问题，其目的是将一组原本无序的数据元素（或记录）序列，按照人们所需要的顺序，排列成有规律的按关键字有序的序列。 在现实生活中，人们要用到排序。如：学生成绩往往需要按照成绩高低或按学号从前到后排序；在图书馆众多的图书中，需要按照各个学科将书籍归类；排队时从高到低的顺序排队等问题。同样，排序也是计算机程序设计中的一个非常重要的操作，在计算机软件设计中占有极其重要的地位。本文将对排序算法中直接插入排序、快速排序和简单选择排序三种算法的实现做一些研究。 2.算法的实现 直接插入排序算法中，第i趟进行的操作为：在含有i-1个记录的有序子序列r[1…i-1]中插入一个记录r[i]后，变成含有i个记录的有序子序列r[1….i]；并且为了在查找插入位置的过程中避免数组下标出界，在r[0]处设置监视哨，在自i-1起往前搜索的过程中，可以同时后移记录。 算法1 直接插入排序算法 Step1:从第二个记录起逐个进行关键字与前面关键字的比较并判断是否把该记录作为哨兵 for ( i=2; i<=L.length; ++i ) if(LT(L.r[i].key, L.r[i-1].key)) 第九章 查找 一、填空题 1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。 2. 线性有序表（a 1，a 2，a 3，…，a 256)是从小到大排列的，对一个给定的值k ，用二分法检索 表中与k 相等的元素，在查找不成功的情况下，最多需要检索 8 次。设有100个结点，用二分法查找时，最大比较次数是 7 。 3. 假设在有序线性表a[1..20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ,其下标从小到大依次是1,3,6,8,11,13,16,19______，平均查找长度为 3.7 。 解：显然，平均查找长度＝O （log 2n ）<5次（25）。但具体是多少次，则不应当按照公式 )1(log 12++=n n n ASL 来计算（即（21×log 221）/20＝4.6次并不正确！）。因为这是在假设n ＝2m -1 的情况下推导出来的公式。应当用穷举法罗列： 全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL ＝74/20=3.7 ！！！ 4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它 将依次与表中元素 28，6，12，20 比较大小。 5. 在各种查找方法中，平均查找长度与结点个数n 无关的查找方法是 散列查找 。 6. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。 7. 有一个表长为m 的散列表，初始状态为空，现将n （n 第10章排序 一、选择题 1．某内排序方法的稳定性是指( )。【南京理工大学 1997 一、10（2分）】A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录 C．平均时间为0（n log n）的排序方法 D．以上都不对 2．下面给出的四种排序法中( )排序法是不稳定性排序法。【北京航空航天大学 1999 一、 10 （2分）】 A. 插入 B. 冒泡 C. 二路归并 D. 堆积 3．下列排序算法中，其中（）是稳定的。【福州大学 1998 一、3 (2分)】 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序 4．稳定的排序方法是（）【北方交通大学 2000 二、3（2分）】 A．直接插入排序和快速排序 B．折半插入排序和起泡排序 C．简单选择排序和四路归并排序 D．树形选择排序和shell排序 5．下列排序方法中，哪一个是稳定的排序方法？（）【北方交通大学 2001 一、8（2分）】 A．直接选择排序 B．二分法插入排序 C．希尔排序 D．快速排序6．若要求尽可能快地对序列进行稳定的排序，则应选（A．快速排序 B．归并排序 C．冒泡排序）。 【北京邮电大学 2001 一、5（2分）】 7．如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。（）就是不稳定的排序方法。【清华大学 1998 一、3 (2分）】 A．起泡排序 B．归并排序 C．Shell排序 D．直接插入排序 E．简单选择排序 8．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（）排序为宜。 A．直接插入 B．直接选择 C．堆 D．快速 E．基数【中科院计算所 2000 一、5（2分）】 9．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。 A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序【中国科技大学 1998 二、4（2分）】【中科院计算所 1998 二、4（2分）】 10．下面的排序算法中，不稳定的是（）【北京工业大学 1999 一、2 (2分)】 A.起泡排序 B.折半插入排序 C.简单选择排序 D.希尔排序 E.基数排序 F.堆排序。 11．下列内部排序算法中：【北京工业大学 2000 一、1 (10分每问2分)】A．快速排序 B.直接插入排序 C. 二路归并排序 D. 简单选择排序 E. 起泡排序F. 堆排序 （1）其比较次数与序列初态无关的算法是（）（2）不稳定的排序算法是（）（3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k< 数据结构各种排序算法总结 计算机排序与人进行排序的不同：计算机程序不能象人一样通览所有的数据，只能根据计算机的"比较"原理，在同一时间内对两个队员进行比较，这是算法的一种"短视"。 1. 冒泡排序BubbleSort 最简单的一个 public void bubbleSort() { int out, in; for(out=nElems-1; out>0; out--) // outer loop (backward) for(in=0; in 3. 插入排序insertSort 在插入排序中，一组数据在某个时刻实局部有序的，为在冒泡和选择排序中实完全有序的。public void insertionSort() { int in, out; for(out=1; out 第10章内部排序 一、单项选择题 1．若要尽可能地完成对实数数组得排序，且要求排序是稳定的，则应选______。 A．快速排序 B．堆排序 C．归并排序 D．基数排序 2．如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用______方法最快。 A．冒泡排序 B．快速排序 C．希尔排序 D．堆排序 E．简单选择排序 3．将两个各有N个元素的有序表归并成一个有序表，其最小的比较次数是______。 A．N B．2N-1 C．2N D．N-1 4．就平均性能而言，目前最好的内排序方法是______排序法。 A．冒泡排序 B．希尔排序 C．插入排序 D．快速排序 5．若需要在O(nlog2n)的时间内完成对数据的排序，且要求排序是稳定的，则可选择的排序方法是______。 A．快速排序 B．堆排序 C．归并排序 D．直接插入排序 6．下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是______。 A．选择排序法 B．插入排序法 C．快速排序法 D．堆排序法 7．数据序列｛8，9，10，4，5，6，20，1，2｝只能是下列排序算法中的（）的两趟排序后的结果。 A．选择排序 B．冒泡排序 C．插入排序 D．堆排序 8．对一组数据｛84，47，25，15，21｝排序，第一趟的排序结果为15，47，25，84，21；第二趟排序的结果为15，21，25，84，47；第三趟排序的结果为15，21，25，47，84，则采用排序的方法是______。 A．选择排序 B．冒泡排序 C．快速排序 D．插入排序 9．下列排序算法中______排序在一趟结束后不一定能选出一个元素放在其最终位置上。 A．选择排序 B．冒泡排序 C．归并排序 D．堆排序 10．在下面的排序方法中，辅助空间为O（n）的是______。 A．希尔排序 B．堆排序 C．选择排序 D．归并排序 11．直接插入排序在最好的情况下的时间复杂度为______。 A．O（log2n） B．O(n) C． O(nlog2n) D．O(n2) 12．若用冒泡排序方法对序列{10，14，26，29，41，52}从大到小排序，需进行______次比较。 A．3 B．10 C．15 Ｄ．25 13．对序列{15，9，7，8，20，-1，4}用希尔排序方法排序，经过一趟后序列变为{15，-1，4，8，20，9，7}，则该次采用的增量是 ______。 A．1 B．4 C．3 D．2 14．对下列关键字序列用快速排序法进行排序，速度最快的情形是 第十章内部排序 10.23 void Insert_Sort1(SqList &L)//监视哨设在高下标端的插入排序算法 { k=L.length; for(i=k-1;i;--i) //从后向前逐个插入排序 if(L.r[i].key>L.r[i+1].key) { L.r[k+1].key=L.r[i].key; //监视哨 for(j=i+1;L.r[j].key>L.r[i].key;++j) L.r[j-1].key=L.r[j].key; //前移 L.r[j-1].key=L.r[k+1].key; //插入 } }//Insert_Sort1 10.24 void BiInsert_Sort(SqList &L)//二路插入排序的算法 { int d[MAXSIZE]; //辅助存储 x=L.r.key;d=x; first=1;final=1; for(i=2;i<=L.length;i++) { if(L.r[i].key>=x) //插入前部 { for(j=final;d[j]>L.r[i].key;j--) d[j+1]=d[j]; d[j+1]=L.r[i].key; final++; } else //插入后部 { for(j=first;d[j] 数据结构排序超级总结 一、插入排序(Insertion Sort) 1. 基本思想： 每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。 2. 排序过程： 【示例】： [初始关键字] [49] 38 65 97 76 13 27 49 J=2(38) [38 49] 65 97 76 13 27 49 J=3(65) [38 49 65] 97 76 13 27 49 J=4(97) [38 49 65 97] 76 13 27 49 J=5(76) [38 49 65 76 97] 13 27 49 J=6(13) [13 38 49 65 76 97] 27 49 J=7(27) [13 27 38 49 65 76 97] 49 J=8(49) [13 27 38 49 49 65 76 97] 1 2Procedure InsertSort(Var R : FileType); 3//对R[1..N]按递增序进行插入排序, R[0]是监视哨// 4Begin 5for I := 2 To N Do //依次插入 R[2],...,R[n]// 6begin 7R[0] := R; J := I - 1; 8While R[0] < R[J] Do //查找R的插入位置// 9begin 10R[J+1] := R[J]; //将大于R的元素后移// 11J := J - 1 12end 13R[J + 1] := R[0] ; //插入R // 14end 15End; //InsertSort // 复制代码 二、选择排序 1. 基本思想： 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 9.1选择题 1．从末排序的序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在排序序列的合适位置，该排序方法称为（）排序法。 A）插入B）选择C）希尔D）二路归并 【答案】A 2．下面各种排序方法中，最好情况下时间复杂度为O(n)的是（） A）快速排序B）直接插入排序C）堆排序D）归并排序 【答案】B 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．下面给出的四种排序法中，（）排序是不稳定排序法。 A）插入B）冒泡C）二路归并D）堆 【答案】D 5．快速排序方法在（）情况下最不利于发挥其长处。 Ａ）要排序的数据量太大 Ｂ）要排序的数据中含有多个相同值 Ｃ）要排序的数据已基本有序 Ｄ）要排序的数据个数为奇数 【答案】Ｃ 6．一组记录的关键码为（46,79,56,38,40,84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（） Ａ）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 【答案】Ｃ 7．对记录的关键码{50，26，38，80，70，90，8，30，40，20}进行排序，各趟排序结束时的结果为： 50,26,38,80,70,90 ,8,30,40,20 50,8,30,40,20,90,26,38,80,70 26,8,30,40,20,80,50,38,90,70 8,20,26,30,38,40,50,70,80,90 其使用的排序方法是（） A）快速排序B）基数排序C）希尔排序D）归并排序 【答案】C 8．以下序列不是堆的是（） 目录 1.引言............................................................................................................................ 错误！未定义书签。 2.需求分析 (2) 3.详细设计 (2) 3.1 直接插入排序 (2) 3.2折半排序 (2) 3.3 希尔排序 (4) 3.4简单选择排序 (4) 3.5堆排序 (4) 3.6归并排序 (5) 3.7冒泡排序 (7) 4.调试 (8) 5.调试及检验 (9) 5.1 直接插入排序 (9) 5.2折半插入排序 (9) 5.3 希尔排序 (10) 5.4简单选择排序 (10) 5.5堆排序 (11) 5.6归并排序 (12) 5.7冒泡排序 (12) 6.测试与比较................................................................................................................ 错误！未定义书签。 6.1调试步骤......................................................................................................... 错误！未定义书签。 6.2结论 (13) 7.实验心得与分析 (13) 8.附录 (15) 8.1直接插入排序 (15) 8.2折半插入排序 (16) 8.3希尔排序 (18) 8.4简单选择排序 (20) 8.5堆排序 (21) 8.6归并排序 (24) 8.7冒泡排序 (27) 8.8主程序 (28) 一、单选题 12．设有5000个无序的元素，希望用最快的速度挑选出其中前50个最大的元素，最好选用( )法。A．冒泡排序B．快速排序C．堆排序D．归并排序 1．已知持排序的n个元素可分为n/k个组，每个组包含k个元素，各组间分块有序，若采用基于比较的排序，其时间下界应为：( ) A．O(nlog2n) B．O(nlog2k) C．O(klog2n) D．O(klog2k) )且稳定的排序方法是( )。 2．最好和最坏时间复杂度均为O(n nlog 2 A．快速排序B．堆排序C．归并排序D．基数排序 3．下列排序算法中，当初始数据有序时，花费时间反而最多的是( )。 A．起泡排序B．希尔排序C．堆排序D．快速排序 4．若需在O（nlog2n）的时间内完成排序，且要求稳定，则可选择（） A．快速排序B．堆排序C．归并排序D．直接插入排序 5．排序趟数与序列的原始状态有关的排序方法是( )排序法。 A．插入B．选择C．希尔D．快速 6．已知数据表每个元素距离其最终位置不远，则最省时间的排序算法是( )。 A．堆排序B．直接插入排序C．快速排序D．直接选择排序 7．关键字比较次数与数据的初始状态无关的排序算法是( )。 A．直接选择排序B．冒泡排序C．直接插入排序D．希尔排序 8. 若一个元素序列基本有序，则选用（）方法较快。 A．直接插入排序B．直接选择排序C．堆排序D．快速排序 9. 若要从1000个元素中得到4个最小值元素，最好采用（）方法。 A．直接插入排序B．直接选择排序C．堆排序D．快速排序 10. 若要对1000个元素排序，要求既快又稳定，则最好采用（）方法。 A．直接插入排序B．归并排序C．堆排序D．快速排序 11. 若要对1000个元素排序，要求既快又节省存储空间，则最好采用（）方法。 A．直接插入排序B．归并排序C．堆排序D．快速排序 12. 在下列排序方法中，空间复杂性为O(log2n)的方法为（）。 A．直接选择排序B．归并排序C．堆排序D．快速排序 13. 在平均情况下速度最快的排序方法为（）。 A．直接选择排序B．归并排序C．堆排序D．快速排序 14、设有关键字初始序列{Q,H,C,Y,P,A,M,S,R,D,F,X}，则用下列哪种排序方法进行第一趟扫描的结果为{F,H,C,D,P,A,M,Q,R,S,Y,X}？ A．直接插入排序B．二路归并排序 C．以第一元素为基准的快速排序D．基数排序 15．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。 A．插入B．选择C．希尔D．二路归并 16．下面排序法中，( )排序法是不稳定的。 A．插入B．冒泡C．二路归并D．堆 17.下列排序方法中，不稳定的是（） A．直接插入排序B．冒泡排序C．归并排序D．直接选择排序 18. 在直接插入排序的第i趟排序前，有序表中的元素个数为（）。 A．i B．i+1 C．i-1 D．1 19. 在直接插入排序的第i趟排序时，为寻找插入位置最多需要进行（）次元素的比较，假定第0号元 第9章查找 一、选择题 1.顺序查找一个共有n个元素的线性表，其时间复杂度为（），折半查找一个具有n个元素的有序表，其时间复 杂度为（）。【＊，★】 A.O(n) B. O(log2n) C. O(n2) D. O(nlog2n) 2.在对长度为n的顺序存储的有序表进行折半查找，对应的折半查找判定树的高度为（）。【＊，★】 A.n B. C. D. 3.采用顺序查找方式查找长度为n的线性表时，平均查找长度为（）。【＊】 A.n B. n/2 C. (n+1)/2 D. (n-1)/2 4.采用折半查找方法检索长度为n的有序表，检索每个元素的平均比较次数（）对应判定树的高度（设高度大于 等于2）。【＊＊】 A.小于 B. 大于 C. 等于 D. 大于等于 5.已知有序表（13，18，24，35，47，50，62，83，90，115，134），当折半查找值为90的元素时，查找成功 的比较次数为（）。【＊】 A. 1 B. 2 C. 3 D. 4 6.对线性表进行折半查找时，要求线性表必须（）。【＊】 A.以顺序方式存储 B. 以链接方式存储 C.以顺序方式存储，且结点按关键字有序排序 D. 以链接方式存储，且结点按关键字有序排序 7.顺序查找法适合于存储结构为（）的查找表。【＊】 A.散列存储 B. 顺序或链接存储 C. 压缩存储 D. 索引存储 8.采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在 的块时，每块应分（）个结点最佳。【＊＊】 A.10 B. 25 C. 6 D. 625 9.从键盘依次输入关键字的值：t、u、r、b、o、p、a、s、c、l，建立二叉排序树，则其先序遍历序列为（）， 中序遍历序列为（）。【＊＊，★】 A.abcloprstu B. alcpobsrut C. trbaoclpsu D. trubsaocpl 10.折半查找和二叉排序树的时间性能（）。【＊】 A.相同 B. 不相同 11.一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有（）个结点。 A.2k-1-1 B. 2k-1 C. 2k-1+1 D. 2k-1 12.利用逐点插入法建立序列{50，72，43，85，75，20，35，45，65，30}对应的二叉排序树以后，查找元素35要《数据结构》知识题汇编09第九章排序试题
数据结构 各种排序算法
数据结构第十章习题课
中南大学数据结构与算法第10章内部排序课后作业答案
数据结构-各类排序算法总结
大数据结构排序超级总结材料
数据结构之排序算法操作论文
数据结构第九、十章 作业答案
目前最完整的数据结构1800题包括完整答案 第十章 排序
数据结构各种排序算法总结
数据结构第10章 内部排序习题
数据结构严蔚敏版第十章答案
数据结构排序超级总结
数据结构第10章排序练习及答案
数据结构各种排序实验报告
数据结构排序部分练习题
《数据结构》习题集：第9章查找(第1次更新2019-5)
- 数据结构第九章排序习题及答案
- 《数据结构》习题汇编09 第九章 排序 试题
- 数据结构(c语言版)题集答案——第九章_查找
- (习题)数据结构第九章 排序
- 《数据结构》知识题汇编09第九章排序试题
- 最新数据结构第九章排序习题及答案
- 数据结构习题第9章
- 《数据结构》习题汇编09 第九章 排序 试题
- 数据结构第九章排序习题及答案
- 数据结构第九章内部排序
- 《数据结构》习题集：第9章查找(第1次更新2019-5)
- 《数据结构》习题汇编09第九章排序试题
- 数据结构第九章排序习题及答案.
- 《数据结构》习题汇编09第九章排序试题
- 数据结构 第10章排序自测题答案
- 数据结构习题汇编09第九章排序试题
- 数据结构习题汇编09 第九章 排序 试题
- 数据结构第九章排序习题与答案
- 数据结构 第9章 内部排序(作业)
- 《数据结构》习题汇编09-第九章-排序-试题