第九章华工数据结构试卷资料电信学院.doc

《第九章华工数据结构试卷资料电信学院.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、习题9．1一、选择题1、一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为(B)。A、79，46，56，38，40，80B、84，79，56，38，40，46C、84，79，56，46，40，38D、84，56，79，40，46，382、排序趟数与序列原始状态(原始排列)有关的排序方法是（ACD）方法。A、插入排序B、选择排序     C、冒泡排序   D、快速排序3、下列排序方法中，（B）是稳定的排序方法。A、直接选择排序B、二分法插入排序C、希尔排序D、快速排序4、数据序列（8，9，10，4，5，6，20，1

2、，2）只能是下列排序算法中(C)的两趟排序后的结果。A、选择排序B、冒泡排序C、插入排序D、堆排序5、对序列(15，9，7，8，20，-1，4)进行排序，进行一趟排序后，数据的排列变为（4，9，-1，8，20，7，15），则采用的是（C）排序。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

3、,84,56,79)7、用直接插入排序对下面四个序列进行排序（由小到大），元素比较次数最少的是（C）。A、94,32,40,90,80,46,21,69B、32,40,21,46,69,94,90,80C、21,32,46,40,80,69,90,94D、90,69,80,46,21,32,94,408、若用冒泡排序对关键字序列（18,16,14,12,10,8）进行从小到大的排序，所需进行的关键字比较总次数是（B）。A、10B、15C、21D、349、就排序算法所用的辅助空间而言，堆排序、快速排序和归并排序的关系（A）。A、堆排序<快速排序<归并排序

4、　B、堆排序<归并排序<快速排序C、堆排序>归并排序>快速排序　D、堆排序>快速排序>归并排序E、以上答案都不对10、采用败者树进行k路平衡归并的外部排序算法，其总的归并效率与k（）。A、有关B、无关9.2填空题1、在直接插入排序和直接选择排序中，若初始数据基本有序，则选用（直接插入排序），若初始数据基本反序，则选用（直接选择排序）。2、在归并排序中，若待排序记录的个数为20，则共需要进行（5）趟归并，在第三趟归并中，是把长度为（4）的有序表归并为长度为（8）的有序表。3、在内排序中，平均比较次数最多的是（快速排序），要求附加的内存空间最大的是（归并排

5、序），排序时不稳定的有（希尔排序）、（选择排序）、（快速排序）和（堆排序）等几种方法。4、对n个元素的序列进行冒泡排序，最少的比较次数是（n-1），此时元素的排列情况（从小到大排列），在（从大到小排列）情况下比较次数最多，其比较次数为（n(n-1)/2）。5、对一组记录（50，40，95，20，15，70，60，45，80）进行直接插入排序时，当把第7条记录60插入到有序表中时，为寻找插入位置需比较（3）次。9.3应用题1、在各种排序方法中，哪些是稳定的？哪些是不稳定的？并为每一种不稳定的排序方法举出一个不稳定的实例。答：稳定的排序算法有直接插入排序、

6、折半插入排序、冒泡排序、归并排序和基数排序。不稳定的排序算法有希尔排序、直接选择排序、堆排序、快速排序。例子：讲课是的例子。2、设待排序的关键码分别为28，13，72，85，39，41，6，20。按折半插入排序已使前七个记录有序，中间结果如下：613283941728520i=1m=4r=7试在此基础上，沿用上述表达方式，给出继续采用折半插入第八条记录的比较过程，并回答以下问题：(1)使用折半插入排序所要进行的比较次数，是否与待排序的记录的初始状态有关？(2)在一些特殊情况下，二分法插入排序比直接插入排序要执行更多的比较。这句话对吗？答：插入20的过程

7、：①39>20：r=m-1=3;i<=r;m=(i+r)/2=4/2=2②13<20:i=m+1=3;i>r;查找过程结束，插入位置为i。最终结果为：613202839417285（1）插入排序所要进行的比较次数与待排序的记录的初始状态有关。若初始状态基本有序，每次查找时都会搜索到有序表的最后一个元素才找到插入位置。若每次插入的元素在有序表中的插入位置靠中间，则查找次数最少。（2）在一些特殊情况下，二分法插入排序比直接插入排序要执行更多的比较。这句话是对的。若初始状态基本有序，则折半插入排序，每次查找时都会搜索到有序表的最后一个元素才找到插入位置。直接

8、插入排序则每次只比较一次就找到合适位置。3、已知一关键码序列为：3，87，12，61，70，9