算法設計與分析基礎第七章作業_第1頁
算法設計與分析基礎第七章作業_第2頁
算法設計與分析基礎第七章作業_第3頁
算法設計與分析基礎第七章作業_第4頁
算法設計與分析基礎第七章作業_第5頁
全文預覽已結束

下載本文檔

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、精選優質文檔-傾情為你奉上第七章習題7.11. 分步計數算法是穩定的嗎？解：分步計數算法是穩定的。習題7.23.用Horspool算法在一個1000個0構成的二進制文本中查找下列模式時，分別需要進行多少次字符比較？a.00001;b.10000;c.01010;5解：a.字符c01移動距離t(c)15比較次數：(1000/5)*1=200b.字符c01移動距離t(c)14比較次數：(1000-5+1*5=4980 c.字符c01移動距離t(c)21比較次數：(1000-3)/2*2=996 (1000-3)/2取整數部分4.用Horspool算法在一個長度為n的文本中查找一個長度為m(n>

2、;=m)的模式。請分別給出下面兩種例子。a.最差輸入；b.最優輸入。解：a.模式的每次一移動的舉例均為1，且沒有匹配成功，或者到最后一次匹配才成功。b.模式不需要移動，且比較了m次即成功。7.用Boyer-Moore算法在一個1000個0構成的二進制文本中查找列模式時，分別需要進行多少次字符比較？a.00001;b.10000;c.01010;解：a.壞符號移動表：字符c01移動距離t1(c)15后綴移動表：k模式d2100001 5200001530000154000015d1=maxt1(0),1=1,d2=5模式移動max(d1,d2)=5，所以每次移動5位，且每次只比較一次。比較次數為

3、:1000/5=200b.壞符號移動表： 字符c01移動距離t(c)14后綴移動表：k模式d21100001210000131000014100001d1=maxt1(0)-4,1=1,d2=1模式移動max(d1,d2)=1,所以每次都移動一位，比較5次。比較次數：(1000-5+1*5=4980c.壞符號移動表：字符c01移動距離t(c)21后綴移動表：k模式d2101010 2201010230101024010102d1=maxt1(0)-1,1=1,d2=2模式移動max(d1,d2)=2,所以每次都能移動2位，比較2次。比較次數：(1000-3)/2*2=996習題7.32.對于輸入30,20,56,75,31,19和散列函數h(K)=K mod11a.構造它們的閉散列表；b.求在本表中成功查找的最大鍵值比較次數；c.求在本表中成功查找的平均鍵值比較次數；解：a.鍵302056753119散列地址891998012345678910315619302075b.最大的鍵值是19，k(19)=8，先將散列地址為8的中的鍵30與75比較，其次是散列地址為10的75與75比較，所以成功查找的比較次數是6。c.查找的鍵302056

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間，僅對用戶上傳內容的表現方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容，請與我們聯系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論