數(shù)據(jù)結(jié)構(gòu)C版課后答案 王紅梅 查找技術(shù)

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

2、構(gòu)組織該數(shù)列，則查找一個(gè)數(shù)的平均比較次數(shù)為（ ）。若按二叉排序樹組織該數(shù)列，則查找一個(gè)數(shù)的平均比較次數(shù)為（ ）?！窘獯稹?，59/15【分析】根據(jù)數(shù)列將二叉排序樹畫出，將二叉排序樹中查找每個(gè)結(jié)點(diǎn)的比較次數(shù)之和除以數(shù)列中的元素個(gè)數(shù)，即為二叉排序樹的平均查找長度。 長度為20的有序表采用折半查找，共有（ ）個(gè)元素的查找長度為3?！窘獯稹?【分析】在折半查找判定樹中，第3層共有4個(gè)結(jié)點(diǎn)。 假定一個(gè)數(shù)列25，43，62，31，48，56，采用的散列函數(shù)為H(k)=k mod 7，則元素48的同義詞是（ ）?！窘獯稹?2【分析】H(48)= H(62)=6 在散列技術(shù)中，處理沖突的兩種主要方法是（ ）和

3、（ ）?！窘獯稹块_放定址法，拉鏈法 在各種查找方法中，平均查找長度與結(jié)點(diǎn)個(gè)數(shù)無關(guān)的查找方法是（ ）?！窘獯稹可⒘胁檎摇痉治觥可⒘斜淼钠骄檎议L度是裝填因子的函數(shù)，而不是記錄個(gè)數(shù)n的函數(shù)。 與其他方法相比，散列查找法的特點(diǎn)是（ ）?！窘獯稹客ㄟ^關(guān)鍵碼計(jì)算記錄的存儲(chǔ)地址，并進(jìn)行一定的比較2. 選擇題 靜態(tài)查找與動(dòng)態(tài)查找的根本區(qū)別在于（ ）。A 它們的邏輯結(jié)構(gòu)不一樣 B 施加在其上的操作不同C 所包含的數(shù)據(jù)元素的類型不一樣 D 存儲(chǔ)實(shí)現(xiàn)不一樣【解答】B【分析】靜態(tài)查找不涉及插入和刪除操作，而動(dòng)態(tài)查找涉及插入和刪除操作。 有一個(gè)按元素值排好序的順序表（長度大于2），分別用順序查找和折半查找與給定值相等

4、的元素，比較次數(shù)分別是s和b，在查找成功的情況下，s和b的關(guān)系是（ ）；在查找不成功的情況下，s和b的關(guān)系是（ ）。A s=b B s>b C s<b D 不一定【解答】D，B【分析】此題沒有指明是平均性能。例如，在有序表中查找最大元素，則順序查找比折半查找快，而平均性能折半查找要優(yōu)于順序查找，查找不成功的情況也類似。 長度為 12的有序表采用順序存儲(chǔ)結(jié)構(gòu)，采用折半查找技術(shù)，在等概率情況下，查找成功時(shí)的平均查找長度是（ ），查找失敗時(shí)的平均查找長度是（ ）。A 37/12 B 62/13 C 3 9/12 D 49/13【解答】A，D【分析】畫出長度為12的折半查找判定樹，判定樹中

5、有12個(gè)內(nèi)結(jié)點(diǎn)和13個(gè)外結(jié)點(diǎn)。 用n個(gè)鍵值構(gòu)造一棵二叉排序樹，其最低高度為（ ）。A n/2 B n C log2n D log2n+1【解答】D【分析】二叉排序樹的最低高度與完全二叉樹的高度相同。 二叉排序樹中，最小值結(jié)點(diǎn)的（ ）。A 左指針一定為空 B 右指針一定為空C 左、右指針均為空 D 左、右指針均不為空【解答】A【分析】在二叉排序樹中，值最小的結(jié)點(diǎn)一定是中序遍歷序列中第一個(gè)被訪問的結(jié)點(diǎn)，即二叉樹的最左下結(jié)點(diǎn)。 散列技術(shù)中的沖突指的是（ ）。A 兩個(gè)元素具有相同的序號(hào) B 兩個(gè)元素的鍵值不同，而其他屬性相同C 數(shù)據(jù)元素過多 D 不同鍵值的元素對(duì)應(yīng)于相同的存儲(chǔ)地址【解答】D 設(shè)散列表表

