数据结构第10章排序练习及答案

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．以下序列不是堆的是（）

A）100,85,98,77,80,60,82,40,20,10,66

B）100,98,85,82,80,77,66,60,40,20,10

C）10,20,40,60,66,77,80,82,85,98,100

D）100,85,40,77,80,60,66,98,82,10,20

【答案】D

【解析】根据堆采用完全二叉树的顺序存储形式及堆的特点，因第一个结点即根结点关键字值最大，则应建立一个大根堆，但依据此数据序列建立起堆后关键字值为40的左右孩子结点分别为60、66，不符合大根堆特点。

9．一组记录的关键字为{45，80，55，40，42，85}，则利用堆排序的方法建立的初始堆为（）

A）80,45,50,40,42,85

B）85,80,55,40,42, 45

C）85,80,55,45,42,40

D）85,55,80,42,45,40

【答案】B

10．一组记录的关键字为{25，50，15，35，80，85，20，40，36，70}，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果为（）

A）15,25,35,50,20,40,80,85,36,70

B）15,25,35,50,80,20,85,40,70,36

C）15,25,50,35,80,85,20,36,40,70

D）15,25,35,50,80,20,36,40,70,85

【答案】A

【解析】对5个长度为2的有序表一趟归并后得到前两个长度为4的有序表和最后一个长度为2的有序表，故选A。

11．n个元素进行冒泡排序的过程中，最好情况下的时间复杂度为（）

A）O(1) B）O(log2n) C）O(n2) D）O(n)

【答案】D

【解析】最好情况下至少需要一趟排序，即比较n-1次，故选D。

12．下述几种排序方法中，要求内存量最大的是（）

A）插入排序B）选择排序C）快速排序D）归并排序

【答案】D

【解析】插入排序和选择排序需要的辅助空间为O(1)，快速排序需要的辅助空间为O(log2n )，归并排序需要的辅助空间为O(n)，因此选D。

13．下面排序方法中，时间复杂度不是O(n2)的是（）

A）直接插入排序B）二路归并排序C）冒泡排序D）直接选择排序

【答案】B

【解析】直接插入排序、冒泡排序和直接选择排序的时间复杂度为O(n2)，而二路归并排序的时间复杂度为O(n log2n)，故选B。

填空题

1．当数据量特别大需借助外部存储器对数据进行排序，则这种排序称为_____________。【答案】外部排序

2．在堆排序、快速排序和归并排序中，若从节省存储空间考虑，则应首先选取_____________方法，其次选取_____________方法；若只从排序结果的稳定性考虑，则应先择_____________方法；若只从平均情况下排序的速度来考虑，则选择_____________方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取_____________方法。

【答案】（1）堆排序（2）快速排序（3）归并排序（4）快速（5）堆

3．对n个元素的序列进行冒泡排序，最少的比较次数是_____________，此时元素的排列情况为_____________，在_____________情况下比较次数最多，其比较次数为_____（4）_ ____。【答案】

（1）n-1（2）从小到大排序（3）元素从大到小排列（4）n(n-1)/2

【解析】初始元素正序时，第一趟比较n-1次，并无数据交换，则不再比较，故只比较n-1次。若反序，则比较(n-1)+(n-2)+(n-3)+…..+2+1共n(n-1)/2次。

4．设表中元素的初态是按键值递增的，若分别用堆排序、快速排序、冒泡排序和归并排序方法对其仍按递增顺序进行排序，则_____________最省时间，_____________最费时间。【答案】（1）冒泡排序（2）快速排序

【解析】若初始序列已经有序，则冒泡排序仅需一趟(比较n-1次)；而快速排序则需n-1趟，其时间复杂度升至O(n2)。因此填：冒泡排序，快速排序。

4．设待排序的排序码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 试分别写出使用以下排序方法每趟排序后的结果。并说明做了多少次排序码比较。

（1）直接插入排序（2）希尔排序（增量为5,2,1）

（3）起泡排序（4）快速排序

（5）堆排序

【答案】

（1）直接插入排序

（2）希尔排序(增量为5,2,1)

（3）起泡排序

（4）快速排序

（5）堆排序

第一步，形成初始的最大堆(略)，第二步，做堆排序。

初始排列，不是最大堆形成初始最大堆交换0# 与9# 对象

从0# 到8# 重新形成堆交换0# 与8# 对象从0# 到7# 重新形成堆

交换0# 与7# 对象从0# 到6# 重新形成堆交换0# 与6# 对象

从0# 到5# 重新形成堆交换0# 与5# 对象从0# 到4# 重新形成堆

