9-1 什麼是內排序? 什麼是外排序? 什麼排序方法是穩定的? 什麼排序方法是不穩定的?
【解答】
9-2 設待排序的關鍵碼序列為, 試分別寫出使用以下排序方法每趟排序後的結果。並說明做了多少次關鍵碼比較。
(1) 直接插入排序2) 希爾排序(增量為5,2,13) 起泡排序
(4) 快速排序5) 直接選擇排序6) 錦標賽排序
(7) 堆排序8) 二路歸併排序9) 基數排序
【解答】
9-3 在起泡排序過程中，什麼情況下關鍵碼會朝向與排序相反的方向移動，試舉例說明。在快速排序過程中有這種現象嗎？
【解答】
如果在待排序序列的後面的若干關鍵碼比前面的關鍵碼小，則在起泡排序的過程中，關鍵碼可能向與最終它應移向的位置相反的方向移動。例如，
57 40 38 11 13 34 48 75 6 19 9 7 如9向相反方向移動
6 57 40 38 11 13 34 48 75 7 19 9 如19向相反方向移動
6 7 57 40 38 11 13 34 48 75 9 19 如9向最終方向移動
6 7 9 57 40 38 11 13 34 48 75 19 如13向相反方向移動
6 7 9 11 57 40 38 13 19 34 48 75 如13向最終方向移動
6 7 9 11 13 57 40 38 19 34 48 75 如34向相反方向移動
6 7 9 11 13 19 57 40 38 34 48 75
6 7 9 11 13 19 34 57 40 38 48 75
6 7 9 11 13 19 34
9-4 試修改起泡排序演算法，在正反兩個方向交替進行掃瞄，即第一趟把關鍵碼最大的物件放到序列的最後，第二趟把關鍵碼最小的物件放到序列的最前面。如此反覆進行。
【解答】
template void datalist :: shake_sort ( )
}9-5 如果待排序的關鍵碼序列已經按非遞減次序有序排列，試證明函式quicksort( )的計算時間將下降到o(n2)。
9-6 在實現快速排序的非遞迴演算法時，可根據基準物件，將待排序關鍵碼序列劃分為兩個子串行。若下一趟首先對較短的子串行進行排序，試證明在此做法下，快速排序所需要的棧的深度為o(log2n)。
9-7 在實現快速排序演算法時，可先檢查位於兩端及中點的關鍵碼，取三者之中的數值不是最大也不是最小的關鍵碼作為基準物件。試編寫基於這種思想的快速排序演算法，並證明對於已排序的關鍵碼序列，該演算法的計算時間為o(nlog2n)。
9-8在使用非遞迴方法實現快速排序時, 通常要利用乙個棧記憶待排序區間的兩個端點。那麼能否用佇列來代替這個棧? 為什麼?
【解答】
可以用佇列來代替棧。在快速排序的過程中，通過一趟劃分，可以把乙個待排序區間分為兩個子區間，然後分別對這兩個子區間施行同樣的劃分。棧的作用是在處理乙個子區間時，儲存另乙個子區間的上界和下界，待該區間處理完成後再從棧中取出另一子區間的邊界，對其進行處理。
這個功能利用佇列也可以實現，只不過是處理子區間的順序有所變動而已。
9-9 試設計乙個演算法, 使得在o(n)的時間內重排陣列, 將所有取負值的關鍵碼排在所有取正值(非負值)的關鍵碼之前。
【解答】
9-10 奇偶交換排序是另一種交換排序。它的第一趟對序列中的所有奇數項i掃瞄，第二趟對序列中的所有偶數項i掃瞄。若a[i] > a[i+1]，則交換它們。
第三趟有對所有的奇數項，第四趟對所有的偶數項，…，如此反覆，直到整個序列全部排好序為止。
(1) 這種排序方法結束的條件是什麼？
(2) 寫出奇偶交換排序的演算法。
(3) 當待排序關鍵碼序列的初始排列是從小到大有序，或從大到小有序時，在奇偶交換排序過程中的關鍵碼比較次數是多少？
【解答】
9-11 請編寫乙個演算法，在基於單鏈表表示的待排序關鍵碼序列上進行簡單選擇排序。
【解答】
9-12 若參加錦標賽排序的關鍵碼有11個，為了完成排序，至少需要多少次關鍵碼比較？
【解答】
9-13 試給出適用於錦標賽排序的勝者樹的型別宣告。並寫乙個函式，對n個參加排序的物件，構造勝者樹。設n是2的冪。
【解答】
9-14 手工跟蹤對以下各序列進行堆排序的過程。給出形成初始堆及每選出乙個關鍵碼後堆的變化。
(1) 按字母順序排序：tim, dot, eva, rom, kim, guy, ann, jim, kay, ron, jan
(2) 按數值遞增順序排序：26, 33, 35, 29, 19, 12, 22
(3) 同樣7個數字，換乙個初始排列，再按數值的遞增順序排序：12, 19, 33, 26, 29, 35, 22
【解答】
9-15 如果只想在乙個有n個元素的任意序列中得到其中最小的第k (k<【解答】
一般來講，當n比較大且要選的資料k << n時, 採用堆排序方法中的篩選(調整)演算法最好。但當n比較小時，採用錦標賽排序方法更好。
例如，對於序列，選最小的資料6，需形成初始堆，進行18次資料比較；選次小資料7時，需進行4次資料比較；再選資料9時，需進行6次資料比較；選資料11時，需進行4次資料比較。
但如果選用錦標賽排序，對於有n個資料的序列，選最小資料需進行n -1次資料比較，以後每選乙個資料，進行資料比較的次數，均需 log2n 次。例如，同樣12個資料，第一次選最小的資料6，需進行11次資料比較，以後選7、9、11時，都是 log212 = 3次資料比較。
9-16 希爾排序、簡單選擇排序、快速排序和堆排序是不穩定的排序方法, 試舉例說明。
【解答】
(1) 希爾排序512 275 275* 061 } 增量為2
275* 061 512 275 } 增量為1
061 275* 275 512 }
(2) 直接選擇排序 i = 1
061 275* 512 275 } i = 2
061 275* 512 275 } i = 3
061 275* 275 512 }
(3) 快速排序512 275 275* }
275* 275 512 }
(4) 堆排序275 275* 061 170 } 已經是最大堆，交換275與170
170 275* 061 275 } 對前3個調整
275* 170 061 275 } 前3個最大堆，交換275*與061
061 170 275* 275 } 對前2個調整
170 061 275* 275 } 前2個最大堆，交換170與061
061 170 275* 275 }
9-17 設有n個待排序元素存放在乙個不帶表頭結點的單鏈表中, 每個鍊錶結點只存放乙個元素, 頭指標為r。試設計乙個演算法, 對其進行二路歸併排序, 要求不移動結點中的元素, 只改各鏈結點中的指標, 排序後r仍指示結果鍊錶的第乙個結點。（提示：
先對待排序的單鏈表進行一次掃瞄, 將它劃分為若干有序的子鍊錶, 其表頭指標存放在乙個指標佇列中。當佇列不空時重複執行, 從佇列中退出兩個有序子鍊錶, 對它們進行二路歸併, 結果鍊錶的表頭指標存放到佇列中。如果佇列中退出乙個有序子煉表後變成空佇列, 則演算法結束。
這個有序子煉錶即為所求。)
【解答】
(1) 兩路歸併演算法
2019考研清華大學資料結構專業真題回憶版
1.長度分別為m 和n 的公升序鍊錶，若將它們合併為乙個長度為m n 的降序鍊錶，則最壞情況下的時間複雜度是 a.o n b.o m n c.o min m,n d.o max m,n 2.乙個棧的入棧序列為1,2,3,n 其出棧序列是 p1,p2,p3,pn。若p2 3，則p3 可能取值的個數是 ...
資料結構C語言版第7章練習清華大學出版社
第七章資料結構作業 第七章圖 選擇題1 設無向圖的頂點個數為n，則該圖最多有 條邊。a n 1 b n n 1 2 c n n 1 2 d 0 e n2 2 乙個n個頂點的連通無向圖，其邊的個數至少為 a n 1b nc n 1d nlogn 3 乙個有n個結點的圖，最少有 個連通分量，最多有 個連...
資料結構第2章答案
一 填空題 01 當線性表的元素總數基本穩定，且很少進行插入和刪除操作，但要求以最快的速度訪問線性表中的元素時，應採用順序儲存結構。02 線性表l a1,a2,an 用陣列表示，假定刪除表中任一元素的概率相同，則刪除乙個元素平均需要移動元素的個數是 n 1 2。03 在有n個元素的順序表中插入乙個新...