數(shù)據(jù)結(jié)構(gòu)章節(jié)練習(xí)題及答案8

第8章查找算法

i.請(qǐng)簡(jiǎn)述查找的作用。

查找的作用是根據(jù)給定值從一個(gè)數(shù)據(jù)集合中搜索某個(gè)元素。若某

個(gè)元素的關(guān)鍵字值與給定值相等，則查找成功；否則查找失敗。

2.請(qǐng)簡(jiǎn)述靜態(tài)查找和動(dòng)態(tài)查找的含義。

靜態(tài)查找只根據(jù)給定值在數(shù)據(jù)集合中按關(guān)鍵字查找匹配元素'訪

問匹配元素的屬性，而不對(duì)數(shù)據(jù)集合進(jìn)行插入元素'刪除元素等操作;

而動(dòng)態(tài)查找可能會(huì)在查找過程中向數(shù)據(jù)集合中插入一個(gè)新元素或從

數(shù)據(jù)集合中刪除一個(gè)已有元素。

3.請(qǐng)簡(jiǎn)述各種查找算法的適用范圍。

各種查找算法的適用范圍：

(a)順序查找雖然查找效率最低，但其對(duì)待查找數(shù)據(jù)集合的存儲(chǔ)

結(jié)構(gòu)無特別要求，在對(duì)數(shù)據(jù)集合進(jìn)行增'冊(cè)h改等操作時(shí)效率較高，

因此，根據(jù)那些不需要經(jīng)常作查找操作的關(guān)鍵字進(jìn)行查找時(shí)，一般采

用順序查找算法。若經(jīng)常作查找操作，則應(yīng)使用效率較高的其他查找

算法。

(b)折半查找和分塊查找主要適用于數(shù)據(jù)集合增'冊(cè)h改等操

作較少的情況；二叉排序樹查找則適用于數(shù)據(jù)集合變化較頻繁的情

況。

(c)哈希查找雖然在理論上具有最短的平均查找長(zhǎng)度，但它占

用的存儲(chǔ)空間較多，且在實(shí)際中只有哈希函數(shù)構(gòu)造得好才能達(dá)到常量

級(jí)的平均查找長(zhǎng)度。而要想構(gòu)造出好的哈希函數(shù)，必須以大量數(shù)據(jù)為

基礎(chǔ)，因此，哈希查找主要適用于數(shù)據(jù)分布已知的情況。

4.請(qǐng)簡(jiǎn)述順序查找對(duì)待查找數(shù)據(jù)集合的要求及順序查找的具體

步驟。

順序查找是一種最簡(jiǎn)單'直觀的查找算法，適用于采用任何存儲(chǔ)

結(jié)構(gòu)的數(shù)據(jù)集合，其具體步驟為：

(a)按預(yù)先規(guī)定的順序依次將數(shù)據(jù)集合中每個(gè)元素的關(guān)鍵字與

給定值進(jìn)行比較，若某個(gè)元素的關(guān)鍵字與給定值相同，則查找成功；

(b)若遍歷所有元素后，仍沒有找到關(guān)鍵字與給定值相同的元

素，則查找失敗。

5.請(qǐng)簡(jiǎn)述折半查找對(duì)待查找數(shù)據(jù)集合的要求及折半查找的具體

步驟。

折半查找，又稱二分查找，它要求數(shù)據(jù)集合采用順序表存儲(chǔ)結(jié)構(gòu),

且數(shù)據(jù)集合中的元素是按關(guān)鍵字大小有序排列的。假設(shè)數(shù)據(jù)集合的元

素按關(guān)鍵字遞增排列，折半查找算法的具體步驟為：

(a)對(duì)于包含n個(gè)元素的遞增數(shù)據(jù)集合R=(R[1],R[2],R[n]}

(R[i]<R[i+l])，根據(jù)給定元素K進(jìn)行折半查找，初始化待查找數(shù)據(jù)

集合的下標(biāo)起始位置low=l和結(jié)束位置high=no

(b)計(jì)算中間元素下標(biāo)mid=|_(low+high)/2_|,若R[mid]==K,則

查找成功，折半查找算法結(jié)束；若R[midJ<K,則令low=mid+l；否

則，若R[mid]>K,則令high=mid-l。

(c)若新的待查找數(shù)據(jù)集合不為空，即low<high,則返回到上

一步在新的數(shù)據(jù)集合(R[low],R[low+1.,R[high])上繼續(xù)進(jìn)行折半

查找；否則查找失敗。

6.請(qǐng)簡(jiǎn)述分塊查找對(duì)待查找數(shù)據(jù)集合的要求及分塊查找的具體

步驟。

在分塊查找算法中，除了待查找的數(shù)據(jù)集合外，還需建立一個(gè)索

引表。待查數(shù)據(jù)集合與索引表的關(guān)系描述如下：(a)將包含n個(gè)元

素的待查找數(shù)據(jù)集合均勻分為b塊(即b個(gè)子集合)，前b-1塊中元

素?cái)?shù)目s=Ln/bJ,最后一塊中元素?cái)?shù)目小于等于So(b)分塊后塊內(nèi)

