算法与数据结构（山东联盟）第七章测试_智慧树知到答案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]
[12，27，45，41] 55 [34，63，72]
 [63，12，34，45，27] 55 [41，72]
 [41，12，34，45，27] 55 [72，63]
答案：[41，12，34，45，27] 55 [72，63]
[判断题]排序分稳定排序和不稳定排序。（  ）
对
错[单选题]设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（ ）
40
30
45
20[判断题]冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（ ）
错
对[单选题]设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录关键字45为基准而得到一趟快速排序的结果是（  ）。         
42，40，45，55，80，85
42，40，45，85，55，80
42，40，45，80，85，88
40，42，45，55，80，83  [单选题]设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（   ）。 
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，20，36，40，70，85
15，25，35，50，80，85，20，36，40，70[单选题]设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为（   ）。          
45，40，15，20
15，20，40，45 
 40，50，20，95     
15，40，60，20[单选题]队列的顺序存储结构用C语言中（ ）数据类型实现。
一维数组实现
二维数组实现
枚举型
结构体[单选题]时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是（  ）。          
 堆排序
 希尔排序 
 冒泡排序
快速排序