交换0# 与4# 对象从0# 到3# 重新形成堆交换0# 与3# 对象

从0# 到2# 重新形成堆交换0# 与2# 对象从0# 到1# 重新形成堆

交换0# 与1# 对象从0# 到1# 重新形成堆，得到结果

第10章排序自测题答案

第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．从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为

数据结构课程设计(内部排序算法比较_C语言)

数据结构课程设计 课程名称：内部排序算法比较 年级/院系：11级计算机科学与技术学院 姓名/学号： 指导老师： 第一章问题描述 排序是数据结构中重要的一个部分，也是在实际开发中易遇到的问题，所以研究各种排算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决！该系统通过对各种内部排序算法如直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序、二路归并排序等，以关键码的比较次数和移动次数分析其特点，并进行比较，估算每种算法的时间消耗，从而比较各种算法的优劣和使用情况！排序表的数据是多种不同的情况，如随机产生数据、极端的数据如已是正序或逆序数据。比较的结果用一个直方图表示。

第二章系统分析 界面的设计如图所示： |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| 请选择操作方式： 如上图所示该系统的功能有： （1）：选择1 时系统由客户输入要进行测试的元素个数由电脑随机选取数字进行各种排序结果得到准确的比较和移动次数并 打印出结果。 （2）选择2 时系统由客户自己输入要进行测试的元素进行各种排序结果得到准确的比较和移动次数并打印出结果。 （3）选择0 打印“谢谢使用！！”退出系统的使用！！ 第三章系统设计 （I）友好的人机界面设计：（如图3.1所示） |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------|

数据结构第十章习题课

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章排序练习题答案(可编辑修改word版)

第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．对ｎ个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为

中南大学数据结构与算法第10章内部排序课后作业答案

第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)快速排序：（方括号表示无序区，层表示对应的递归树的层数）

数据结构实验八内部排序

实验八内部排序 一、实验目的 1、掌握内部排序的基本算法； 2、分析比较内部排序算法的效率。 二、实验内容和要求 1. 运行下面程序： #include #include #define MAX 50 int slist[MAX]; /*待排序序列*/ void insertSort(int list[], int n); void createList(int list[], int *n); void printList(int list[], int n); void heapAdjust(int list[], int u, int v); void heapSort(int list[], int n); /*直接插入排序*/ void insertSort(int list[], int n) { int i = 0, j = 0, node = 0, count = 1; printf("对序列进行直接插入排序：\n"); printf("初始序列为：\n"); printList(list, n); for(i = 1; i < n; i++) { node = list[i]; j = i - 1; while(j >= 0 && node < list[j]) { list[j+1] = list[j]; --j; } list[j+1] = node; printf("第%d次排序结果：\n", count++); printList(list, n); } } /*堆排序*/ void heapAdjust(int list[], int u, int v)

第十章：内部排序练习题

第十章：内部排序练习题 一、选择题 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、要排序的数据中含有多个相同值。

(完整word版)第10章习题(带答案)

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、直接插入排序在最好情况下的时间复杂度为( )。

数据结构课程设计(内部排序算法比较 C语言)

课题：内部排序算法比较 第一章问题描述 排序是数据结构中重要的一个部分，也是在实际开发中易遇到的问题，所以研究各种排算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决！该系统通过对各种内部排序算法如直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序、二路归并排序等，以关键码的比较次数和移动次数分析其特点，并进行比较，估算每种算法的时间消耗，从而比较各种算法的优劣和使用情况！排序表的数据是多种不同的情况，如随机产生数据、极端的数据如已是正序或逆序数据。比较的结果用一个直方图表示。 第二章系统分析 界面的设计如图所示： |******************************| |-------欢迎使用---------| |-----（1）随机取数-------|

|-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| 请选择操作方式： 如上图所示该系统的功能有： （1）：选择 1 时系统由客户输入要进行测试的元素个数由电脑随机选取数字进行各种排序结果得到准确的比较和移动次数并打印出结果。 （2）选择 2 时系统由客户自己输入要进行测试的元素进行各种排序结果得到准确的比较和移动次数并打印出结果。 （3）选择0 打印“谢谢使用！！”退出系统的使用！！ 第三章系统设计 （I）友好的人机界面设计：（如图3.1所示） |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| （3.1） （II）方便快捷的操作：用户只需要根据不同的需要在界面上输入系统提醒的操作形式直接进行相应的操作方式即可！如图（3.2所示） |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------|

数据结构第九、十章 作业答案

