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

數(shù)據(jù)結(jié)構(gòu)習(xí)題第7章 吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院谷方明 1 第7章作業(yè) 247頁(yè) 每組的第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 若對(duì)序列 7 3 1 8 6 2 4 5 按從小到大排序 請(qǐng)寫出冒泡排序的第一趟結(jié)果 3 參考答案3 1 7 6 2 4 5 8 4 7 3 設(shè)文件 R1 R2 Rn 以單鏈表方式表示 指針變量FIRST指向表頭結(jié)點(diǎn) 且表中的結(jié)點(diǎn)結(jié)構(gòu)為 其中KEY為該結(jié)點(diǎn)的關(guān)鍵詞域 LINK為鏈接域 請(qǐng)給出這種線性表的直接插入排序算法 并要求算法的時(shí)間復(fù)雜度為O n2 且算法是穩(wěn)定的 5 算法InsertSort FIRST FIRST 對(duì)單鏈表直接插入排序 FIRST指向表頭結(jié)點(diǎn) 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è)計(jì)一算法 在盡可能少的時(shí)間內(nèi)重排數(shù)組 使所有取負(fù)值的關(guān)鍵詞放在所有取非負(fù)值的關(guān)鍵詞之前 并分析算法的時(shí)間復(fù)雜度 7 基本思想 以0為基準(zhǔn)記錄 使用快速排序的一次分劃過(guò)程即可 時(shí)間復(fù)雜度為O n 8 算法Part A n A 以0為基準(zhǔn)元素一次分劃 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 時(shí)才會(huì)發(fā)生交換 關(guān)鍵詞相同的記錄不會(huì)發(fā)生交換 即相同位置不變 因此是冒泡排序算法是穩(wěn)定的 11 7 10 類似于冒泡過(guò)程 從下到上 與之對(duì)應(yīng)的是下沉過(guò)程 從上到下 如果排序是冒泡和下沉的交替過(guò)程 證明如果經(jīng)過(guò)一趟冒泡和一次下沉后發(fā)現(xiàn)Rj和Rj 1 1 j n 1 沒(méi)有交換 則它們已經(jīng)進(jìn)入最終排序位置 12 參考答案 證明 如果經(jīng)過(guò)一趟冒泡和一次下沉后發(fā)現(xiàn)Rj和Rj 1 1 j n 1 沒(méi)有交換 那么有R1 R2 R3 Rn即所有記錄已經(jīng)進(jìn)入最終排序位置 13 7 18 奇偶交換排序算法的基本思想描述如下 排序過(guò)程通過(guò)對(duì)文件x i l i n 的若干次掃描來(lái)完成 第奇數(shù)次掃描 對(duì)所有下標(biāo)為奇數(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ù)次掃描 對(duì)所有下標(biāo)為偶數(shù)的記錄x i 與其后面的記錄x i 1 2 i n 1 相比較 若x i KEY x i 1 KEY 則交換x i 和x i 1 之內(nèi)容 重復(fù)上述過(guò)程直到排序完成為止 14 1 排序的終止條件是什么 2 完成該算法的具體設(shè)計(jì) 3 分析該算法的平均運(yùn)行時(shí)間 15 算法Sort X n S1 一趟掃描過(guò)程中 均沒(méi)有記錄交換則算法終止 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 次 無(wú)記錄交換 正序 2 最壞情況下比較 n 2 1趟 總比較次數(shù)為 n 1 n 2 1 次 每次比較都交換 總交換次數(shù)為 n 1 n 2或 n 1 3n 2 逆序 3 最好時(shí)間O n 最壞時(shí)間O n2 平均時(shí)間O n2 書上P201反序?qū)Φ钠骄鶖?shù) 17 正確性證明 數(shù)學(xué)歸納法 對(duì)元素個(gè)數(shù)n進(jìn)行歸納當(dāng)n 1是 算法正確假設(shè)當(dāng)n k時(shí) 算法能對(duì)n個(gè)元素的數(shù)組進(jìn)行排序 則當(dāng)n k 1時(shí) 進(jìn)行一趟分劃后 軸心元素R s 進(jìn)入了最終排序應(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個(gè) 按照假設(shè) 都能正確排序 因此 該算法能對(duì)全部k 1個(gè)元素正確排序 18 7 24 填充如下排序算法中的方框 并證明該算法的正確性 實(shí)質(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 分劃過(guò)程 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可能包含的最大元素個(gè)數(shù) 表示成M和n的函數(shù) 21 參考答案 當(dāng)n 2 M 才會(huì)在輔助堆棧中壓入第1個(gè)元素當(dāng)n 22 M 才會(huì)在輔助堆棧中壓入第2個(gè)元素 依此類推 當(dāng)n 2k M 才會(huì)在輔助堆棧中壓入第k個(gè)元素則2k n M k log2 n M 因此最多為floor log2 n M 個(gè) 22 7 30 證明 用淘汰賽找n個(gè)元素的最大元素正好需要n 1次元素比較 23 參考答案 證明 在淘汰賽中 每進(jìn)行一場(chǎng)比賽 即進(jìn)行依次比較 都恰淘汰1個(gè)元素 找到最大元素需要淘汰n 1個(gè)元素 因此需要n 1比較 24 7 31 證明 用淘汰賽找n個(gè)元素的最大元素所形成的樹高為 log2n 25 參考答案 證明 當(dāng)n 2K時(shí) 第1輪后剩下n 2 2K 1 第二輪后剩下n 4 2K 2 依次類推 第k輪淘汰賽后就剩下1個(gè)選手 就是最大元素 每一輪淘汰賽都對(duì)應(yīng)比賽樹中的一層 因此當(dāng)n 2K時(shí) 比賽樹的最大層數(shù)是k 比賽樹的高度是log2n當(dāng)n為任意數(shù)時(shí) 總可以找到一個(gè)k 使得2K 1 n 2k 只需要k輪淘汰賽就可以最大元素 對(duì)應(yīng)的比賽樹高為k 由2K 1 n 2k 得log2n k log2n 1 即形成的樹高為 log2n 26 7 35 設(shè)文件 R1 R2 Rn 是一個(gè)堆 Rn 1是任意一個(gè)結(jié)點(diǎn) 請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法 該算法把Rn 1添加到堆 R1 R2 Rn 中 并使 R1 R2 Rn Rn 1 成為一個(gè)堆 要求算法的時(shí)間復(fù)雜度為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 是一個(gè)堆 1 i n 請(qǐng)給出一個(gè)算法 該算法從 R1 R2 Rn 中刪除Ri 并使刪除后的文件仍然是堆 要求算法的時(shí)間復(fù)雜度為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 比較計(jì)數(shù) 本算法按關(guān)鍵詞K1 K2 Kn排序記錄R1 R2 Rn 一維數(shù)組COUNT 1 n 用來(lái)記錄各個(gè)記錄的排序位置 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 有一種簡(jiǎn)單的排序算法 叫做計(jì)數(shù)排序 CountSorting 這種排序算法對(duì)一個(gè)待排序的表 用數(shù)組表示 進(jìn)行排序 并將排序結(jié)果存放到另一個(gè)新的表中 必須注意的是 表中所有待排序的關(guān)鍵詞互不相同 計(jì)數(shù)排序算法針對(duì)表中的每個(gè)記錄 掃描待排序的表一趟 統(tǒng)計(jì)表中有多少個(gè)記錄的關(guān)鍵詞比該記錄的關(guān)鍵詞小 假設(shè)針對(duì)某一個(gè)記錄 統(tǒng)計(jì)出的計(jì)數(shù)值為c 那么 這個(gè)記錄在新的有序表中的合適的存放位置即為c 1 給出適用于計(jì)數(shù)排序的數(shù)據(jù)表定義