第8章+排序习题解析(答)

《第8章+排序习题解析(答)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、排序习题解析11.填空题⑴排序的主要目的是为了以后对已排序的数据元素进行（查找）。⑵对n个元素进行起泡排序，在（正序）情况下比较的次数最少，其比较次数为（n-1）。在（反序）情况下比较次数最多，其比较次数为（n(n-1)/2）。⑶对一组记录（54,38,96,23,15,72,60,45,83）进行直接插入排序，当把第7个记录60插入到有序表时，为寻找插入位置需比较（3）次。⑷对一组记录（54,38,96,23,15,72,60,45,83）进行快速排序，在递归调用中使用的栈所能达到的最大深度为（

2、3）。⑸对n个待排序记录序列进行快速排序，所需要的最好时间是（O(nlog2n)），最坏时间是（O(n2)）。 ⑹利用简单选择排序对n个记录进行排序，最坏情况下，记录交换的次数为（n-1）。2.选择题⑴下述排序方法中，比较次数与待排序记录的初始状态无关的是（）。A、插入排序和快速排序B、归并排序和快速排序C、选择排序和归并排序D、插入排序和归并排序⑵下列序列中，（）是执行第一趟快速排序的结果。A、[da，ax，eb，de，bb]ff[ha，gc]B、[cd，eb，ax，da]ff[ha，gc，bb

3、]C、[gc，ax，eb，cd，bb]ff[da，ha]D、[ax，bb，cd，da]ff[eb，gc，ha]⑶对初始状态为递增有序的序列进行排序，最省时间的是（B），最费时间的是（C）。已知待排序序列中每个元素距其最终位置不远，则采用（B）方法最节省时间。A、堆排序B、插入排序C、快速排序D、直接选择排序⑸当待排序序列基本有序或个数较小的情况下，最佳的内部排序方法是（A），就平均时间而言，（D）最佳。A直接插入排序B起泡排序C简单选择排序D快速排序⑼快速排序在（）情况下最不利于发挥其长处。A、待

4、排序的数据量太大B、待排序的数据中含有多个相同值C、待排序的数据已基本有序D、待排序的数据数量为奇数⑽（）方法是从未排序序列中挑选元素，并将其放入已排序序列的一端。A、归并排序B、插入排序C、快速排序D、选择排序3.判断题⑴如果某种排序算法是不稳定的，则该排序方法没有实际应用价值。错⑵当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂性的主要因素。对⑶对n个记录的集合进行快速排序，所需要的附加空间是Ο(n)。错排序----习题解析2一、选择题1、以下序列不是堆的是

5、  D    。    A、（100，85，98，77，80，60，82，40，20，10，66）B、（100，98，85，82，80，77，66，60，40，20，10）C、（10，20，40，60，66，77，80，82，85，98，100）D、（100，85，40，77，80，60，66，98，82，10，20）2、在文件“局部有序”或文件长度较小的情况下，最佳内部排序方法是  A    。    A、直接插入排序        B、冒泡排序C、简单选择排序     D、归并排序3、在下列算

6、法中，   C   算法可能出现下列情况；在最后一趟开始之前，所有的元素都不在其最终的位置上。    A、堆排序        B、冒泡排序C、插入排序             D、快速排序4、从未排序的序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在排序序列的合适位置，该排序方法称为   A   排序法。    A、插入         B、选择        C、希尔         D、二路归并5、排序趟数与序列原始状态有关的排序方法是 D或C     排序法。    A

7、、插入        B、选择        C、冒泡          D、快速6、下面给出的四种排序方法中， D     排序是不稳定排序法。   A、插入        B、冒泡        C、二路归并      D、堆7、快速排序在最坏情况下时间复杂度是O（n2），比   A   的性能差。   A、堆排序             B、起泡排序            C、选择排序8、若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是   C   

8、。   A、快速排序    B、堆排序      C、归并[排序      D、直接插入排序9、就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是   A 。 A、堆排序<快速排序<归并排序    B、堆排序<归并排序<快速排序C、堆排序>归并排序>快速排序    D、堆排序>快速排序>归并排序E、以上答案都不对10、下面排序方法中，关键字比较次数与记录的初始排列无关的是   D   。    A、希尔排序     B、冒泡排序     C、直接插入排序    D、直