算法設計與分析基礎第七章作業(yè)

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

2、;=m)的模式。請分別給出下面兩種例子。a.最差輸入；b.最優(yōu)輸入。解：a.模式的每次一移動的舉例均為1，且沒有匹配成功，或者到最后一次匹配才成功。b.模式不需要移動，且比較了m次即成功。7.用Boyer-Moore算法在一個1000個0構(gòu)成的二進制文本中查找列模式時，分別需要進行多少次字符比較？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位，且每次只比較一次。比較次數(shù)為

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