數(shù)據(jù)結(jié)構(gòu)習題課7ppt課件.ppt

數(shù)據(jù)結(jié)構(gòu)習題第7章 吉林大學計算機科學與技術(shù)學院谷方明 1 第7章作業(yè) 247頁 每組的第1題是必交的 即7 2 7 5 7 18 7 24 7 497 2 7 3 7 5 7 8 7 10 7 18 7 24 7 26 7 30 7 31 7 35 7 367 49 7 50 2 7 2 若對序列 7 3 1 8 6 2 4 5 按從小到大排序 請寫出冒泡排序的第一趟結(jié)果 3 參考答案3 1 7 6 2 4 5 8 4 7 3 設(shè)文件 R1 R2 Rn 以單鏈表方式表示 指針變量FIRST指向表頭結(jié)點 且表中的結(jié)點結(jié)構(gòu)為 其中KEY為該結(jié)點的關(guān)鍵詞域 LINK為鏈接域 請給出這種線性表的直接插入排序算法 并要求算法的時間復雜度為O n2 且算法是穩(wěn)定的 5 算法InsertSort FIRST FIRST 對單鏈表直接插入排序 FIRST指向表頭結(jié)點 IS1 邊界 IF LINK FIRST NULLORLINK LINK FIRST NULL THENRETRUN IS2 插入排序 q LINK FIRST q0 LINK q WHILE qNULL p LINK FIRST p0 FIRST WHILE KEY p q DO p0 p p LINK p IF KEY p KEY q THEN LINK q0 LINK q LINK p0 q LINK q p q LINK q0 ESLE q0 q q LINK q0 6 7 5 設(shè)計一算法 在盡可能少的時間內(nèi)重排數(shù)組 使所有取負值的關(guān)鍵詞放在所有取非負值的關(guān)鍵詞之前 并分析算法的時間復雜度 7 基本思想 以0為基準記錄 使用快速排序的一次分劃過程即可 時間復雜度為O n 8 算法Part A n A 以0為基準元素一次分劃 P1 初始化 i 1 j n P2 以0分劃 WHILEi0ANDi jDOj j 1 IFi jTHENRi Rj 9 7 8 討論冒泡排序算法的穩(wěn)定性 10 參考答案 冒泡排序中 每一趟冒泡 相鄰的關(guān)鍵詞只有滿足 Rj Rj 1 時才會發(fā)生交換 關(guān)鍵詞相同的記錄不會發(fā)生交換 即相同位置不變 因此是冒泡排序算法是穩(wěn)定的 11 7 10 類似于冒泡過程 從下到上 與之對應(yīng)的是下沉過程 從上到下 如果排序是冒泡和下沉的交替過程 證明如果經(jīng)過一趟冒泡和一次下沉后發(fā)現(xiàn)Rj和Rj 1 1 j n 1 沒有交換 則它們已經(jīng)進入最終排序位置 12 參考答案 證明 如果經(jīng)過一趟冒泡和一次下沉后發(fā)現(xiàn)Rj和Rj 1 1 j n 1 沒有交換 那么有R1 R2 R3 Rn即所有記錄已經(jīng)進入最終排序位置 13 7 18 奇偶交換排序算法的基本思想描述如下 排序過程通過對文件x i l i n 的若干次掃描來完成 第奇數(shù)次掃描 對所有下標為奇數(shù)的記錄x i 與其后面的記錄x i 1 l i n 1 相比較 若x i KEY x i 1 KEY 則交換x i 和x i 1 的內(nèi)容 第偶數(shù)次掃描 對所有下標為偶數(shù)的記錄x i 與其后面的記錄x i 1 2 i n 1 相比較 若x i KEY x i 1 KEY 則交換x i 和x i 1 之內(nèi)容 重復上述過程直到排序完成為止 14 1 排序的終止條件是什么 2 完成該算法的具體設(shè)計 3 分析該算法的平均運行時間 15 算法Sort X n S1 一趟掃描過程中 均沒有記錄交換則算法終止 change 1 while change change 0 fori 1ton 1step2 奇交換if X i key X i 1 key X i X i 1 change 1 fori 2ton 1step2 偶交換if X i key X i 1 key X i X i 1 change 1 16 1 最好情況下 比較一趟 每趟中奇交換偶交換比較次數(shù)共 n 1 次 無記錄交換 正序 2 最壞情況下比較 n 2 1趟 總比較次數(shù)為 n 1 n 2 1 次 每次比較都交換 總交換次數(shù)為 n 1 n 2或 n 1 3n 2 逆序 3 最好時間O n 最壞時間O n2 平均時間O n2 書上P201反序?qū)Φ钠骄鶖?shù) 17 正確性證明 數(shù)學歸納法 對元素個數(shù)n進行歸納當n 1是 算法正確假設(shè)當n k時 算法能對n個元素的數(shù)組進行排序 則當n k 1時 進行一趟分劃后 軸心元素R s 進入了最終排序應(yīng)在的位置R i 即R i 之前的元素R s R i 1 都小于等于R i R i 之后的元素R i 1 R e 都大于等于R i 由于R s R i 1 R i 1 R e 任意一部分最多為k個 按照假設(shè) 都能正確排序 因此 該算法能對全部k 1個元素正確排序 18 7 24 填充如下排序算法中的方框 并證明該算法的正確性 實質(zhì)是一趟快速排序算法 算法PartA R s e 分劃文件 Rs Rs 1 Re 且Ks 1 Ke 1 PA1 初始化 i s j K Ks R Rs e 1 19 PA2 分劃過程 whilei jdo j j 1 while doj j 1 if i j thenj i else Ri Rj i i 1 whileKi Kdoi i 1 if thenRj Ri PA3 Kj K i j Rj R 20 7 26 分析算法HSort中的堆棧S可能包含的最大元素個數(shù) 表示成M和n的函數(shù) 21 參考答案 當n 2 M 才會在輔助堆棧中壓入第1個元素當n 22 M 才會在輔助堆棧中壓入第2個元素 依此類推 當n 2k M 才會在輔助堆棧中壓入第k個元素則2k n M k log2 n M 因此最多為floor log2 n M 個 22 7 30 證明 用淘汰賽找n個元素的最大元素正好需要n 1次元素比較 23 參考答案 證明 在淘汰賽中 每進行一場比賽 即進行依次比較 都恰淘汰1個元素 找到最大元素需要淘汰n 1個元素 因此需要n 1比較 24 7 31 證明 用淘汰賽找n個元素的最大元素所形成的樹高為 log2n 25 參考答案 證明 當n 2K時 第1輪后剩下n 2 2K 1 第二輪后剩下n 4 2K 2 依次類推 第k輪淘汰賽后就剩下1個選手 就是最大元素 每一輪淘汰賽都對應(yīng)比賽樹中的一層 因此當n 2K時 比賽樹的最大層數(shù)是k 比賽樹的高度是log2n當n為任意數(shù)時 總可以找到一個k 使得2K 1 n 2k 只需要k輪淘汰賽就可以最大元素 對應(yīng)的比賽樹高為k 由2K 1 n 2k 得log2n k log2n 1 即形成的樹高為 log2n 26 7 35 設(shè)文件 R1 R2 Rn 是一個堆 Rn 1是任意一個結(jié)點 請設(shè)計一個算法 該算法把Rn 1添加到堆 R1 R2 Rn 中 并使 R1 R2 Rn Rn 1 成為一個堆 要求算法的時間復雜度為O log2n 分析 堆有大根堆和小根堆 教材上用的是大根堆 27 參考答案 算法Insert R n x R n 在堆中插入元素x 從下往上調(diào)整堆 U1 x放入R n 1 n n 1 R n x U2 從下往上調(diào)整 稱上浮 i n WHILE i 1ANDR i 2 R i DOi i 2 28 C inth MAXN intn 0 voidinsert x h n x for intj n j 1 j 1 上浮if a j a j 1 swap a j a j 1 29 7 36 文件 R1 R2 Rn 是一個堆 1 i n 請給出一個算法 該算法從 R1 R2 Rn 中刪除Ri 并使刪除后的文件仍然是堆 要求算法的時間復雜度為O log2n 30 參考答案 算法Delete R n i R n 在堆中刪除元素R i 從上往下調(diào)整堆 D1 R i 與R n 交換 R i R n n n 1 D2 從上往下調(diào)整 稱下沉 j i WHILE 2 jR j OR2 j 1R j DO y 2 j IF 2 j 1R 2 j THENy y 1 R j R y j y 31 C inth MAXN intn 0 voiddelete inti h i h n while 2 ih i 2 i 1h i inty 2 i if y 1h y y swap h i h y i y 32 7 49 填充如下排序算法中的方框 并討論該算法的穩(wěn)定性 算法C R n 比較計數(shù) 本算法按關(guān)鍵詞K1 K2 Kn排序記錄R1 R2 Rn 一維數(shù)組COUNT 1 n 用來記錄各個記錄的排序位置 33 C1 FORi 1TOnDO C2 FORi nTO2 DOFORj i 1TO1STEP 1DOIF THENCOUNT j COUNT j 1ELSE STEP 1 Kj Ki count i count i 1 count i 1 34 穩(wěn)定性討論 該算法是穩(wěn)定的 35 7 50 有一種簡單的排序算法 叫做計數(shù)排序 CountSorting 這種排序算法對一個待排序的表 用數(shù)組表示 進行排序 并將排序結(jié)果存放到另一個新的表中 必須注意的是 表中所有待排序的關(guān)鍵詞互不相同 計數(shù)排序算法針對表中的每個記錄 掃描待排序的表一趟 統(tǒng)計表中有多少個記錄的關(guān)鍵詞比該記錄的關(guān)鍵詞小 假設(shè)針對某一個記錄 統(tǒng)計出的計數(shù)值為c 那么 這個記錄在新的有序表中的合適的存放位置即為c 1 給出適用于計數(shù)排序的數(shù)據(jù)表定義