《数据结构第9章测试题A.docx》由会员分享，可在线阅读，更多相关《数据结构第9章测试题A.docx（3页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 米 第9章测试题A卷一、单项选择题.在所有排序方法中，关键字比拟的次数与记录的初始排列次序无关的是（）。A.希尔排序 B.起泡排序 C.插入排序D.选择排序.设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最 好选用（）排序法。A.起泡排序B.快速排序 C.堆排序 I）.基数排序.在待排序的元素序列基本有序的前提下，效率最高的排序方法是（）。A.插入排序 B.选择排序 C.快速排序D.归并排序. 一组记录的排序码为（46, 79, 56, 38, 40, 84）,那么利用堆排序的方法建立的 初始堆为（）。A. 79, 46, 56, 38, 40, 80B. 38,
2、46, 56, 79, 40, 84,C. 84, 79, 56, 46, 40, 38D. 84, 56, 79, 40, 46, 38. 一组记录的关键码为（46, 79, 56, 38, 40, 84）,那么利用快速排序的方法，以 第一个记录为基准得到的一次划分结果为（）_。A.38, 40, 46, 56, 79, 84B.40,38,46,79,56,84C.40, 38, 46, 56, 79, 84I）.40,38,46,84,56,79.一组记录的排序码为（25,48,16,35,79,82,23,40,36,72）,其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一
3、趟归并后的结果为（）。A.B.C.D.16, 25, 35,16, 25, 35,16, 25, 48,16, 25, 35,48, 23, 40,48, 79, 82,35, 79, 82,48, 79, 23,79, 82, 36, 7223, 36, 40, 7223, 36, 40, 7236, 40, 72, 827 .排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元 素进行比拟，将其放入已排序序列的正确位置上的方法，称为（）。A.希尔排序 B.起泡排序 C.插入排序 D.选择排序.排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为 空）的一
4、端的方法，称为（）。A.希尔排序 B.归并排序 C.插入排序9.用某种排序方法对线性表（25, 84, 21, 47,D.选择排序15, 27, 68, 35, 20）进行排序时，元素序列的变化情况如下:(1) 25, 84, 21, 47, 15, 20, 15, 21, 25, 47, 15, 20, 21, 25, 35, (4) 15, 20, 21, 25, 27, 那么所采用的排序方法是(27, 68,27, 68,27, 47,35, 47, )oA.选择排序 B.希尔排序35, 2035, 8468, 8468, 84C.归并排序D.10.下述几种排序方法中，平均查找长度最小的
5、是（快速排序 ）。A.插入排序B.选择排序 C.快速排序 D.归并排序.下述几种排序方法中，要求内存量最大的是（）oA.插入排序B.选择排序 C快速排序 I）.归并排序.快速排序方法在（）情况下最不利于发挥其长处。A.要排序的数据量太大 B.要排序的数据中含有多个相同值C.要排序的数据已基本有序D.要排序的数据个数为奇数.以下排序算法中（）不能保证每越排序至少能将一个元素放到其最终的位置 上。A.快速排序B. shell排序C.堆排序D.冒泡排序.以下排序算法中（）排序在一趟结束后不一定能选出一个元素放在其最终位 置上。A.选择B.冒泡C.归并 D.堆.以下序列中，（）是执行第一趟快速排序后所
6、得的序列。A. 68, 11, 18, 6923, 93, 73 B. 68, 11, 69, 2318,93, 73C. 93, 7368, 11, 69, 23, 18 D. 68, 11, 69, 23, 1893,73.有一组数据（15, 9, 7, 8, 20, -1, 7, 4）用快速排序的划分方法进行一趟 划分后数据的排序为（）（按递增序）。A.下面的 B, C, D 都不对。B. 9, 7, 8, 4, -1, 7, 15, 20C. 20, 15, 8, 9, 7, -1, 4, 7 D. 9, 4, 7, 8, 7, -1, 15, 20. 一组记录的关键码为（46, 79
7、, 56, 38, 40, 84）,那么利用快速排序的方法，以 第一个记录为基准得到的一次划分结果为（）。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）.在下面的排序方法中，辅助空间为0 （n）的是（）。A.希尔排序 B.堆排序C.选择排序D.归并排序.以下排序算法中，在待排序数据已有序时，花费时间反而最多的是（ ）排序。A.冒泡B.希尔C.快速D.堆】.以下排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性 能受数据初始特性影响的是：（）。A.直接
8、插入排序 B.快速排序 C.直接选择排序 D.堆排序 二、填空题（将正确的答案填在相应的空中）.在对一组记录（54, 38, 96, 23, 15, 72, 60, 45, 83）进行直接插入排序时， 当把第7个记录60插入到有序表时，为寻找插入位置需比拟一。1 .在利用快速排序方法对一组记录（54, 38, 96, 23, 15, 72, 60, 45, 83）进行 快速排序时，递归调用而使用的栈所能到达的最大深度为 ，共需递归调用的次 数为，其中第二次递归调用是对组记录进行快速排序。 米 2 .在堆排序，快速排序和归并排序中，假设只从存储空间考虑，那么应首先选取 一方 法，其次选取方法，最
9、后选取方法；假设只从排序结果的稳定性考虑，疝应 选取方法；假设只从平均情况下排后最快考虑，那么应选取方法；假设只从最坏 情况下排序最快并且要节省内存考虑，那么应选取方法。3 .在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中, 排序是不稳定的有0.在在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序 中，平均比拟次数最少的排序是，需要内存容量最多的是O.在堆排序和快速排序中，假设原始记录接近正序或反序，那么选用，假设原始记录 无序，那么最好选用0.在插入和选择排序中，假设初始数据基本正序，那么选用一；假设初始数据基本反序, 那么选用。4 .对n个元素的序
10、列进行起泡排序时，最少的比拟次数是o 三、综合题1、在堆排序、快速排序和合并排序中：(1) .假设只从存储空间考虑，那么应首先选取哪种排序方法，其次选取哪种排序方法, 最后选取哪种排序方法？(2) .假设只从排序结果的稳定性考虑，那么应选取哪种排序方法？(3) .假设只从平均情况下排序最快考虑，那么应选取哪种排序方法？(4) .假设只从最坏情况下排序最快并且要节省内存考虑，那么应选取哪种排序方法？ 2、设要求从大到小排序。问在什么情况下冒泡排序算法关键字交换的次数为最大。 3、二路插入排序是将待排关键字序列rL.n中关键字分二路分别按序插入到辅助 向量前半部和后半部(注：向量d可视为循环表)，其原那么为，先将”1赋 给dl,再从r2记录开始分二路插入。编写实现二路插入排序算法。