第9章排序習題答案
1. 假設含n個記錄的序列為，其相應的關鍵字序列為，這些關鍵字相互之間可以進行比較，即在它們之間存在著這樣乙個關係ks1≤ks2≤…≤ksn，按此固有關係將n個記錄序列重新排列為。若整個排序過程都在記憶體中完成，則稱此類排序問題為內部排序。
2. 3. 直接插入排序的基本思想是基於插入，開始假定第乙個記錄有序，然後從第二個記錄開始，依次插入到前面有序的子檔案中。
即將記錄r[i](2<=i<=n)插入到有序子串行r[1..i-1]中，使記錄的有序序列從r[1..i-1]變為r[1..
i] ，最終使整個檔案有序。共進行n-1趟插入。最壞時間複雜度是0(n2)，平均時間複雜度是0(n2)，空間複雜度是o(1)，是穩定排序。
簡單選擇排序的基本思想是基於選擇，開始有序序列長度為零，第i(1<=i二路並歸排序的基本思想是基於歸併，開始將具有n個待排序記錄的序列看成是n個長度為1的有序序列，然後進行兩兩歸併，得到n/2個長度為2的有序序列，再進行兩兩歸併，得到n/4個長度為4的有序序列。如此重複，經過log2n趟歸併，最終得到乙個長度為n的有序序列。最壞時間複雜度和平均時間複雜度都是0(nlog2n)，空間複雜度是o(n)，是穩定排序。
4. 錯誤。快速排序，堆排序和希爾排序是時間效能較好的排序方法，但都是不穩定的排序方法。
5. (1)堆排序，快速排序，歸併排序 (2)歸併排序 (3)快速排序 (4)堆排序
6. 不是。因為當序列已有序時，快速排序將退化成氣泡排序，時間複雜度為o(n2)。當待排序序列無序，使每次劃分完成後，樞軸兩側子檔案長度相當，此時快速排序效能最好。
7.外排序用k-路歸併(k>2)是因為k越小，歸併趟數越多，讀寫外存次數越多，時間效率越低，故，一般應大於最少的2路歸併。若將k-路歸併的敗者樹思想單純用於內排序，因其由勝者樹改進而來，且輔助空間大，完全可由堆排序取代，故將其用於內排序效率並不高。
《資料結構》習題答案
習題1一 選擇題 1 c 2 b 3 b 4 b d 5 c 6 a 7 c b 8 d 9 b 10 d 二 填空題 1 相互關係 2 一對 一 一對多 多對多 3 線性結構 集合 圖 樹 4 有窮性 確定性 可行性 輸入 輸出 5 o n 6 o n2 7 物理 8 1 log2n n n2 2...
資料結構實驗 排序
排序實驗 常用排序方法實現 實驗目的 1 熟悉常用的內部排序方法 插入排序 選擇排序 交換排序 基數排序和歸併排序 2 通過實驗，掌握排序的思路和方法，並能分析常用的排序方法的時間複雜度和穩定性。實驗要求 1 在vc 或tc環境下實現基本功能 2 先完成基本功能，基本功能為必做內容，有多餘時間的同學...
資料結構課後習題答案
5 選擇題 ccbdca 6 試分析下面各程式段的時間複雜度。1 o 1 2 o m n 3 o n2 4 o log3n 5 因為x 共執行了n 1 n 2 1 n n 1 2，所以執行時間為o n2 6 o 1 選擇題 babadbcabdcddac 2 演算法設計題 6 設計乙個演算法，通過一...