元素可以無序，但塊間必須有序，這里假設(shè)塊間為遞增排列，即第i+1

塊中的任一元素大于第i塊中的任一元素(i<b)。(c)構(gòu)造一個(gè)包

含b個(gè)元素的索引表，用于記錄每塊的起始位置和最大元素值。

分塊查找算法的具體步驟為：(a)在索引表中查找，確定待查

找元素在哪一塊，由于索引表有序，因此可以使用二分查找算法。(b)

在已確定的塊中，進(jìn)行順序查找。

7.請(qǐng)簡(jiǎn)述二叉排序樹的定義。

二叉排序樹，又稱二叉查找樹，它或者是一棵空樹，或者是具有

如下性質(zhì)的二叉樹：

(a)若它的左子樹非空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)

點(diǎn)的值。

(b)若它的右子樹非空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)

點(diǎn)的值。

(c)左、右子樹也分別是二叉排序樹。

8.請(qǐng)簡(jiǎn)述二叉排序樹的插入和創(chuàng)建過程。

二叉排序樹的插入過程：

在二叉排序樹中插入一個(gè)新結(jié)點(diǎn)，應(yīng)保證插入新結(jié)點(diǎn)后的二叉樹

仍然是一棵二叉排序樹。對(duì)于一個(gè)給定元素K,將其插入到二叉排序

樹中的具體步驟如下：

(a)若二叉排序樹為一棵空樹，則將元素K作為二叉排序樹的

根結(jié)點(diǎn)。

(b)若K等于根結(jié)點(diǎn)的值，則該元素已經(jīng)是二叉排序樹中的結(jié)

點(diǎn)，不需重復(fù)插入，直接返回；若K小于根結(jié)點(diǎn)的值，則將K插入

到左子樹中；若K大于根結(jié)點(diǎn)的值，則將K插入到右子樹中。重復(fù)

該步驟，直至要插入的子樹為空，此時(shí)將K作為該子樹的根結(jié)點(diǎn)。

二叉排序樹的創(chuàng)建過程就是不斷插入新結(jié)點(diǎn)的過程。

9.請(qǐng)簡(jiǎn)述二叉排序樹的查找過程。

對(duì)于給定值K,先將K與根結(jié)點(diǎn)的值比較，若相等則查找成功;

若K小于根結(jié)點(diǎn)的值，則在左子樹中繼續(xù)進(jìn)行二叉排序樹的查找；

否則，若K大于根結(jié)點(diǎn)的值，則在右子樹中繼續(xù)進(jìn)行二叉排序樹的

查找。重復(fù)該過程，直至找到匹配的結(jié)點(diǎn)，查找成功；或者子樹為空,

查找失敗。

10.請(qǐng)簡(jiǎn)述哈希表的元素存儲(chǔ)原理。

確定一函數(shù)h,對(duì)于關(guān)鍵字值是k的元素，以k為自變量計(jì)算函

數(shù)值h(k),這個(gè)函數(shù)值被解釋為一片連續(xù)存儲(chǔ)空間中的一個(gè)地址(即

數(shù)組中的一個(gè)下標(biāo)值)，元素即被存入到這個(gè)地址中。

11.請(qǐng)簡(jiǎn)述常用的四種哈希函數(shù)及其計(jì)算規(guī)則。

除余法：選取一個(gè)適當(dāng)?shù)恼麛?shù)P（通常P為不大于哈希表存儲(chǔ)

空間尺寸的最大素?cái)?shù)），以元素的關(guān)鍵字值k除以P,得到的余數(shù)作

為元素的存儲(chǔ)地址，即h（k）=k%p。

數(shù)字分析法：若元素的關(guān)鍵字由多位組成，且關(guān)鍵字的位數(shù)比存

儲(chǔ)空間地址碼位數(shù)多'每一位的取值范圍及關(guān)鍵字的取值分布情況預(yù)

先知道，則可以對(duì)元素關(guān)鍵字的各位進(jìn)行分析,去掉分布較集中的位'

保留分布較均勻的位。

折疊法：若元素的關(guān)鍵字由多位組成，且關(guān)鍵字的位數(shù)比存儲(chǔ)空

間地址碼位數(shù)多，但關(guān)鍵字的取值分布情況未知，則可以用折疊法將

關(guān)鍵字分為幾段（除了最后一段位數(shù)可以少一些，其他各段的位數(shù)均

等于存儲(chǔ)空間地址碼位數(shù)），并將所有段的值做疊加求和運(yùn)算，將疊

加和的最高位進(jìn)位舍去后取剩余部分作為元素的存儲(chǔ)地址。

平方取中法：對(duì)元素的關(guān)鍵字值求平方，并取中間幾位作為元素

的存儲(chǔ)地址。

12.請(qǐng)簡(jiǎn)述常用的兩種哈希表沖突處理方法。

開放定址法：按照某個(gè)探查序列在哈希表中進(jìn)行搜索，直至找到

一個(gè)空閑的地址，將發(fā)生沖突的新元素存儲(chǔ)在該地址中。

拉鏈法：將所有同義詞存儲(chǔ)在一