1、習題七參考答案一、選擇題1 內部排序算法的穩定性是指（D ）。A 該排序算法不允許有相同的關鍵字記錄B 該排序算法允許有相同的關鍵字記錄C .平均時間為0 （n log n）的排序方法D .以上都不對2. 下面給出的四種排序算法中，（B ）是不穩定的排序。A 插入排序B 堆排序C 二路歸并排序D 冒泡排序3. 在下列排序算法中，哪一種算法的時間復雜度與初始排序序列無關（D ）。A .直接插入排序B .冒泡排序C .快速排序D .直接選擇排序4. 關鍵字序列（8, 9, 10, 4, 5, 6, 20, 1 , 2）只能是下列排序算法中（C ）的兩趟排序后的結果。 A 選擇排序B.冒泡排序C.插

2、入排序D.堆排序5下列排序方法中，（D）所需的輔助空間最大。A .選擇排序B.希爾排序C.快速排序D .歸并排序6.組記錄的關鍵字為（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,84,56,79)7.在對一組關鍵字序列70 , 55, 100, 15, 33, 65, 50, 40, 95，進行直接插入排序時，把65插入，需要比較（A）次。A. 2B. 4C.

3、 6D. 88.從待排序的序列中選出關鍵字值最大的記錄放到有序序列中，該排序方法稱為(B)。A.希爾排序B.直接選擇排序C.冒泡排序D.快速排序9.當待排序序列基本有序時，以下排序方法中,（B ）最不利于其優勢的發揮。A.直接選擇排序B.快速排序C.冒泡排序D.直接插入排序10 .在待排序序列局部有序時，效率最咼的排序算法是（B ）。A.直接選擇排序B.直接插入排序C.快速排序D.歸并排序、填空題1. 執行排序操作時，根據使用的存儲器可將排序算法分為內排序 和 外排序 。2. 在對一組記錄序列50,40,95,20,15,70,60,45,80進行直接插入排序時，當把第7個記錄60插入到有序表

4、中時，為尋找插入位置需比較3 次。3. 在直接插入排序和直接選擇排序中，若初始記錄序列基本有序，則選用直接插入排序。4. 在對一組記錄序列50,40,95,20,15,70,60,45,80進行直接選擇排序時，第4次交換和選擇后，未排序記錄為50,70,60,95,80。5. n個記錄的冒泡排序算法所需的最大移動次數為3n（n-1）/2，最小移動次數為0。6. 對n個結點進行快速排序，最大的比較次數是_n（n-1）/2。7. 對于堆排序和快速排序，若待排序記錄基本有序，則選用堆排序 。8. 在歸并排序中，若待排序記錄的個數為20,則共需要進行 5趟歸并。9. 若不考慮基數排序，則在排序過程中，

5、主要進行的兩種基本操作是關鍵字的比較和數據元素的移動。10. 在插入排序、希爾排序、選擇排序、快速排序、堆排序、歸并排序和基數排序中，平均比較次數最少 的是快速排序，需要內存容量最多的是基數排序 。三、算法設計題1 .試設計算法，用插入排序方法對單鏈表進行排序。參考答案：public static void in sertSort(L in kList L) Node p, q, r, u;p = L.getHead().getNext();L.getHead().setNext(null);/ 置空表，然后將原鏈表結點逐個插入到有序表中while (p != null) / 當鏈表尚未到尾，

