算法与数据结构（山东联盟） 第七章_智慧树知到答案2021年

第七章 排序：排序(Sorting)是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。本章讲了排序算法的特性，主要讲解内部排序的各种排序方法。7.1排序的基本概念:排序(Sorting)是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。排序分为两类：内部排序和外部排序。为了便于读者理解，记录序列中只列出关键字部分，设待排序记录的关键字均为整数，则在以后讨论的大部分算法中，待排记录的数据类型也都介绍了。
7.2插入排序---直接插入排序:直接插入排序(基于顺序查找)是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。本节介绍直接插入排序的算法及C语言编写。
7.3插入排序---折半插入排序:在有序表中确定插入位置，还可以通过二分有序表的方法来确定插入位置，由此进行的插入排序称为折半插入排序。本节介绍折半排序算法及C语言编程。
7.4插入排序---希尔排序:希尔排序又称缩小增量排序，是1959年由D. L. Shell提出来的，较前述几种插入排序方法有较大的改进。本节介绍希尔排序算法
7.5交换排序---冒泡排序:本节介绍冒泡排序算法
7.6交换排序---快速排序:本节介绍交换排序---快速排序算法
7.7选择排序---简单选择排序:选择排序---简单选择排序
7.8选择排序---树形选择排序:选择排序---树形选择排序
7.9选择排序---堆排序:选择排序---堆排序
7.10二路归并排序:堆排序举例
7.11实验编程---学生信息管理系统中的排序:对记录项进行排序
7.1排序的基本概念:排序(Sorting)是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。排序分为两类：内部排序和外部排序。为了便于读者理解，记录序列中只列出关键字部分，设待排序记录的关键字均为整数，则在以后讨论的大部分算法中，待排记录的数据类型也都介绍了。
7.2插入排序---直接插入排序:直接插入排序(基于顺序查找)是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。本节介绍直接插入排序的算法及C语言编写。
7.3插入排序---折半插入排序:在有序表中确定插入位置，还可以通过二分有序表的方法来确定插入位置，由此进行的插入排序称为折半插入排序。本节介绍折半排序算法及C语言编程。
7.4插入排序---希尔排序:希尔排序又称缩小增量排序，是1959年由D. L. Shell提出来的，较前述几种插入排序方法有较大的改进。本节介绍希尔排序算法
7.5交换排序---冒泡排序:本节介绍冒泡排序算法
7.6交换排序---快速排序:本节介绍交换排序---快速排序算法
7.7选择排序---简单选择排序:选择排序---简单选择排序
7.8选择排序---树形选择排序:选择排序---树形选择排序
7.9选择排序---堆排序:选择排序---堆排序
7.10二路归并排序:堆排序举例
7.11实验编程---学生信息管理系统中的排序:对记录项进行排序

[单选题]

执行一趟快速排序能够得到的序列是（  ）。

           

选项:[[45，34，12，41] 55 [72，63，27],  [41，12，34，45，27] 55 [72，63],  [63，12，34，45，27] 55 [41，72], [12，27，45，41] 55 [34，63，72]]
[判断题]排序分稳定排序和不稳定排序。（  ）

选项:[对, 错]
[判断题]冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（ ）选项:[对, 错]
[单选题]

设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录关键字45为基准

而得到一趟快速排序的结果是（  ）。

         

选项:[42，40，45，80，85，88, 42，40，45，85，55，80, 40，42，45，55，80，83  , 42，40，45，55，80，85]
[单选题]

设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度

为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（   ）。

 

选项:[15，25，35，50，80，20，36，40，70，85, 15，25，35，50，20，40，80，85，36，70, 15，25，35，50，80，20，85，40，70，36, 15，25，35，50，80，85，20，36，40，70]
[单选题]

设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔

排序结束后前4条记录关键字为（   ）。

          

选项:[15，20，40，45 ,  40，50，20，95     , 15，40，60，20, 45，40，15，20]
[单选题]

执行一趟快速排序能够得到的序列是（  ）。

           

选项:[[45，34，12，41] 55 [72，63，27], [63，12，34，45，27] 55 [41，72], [41，12，34，45，27] 55 [72，63]]