數據結構單元練習10

1、單元測驗單元測驗1010一判斷題（下列各題，正確的請在前面的括號內打一判斷題（下列各題，正確的請在前面的括號內打√；錯誤的打；錯誤的打╳）（ㄨ）（1）如果某種排序算法不穩(wěn)定，則該排序方法就沒有實用價值。（√）（2）希爾排序是不穩(wěn)定的排序。（ㄨ）（3）冒泡排序是不穩(wěn)定的排序。（√）（4）對n個記錄的進行快速排序，所需要的平均時間是O(nlog2n)。（ㄨ）（5）堆排序所需的時間與待排序的記錄個數無關。（√）（6）當待排序的元素個數很多時，

2、為了交換元素的位置要占用較多的時間，這是影響時間復雜度的主要因素。（ㄨ）（7）快速排序在任何情況下都比其它排序方法速度快。（√）（8）對快速排序來說，初始序列為正序或反序都是最壞情況。（√）（9）采用歸并排序可以實現(xiàn)外排序。（√）（10）采用希爾方法排序時，若關鍵字的排列雜亂無序，則效率最高。二填空題二填空題（1）大多數排序算法都有兩個基本的操作：比較和移動。（2）評價排序算法優(yōu)劣的主要標準是時間復雜度和算法所需的附加空間。（3）根據被

3、處理的數據在計算機中使用不同的存儲設備，排序可分為：內排序和外排序。（4）外排序是指在排序過程中，數據的主要部分存放在計算機的外存中。（5）對n個關鍵字進行冒泡排序，其可能的最小比較次數為：n1次。（6）在最壞情況下，在第i趟直接插入排序中，要進行i1次關鍵字的比較。（7）對n個關鍵字進行冒泡排序，時間復雜度為O(n2)。（8）快速排序在最壞情況下的時間復雜度是O(n2)。（9）對于n個記錄的集合進行歸并排序，所需要的平均時間為：O(l

4、og2n)。（10）對于n個記錄的集合進行歸并排序，所需要的附加空間是O(n)。（11）若原始數據接近無序，則選用快速排序最好。（12）在排序前，關鍵字值相等的不同記錄，排序后相對位置保持不變的排序方法，稱為穩(wěn)定排序方法。（13）在插入排序和選擇排序中，若初始數據基本正序，則選用插入排序較好。（14）當增量為1時，該趟希爾排序與直接插入排序基本一致。（15）第一趟排序后，序列中鍵值最大的記錄交換到最后的排序算法是冒泡排序。（16）依次將

5、每個記錄插入到一個有序的子文件中的排序方法稱為直接插入排序。（17）在插入排序、選擇排序和歸并排序中，排序是不穩(wěn)定的為：選擇排序。（18）在對一組記錄（54，38，96，23，15，72，60，45，83）進行直接插入排序時，當把第7個記錄60插入到有序表時，為尋找插入位置需比較3次。（19）兩個序列分別為：L1=25，57，48，37，92，86，12，33（15）對有n個記錄的表作快速排序，在最壞情況下，算法的時間復雜度是（B）。A

6、O(n)BO(n2)CO(nlog2n)DO(n3)（16）冒泡排序的方法對n個數據進行排序，第一趟排序共需要比較（C）次。A1B2Cn1Dn（17）對ｎ個不同的排序碼進行冒泡（遞增）排序，在下列（B）情況比較的次數最多。A從小到大排列好的B從大到小排列好的C元素無序D元素基本有序（18）用直接插入排序法對下面的四個序列進行由小到大的排序，元素比較次數最少的是（B）。A，94，32，40，90，80，46，21，69B21，32，46，

7、40，80，69，90，94C32，40，21，46，69，94，90，80D90，69，80，46，21，32，94，40（19）一組記錄的排序碼為(25，48，16，35，79，82，23，40)，其中含有4個長度為2的有序表，按歸并排序的方法對該序列進行一趟歸并后的結果為：（A）。A，16253548234079823672B16253548798223364072C16254835798223364072D16253548792

8、336407282（20）一個數據序列的關鍵字為：（46，79，56，38，40，84），采用快速排序，并以第一個數為基準得到第一次劃分的結果為：（C）A（38，40，46，56，79，84）B（40，38，46，79，56，84）C（40，38，46，56，79，84）D（40，38，46，79，56，84）四排序過程分析四排序過程分析1已知數據序列10，8，18，15，7，16，寫出采用直接插入算法排序時，每一趟排序的結果。解：10

9、81815716第一趟結束時結果：[810]1815716第二趟結束時結果：[81018]15716第三趟結束時結果：[8101518]716第四趟結束時結果：[78101518]16第五趟結束時結果：[7810151618]2已知數據序列18，17，60，40，07，32，73，65，寫出采用直接插入算法排序時，每一趟排序的結果。解：1817604007327365第一趟結束時結果：[1718]604007327365第二趟結束時結果