查找技術(shù)模板

1、第7章查找技術(shù)課后習(xí)題講解1,填空題順序查找技術(shù)適合于存儲(chǔ)結(jié)構(gòu)為 的線性表,而折半查找技 術(shù)適用于存儲(chǔ)結(jié)構(gòu)為的線性表,而且表中的元素必須是.【解答】順序存儲(chǔ)和鏈接存儲(chǔ),順序存儲(chǔ),按關(guān)鍵碼有序設(shè)有一個(gè)已按各元素值排好序的線性表 ,長(zhǎng)度為125,用折半查 找與給定值相等的元素,假設(shè)查找成功,那么至少需要比擬次,至 多需比擬次.【解答】1,7【分析】在折半查找判定樹(shù)中,查找成功的情況下,和根結(jié)點(diǎn)的比 較次數(shù)最少,為1次,最多不超過(guò)判定樹(shù)的深度. 對(duì)于數(shù)列25, 30, 8, 5, 1, 27, 24, 10, 20, 21, 9, 28, 7, 13, 15,假定 每個(gè)結(jié)點(diǎn)的查找概率相同,假設(shè)用順序

2、存儲(chǔ)結(jié)構(gòu)組織該數(shù)列,那么查找 一個(gè)數(shù)的平均比擬次數(shù)為.假設(shè)按二叉排序樹(shù)組織該數(shù)列,那么查 找一個(gè)數(shù)的平均比擬次數(shù)為.【解答】8, 59/15【分析】根據(jù)數(shù)列將二叉排序樹(shù)畫(huà)出,將二叉排序樹(shù)中查找每個(gè)結(jié)點(diǎn)的比擬次數(shù)之和除以數(shù)列中的元素個(gè)數(shù),即為二叉排序樹(shù)的平均查找長(zhǎng)度.長(zhǎng)度為20的有序表采用折半查找,共有()個(gè)元素的查找長(zhǎng)度為3.【解答】4【分析】在折半查找判定樹(shù)中,第3層共有4個(gè)結(jié)點(diǎn). 假定一個(gè)數(shù)列25,43, 62, 31,48, 56),采用的散列函數(shù)為 H(k)=kmod 7,那么元素48的同義詞是().【解答】62【分析】H(48)= H(62)=6在散列技術(shù)中,處理沖突的兩種主要方法是

3、()和().【解答】開(kāi)放定址法,拉鏈法在各種查找方法中,平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)的查找方法是().【解答】散列查找【分析】散列表的平均查找長(zhǎng)度是裝填因子的函數(shù),而不是記錄個(gè)數(shù)n的函數(shù). 與其它方法相比,散列查找法的特點(diǎn)是.【解答】經(jīng)過(guò)關(guān)鍵碼計(jì)算記錄的存儲(chǔ)地址,并進(jìn)行一定的比擬2 .選擇題.B施加在其上的操作不同D存儲(chǔ)實(shí)現(xiàn)不一樣,而動(dòng)態(tài)查找涉及插入和靜態(tài)查找與動(dòng)態(tài)查找的根本區(qū)別在于A它們的邏輯結(jié)構(gòu)不一樣C所包含的數(shù)據(jù)元素的類型不一樣【解答】B【分析】靜態(tài)查找不涉及插入和刪除操作 刪除操作.有一個(gè)按元素值排好序的順序表長(zhǎng)度大于2,分別用順序查 找和折半查找與給定值相等的元素,比擬次數(shù)分別是s和b

4、,在查找 成功的情況下,s和b的關(guān)系是；在查找不成功的情況下,s和b 的關(guān)系是.A s=b B s>b C s【解答】D, D【分析】此題沒(méi)有指明是平均性能.例如,在有序表中查找最大元 素,那么順序查找比折半查找快,而平均性能折半查找要優(yōu)于順序查找,查找不成功的情況也類似.長(zhǎng)度為12的有序表采用順序存儲(chǔ)結(jié)構(gòu),采用折半查找技術(shù),在 等概率情況下,查找成功時(shí)的平均查找長(zhǎng)度是,查找失敗時(shí)的 平均查找長(zhǎng)度是.A 37/12 B 62/13 C 3 9/12 D 49/13【解答】A, B【分析】畫(huà)出長(zhǎng)度為12的折半查找判定樹(shù),判定樹(shù)中有12個(gè)內(nèi)結(jié) 點(diǎn)和13個(gè)外結(jié)點(diǎn).用n個(gè)鍵值構(gòu)造一棵二叉排序樹(shù),

5、其最低高度為.A n/2 B n C log2n D log2n+1【解答】D【分析】二叉排序樹(shù)的最低高度與完全二叉樹(shù)的高度相同.二叉排序樹(shù)中,最小值結(jié)點(diǎn)的.A左指針一定為空 B右指針一定為空C左、右指針均為空D左、右指針均不為空【解答】A【分析】在二叉排序樹(shù)中,值最小的結(jié)點(diǎn)一定是中序遍歷序列中第 一個(gè)被訪問(wèn)的結(jié)點(diǎn),即二叉樹(shù)的最左下結(jié)點(diǎn).散列技術(shù)中的沖突指的是.A兩個(gè)元素具有相同的序號(hào)B兩個(gè)元素的鍵值不同,而其它屬性相同C數(shù)據(jù)元素過(guò)多 D不同鍵值的元素對(duì)應(yīng)于相同的存儲(chǔ)地址【解答】D 設(shè)散列表表長(zhǎng) m=14,散列函數(shù)Hk=k mod 11.表中已有15、 38、61、84四個(gè)元素,如果用線性探側(cè)

6、法處理沖突,那么元素49的 存儲(chǔ)地址是.A 8 B 3 C 5 D 9【解答】A【分析】元素15、38、61、84分別存儲(chǔ)在4、5、6、7單元,而 元素49的散列地址為5,發(fā)生沖突,向后探測(cè)3個(gè)單元,其存儲(chǔ)地址 為8.在采用線性探測(cè)法處理沖突所構(gòu)成的閉散列表上進(jìn)行查找,可能要探測(cè)多個(gè)位置,在查找成功的情況下,所探測(cè)的這些位置的鍵值.A 一定都是同義詞 B 一定都不是同義詞 C不一定都是同義詞 D 都相同【解答】C【分析】采用線性探測(cè)法處理沖突會(huì)產(chǎn)生堆積,即非同義詞爭(zhēng)奪同一個(gè)后繼地址.3 .判斷題二叉排序樹(shù)的充要條件是任一結(jié)點(diǎn)的值均大于其左孩子的值,小于其右孩子的值.【解答】錯(cuò).分析二叉排序樹(shù)的定義,是左子樹(shù)上的所有結(jié)點(diǎn)的值都小于根結(jié)點(diǎn)的值,右子樹(shù)上的所有結(jié)點(diǎn)的值都大于根結(jié)點(diǎn)的值.例如圖 7-7所示二叉樹(shù)滿足任一結(jié)點(diǎn)的值均大于其左孩子的值,小于其右孩子的值,但不是二叉排序樹(shù). 二叉排序樹(shù)的查找和折半查找的時(shí)間性能相同.【解答】錯(cuò).二叉排序樹(shù)的查找性能在最好情況和折半查找相同. 假設(shè)二叉排序樹(shù)中關(guān)鍵碼互不相同,那么其中最小元素