6、 p 為工作指針r = L.getHead();q = L.getHead().getNext();while (q != null && (Integer.parseInt(String) q.getData() <=(Integer.parseInt(String) p.getData() /查P結點在鏈表中的插入位置，這時q是工作指針r = q;q = q.getNext();u = p.getNext();p.setNext(r.getNext();r.setNext(p);p = u;/將P結點鏈入鏈表中，r是q的前驅，u是下一個待插入結點的指針2 試設計算法，

7、用選擇排序方法對單鏈表進行排序。參考答案 :/ 單鏈表選擇排序算法public static void selectSort(LinkList L) /p 為當前最小 ,r 為此過程中最小 ,q 為當前掃描接點Node p, r, q;Node newNode = new Node();newNode.setNext(L.getHead();L.setHead(newNode);/制造一個最前面的節點newNode解決第一個節點的沒有前續節點需要單獨語句的問題。p = L.getHead();while (p.getNext().getNext() != null) r = p.getNext

8、();q = p.getNext().getNext();while (q.getNext() != null) if (Integer.parseInt(String) q.getNext().getData() <=(Integer.parseInt(String) r.getNext().getData() r = q;q = q.getNext();if (r != p) /交換 p 與 rNode swap = r.getNext();r.setNext(r.getNext().getNext(); /r的 next 指向其后繼的后繼swap.setNext(p.getNext

9、();p.setNext(swap); /p的后繼為 swap p = p.getNext();/while p.setNext(null);3 試設計算法，實現雙向冒泡排序 ( 即相鄰兩遍向相反方向冒泡 ) 。 參考答案 :/ 產生隨機數方法public static int random(int n) if (n > 0) int table = new intn;for (int i = 0; i < n; i+) tablei = (int) (Math.random() * 100);/ 產生一個 0100 之間的隨機數return table;return null;/

10、 輸出數組元素方法 public static void print(int table) if (table.length > 0) for (int i = 0; i < table.length; i+) System.out.print(tablei + " ");System.out.println();/ 雙向冒泡排序方法 public static void dbubblesort(int table) int high = table.length;int left = 1;int right = high - 1;int t = 0;do /

11、正向部分for (int i = right; i >= left; i-) if (tablei < tablei - 1) int temp = tablei; tablei = tablei - 1; tablei - 1 = temp; t = i;left = t + 1;/ 反向部分for (int i = left; i < right + 1; i+) if (tablei < tablei - 1) int temp = tablei; tablei = tablei - 1; tablei - 1 = temp; t = i;right = t -

12、1; while (left <= right);4 試設計算法，使用非遞歸方法實現快速排序。 參考答案 :public static void NonrecursiveQuickSort(int ary) if (ary.length < 2) return;/ 數組棧：記錄著高位和低位的值int stack = new int2ary.length;/ 棧頂部位置int top = 0;/ 低位，高位，循環變量，基準點/ 將數組的高位和低位位置入棧 stack1top = ary.length - 1; stack0top = 0;top+;/ 要是棧頂不空，那么繼續while

13、 (top != 0) /將高位和低位出棧/低位：排序開始的位置top-;int low = stack0top;/高位：排序結束的位置int high = stack1top; /將高位作為基準位置/基準位置int pivot = high;int i = low;for (int j = low; j < high; j+) if (aryj <= arypivot) int temp = aryj; aryj = aryi; aryi = temp; i+;/ 如果 i 不是基準位，那么基準位選的就不是最大值/而 i 的前面放的都是比基準位小的值，那么基準位/的值應該放到 i

14、 所在的位置上if (i != pivot) int temp = aryi; aryi = arypivot; arypivot = temp;if (i - low > 1) / 此時不排 i 的原因是 i 位置上的元素已經確定了， i 前面的都是比 i 小的， i 后面的都 是比 i 大的stack1top = i - 1;stack0top = low;top+;/ 當 high-i 小于等于 1 的時候，就不往棧中放了，這就是外層 while 循環能結束的原因/ 如果從 i 到高位之間的元素個數多于一個，那么需要再次排序if (high - i > 1) / 此時不排 i

15、 的原因是 i 位置上的元素已經確定了， i 前面的都是比 i 小的， i 后面的都 是比 i 大的stack1top = high;stack0top = i + 1;top+;5 試設計算法，判斷完全二叉樹是否為大頂堆。參考答案 :boolean checkmax(BiTreeNode t) / 判斷完全二叉樹是否為大頂堆BiTreeNode p = t;if (p.getLchild() = null && p.getRchild() = null) return true; else if (p.getLchild() != null && p.getR

16、child() != null) if (RecordNode)p.getLchild().getData().getKey().compareTo(RecordNode) p.getData().getKey() <= 0 && (RecordNode) p.getRchild().getData().getKey().compareTo(RecordNode) p.getData().getKey() <= 0) return checkmax(p.getLchild() && checkmax(p.getRchild(); elsereturn false; else if (p.getLchild() != null && p.getRchild() = null) if (RecordNode)p.getLchild().getData().getKey().compareTo(RecordNode) p.getData().getKey() <= 0) return checkmax(p.