【正文】 排序 L 從左至右成對掃描 L If Li=Li+1 Add Li to C i←i+2 效率分析 : 假設(shè)排序的效率是 O(nlogn),則該算法效率 O((n+m)logn))+ Θ (n+m) =O(slogs) where s=max{n,m} a. 排序數(shù)組 ,然后返回它的第一和最后元素 . 假設(shè)排序的效率是 O(nlogn),則該算法效率 O(nlogn)+Θ (1)+Θ (1)= O(nlogn) ,所以優(yōu)于基于預排序 的算法 習題 . 28 . 29 . 二叉查找樹中最大值和最小值分別是樹中最右邊和最左邊的結(jié)點 .因此 ,從根開始 ,沿著向左的路徑一直走到這樣的結(jié)點 :它的左孩子為空 .這個結(jié)點里的值就是最小值 .同理 ,可以找到最大值 .最后 ,這兩個值做一次減法運算即可 . 算法的效率 : Θ (logn)+ Θ (logn)+ Θ (1)= Θ (logn) . 8. 不成立 . 例如 :列表 {A,B},查找 A,二分查找只做 1次比較 .而在 23樹中查找則要做 2 次比較 習題 1. 30 a. b. c. 錯誤 .對于列表 {1,2,3} 按自頂向下 :{3,1,2} 自底向上 :{3,2,1} ,尋找并刪除堆中最小元素 ,然后確定其時間效率 Hints: 最小元素一定在堆的葉子中 . 在堆 H[1..n]的后半部分 ,(H[ n/2 +1],? ,H[n])中 查找最小元素 ,并與最后的元素H[n]互換 ,刪除最后的元素 .堆規(guī)模降 1,如果 必要的話 ,調(diào)整元素 H[n],使其滿足雙親優(yōu)勢 . 效率分析 : 查找 :Θ (n) 交換并刪除 : Θ (1)+ Θ (1) 調(diào)整為堆 :O(logn) ,在給定的堆 H中尋找并刪除一個包含給定值 v的元素 ,然后確定其時間效率 . Hints: 在 H中順序查找滿足條件的第一個元素 H[i]. H[i]與 H[n]互換 . 刪除最后元素 堆規(guī)模降 1 調(diào)整元素 H[n]使其滿足雙親優(yōu)勢 效率分析 : 查找 :Θ (n) 交換并刪除 : Θ (1)+ Θ (1) 調(diào)整為堆 :O(logn) 習題 1. 31 乘法總次數(shù) M(n) 加法總次數(shù) A(n) 32 習題 {a,b,c,d},用分布計數(shù)算法對下面的列表按照字母順序排序 . b,c,d,c,b,a,a,b 解 : 輸入 A: b,c,d,c,b,a,a,b 頻率 : 分布值 : ? 是穩(wěn)定的 . 因為算法從右至左掃描輸入 ,等值元素也是被從右至左地放入排序好的數(shù)組里 . 習題 1. 應(yīng)用 Horspool算法在下面的文本中查找模式 BAOBAB: BESS_KNEW_ABOUT_BAOBABS 解 :字符移動表 : 匹配過程 : Horspool 算法在一個長度為 n 的文本中查找一個長度為 m 的模式 ,請分別給出下面兩種例子 . 輸入 hints: a. 在 n個 ” 0” 組成的文本中查找 ” 10..0” (長度為 m),查找次數(shù) Cw=m(nm+1) b. 在 n個 ” 0” 組成的文本中查找由 m個 ” 0” 組成的模式 ,查找次數(shù) Cb=m 習題 33 1. 對于輸入 30,20,56,75,31,19 和散列函數(shù) h(K)=Kmod11 a. 構(gòu)造它們的開散列表 b. 求在本表中成功查找的最大鍵值比較次數(shù) c. 求在本表中成功查找的平均比較次數(shù) Hints: 鍵 值列表 : 30,20,56,75,31,19 Hash 函數(shù) : h(K)=Kmod11 Hash 地址 : 開散列表 : (查找鍵值 31) c. 2.(題略 ) a. 鍵值列表 : 30,20,56,75,31,19 Hash 函數(shù) : h(K)=Kmod11 Hash 地址 : 閉散列表 : (查找鍵值 19) 34 c. 35 第 8章 動態(tài)規(guī)劃 習題 ?(基于分解為更小的子問題 ) 么主要的不同點 ? 分治法分解出的子問題相對獨立 ,而動態(tài)規(guī)劃則相互交疊 。 分治法通常不需要保存子問題的結(jié)果 ,而動態(tài)規(guī)劃則保存 2. C(6,3) b. 為了計算 C(n,k),需要填充算法的動態(tài)規(guī)劃表 ,在填表時是否可以一列接一列地填 ,而不是一行接一行地填 ? 解 :a. .每一列從主對線由 1開始 ,自上而下填表 . : 解 : kknkknkkk 2121)(2 )1( 2 ?????? 對 n,k=0,顯然 : nkkknk ??? 2121 2 成立 . 對 n=2, 0=k=n,則有 : nknknknkkknk 412121212121 2 ?????? 習題 ,應(yīng)用 warshall 算法求它的傳遞閉包 ????????????0000100010000010 解 : 36 ?????????????0000100010000010)0(R ?????????????0000100010000010)1(R ?????????????0000100010001010)2(R ?????????????0000100010001010)3(R ?????????????0000100010001010)4(R 3. 如果不使用額外的存儲空間來存儲 warshall算法中間矩陣的元素 ,如何實現(xiàn) ? Hints: Warshall算法計算新矩陣是按下面的遞推關(guān)系 : 可以看出從 R(k1)生成 R(k)時 ,第 k 行和第 k 列的并沒有改變 .因此 ,對每個 i,j 來說 ,第 i行第 j列的新值 R(k)[i,j]可以覆蓋對應(yīng)位置上的 R(k1)[i,j] 4. 如何重構(gòu) warshall算法最內(nèi)層循環(huán) ,使得它到少對于某此輸入來說運行得列快 ? hints: 如果 R(k1)[i,k]=0,那么 ],[],[],[],[],[ )1()1()1()1()( jiRjkandRkiRjiRjiR kkkkk ???? ??????? ,則不需要進行最內(nèi)層循環(huán) . 由于 R(k1)[i,k]不依賴于 j,所以 R(k1)[i,k]=0 這個判斷可以在最內(nèi)層 j 循環(huán)外面進行 .算法改進如下 : Warshall2(A[1..n,1..n]) //內(nèi)層循環(huán)更有效的 Warshall 算法 //輸入 :n節(jié)點的有向圖的鄰接矩陣 A //輸出 :該圖的傳遞閉包 A for k← 1 to n do for i← 1 to n do if A[i,k] for j← 1 to n do if A[k,j] A[i,j]=true Return A 習題 . 解 : 37 . 算法 optimalBST的時間效率為什么是立方級 ? b. 算法 optimalBST的空間效率為什么是平方級 ? 解 : : 38 b. 算法 optimalBST使用了兩個表 :C(n+1) (n+1),Rn n,并且每個表只填了一半 . ,來從根表中生成最優(yōu)二叉查找樹 Algorithms OptimalTree(i,j) //輸入 :有序列表的第一和最后序號 //輸入 :先序遍歷最優(yōu)二叉查找樹節(jié)點編號的列表 39 習題 給出一個找零問題的實例 ,使得貪婪算法不能輸出一個最優(yōu)解 . 為找零問題寫一個貪婪算法的偽代碼 ,它以金額 n 和硬幣的面額 d1d2…dm作為輸入 .以 n 的函數(shù)形式給出該算法的效率類型 . Hints: Algorithms change(n,D[1..m]) //用貪婪法求找零問題 //輸入 :非負整數(shù) n,硬幣面額以降序排列的數(shù)組 D //輸出 :數(shù)組 A[1..m]每種面額硬 幣的數(shù)量 ,或者無解 習題 1.(題略 ) a. 40 b. c. ？ 解答： 只有一個，為 {0,0,1,0,1} ，如何從動態(tài)規(guī)劃算法所生成的表中判斷背包問題的實例是不是具有不止一個最優(yōu)子集？ 41 解答： 一般來說，可以通過判斷表中最后一列的最大值個數(shù)來判斷，因為背包問題的最優(yōu)值的產(chǎn)生只會在最后一列產(chǎn)生。