资源描述：
《数据结构第10章排序练习及答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、9.1 选择题1．从末排序的序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在排序序列的合适位置，该排序方法称为（ ）排序法。A）插入B）选择C）希尔D）二路归并【答案】A2．下面各种排序方法中，最好情况下时间复杂度为O(n)的是（ ）A）快速排序B）直接插入排序C）堆排序D）归并排序【答案】B3．用某种排序方法对线性表（25,84,21,47,15,27,68,35,20）进行排序时，无序序列的变化情况如下：258421471527683520201521254727683584152021253527476884152021
2、252735476884则所采用的排序方法是（ ）Ａ）选择排序 Ｂ）希尔排序 Ｃ）归并排序 Ｄ）快速排序【答案】Ｄ4．下面给出的四种排序法中，（ ）排序是不稳定排序法。A）插入B）冒泡C）二路归并D）堆【答案】D5．快速排序方法在（ ）情况下最不利于发挥其长处。Ａ）要排序的数据量太大Ｂ）要排序的数据中含有多个相同值Ｃ）要排序的数据已基本有序Ｄ）要排序的数据个数为奇数【答案】Ｃ6．一组记录的关键码为（46,79,56,38,40,84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）Ａ）38,40,46,56,79,
3、84B）40,38,46,79,56,84C）40,38,46,56,79,84D）40,38,46,84,56,79【答案】Ｃ7．对记录的关键码{50，26，38，80，70，90，8，30，40，20}进行排序，各趟排序结束时的结果为：50,26,38,80,70,90,8,30,40,2050,8,30,40,20,90,26,38,80,7026,8,30,40,20,80,50,38,90,708,20,26,30,38,40,50,70,80,90其使用的排序方法是（ ）A）快速排序B）基数排序C）希尔排序D）归并排序【答案】C8．以下
4、序列不是堆的是（ ）A）100,85,98,77,80,60,82,40,20,10,66B）100,98,85,82,80,77,66,60,40,20,10C）10,20,40,60,66,77,80,82,85,98,100D）100,85,40,77,80,60,66,98,82,10,20【答案】D【解析】根据堆采用完全二叉树的顺序存储形式及堆的特点，因第一个结点即根结点关键字值最大，则应建立一个大根堆，但依据此数据序列建立起堆后关键字值为40的左右孩子结点分别为60、66，不符合大根堆特点。9．一组记录的关键字为{45，80，55，40
5、，42，85}，则利用堆排序的方法建立的初始堆为（ ）A）80,45,50,40,42,85B）85,80,55,40,42,45C）85,80,55,45,42,40D）85,55,80,42,45,40【答案】B10．一组记录的关键字为{25，50，15，35，80，85，20，40，36，70}，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果为（ ）A）15,25,35,50,20,40,80,85,36,70B）15,25,35,50,80,20,85,40,70,36C）15,25,50,35,80,85,20
6、,36,40,70D）15,25,35,50,80,20,36,40,70,85【答案】A【解析】对5个长度为2的有序表一趟归并后得到前两个长度为4的有序表和最后一个长度为2的有序表，故选A。11．n个元素进行冒泡排序的过程中，最好情况下的时间复杂度为（ ）A）O(1)B）O(log2n)C）O(n2)D）O(n)【答案】D【解析】最好情况下至少需要一趟排序，即比较n-1次，故选D。12．下述几种排序方法中，要求内存量最大的是（ ）A）插入排序B）选择排序C）快速排序D）归并排序【答案】D【解析】插入排序和选择排序需要的辅助空间为O(1)，快速排
7、序需要的辅助空间为O(log2n)，归并排序需要的辅助空间为O(n)，因此选D。13．下面排序方法中，时间复杂度不是O(n2)的是（ ）A）直接插入排序B）二路归并排序C）冒泡排序D）直接选择排序【答案】B【解析】直接插入排序、冒泡排序和直接选择排序的时间复杂度为O(n2)，而二路归并排序的时间复杂度为O(nlog2n)，故选B。 填空题1．当数据量特别大需借助外部存储器对数据进行排序，则这种排序称为_____________。【答案】外部排序2．在堆排序、快速排序和归并排序中，若从节省存储空间考虑，则应首先选取_____________方法，其次
8、选取_____________方法；若只从排序结果的稳定性考虑，则应先择_____________方法；若只