6、長m=14，散列函數(shù)H(k)=k mod 11。表中已有15、38、61、84四個(gè)元素，如果用線性探側(cè)法處理沖突，則元素49的存儲(chǔ)地址是（ ）。A 8 B 3 C 5 D 9 【解答】A【分析】元素15、38、61、84分別存儲(chǔ)在4、5、6、7單元，而元素49的散列地址為5，發(fā)生沖突，向后探測3個(gè)單元，其存儲(chǔ)地址為8。 在采用線性探測法處理沖突所構(gòu)成的閉散列表上進(jìn)行查找，可能要探測多個(gè)位置，在查找成功的情況下，所探測的這些位置的鍵值（ ）。A 一定都是同義詞 B 一定都不是同義詞 C不一定都是同義詞 D 都相同【解答】C【分析】采用線性探測法處理沖突會(huì)產(chǎn)生堆積，即非同義詞爭奪同一個(gè)后繼地址。3

7、. 判斷題 二叉排序樹的充要條件是任一結(jié)點(diǎn)的值均大于其左孩子的值，小于其右孩子的值?！窘獯稹垮e(cuò)。分析二叉排序樹的定義，是左子樹上的所有結(jié)點(diǎn)的值都小于根結(jié)點(diǎn)的值，右子樹上的所有結(jié)點(diǎn)的值都大于根結(jié)點(diǎn)的值。例如圖7-7所示二叉樹滿足任一結(jié)點(diǎn)的值均大于其左孩子的值，小于其右孩子的值，但不是二叉排序樹。 二叉排序樹的查找和折半查找的時(shí)間性能相同?！窘獯稹垮e(cuò)。二叉排序樹的查找性能在最好情況和折半查找相同。 若二叉排序樹中關(guān)鍵碼互不相同，則其中最小元素和最大元素一定是葉子結(jié)點(diǎn)?！窘獯稹垮e(cuò)。在二叉排序樹中，最小元素所在結(jié)點(diǎn)一定是中序遍歷序列中第一個(gè)被訪問的結(jié)點(diǎn)，即是二叉樹的最左下結(jié)點(diǎn)，但可能有右子樹。最大元素

8、所在結(jié)點(diǎn)一定是中序遍歷序列中最后一個(gè)被訪問的結(jié)點(diǎn)，即是二叉樹的最右下結(jié)點(diǎn)，但可能有左子樹。如圖7-8所示，5是最小元素，25是最大元素，但5和25都不是葉子結(jié)點(diǎn)。 散列技術(shù)的查找效率主要取決于散列函數(shù)和處理沖突的方法?！窘獯稹垮e(cuò)。更重要的取決于裝填因子，散列表的平均查找長度是裝填因子的函數(shù)。 當(dāng)裝填因子小于1時(shí)，向散列表中存儲(chǔ)元素時(shí)不會(huì)引起沖突?！窘獯稹垮e(cuò)。裝填因子越小，只能說明發(fā)生沖突的可能性越小。4分別畫出在線性表（a，b，c，d，e，f，g）中進(jìn)行折半查找關(guān)鍵碼e和g的過程?！窘獯稹坎檎谊P(guān)鍵碼e的過程如圖7-9所示，查找關(guān)鍵碼g的過程如圖7-10所示。5畫出長度為10的折半查找判定樹，并

9、求等概率時(shí)查找成功和不成功的平均查找長度?！窘獯稹繀⒁?。6將數(shù)列（24，15，38，27，121，76，130）的各元素依次插入一棵初始為空的二叉排序樹中，請(qǐng)畫出最后的結(jié)果并求等概率情況下查找成功的平均查找長度。【解答】二叉排序樹如圖7-11所示，其平均查找長度=1+2×2+3×2+4×2=19/77一棵二叉排序樹的結(jié)構(gòu)如圖7-12所示，結(jié)點(diǎn)的值為18，請(qǐng)標(biāo)出各結(jié)點(diǎn)的值。【解答】二叉排序樹中各結(jié)點(diǎn)的值如圖7-13所示。8已知散列函數(shù)H(k)=k mod 12，鍵值序列為(25, 37, 52, 43, 84, 99, 120, 15, 26, 11, 70, 82

10、)，采用拉鏈法處理沖突，試構(gòu)造開散列表，并計(jì)算查找成功的平均查找長度。【解答】H(25)=1, H(37)=1, H(52)=4, H(43)=7, H(84)=0, H(99)=3, H(120)=0, H(15)=3, H(26)=2, H(11)=11, H(70)=10, H(82)=10構(gòu)造的開散列表如下： 平均查找長度ASL=(8×1+4×2)/12=16/129. 算法設(shè)計(jì) 設(shè)計(jì)順序查找算法，將哨兵設(shè)在下標(biāo)高端?！窘獯稹繉⑸诒O(shè)置在下標(biāo)高端，表示從數(shù)組的低端開始查找，在查找不成功的情況下，算法自動(dòng)在哨兵處終止。具體算法如下： 編寫算法求給定結(jié)點(diǎn)在二叉排序樹中所

