第八章 排序--练习答案.pptVIP

* 第八章 排序 --练习 1．一组记录的排序码为47,78,57,39,41,85.,则利用堆排序的方法建立的初始推为 。A).78,47,57,39,41,85 B).85,78,57,39,41,47C).85,78,57,47,41,39 D).85,57,78,41,47,39 2．一组记录的关键码为48,79,52,38,40,84.,则利用快速排序的方法,以第一个记录为基准得到的一次划分结果为 。 A).38,40, 48, 52,79,84 B).40,38, 48,79, 52,84 C).40,38, 48, 52,79,84 D).40,38, 48,84, 52,79 B C 3．一组记录的排序码为26,48,16,35,78,82,22,40,37,72.,其中含有5个长度为2的有序表,按归并排序的方法对该序列进行一趟归并后的结果为 。 A).16, 26,35,48, 22,40, 78,82, 37,72 B).16, 26,35,48, 78,82, 22, 37,40,72 C).16, 26,48,35, 78,82, 22, 37,40,72 D).16, 26,35,48, 78, 22, 37,40,72,82 A 4.以下序列不是堆的是 A.105,85,98,77,80,61,82,40,22,13,66B.105,98,85,82,80,77,66,61,40,22,13C.13,22,40,61,66,77,80,82,85,98,105D.105，85,40,77,80,61,66,98,82,13,22 D 5、下列四种排序方法中，不稳定的方法是 A.直接插入排序 B.冒泡排序 C.归并排序　 D. 简单选择排序 D 6、对下列4个序列用快速排序方法进行排序，以序列的第1个元素为基准进行划分。在第1趟划分过程中，元素移动次数最多的是序列 A.71,75,82,90, 24,18,10,68  B.71,75,68,23,10,18,90,82 C.82,75,71,18,10,90,68,24  D.24,10,18,71,82,75,68,90 A 7.下列排序算法中，___________算法可能在初始数据有序时，花费的时间反而最多。 A 堆排序 B 冒泡排序 C 快速排序 D 插入排序 C 8.对包含N个元素的散列表进行检索，平均查找长度为_________. A .O(log2N) B. O(N) C.不直接依赖于N D. 上述说法都不对 9.在各种排序方法中,从未排序序列中挑选元素,并将其依次放入已排序序列(初始时为空)的一端的方法是________________ 插入排序 B. 希尔排序 C. 选择排序 D. 归并排序 C C 10.一组记录的关键字为(46,79,56,38,40,84),则利用堆排序的方法建立的初始堆为_____________ A 79,46,56,38,40,80 B 84,79,56,38,40,46 C 84,79,56,46,40,38 D 84,56,79,40,46,38 12.对具有8个元素的序列(49,38,65,97,76,13,27,50),按升序排序,采用快速排序法第一趟的结果为_________ 11.下列哪个排序属于稳定排序_________ A 希尔排序 B 2路排序 C 堆排序 D 快速排序 B B 答案：27，38，13，49，76，97，65，50 14、已知关键字序列为（20，15，14，18，21，36，40，10），采用快速排序法对其排序，第一趟排序后的关键字序列为___________________ 15.对关键字序列(52，80，63， 46，90.)进行一趟快速排序之后得到的结果为___________________ (10,15,14,18,20,36,40,21) (46,52,63,80,90) 13、用冒泡法对n个关键字排序，在最好的情况下，只需做 _____次比较和 _________次移动；在最坏的情况下，要做 __________次比较 n-1 0 n(n-1)/2 16．已知序列｛72，83，99，65，10，36，7，