第九章 查找 一、填空题 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

南邮数据结构上机实验四内排序算法的实现以及性能比较

实验报告 （2015 / 2016学年第二学期） 课程名称数据结构A 实验名称内排序算法的实现以及性能比较 实验时间2016 年 5 月26 日 指导单位计算机科学与技术系 指导教师骆健 学生姓名耿宙班级学号B14111615 学院(系) 管理学院专业信息管理与信息系统

—— 实习题名:内排序算法的实现及性能比较 班级 B141116 姓名耿宙学号 B14111615 日期2016.05.26 一、问题描述 验证教材的各种内排序算法，分析各种排序算法的时间复杂度；改进教材中的快速排序算法，使得当子集合小于10个元素师改用直接插入排序；使用随即数发生器产生大数据集合，运行上述各排序算法，使用系统时钟测量各算法所需的实际时间，并进行比较。系统时钟包含在头文件“time.h”中。 二、概要设计 文件Sort.cpp中包括了简单选择排序SelectSort()，直接插入排序InsertSort()，冒泡排序BubbleSort()，两路合并排序Merge()，快速排序QuickSort()以及改进的快速排序GQuickSort()六个内排序算法函数。主主函数main的代码如下图所示： 三、详细设计 1.类和类的层次设计 在此次程序的设计中没有进行类的定义。程序的主要设计是使用各种内排序算法对随机 生成的数列进行排列，并进行性能的比较，除此之外还对快速排序进行了改进。下图为主函 数main的流程图：

——

main() 2.核心算法 1)简单选择排序： 简单选择排序的基本思想是：第1趟，在待排序记录r[1]~r[n]中选出最小的记录，将它与r[1]交换；第2趟，在待排序记录r[2]~r[n]中选出最小的记录，将它与r[2]交换；以此类推，第i趟在待排序记录r[i]~r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到

目前最完整的数据结构1800题包括完整答案 第十章 排序

第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<

数据结构课程设计(内部排序算法比较-C语言)

` 课题：内部排序算法比较… 第一章问题描述 排序是数据结构中重要的一个部分，也是在实际开发中易遇到的问题，所以研究各种排算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决！该系统通过对各种内部排序算法如直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序、二路归并排序等，以关键码的比较次数和移动次数分析其特点，并进行比较，估算每种算法的时间消耗，从而比较各种算法的优劣和使用情况！排序表的数据是多种不同的情况，如随机产生数据、极端的数据如已是正序或逆序数据。比较的结果用一个直方图表示。 第二章系统分析 界面的设计如图所示： !

|******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| ~ 请选择操作方式： 如上图所示该系统的功能有： （1）：选择 1 时系统由客户输入要进行测试的元素个数由电脑随机选取数字进行各种排序结果得到准确的比较和移动次数并打印出结果。 （2）选择 2 时系统由客户自己输入要进行测试的元素进行各种排序结果得到准确的比较和移动次数并打印出结果。 （3）选择0 打印“谢谢使用！！”退出系统的使用！！ 、 第三章系统设计 （I）友好的人机界面设计：（如图所示） |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| ： （）

数据结构第10章 内部排序习题

第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．对下列关键字序列用快速排序法进行排序，速度最快的情形是

第7章 排序 习题参考答案

习题七参考答案 一、选择题 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) {

数据结构严蔚敏版第十章答案

第十章内部排序 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]

数据结构第九章排序习题及答案

习题九排序 一、单项选择题 1．下列内部排序算法中： A．快速排序 B.直接插入排序 C. 二路归并排序 D. 简单选择排序 E. 起泡排序 F. 堆排序 （1）其比较次数与序列初态无关的算法是（） （2）不稳定的排序算法是（） （3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k<

数据结构内排序实验报告

一、实验目的 1、了解内排序都是在内存中进行的。 2、为了提高数据的查找速度，需要对数据进行排序。 3、掌握内排序的方法。 二、实验内容 1、设计一个程序e xp10—1.cpp实现直接插入排序算法，并输出{9,8,7,6,5,4,3,2,1,0}的排序 过程。 （1）源程序如下所示： //文件名:exp10-1.cpp #include #define MAXE 20 //线性表中最多元素个数 typedef int KeyType; typedef char InfoType[10]; typedef struct //记录类型 { KeyType key; //关键字项 InfoType data; //其他数据项,类型为InfoType } RecType; void InsertSort(RecType R[],int n) //对R[0..n-1]按递增有序进行直接插入排序 { int i,j,k; RecType temp; for (i=1;i=0 && temp.key