资源描述：
《第八章 排序练习答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第八章排序（答案）一、选择题1．一组记录的排序码为47,78,57,39,41,85.,则利用堆排序的方法建立的初始推为。A).78,47,57,39,41,85B).85,78,57,39,41,47C).85,78,57,47,41,39D).85,57,78,41,47,392．一组记录的关键码为48,79,52,38,40,84.,则利用快速排序的方法,以第一个记录为基准得到的一次划分结果为。A).38,40,48,52,79,84B).40,38,48,79,52,84C).40,38,48,52,79,84D).40,38,48,84
2、,52,793．一组记录的排序码为26,48,16,35,78,82,22,40,37,72.,其中含有5个长度为2的有序表,按归并排序的方法对该序列进行一趟归并后的结果为。A).16,26,35,48,22,40,78,82,37,72B).16,26,35,48,78,82,22,37,40,72C).16,26,48,35,78,82,22,37,40,72D).16,26,35,48,78,22,37,40,72,824.以下序列不是堆的是A.105,85,98,77,80,61,82,40,22,13,66B.105,98,85,82,
3、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,225、下列四种排序方法中，不稳定的方法是A.直接插入排序B.冒泡排序C.归并排序 D.简单选择排序6、对下列4个序列用快速排序方法进行排序，以序列的第1个元素为基准进行划分。在第1趟划分过程中，元素移动次数最多的是序列A.71,75,82,90,24,18,10,68B.71,75,68,23,10,18,90,82C.82,75,71,18,10,90,68,24D.2
4、4,10,18,71,82,75,68,907.下列排序算法中，___________算法可能在初始数据有序时，花费的时间反而最多。A堆排序B冒泡排序C快速排序D插入排序8.对包含N个元素的散列表进行检索，平均查找长度为_________.A.O(log2N)B.O(N)C.不直接依赖于ND.上述说法都不对9.在各种排序方法中,从未排序序列中挑选元素,并将其依次放入已排序序列(初始时为空)的一端的方法是________________A.插入排序B.希尔排序C.选择排序D.归并排序10.一组记录的关键字为(46,79,56,38,40,84),则
5、利用堆排序的方法建立的初始堆为_____________A79,46,56,38,40,80B84,79,56,38,40,46C84,79,56,46,40,38D84,56,79,40,46,3811.对具有8个元素的序列(49,38,65,97,76,13,27,50),按升序排序,采用快速排序法第一趟的结果为_________答案：27，38，13，49，76，97，65，50A)13,65,38,97,76,49,27,50B)13,27,38,49,50,65,76,97C)97,76,65,50,49,38,27,13D)13,38
6、,65,97,76,49,27,5012.下列哪个排序属于稳定排序_________A希尔排序B2路排序C堆排序D快速排序二、填空题1、在插入排序、选择排序、快速排序和归并排序中，平均查找时间最少的是快速排序,要求存储量最大的是归并排序.2、用冒泡法对n个关键字排序，在最好的情况下，只需做n-1次比较和0次移动；在最坏的情况下，要做n(n-1)/2次比较3、在快速排序和堆排序中，若待排序记录序列接近正序或逆序，则应该选用堆排序,若待排序记录序列无序，则应该选用快速排序.4、设顺序表中有1000个元素，用折半查找时，最大比较次数为10,最小比较次数
7、为1..5、已知关键字序列为（20，15，14，18，21，36，40，10），采用快速排序法对其排序，第一趟排序后的关键字序列为(10,15,14,18,20,36,40,21)6、对关键字序列(52，80，63，46，90.)进行一趟快速排序之后得到的结果为(46,52,63,80,90)三、简答题1．已知序列｛72，83，99，65，10，36，7，9｝，请给出采用插入排序法对该序列作升序排序时的每一趟的结果。初始：（72），83，99，65，10，36，7，9第1趟：（72，83），99，65，10，36，7，9第2趟：（72，83，99
8、），65，10，36，7，9第3趟：（65，72，83，99），10，36，7，9第4趟：（10，65，72，83，99），36，7，9
