资源描述：
《第九章,,华工数据结构试卷资料,电信学院,》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、第九章,,华工数据结构试卷资料,电信学院, 习题 9．1一、选择题 1、一组记录的排序码为，则利用堆排序的方法建立的初始堆为(B)。 A、79，46，56，38，40，80 B、84，79，56，38，40，46C、84，79，56，46，40，38 D、84，56，79，40，46，382、排序趟数与序列原始状态(原始排列)有关的排序方法是方法。 A、插入排序 B、选择排序 C、冒泡排序 D、快速排序3、下列排序方法中，是稳定的排序方法。 A、直接选择排序 B、二分法插入排序 C、希尔排序 D、快速排序4、数据序列只能是
2、下列排序算法中(C)的两趟排序后的结果。 A、选择排序 B、冒泡排序 C、插入排序 D、堆排序 5、对序列(15，9，7，8，20，-1，4)进行排序，进行一趟排序后，数据的排列变为，则采用的是排序。 A、选择 B、快速 C、希尔 D、冒泡6、一组待排序记录的关键字为，则利用快速排序，以第一个记录为基准元素得到的一次划分结果为。 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、用直接插入排序对下面四个
3、序列进行排序，元素比较次数最少的是。 A、94,32,40,90,80,46,21,69 B、32,40,21,46,69,94,90,80C、21,32,46,40,80,69,90,94 D、90,69,80,46,21,32,94,408、若用冒泡排序对关键字序列进行从小到大的排序，所需进行的关键字比较总次数是。 A、10 B、15 C、21 D、34 9、就排序算法所用的辅助空间而言，堆排序、快速排序和归并排序的关系。A、堆排序归并排序>快速排序 D、堆排序>快速排序>归并排序 E、以上答案都不对 10、采用败者树进行k
4、路平衡归并的外部排序算法，其总的归并效率与k。A、有关 B、无关填空题 1、在直接插入排序和直接选择排序中，若初始数据基本有序，则选用，若初始数据基本反序，则选用。 2、在归并排序中，若待排序记录的个数为20，则共需要进行趟归并，在第三趟归并中，是把长度为的有序表归并为长度为的有序表。 3、在内排序中，平均比较次数最多的是，要求附加的内存空间最大的是，排序时不稳定的有、、和等几种方法。 4、对n个元素的序列进行冒泡排序，最少的比较次数是，此时元素的排列情况 在情况下比较次数最多，其比较次数为。 5、对一组记录进行直接插入排序时，当把第7
5、条记录60插入到有序表中时，为寻找插入位置需比较次。应用题 1、在各种排序方法中，哪些是稳定的？哪些是不稳定的？并为每一种不稳定的排序方法举出一个不稳定的实例。 答：稳定的排序算法有直接插入排序、折半插入排序、冒泡排序、归并排序和基数排序。 不稳定的排序算法有希尔排序、直接选择排序、堆排序、快速排序。例子：讲课是的例子。 2、设待排序的关键码分别为28，13，72，85，39，41，6，20。按折半插入排序已使前七个记录有序，中间结果如下： 6 13 28 39 417285 20 i=1 m=4 r=7试在此基础上，沿用上
6、述表达方式，给出继续采用折半插入第八条记录的比较过程，并回答以下问题： (1)使用折半插入排序所要进行的比较次数，是否与待排序的记录的初始状态有关？(2)在一些特殊情况下，二分法插入排序比直接插入排序要执行更多的比较。这句话对吗？答： 插入20的过程： ①39>20：r=m-1=3;ir;查找过程结束，插入位置为i。最终结果为：613202839417285插入排序所要进行的比较次数与待排序的记录的初始状态有关。若初始状态基本有序，每次查找时都会搜索到有序表的最后一个元素才找到插入位置。若每次插入的元素在有序表中的插入位置靠中间，则查找次数最少
7、。 在一些特殊情况下，二分法插入排序比直接插入排序要执行更多的比较。这句话是对的。若初始状态基本有序，则折半插入排序，每次查找时都会搜索到有序表的最后一个元素才找到插入位置。直接插入排序则每次只比较一次就找到合适位置。 3、已知一关键码序列为：3，87，12，61，70，97，26，45。试根据堆排序原理，填写完整下示各步骤结果。 建立初始堆：_978726617012345堆排序过程： 877026614512397;706126345128797;614526312708797;451226361708797;26123456170879
8、7;123264561708797;312264561708797; 4、全国有10000人参加物理竞赛，
