第10章内部排序习题
一、单项选择题
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.
9.采用任何基于排序码比较的算法，对5个互异的整数进行排序，至少需要（）次比较。
A. 5
B. 6
C. 7
D. 8
10.下列算法中（）算法不具有这样的特性：对某些输入序列，可能不需要移动数据对象即可完成
排序。
A. 起泡排序
B. 希尔排序
C. 快速排序
D. 直接选择排序
11.使用递归的归并排序算法时，为了保证排序过程的时间复杂度不超过O(nlog2n)，必须做到（）。
A. 每次序列的划分应该在线性时间内完成
B. 每次归并的两个子序列长度接近
C. 每次归并在线性时间内完成
D. 以上全是
12.在基于排序码比较的排序算法中，（）算法的最坏情况下的时间复杂度不高于O(nlog2n)。
A. 起泡排序
B. 希尔排序
C. 归并排序
D. 快速排序
13.一个对象序列的排序码为{ 46, 79, 56, 38, 40, 84 }，采用快速排序（以位于最左位置的对象为基准而）
得到的第一次划分结果为：
A. { 38, 46, 79, 56, 40, 84 }
B. { 38, 79, 56, 46, 40, 84 }
C. { 40, 38, 46, 79, 56, 84 }
D. { 38, 46, 56, 79, 40, 84 }
参考答案： 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
二、填空题
1.第i (i = 1, 2, …, n-1) 趟从参加排序的序列中取出第i个元素，把它插入到由第0个~第i-1个元素组成
的有序表中适当的位置，此种排序方法叫做________排序。
2.第i (i = 0, 1, …, n-2) 趟从参加排序的序列中第i个～第n-1个元素中挑选出一个最小（大）元素，把
它交换到第i个位置，此种排序方法叫做________排序。
3.每次直接或通过基准元素间接比较两个元素，若出现逆序排列，就交换它们的位置，这种排序方法叫
做________排序。
4.每次使两个相邻的有序表合并成一个有序表，这种排序方法叫做________排序。
5.在直接选择排序中，排序码比较次数的时间复杂度为O(________)。
6.在直接选择排序中，数据对象移动次数的时间复杂度为O(________)。
7.在堆排序中，对n个对象建立初始堆需要调用________次调整算法。
8.在堆排序中，如果n个对象的初始堆已经建好，那么到排序结束，还需要从堆顶结点出发调用________
次调整算法。
9.在堆排序中，对任一个分支结点进行调整运算的时间复杂度为O(________)。
10.对n个数据对象进行堆排序，总的时间复杂度为O(________)。
11.给定一组数据对象的排序码为{ 46, 79, 56, 38, 40, 84 }，则利用堆排序方法建立的初始堆（最大堆）为
________。
12.快速排序在平均情况下的时间复杂度为O(________)。
13.快速排序在最坏情况下的时间复杂度为O(________)。
14.快速排序在平均情况下的空间复杂度为O(________)。
15.快速排序在最坏情况下的空间复杂度为O(________)。
16.给定一组数据对象的排序码为{46, 79, 56, 38, 40, 84}，对其进行一趟快速排序，结果为________。
17.在n个数据对象的二路归并排序中，每趟归并的时间复杂度为O(________)。
18.在n个数据对象的二路归并排序中，整个归并的时间复杂度为O(________)。
参考答案：1. 插入 2. 直接选择 3. 交换
4. 两路归并
5. n2
6. n
7. ?n/2?8. n-1 9. log2n
10. nlog2n 11. 84, 79, 56, 38, 40, 46 12. nlog2n
13. n214. log2n 15. n
16. [40 38] 46 [79 56 84] 17. n 18. nlog2n
三、判断题
1.直接选择排序是一种稳定的排序方法。
2.若将一批杂乱无章的数据按堆结构组织起来, 则堆中各数据是否必然按自小到大的顺序排列起来。
3.当输入序列已经有序时，起泡排序需要的排序码比较次数比快速排序要少。
4.在任何情况下，快速排序需要进行的排序码比较的次数都是O(nlog2n)。
5.在2048 个互不相同的排序码中选择最小的5个排序码，用堆排序比用锦标赛排序更快。
6.若用m个初始归并段参加k路平衡归并排序，则归并趟数应为?log2m?。
7.堆排序是一种稳定的排序算法。
8.对于某些输入序列，起泡排序算法可以通过线性次数的排序码比较且无需移动数据对象就可以完成排
序。
9.如果输入序列已经排好序，则快速排序算法无需移动任何数据对象就可以完成排序。
10.希尔排序的最后一趟就是起泡排序。
11.任何基于排序码比较的算法，对n个数据对象进行排序时，最坏情况下的时间复杂度不会低于
O(nlog2n)。
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)给出第一次取出堆顶后，重新调整H A后的结果（以线性数组表示）；
(3)给出第二次取出堆顶后，重新调整H A后的结果（以线性数组表示）。
3.希尔排序、直接选择排序、快速排序和堆排序是不稳定的排序方法, 试举例说明。
参考答案：
1.(1) { 100, 86, 48, 73, 35, 39, 42, 57, 66, 21 }为最大堆。
调整为小根堆后为{ 21, 35, 39, 57, 86, 48, 42, 73, 66, 100 }
(2){ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 }不是最小堆。
调整为小根堆后为{ 12, 24, 33, 65, 33, 56, 48, 92, 86, 70 }
2.(1) 建堆结果
H A = 5 23 7 41 56
(2) 第一次取出堆顶，并重新调整后
H A = 7 23 56 41
(3) 第二次取出堆顶，并重新调整后
H A = 23 41 56
3.(1) 希尔排序{ 512 275 275* 061 }增量为2
{ 275* 061 512 275 }增量为1
{ 061 275* 275 512 }
(2) 直接选择排序{ 275 275* 512 061 }i = 1
{061275* 512 275 }i = 2
{061 275* 512 275 }i = 3
{061 275* 275512 }
(3) 快速排序{ 512 275 275* }
{ 275* 275 512}
(4) 堆排序{ 275 275* 061 170 }已经是最大堆，交换275与170
{ 170 275* 061 275}对前3个调整
{ 275* 170 061 275 }前3个最大堆，交换275*与061
{ 061 170 275* 275 }对前2个调整
{ 170 061 275* 275 }前2个最大堆，交换170与061
{ 061 170 275* 275 }
第十章：内部排序练习题 一、选择题 1、下述几种排序方法中，平均查找长度最小的是（）。 A、插入排序 B、选择排序 C、快速排序 D、归并排序 2、设关键字序列为（3，7，6，9，7，1，4，5，20），对其进行排序的最小交换次数为（）。 A、6 B、7 C、8 D、20 3、下列排序算法中不稳定的有（）。 A、直接选择排序 B、直接插入排序 C、冒泡排序 D、二叉排序 E、Shell排序 F、快速排序 G、归并排序 H、堆排序 I、基数排序 4、内部排序多个关键字的文件，最坏情况下最快的排序方法是（），相应的时间复杂度为（），该算法是（）排序方法。 A、快速排序 B、插入排序 C、归并排序 D、简单选择排序 E、O(nlog2n) F、O(n2) G、O(n2log2n) H、O(n) I、稳定J、不稳定 5、对初始状态为递增的表按递增顺序排序，最省时间的是（）算法，最费时间的算法是（）。 A、堆排序 B、快速排序 C、插入排序 D、归并排序 6、下述几种排序方法中，要求内存量最大的是（）。 A、插入排序 B、选择排序 C、快速排序 D、归并排序 7、在下面的排序方法中，关键字比较的次数与记录的初始排列次序无关的是（）。 A、希尔排序 B、冒泡排序 C、插入排序 D、选择排序 8、下列排序中，排序速度与数据的初始排列状态没有关系的是（）。 A、直接选择排序 B、基数排序 C、堆排序 D、直接插入排序 9、若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法为（）。 A、快速排序 B、堆排序 C、归并排序 D、直接插入排序 10、排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列正确位置上的方法，称为（）。 A、希尔排序 B、冒泡排序 C、插入排序 D、选择排序 11、每次把待排序的元素划分为左右两个子区间，其中左区间中元素的关键字均小于等于基准元素的关键字，右区间中元素的关键字均大于基准元素的关键字，则此排序方法为（）。 A、堆排序 B、快速排序 C、冒泡排序 D、Shell排序 12、排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（）。 A、希尔排序 B、归并排序 C、插入排序 D、选择排序 13、n个记录的直接插入排序所需记录关键码的最大比较次数为（）。 A、nlog2n B、n2/2 C、(n+2)(n-1)/2 D、n-1 14、n个记录的直接插入排序所需的记录最小移动次数为（）。 A、2(n-1) B、n2/2 C、(n+3)(n-2)/2 D、2n 15、快速排序在（）情况下最不利于发挥其长处，在（）情况下最易发挥其长处。 A、被排序的数据量很大 B、被排序的数据已基本有序 C、被排序的数据完全有序 D、被排序的数据中最大与最小值相差不大 E、要排序的数据中含有多个相同值。
第9章排序自测卷姓名班级 一、填空题（每空1分，共24分） 1. 大多数排序算法都有两个基本的操作：比较和移动。 2. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插 入到有序表时，为寻找插入位置至少需比较6 次。 3. 在插入和选择排序中，若初始数据基本正序，则选用插入；若初始数据基本反序，则选用 选择。 4. 在堆排序和快速排序中，若初始记录接近正序或反序，则选用堆排序；若初始记录基本 无序，则最好选用快速排序。 5. 对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是O(n2) 。若对其进行快速 排序，在最坏的情况下所需要的时间是O(n2)。 6. 对于n个记录的集合进行归并排序，所需要的平均时间是O(nlog2n)，所需要的附加空间 是O(n) 。 7．对于n个记录的表进行2路归并排序，整个归并排序需进行┌log2n┐趟（遍）。 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 H F X R D 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．从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为
常见内部排序算法比较 排序算法是数据结构学科经典的内容，其中内部排序现有的算法有很多种，究竟各有什么特点呢？本文力图设计实现常用内部排序算法并进行比较。分别为起泡排序，直接插入排序，简单选择排序，快速排序，堆排序，针对关键字的比较次数和移动次数进行测试比较。 问题分析和总体设计 ADT OrderableList { 数据对象：D={ai| ai∈IntegerSet,i=1,2,…,n,n≥0} 数据关系：R1={〈ai-1，ai〉|ai-1, ai∈D, i=1,2,…,n} 基本操作： InitList(n) 操作结果：构造一个长度为n，元素值依次为1，2，…，n的有序表。Randomizel(d,isInverseOrser) 操作结果：随机打乱 BubbleSort( ) 操作结果：进行起泡排序 InserSort( ) 操作结果：进行插入排序 SelectSort( ) 操作结果：进行选择排序 QuickSort( ) 操作结果：进行快速排序 HeapSort( ) 操作结果：进行堆排序 ListTraverse(visit( )) 操作结果：依次对L种的每个元素调用函数visit( ) }ADT OrderableList 待排序表的元素的关键字为整数.用正序,逆序和不同乱序程度的不同数据做测试比较,对关键字的比较次数和移动次数(关键字交换计为3次移动)进行测试比较.要求显示提示信息,用户由键盘输入待排序表的表长(100-1000)和不同测试数据的组数(8-18).每次测试完毕,要求列表现是比较结果. 要求对结果进行分析.
详细设计 1、起泡排序 算法：核心思想是扫描数据清单，寻找出现乱序的两个相邻的项目。当找到这两个项目后，交换项目的位置然后继续扫描。重复上面的操作直到所有的项目都按顺序排好。 bubblesort(struct rec r[],int n) { int i,j; struct rec w; unsigned long int compare=0,move=0; for(i=1;i<=n-1;i++) for(j=n;j>=i+1;j--) { if(r[j].key 排序习题参考标准答案 ————————————————————————————————作者：————————————————————————————————日期： 习题七参考答案 一、选择题 1．内部排序算法的稳定性是指( D )。 A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录 C．平均时间为0（n log n）的排序方法 D．以上都不对 2．下面给出的四种排序算法中，( B )是不稳定的排序。 A．插入排序B．堆排序C．二路归并排序D．冒泡排序 3. 在下列排序算法中，哪一种算法的时间复杂度与初始排序序列无关（D ）。 A．直接插入排序B．冒泡排序C．快速排序D．直接选择排序 4．关键字序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中( C )的两趟排序后的结果。 A．选择排序 B.冒泡排序 C.插入排序 D.堆排序 5．下列排序方法中，( D )所需的辅助空间最大。 A．选择排序B．希尔排序C．快速排序D．归并排序 6．一组记录的关键字为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为支点得到的一次划分结果为（C ）。 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) 7．在对一组关键字序列{70，55，100，15，33，65，50，40，95}，进行直接插入排序时，把65插入，需要比较( A )次。 A. 2 B. 4 C. 6 D. 8 8.从待排序的序列中选出关键字值最大的记录放到有序序列中，该排序方法称为( B )。 A. 希尔排序 B. 直接选择排序 C. 冒泡排序 D. 快速排序 9．当待排序序列基本有序时，以下排序方法中，( B )最不利于其优势的发挥。 A. 直接选择排序 B. 快速排序 C.冒泡排序 D.直接插入排序 10．在待排序序列局部有序时，效率最高的排序算法是( B )。 A. 直接选择排序 B. 直接插入排序 C. 快速排序 D.归并排序 二、填空题 1.执行排序操作时，根据使用的存储器可将排序算法分为内排序和外排序。 2.在对一组记录序列{50,40,95,20,15,70,60,45,80}进行直接插入排序时，当把第7个记录60插入到有序表中时， 为寻找插入位置需比较 3 次。 3.在直接插入排序和直接选择排序中，若初始记录序列基本有序，则选用直接插入排序。 4.在对一组记录序列{50,40,95,20,15,70,60,45,80}进行直接选择排序时，第4次交换和选择后，未排序记录为 {50,70,60,95,80}。 5.n个记录的冒泡排序算法所需的最大移动次数为3n(n-1)/2 ，最小移动次数为0 。 6.对n个结点进行快速排序，最大的比较次数是n(n-1)/2 。 7.对于堆排序和快速排序，若待排序记录基本有序，则选用堆排序。 8.在归并排序中，若待排序记录的个数为20，则共需要进行5 趟归并。 9.若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的比较和数据元素 的移动。 10．在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的是快速排序，需要内存容量最多的是基数排序。 三、算法设计题 1．试设计算法，用插入排序方法对单链表进行排序。 参考答案: 第10 章排序练习题答案 一、填空题 1. 大多数排序算法都有两个基本的操作：比较和移动。 2. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7 个记录60 插 入到有序表时，为寻找插入位置至少需比较 3 次。 3.在插入和选择排序中，若初始数据基本正序，则选用插入；若初始数据基本反序，则选用 选择。 正序时两种方法移动次数均为0，但比较次数量级不同，插入法：n-1 即O(n)，选择法：O(n2) 反序时两种方法比较次数量级相同，均为O(n2)，但移动次数不同，插入法：O(n2)，选择法：3(n-1)即O(n) 4.在堆排序和快速排序中，若初始记录接近正序或反序，则选用堆排序；若初始记录基本无 序，则最好选用快速排序。 5.对于n 个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是O(n2) 。若对其进行快速 排序，在最坏的情况下所需要的时间是O(n2) 。 6.对于n 个记录的集合进行归并排序，所需要的平均时间是O(nlog2n) ，所需要的附加空间是O(n) 。 7.对于n 个记录的表进行2 路归并排序，整个归并排序需进行┌log2n┐趟（遍）。 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 ； 二路归并排序一趟扫描的结果是H Q C Y A P M S D R F X； 快速排序一趟扫描的结果是 F H C D P A M Q R S Y X； 堆排序初始建堆的结果是Y S X R P C M H Q D F A 。（大根堆） 9.在堆排序、快速排序和归并排序中， 若只从存储空间考虑，则应首先选取堆排序方法，其次选取快速排序方法，最后选取归并排序方法；若只从排序结果的稳定性考虑，则应选取归并排序方法； 若只从平均情况下最快考虑，则应选取快速排序方法； 若只从最坏情况下最快并且要节省内存考虑，则应选取堆排序方法。 二、单项选择题 （ C ）1．排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为 Ａ. 归并排序Ｂ. 冒泡排序Ｃ. 插入排序Ｄ. 选择排序 （ D ）2．从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为Ａ. 冒泡排序Ｂ. 归并排序Ｃ. 插入排序Ｄ. 选择排序 （ B ）3．对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。 Ａ. 从小到大排列好的Ｂ. 从大到小排列好的Ｃ. 元素无序Ｄ. 元素基本有序 （ D ）4．对ｎ个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为 #include for(j=i-dk;j>0&&L.r[0] 习题九排序 一、单项选择题 1．下列内部排序算法中： A．快速排序 B.直接插入排序 C. 二路归并排序 D. 简单选择排序 E. 起泡排序 F. 堆排序 （1）其比较次数与序列初态无关的算法是（） （2）不稳定的排序算法是（） （3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k< 第10章排序 一、填空题 1. 大多数排序算法都有两个基本的操作：和。 2. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7 个记录60插入到有序表时，为寻找插入位置至少需比较次。 3. 在插入和选择排序中，若初始数据基本正序，则应选用排序算法；若初始数据基 本反序，则应选用排序算法。 4. 在堆排序和快速排序中，若初始记录接近正序或反序，则选用；若初始记录基本 无序，则最好选用。 5. 对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是。若对其进 行快速排序，在最坏的情况下所需要的时间是。 6. 对于n个记录的集合进行归并排序，所需要的平均时间是，所需要的附加空间 是。 7．对于n个记录的表进行2路归并排序，整个归并排序需进行趟（遍）。 8. 设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排 列，则：冒泡排序一趟扫描的结果是；初始步长为4的希尔（shell）排序一趟的结果是；归并排序一趟扫描的结果是；快速排序一趟扫描的结果是；堆排序初始建堆的结果是。 9. 分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表进行排序，则最省 时间的是算法，最费时间的是算法。 10、对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为。 二、单项选择题 1、下列四个序列中，（）是堆。 A. 75,65,30,15,25,45,20,10 B. 75,65,45,10,30,25,20,15 C. 75,45,65,30,15,25,20,10 D. 75,45,65,10,25,30,20,15 2．排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（） Ａ. 希尔排序Ｂ. 冒泡排序Ｃ. 插入排序Ｄ. 选择排序 3．从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为（） Ａ. 希尔排序Ｂ. 归并排序Ｃ. 插入排序Ｄ. 选择排序 4．对ｎ个不同的排序码进行冒泡排序，在下列（）情况下比较的次数最多。 习题七参考答案 一、选择题 1．内部排序算法的稳定性是指( D )。 A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录 C．平均时间为0（n log n）的排序方法 D．以上都不对 2．下面给出的四种排序算法中，( B )是不稳定的排序。 A．插入排序B．堆排序C．二路归并排序D．冒泡排序 3. 在下列排序算法中，哪一种算法的时间复杂度与初始排序序列无关（D ）。 A．直接插入排序B．冒泡排序C．快速排序D．直接选择排序 4．关键字序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中( C )的两趟排序后的结果。 A．选择排序 B.冒泡排序 C.插入排序 D.堆排序 5．下列排序方法中，( D )所需的辅助空间最大。 A．选择排序B．希尔排序C．快速排序D．归并排序 6．一组记录的关键字为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为支点得到的一次划分结果为（C ）。 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) 7．在对一组关键字序列{70，55，100，15，33，65，50，40，95}，进行直接插入排序时，把65插入，需要比较( A )次。 A. 2 B. 4 C. 6 D. 8 8.从待排序的序列中选出关键字值最大的记录放到有序序列中，该排序方法称为( B )。 A. 希尔排序 B. 直接选择排序 C. 冒泡排序 D. 快速排序 9．当待排序序列基本有序时，以下排序方法中，( B )最不利于其优势的发挥。 A. 直接选择排序 B. 快速排序 C.冒泡排序 D.直接插入排序 10．在待排序序列局部有序时，效率最高的排序算法是( B )。 A. 直接选择排序 B. 直接插入排序 C. 快速排序 D.归并排序 二、填空题 1.执行排序操作时，根据使用的存储器可将排序算法分为内排序和外排序。 2.在对一组记录序列{50,40,95,20,15,70,60,45,80}进行直接插入排序时，当把第7个记录60插入到有序表中 时，为寻找插入位置需比较 3 次。 3.在直接插入排序和直接选择排序中，若初始记录序列基本有序，则选用直接插入排序。 4.在对一组记录序列{50,40,95,20,15,70,60,45,80}进行直接选择排序时，第4次交换和选择后，未排序记录为 {50,70,60,95,80}。 5.n个记录的冒泡排序算法所需的最大移动次数为3n(n-1)/2 ，最小移动次数为0 。 6.对n个结点进行快速排序，最大的比较次数是n(n-1)/2 。 7.对于堆排序和快速排序，若待排序记录基本有序，则选用堆排序。 8.在归并排序中，若待排序记录的个数为20，则共需要进行5 趟归并。 9.若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的比较和数据元 素的移动。 10．在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的是快速排序，需要内存容量最多的是基数排序。 三、算法设计题 1．试设计算法，用插入排序方法对单链表进行排序。 参考答案: public static void insertSort(LinkList L) { 1、对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是 ( )。 A. 直接选择排序 B. 直接插入排序 C. 快速排序 D. 起泡排序 2、对5个不同的数据元素进行直接插入排序，最多需要进行 ( ) 次比较。 A. 8 B. 10 C. 15 D. 25 3、用快速排序法对n 个数据进行排序，在最好情况下的时间复杂度是 O(nlogn)，在最坏情况下的时间复杂度是 O(n 2) ，在平均情况下的时间复杂度是 O(nlogn) 。 4、用归并排序法对n 个数据进行排序，在最好情况下的时间复杂度是 O(nlogn) ，在最坏情况下的时间复杂度是 O(nlogn) ，在平均情况下的时间复杂度是 O(nlogn) 。 5、在对n 个元素进行直接插入排序的过程中，共需要进行2n 趟。（ 错 ） 快速排序在最坏情况下的时间复杂度为)(2n 。（ 对 ） 6、若一组记录的关键字为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到一次划分结构为( )。 A.40，38，46，84，56，79 B.40，38，46，56，79，84 C.40，38，46，79，56，84 D.38，40，46，56，79，84 7、下列四个序列中，哪一个是堆（ ）。 A. 75,65,30,15,25,45,20,10 B. 75,65,45,10,30,25,20,15 C. 75,45,65,30,15,25,20,10 D. 75,45,65,10,25,30,20,15 8、由无序序列{ 15，9，7，8，20，7}建立的初始小顶堆为 7,8,7,9,20,15_ 。 9、已知5个数据元素为（54，28，16，34，73），对该数列按从小到大排序，经过一趟冒泡排序后的序列为 28,16,34,54,73_ 。 10、若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的__ 比较_____和记录的___移动__。 11、直接插入排序在最好情况下的时间复杂度为( )。 内部排序算法的实现与 比较 Company Document number：WUUT-WUUY-WBBGB-BWYTT-1982GT 实验四：内部排序算法的实现与比较 一、问题描述 1．实验题目：在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大致执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。 2．基本要求：（1）对常用的内部排序算法进行比较：直接插入排序、简单选择排序、冒泡排序、快速排序、希尔排序、归并排序。 （2利用随机函数产生N（N=30000）个随机整数，作为输入数据作比较；比较的指标为关键字参加的比较次数和关键字的移动次数（关键字交换记为3次移动）。 （3)对结果作出简要分析。 3．测试数据：随机函数产生。 二、需求分析 1．程序所能达到的基本可能：通过随机数据产生N个随机数，作为输入数据作比较；对常用的内部排序算法：直接插入排序、简单选择排序、冒泡排序、快速排序、希尔排序、归并排序进行比较：比较的指标为关键字参加的比较次数和关键字的移动次数（关键字交换记为3次移动）。最后结果输出各种排序算法的关键字参加的比较次数和关键字的移动次数，并按从小到大排列。 2．输入的形式及输入值范围：随机函数产生的N（N=30000）个随机整数。 3．输出的形式：输出各种排序算法的关键字参加的比较次数和关键字的移动次数。并按从小到大排列。 4．测试数据要求：随机函数产生的N（N=30000）个随机整数。 三、概要设计 1. 所用到得数据结构及其ADT 为了实现上述功能，应以一维数组表示集合数据类型。 int s[N]; int compare[6]={0},move[6]={0},D[N]={0},RS[N]={0}; 基本操作： 数组赋值： for(i=1;i 公共部门人力资源管理练习题 （） 一、选择题（每题2分，30题共计60分，每题至少有一个答案，多选或者少选均不能得分） 74. 对于公共部门人才所要测评的要素来说，（A）是最基本的测评方式，具有重要的把关作用。 A. 笔试 B. 资质测试 C. 评价中心技术 D. 无领导小组讨论 83. 美国哈佛大学威廉·詹姆斯教授，在实地调查中发现一个人平常表现的能力水平，与经过激发可能达到的能力水平之间存在着大约（ A ）左右的差距。 A. 60％ B. 50％ C. 80％ D. 70％ 89. （ A）是绩效管理的重要环节，也是传统的绩效管理模式与现代模式的本质区别之一。 A. 持续沟通 B. 实施绩效评价 C. 提供绩效反馈 D. 绩效改进指导 53. 第一个被公认的现代人事管理部门是1902年在（B）现金出纳公司设立的劳工部门，它的工作内容包括工资行政、诉怨、雇用工作情况和工作改善等。 A. 英国 B. 美国 C. 德国 D. 比利时 57. 我国古代社会中按官职高低授予不同政治待遇以表明官员等级尊卑的制度是（B）。 A. 俸禄 B. 品秩 C. 致仕 D. 回避 58. 《中华人民共和国公务员法》于（B）开始施行。 A. 2006年10月1日 B. 2006年1月1日 C. 2007年10月1日 D. 2007年1月1日 62. 我国劳动力市场体系已初步形成，（B）在人力资源配置中的主导地位也已初步确立。 A. 政府部门 B. 市场机制 C. 第三部门 D. 三资企业 70. （ B）是一种以工作为中心的工作分析方法，是对管理工作进行定量化测试的方法，适用于不同组织内管理层次以上职位的分析。 A. 职位分析问卷 B. 管理职位描述问卷 C. 体能分析问卷 D. 心理分析问卷 77. 公共部门人力资源招募与选录工作只有在（ B ）分析的基础上，才能确定公共职位空缺的数量、结构、任职资格条件、具体的招募途径以及甄选方法等。 A. 劳动力市场的供需状况 B. 内部环境 C. 外部环境 D. 经济环境 80. ( B )是公职人员职业生涯开始时或任新职时所经历的第一种类型的培训。 A. 技能培训 B. 初任培训 C. 专业培训 D. 知识更新培训 85. 我国古代的"卧薪尝胆"、"破釜沉舟"的故事充分说明了( B )的重大作用。 A. 情感激励 B. 危机激励 C. 荣誉激励 D. 目标激励 86. 目前，大多数公共管理部门所采取的考评模式均属于（ B）。 A. 发展型评估 B. 判断型评估 C. 参与型评估 D. 专项型评估 88. 实践证明，采用（B）的考核方法，很难区分不同部门之间公务员业绩的差别和同一部门内工作性质差别不太大的公务员工作业绩的高下，也很难根据考核结果客观、完整地评价一个公务员。 A. 定量分析 B. 定性分析 C. 360度绩效分析 D. 平衡记分卡 106. 公共部门人力资源部内培训的最大优点在于( B)。 A.有助于增进部门之间的相互联系和信息交流，并有助于节省培训经费 B.针对性较强、容易实施，也比较容易取得实效 C.有助于人们开阔视野，增强应对所面对的现实问题的能力 D.有利于部门工作经验的传授和良好人际关系的维系，也有利于保持部门的优良传统和工作的连续性 67. ( C )是公务员交流最为常见的方式。 A. 调任 B. 聘任 C. 转任 D. 挂职锻炼 107. （C）是目前公职人员培训中普遍采用的方法。 A. 讲授式培训法 B. 研讨式培训法 C. 案例分析培训法 D. 合作研究培训法 第10章排序（参考答案） 18. 对于后三种排序方法两趟排序后，序列的首部或尾部的两个元素应是有序的两个极值，而给定的序列并不满足。 20. 本题为步长为3的一趟希尔排序。 24.枢轴是73。 49. 小根堆中，关键字最大的记录只能在叶结点上，故不可能在小于等于n/2的结点上。 64. 因组与组之间已有序，故将n/k个组分别排序即可，基于比较的排序方法每组的时间下界为O(klog2k),全部时间下界为O(nlog2k)。 部分答案解释如下： 5. 错误。例如冒泡排序是稳定排序，将4,3,2,1按冒泡排序排成升序序列，第一趟变成3,2,1,4，此时3就朝向最终位置的相反方向移动。 12. 错误。堆是n个元素的序列，可以看作是完全二叉树，但相对于根并无左小右大的要求，故其既不是二叉排序树，更不会是平衡二叉树。 22. 错误。待排序序列为正序时，简单插入排序比归并排序快。 三、填空题 1. 比较,移动 2.生成有序归并段（顺串）,归并 3.希尔排序、简单选择排序、快速排序、堆排序等 4. 冒泡,快速 5. (1)简单选择排序 (2)直接插入排序（最小的元素在最后时） 6. 免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。 7. n(n-1)/2 8.题中p指向无序区第一个记录，q指向最小值结点，一趟排序结束，p和q所指结点值交换，同时向后移p指针。(1)!=null (2)p->next (3)r!=null (4)r->data 实验四：内部排序算法的实现与比较 一、问题描述 1．实验题目：在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大致执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。2．基本要求：（1）对常用的内部排序算法进行比较：直接插入排序、简单选择排序、冒泡排序、快速排序、希尔排序、归并排序。 （2利用随机函数产生N（N=30000）个随机整数，作为输入数据作比较；比较的指标为关键字参加的比较次数和关键字的移动次数（关键字交换记为3次移动）。 （3)对结果作出简要分析。 3．测试数据：随机函数产生。 二、需求分析 1．程序所能达到的基本可能：通过随机数据产生N个随机数，作为输入数据作比较；对常用的内部排序算法：直接插入排序、简单选择排序、冒泡排序、快速排序、希尔排序、归并排序进行比较：比较的指标为关键字参加的比较次数和关键字的移动次数（关键字交换记为3次移动）。最后结果输出各种排序算法的关键字参加的比较次数和关键字的移动次数，并按从小到大排列。 2．输入的形式及输入值范围：随机函数产生的N（N=30000）个随机整数。 3．输出的形式：输出各种排序算法的关键字参加的比较次数和关键字的移动次数。并按从小到大排列。 4．测试数据要求：随机函数产生的N（N=30000）个随机整数。 三、概要设计 1. 所用到得数据结构及其ADT 为了实现上述功能，应以一维数组表示集合数据类型。 int s[N]; int compare[6]={0},move[6]={0},D[N]={0},RS[N]={0}; 基本操作： 数组赋值： for(i=1;i 第十章排序 一、名词解释 1.排序 2.内部排序 3.外部排序 4.堆 5.堆排序 二、填空 1.若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序方法是________的，否则称为________的。 2.按照排序过程涉及的存储设备的不同，排序可分为________排序和________排序。 3.按排序过程中依据的不同原则对内部排序方法进行分类，主要有：________、________、________、________等四类。 4.在排序算法中，分析算法的时间复杂性时，通常以________和________为标准操作。评价排序的另一个主要标准是执行算法所需要的________。 5.常用的插入排序方法有________插入排序、________插入排序、________插入排序和________插入排序。 6.以下为直接插入排序的算法。请分析算法，并在________上填充适当的语句。 void straightsort(list r); {for(i=___________;i<=n;i++) {r[0]=r[i];j=i-1; while(r[0].key 第10章排序 一、基础知识题 10.1 基本概念：内排序，外排序，稳定排序，不稳定排序，顺串，败者树，最 佳归并树。 【解答】⑴内排序和外排序若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。内部排序适用于记录个数不多的文件，不需要访问外存，而外部排序适用于记录很多的大文件，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。 ⑵稳定排序和不稳定排序假设待排序记录中有关键字K i=K j（i≠j），且在排序前的序列中R i领先于R j。经过排序后，R i与R j的相对次序保持不变（即R i仍领先于R j），则称这种排序方法是稳定的，否则称之为不稳定的。 ⑶顺串外部排序通常经过两个独立的阶段完成。第一阶段，根据内存大小，每次把文件中一部分记录读入内存，用有效的内部排序方法（如快速排序、堆排序等）将其排成有序段，这有序段又称顺串或归并段。 ⑷败者树败者树为提高外部排序的效率而采用的，是由参加比赛的n个元素作叶子结点而得到的完全二叉树。每个非叶（双亲）结点中存放的是两个子结点中的败者数据,而让胜者去参加更高一级的比赛。另外,还需增加一个结点,即结点0,存放比赛的全局获胜者。 ⑸最佳归并树在外部排序的多路平衡归并的k叉树中，为了提高效率减少对外存的读写次数，按哈夫曼树构造的k叉树称最佳归并树。这棵树中只有度为0和度为k的结点。若用m表示归并段个数，用n k表示度为k的个数，若 (m-1)%(k-1)=0，则不需增加虚段，否则应附加k-(m-1)%(k-1)-1个虚段（即第一个k路归并使用(m-1)%(k-1)+1个归并段）。 10.2设待排序的关键字序列为(15， 21， 6， 30， 23， 6′， 20， 17)，试 分别写出使用以下排序方法每趟排序后的结果。并说明做了多少次比较。 (1) 直接插入排序(2) 希尔排序(增量为5，2，1) (3) 起泡排序 (4) 快速排序(5) 直接选择排序 (6) 锦标赛排序 (7) 堆排序(8) 二路归并排序 (9) 基数排序 【解答】 (1) 直接插入排序 初始关键字序列： 15，21，6，30，23，6′，20，17 第一趟直接插入排序：【15，21】 第二趟直接插入排序：【6，15，21】 第三趟直接插入排序：【6，15，21，30】 第四趟直接插入排序：【6，15，21，23，30】 第五趟直接插入排序：【6，6′，15，21，23，30】 第六趟直接插入排序：【6，6′，15，20，21，23，30】排序习题参考标准答案
第10章排序练习题答案(可编辑修改word版)
内部排序代码
数据结构第九章排序习题及答案
第10章 排序 作业
第7章 排序 习题参考答案
(完整word版)第10章习题(带答案)
内部排序算法的实现与比较
公共部门人力资源管理练习题 排序
第10章 排序答案
内部排序算法的实现与比较
排序自测试题
第10章 排序
相关主题
文本预览