數(shù)據結構第十章排序練習及答案

1、一、選擇題1、在所有的排序方法中，關鍵字比較的次數(shù)與記錄的初始排序無關的是（）A、希爾排序B、冒泡排序C、插入排序D、選擇排序2、設有1000個無序的元素，希望用最快的速度挑選出其中前10個最大的元素，最好選用（）A、冒泡排序B、快速排序C、堆排序D、基數(shù)排序3、在待排序的元素序列基本有序的前提下，效率最高的排序方法是（）A、插入排序B、選擇排序C、快速排序D、歸并排序4、一組記錄為（46，79，56，38，40，84），則利用堆排序的方法建立的初始堆為（）A、79，46，56，38，40，84B、84，79，56，38，40，46C、84，79，56，46，40，38D、84，56，79，4

2、0，46，385、一組記錄為（46，79，56，38，40，84），則利用快速排序的方法，以第一個記錄為基準得到的一次劃分的結果為（）A、38，40，46，56，79，84B、40，38，46，79，56，84C、40，38，46，56，79，84D、40，38，46，84，56，796、一組記錄為（25，48，16，35，79，82，23，40，36，72），其中含有5個長度為2的有序表，按歸并排序的方法對該序列進行一次歸并后的結果為（）A、16，25，35，48，23，40，79，82，36，72B、16，25，35，48，79，82，23，36，40，72C、16，25，48，35，79

3、，82，23，36，40，72D、16，25，35，48，79，23，36，40，72，827、排序方法中，從未排序序列中依次取出元素與已排序序列（初始化為空）中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為（）A、希爾排序B、冒泡排序C、插入排序D、選擇排序8、用某種排序方法對線性表（25，84，21，47，15，27，68，35，20）進行排序時，元素序列的變化情況如下：1）25，84，21，47，15，27，68，35，202）20，15，21，25，47，27，68，35，843）15，20，21，25，35，27，47，68，844）15，20，21，25，27，35，4

4、7，68，84則采用的排序方法是（）A、選擇排序B、希爾排序C、歸并排序D、快速排序9、下述幾種排序方法中，平均查找長度最小的是（）A、插入排序B、選擇排序C、快速排序D、歸并排序10、下述幾種排序方法中，要求內存量最大的是（）A、插入排序B、選擇排序C、快速排序D、歸并排序11、快速排序方法在（）情況下，最不利于發(fā)揮其長處。A、要排序的數(shù)據量太大B、要排序的數(shù)據中含有多個相同值C、要排序的數(shù)據已基本有序D、要排序的數(shù)據個數(shù)為奇數(shù)12、對n個不同的關鍵字進行冒泡排序，在（）情況下比較的次數(shù)最多。A、從小到大排好序的B、從大到小排好序的C、元素無序D、元素基本有序13、對n個不同的關鍵字進行冒泡

5、排序，在元素無序的情況下比較的次數(shù)為（）A、n+1B、nC、n-1D、n（n-1）/214、快速排序在（）情況下最易發(fā)揮其長處。A、被排序的數(shù)據中含有多個相同的排序碼A、被排序的數(shù)據中含有多個相同的排序碼B、被排序的數(shù)據已基本有序C、被排序的數(shù)據完全無序D、被排序的數(shù)據中的最大值和最小值相差懸殊15、將5個不同的數(shù)據進行排序，至少需要比較（）A、4B、5C、6D、716、將5個不同的數(shù)據進行排序，至多需要比較（）A、8B、9C、10D、2517、下列關鍵字序列中（）是堆。A、16，72，31，23，94，53B、94，23，31，72，16，53C、16，53，23，94，31，72D、16，

6、23，53，31，94，7218、堆是一種（）排序。A、插入B、選擇C、交換D、歸并19、堆的形狀是一棵（）A、二叉排序樹B、滿二叉樹C、完全二叉樹D、平衡二叉樹二、填空題1、在對一組記錄（54，38，96，23，15，72，60，45，83）進行直接插入排序時，當把第7個記錄60插入到有序表時，為尋找插入位置需比較（3）次。2、在利用快速排序方法對一組記錄（54，38，96，23，15，72，60，45，83）進行快速排序時，遞歸調用而使用的棧所能達到的最大深度為（3），共需遞歸調用的次數(shù)為（5），其中第二次遞歸調用是對（72,60,96,83）一組記錄進行快速排序。3、在堆排序、快速排序和

7、歸并排序中，若只從存儲空間考慮，則應首先選取（堆排序）方法，其次選?。焖倥判颍┓椒?；若只從排序結果的穩(wěn)定性考慮，則應選?。w并排序）方法；若只從平均情況下排序最快考慮，則應選?。焖倥判颍┓椒ǎ蝗糁粡淖顗那闆r下，排序最快并且要求節(jié)省內存考慮，則應選?。ǘ雅判颍┓椒ā?、在插入排序、希爾排序、選擇排序、快速排序、堆排序、歸并排序和基數(shù)排序中，排序不穩(wěn)定的有（希爾排序、快速排序、堆排序）。5、在插入排序、希爾排序、選擇排序、快速排序、堆排序、歸并排序和基數(shù)排序中，平均比較次數(shù)最小的排序是（堆排序）；需內存容量最多的是（基數(shù)排序）。6、在堆排序和快速排序中，若原始記錄接近正序或反序，則選用（堆排序

8、），若原始記錄元序，最好選用（快速排序）。7、在插入和選擇排序中，若初始數(shù)據基本正序，則選用（插入排序），若初始數(shù)據基本反序，則選用（選擇排序）。8、對N個元素序列進行冒泡排序時，最小的比較次數(shù)是（N-1）。9、對N于個記錄的集合進行歸并排序，所需要的平均時間是（N*LOG2N）。10、對于N個記錄的集合進行冒泡排序，在最壞情況下所需要的時間是（N*（N-1）/2）。11、對于N個記錄的集合進行歸并排序，所需要的附加空間是（N）。12、設要將序（Q,H，C，Y，P，A，M，S，R，D，F(xiàn)，X）中的關鍵字按字母序的升序重新排列，則冒泡排序一趟掃描的結果是（H,C，Q，P，A，M,S，R，D，F(xiàn)，X，Y）；初始步長為4的希爾排序一趟的結果是（P,A，C，S，Q，D，F(xiàn)，X，R，H，M，Y）；二路歸并排序一趟掃描的結果是（H,Q，C