• logo

    您所在位置網站首頁 > 海量文檔  > 高等教育 > 習題/試題

    算法設計與分析基礎第七章作業.docx 5頁

    本文檔一共被下載: ,您可全文免費在線閱讀后下載本文檔。

    • 支付并下載
    • 收藏該文檔
    • 百度一下本文檔
    • 修改文檔簡介
    全屏預覽

    下載提示

    1.本站不保證該用戶上傳的文檔完整性,不預覽、不比對內容而直接下載產生的反悔問題本站不予受理。
    2.該文檔所得收入(下載+內容+預覽三)歸上傳者、原創者。
    3.登錄后可充值,立即自動返金幣,充值渠道很便利
    第七章習題7.1分步計數算法是穩定的嗎?解:分步計數算法是穩定的。習題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=4980c.字符c01移動距離t(c)21比較次數:[(1000-3)/2]*2=996 (1000-3)/2取整數部分4.用Horspool算法在一個長度為n的文本中查找一個長度為m(n>=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=max{t1(0),1}=1,d2=5模式移動max(d1,d2)=5,所以每次移動5位,且每次只比較一次。比較次數為:1000/5=200b.壞符號移動表:字符c01移動距離t(c)14后綴移動表:k模式d21100001210000131000014100001d1=max{t1(0)-4,1}=1,d2=1模式移動max(d1,d2)=1,所以每次都移動一位,比較5次。比較次數:[(1000-5+1]*5=4980c.壞符號移動表:字符c01移動距離t(c)21后綴移動表:k模式d21010102201010230101024010102d1=max{t1(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.查找的鍵302056753119比較次數111236查找成功的平均鍵值比較次數為:(1+1+1+2+3+6)/6=7/3。

    發表評論

    請自覺遵守互聯網相關的政策法規,嚴禁發布色情、暴力、反動的言論。
    用戶名: 驗證碼: 點擊我更換圖片

    “原創力文檔”前稱為“文檔投稿賺錢網”,本站為“文檔C2C交易模式”,即用戶上傳的文檔直接賣給(下載)用戶,本站只是中間服務平臺,本站所有文檔下載所得的收益歸上傳人(含作者)所有【成交的100%(原創)】。原創力文檔是網絡服務平臺方,若您的權利被侵害,侵權客服QQ:3005833200 電話:19940600175 歡迎舉報,上傳者QQ群:784321556

    1216彩票