11、在的層數(shù)?！窘獯稹扛鶕?jù)題目要求采用遞歸方法，從根結(jié)點(diǎn)開始查找結(jié)點(diǎn)p，若待查結(jié)點(diǎn)是根結(jié)點(diǎn)，則深度為1，否則到左子樹（或右子樹）上去找，查找深度加1。具體算法如下： 編寫算法，在二叉排序樹上找出任意兩個(gè)不同結(jié)點(diǎn)的最近公共祖先?！窘獯稹吭O(shè)兩個(gè)結(jié)點(diǎn)分別為A和B，根據(jù)題目要求分下面情況討論： 若A為根結(jié)點(diǎn)，則A為公共祖先； 若A->datadata且root->datadata，root為公共祖先； 若A->datadata且B->datadata，則到左子樹查找； 若A->data>root->data且B->data>root->data，

12、則到右子樹查找。具體算法如下： 設(shè)計(jì)算法判定一棵二叉樹是否為二叉排序樹?！窘獯稹繉?duì)二叉排序樹來講，其中序遍歷序列為一個(gè)遞增序列。因此，對(duì)給定二叉樹進(jìn)行中序遍歷，如果始終能夠保證前一個(gè)值比后一個(gè)值小，則說明該二叉樹是二叉排序樹。具體算法如下：學(xué)習(xí)自測及答案1已知一個(gè)有序表為（12，18，24，35，47，50，62，83，90，115，134），當(dāng)折半查找值為90的元素時(shí)，經(jīng)過（ ）次比較后查找成功。A 2 B 3 C 4 D 5【解答】A2已知10個(gè)元素（54，28，16，73，62，95，60，26，43），按照依次插入的方法生成一棵二叉排序樹，查找值為62的結(jié)點(diǎn)所需比較次數(shù)為（ ）。A 2

13、 B 3 C 4 D 5【解答】B3已知數(shù)據(jù)元素為（34，76，45，18，26，54，92，65），按照依次插入結(jié)點(diǎn)的方法生成一棵二叉排序樹，則該樹的深度為（ ）。A 4 B 5 C 6 D 7【解答】B4按（ ）遍歷二叉排序樹得到的序列是一個(gè)有序序列。A 前序 B 中序 C 后序 D 層次 【解答】B5將二叉排序樹T按前序遍歷序列依次插入初始為空的二叉排序樹T '中，則T與T'是相同的，這種說法是否正確？【解答】正確6. 一棵高度為h的平衡二叉樹，最少含有 個(gè)結(jié)點(diǎn)。A 2h B 2 h -1 C 2 h +1 D 2 h -1【解答】D7在散列函數(shù)H(k)= k mod m

14、中，一般來講，m應(yīng)?。?）。A 奇數(shù) B 偶數(shù) C 素?cái)?shù) D 充分大的數(shù)【解答】C8已知關(guān)鍵碼序列為（Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec），散列表的地址空間為016，設(shè)散列函數(shù)為H(x)= ，其中i為關(guān)鍵碼中第一個(gè)字母在字母表中的序號(hào)，采用線性探測法和鏈地址法處理沖突，試分別構(gòu)造散列表，并求等概率情況下查找成功的平均查找長度?！窘獯稹縃(Jan)=10/2=5, H(Feb)=6/2=3, H(Mar)=13/2=6, H(Apr)=1/2=0H(May)=13/2=6, H(Jun)=10/25, H(Jul)=10/25, H(Aug)=1/2=0H(Sep)=19/2=8, H(Oct) =15/2=7, H(Nov) =14/2=7, H(Dec) =4/2=2 采用線性探測法處理沖突，得到的閉散列表如下：平均查找長