第第頁數(shù)據(jù)結(jié)構(gòu)與算法復習題10（C語言版）

習

判斷題：

9解答

1．用向量和單鏈表表示的有序表均可使用折半查找方法來提高查找速度。答：FALSE(錯。鏈表表示的有序表不能用折半查找法。)

2.有n個數(shù)據(jù)放在一維數(shù)組A[1..n]中，在進行順序查找時，這n個數(shù)的排列有序或無序其平均查找長度不同。

答：FALSE(錯。因順序查找既適合于有序表也適合于無序表；對這兩種表，若對于每個元素的查找概率相等，則順序查找的ASL相同，并且都是(n+1)/2；對于查找概率不同的情況，則按查找概率由大到小排序的無序表其ASL要比有序表的ASL小。)

3.折半查找是先確定待查有序表記錄的范圍，然后逐步縮小范圍，直到找到或找不到該記錄為止。()答：TRUE

4.哈希表的查找效率主要取決于哈希表哈希表造表時選取的哈希函數(shù)和處理沖突的方法。答：TRUE

5.查找表是由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合。答：TRUE

單選題：

6.對于18個元素的有序表采用二分(折半)查找，則查找A[3]的比較序列的下標為()。

A.1、2、3B.9、5、2、3C.9、5、3D.9、4、2、3答：D(第一次?(1?18)/2?=9,第二次?(1?8)/2?=4，第三次

?(1?3)/2?=2,(第四次?(3?3)/2?=3，故選D.

7.順序查找法適合于存儲結(jié)構(gòu)為____________的線性表。

A.散列存儲B.順序存儲或鏈式存儲C.壓縮存儲D.索引存儲答：B

8.對線性表進行二分查找時，要求線性表必須()。

A．以順序方式存儲B.以鏈接方式存儲C．以順序方式存儲，且結(jié)點按關(guān)鍵字有序排序D.以鏈接方式存儲，且結(jié)點按關(guān)鍵字有序排序答：C

9.設(shè)哈希表長m=14，哈希函數(shù)為H(k)=kMOD11。表中已有4個記錄(如下圖

1

所示)，如果用二次探測再散列處理沖突，關(guān)鍵字為49的記錄的存儲地址是()。

01234567891011121315386184A．8B.3C．5D.9答：D(計算H(k)，即H(49)=49mod11=5,沖突，進行二次探測再散列。而二次探測再散列的增量序列為：di=12，-12，22，-22，32，…，土k2，(k≤m/2),沿著增量序列選擇不同的增量按照開放定址公式：

Hi＝(H(key)+di)MODmi＝1，2，…，k(k≤m-1)

尋找新的地址(構(gòu)造后繼散列地址)。

計算Hi＝(H(49)+di)MOD14＝(5+di)MOD14,可知當(5+22)

MOD14=9MOD14=9時不再發(fā)生沖突，故選擇D).

10.以下說法錯誤的是()。

A．散列法存儲的基本思想是由關(guān)鍵碼值決定數(shù)據(jù)的存儲地址B.散列表的結(jié)點中只包含數(shù)據(jù)元素自身的信息，不包含任何指針C．裝填因子是散列法的一個重要參數(shù)，它反映了散列表的裝填程度

D.散列表的查找效率主要取決于散列表造表時選取的散列函數(shù)和處理沖突的方法

答：B(散列表也可以用單鏈表存儲，故選擇B.)

11.以下說法正確的是()。A．數(shù)字分析法需事先知道所有可能出現(xiàn)的鍵值及所有鍵值的每一位上各數(shù)字分布情況，并且鍵值的位數(shù)比散列地址的位數(shù)多B．除余法要求事先知道全部鍵值

C．平方取中法需要事先掌握鍵值的分布情況D．隨機數(shù)法適用于鍵值不相等的場合答：A.

12.設(shè)有一個用線性探測法解決沖突得到的散列表如下圖所示，散列函數(shù)為H(k)=k%11，若要查找元素14，探測的次數(shù)是()。

T：0123456789101325801617614A．8B.9C．3D.6答：D

13.散列表的平均查找長度()。

A．與處理沖突方法有關(guān)而與表的長度無關(guān)B．與處理沖突方法無關(guān)而與表的長度有關(guān)

2

C．與處理沖突方法有關(guān)且與表的長度有關(guān)D．與處理沖突方法無關(guān)且與表的長度無關(guān)答：C

14.在采用線性探測法處理沖突所構(gòu)成的閉散列表上進行查找，可能要探測多個位置，在查找成功的情況下，所探測的這些位置上的鍵值()。A．一定都是同義詞B.一定都不是同義詞C．都相同D.不一定都是同義詞答：D

(例如，當H(k)=kmod7且輸入的關(guān)鍵字為3、4、10時所構(gòu)造的散列表如下圖所示：

01234563410當查找關(guān)鍵字成功時，所探測3、4、5位置上的鍵值：3和10是同義詞而4不是同義詞。)

15.在采用線性探測法處理沖突的閉散列表上，假定裝填因子α的值為0.5，則查找任一元素的平均查找長度為()。

A．1B.1.5C.2D.2.5

答：B(注：線性探測再散列的哈希表查找成功時的平均查找長度為

Snl≈

11(1+)(9-27)21?a參見嚴蔚敏等《（c語言版）數(shù)據(jù)結(jié)構(gòu)》P.261公式9-27。)

16.在采用鏈接法處理沖突的散列表上，假定裝填因子α的值為4，則查找任一元素的平均查找長度為()。

A．3B.3.5C.4D.2.5

答：A(鏈地址法處理沖突的哈希表查找成功時的平均查找長度為

aSnc≈1+(9-29)

2參見嚴蔚敏等《（c語言版）數(shù)據(jù)結(jié)構(gòu)》P.261公式9-29。)

填空題：

17.二分查找的存儲結(jié)構(gòu)僅限于，且是。答：順序存儲結(jié)構(gòu)有序的18.

*在n個記錄的有序順序表中進行折半查找，最大的比較次數(shù)

是。

答：?log2n?+1(相當于走了一個完全二叉樹根到樹葉的長度，即?log2n?+1；故填?log2n?+1.)

3

19.構(gòu)造哈希(Hash)函數(shù)的方法有、、、

、和。

答：直接定址法數(shù)字分析法平方取中法折疊法除留余數(shù)法隨機數(shù)法20.法構(gòu)造的哈希函數(shù)肯定不會發(fā)生沖突。(重大2000年研究生試題。)答：直接定址(參見嚴蔚敏等《（c語言版）數(shù)據(jù)結(jié)構(gòu)》P.253)

21.在各種查找方法中，平均查找長度與結(jié)點個數(shù)n無關(guān)的查找方法是。答：哈希表查找法

22.在散列存儲中，裝填因子α的值越大，則；α的值越小，則。答：存取元素時發(fā)生沖突的可能性就越大存取元素時發(fā)生沖突的可能性就越小

簡答題：

23.比較線性探測、隨機探測和鏈地址法解決沖突的優(yōu)缺點。

解：線性探測：簡單，但可能導致記錄的聚集而使探測效率降低；此外記錄的個數(shù)必須在哈希表允許的范圍內(nèi)。

隨機探測：可以克服記錄聚集的現(xiàn)象，但需要選取合適的隨機函數(shù)且記錄的個數(shù)也有限制。

鏈地址法：只要空間允許就可插入任意多個記錄，并且鏈表的插入和刪除都很方便。

24.在哈希表存儲中，發(fā)生哈希沖突的可能性與哪些因素有關(guān)？為什么？答：在哈希表存儲中，發(fā)生哈希沖突的可能性與裝填因子α、所采用的哈希函數(shù)、解決沖突的哈希沖突函數(shù)三個因素有關(guān)。

這是因為：(1)裝填因子α是哈希表中已存入的數(shù)據(jù)元素n與哈希地址空間大小m的比值，即n/m，顯然，當α越小時，沖突的可能性就越小，α越大(最大可取1)時，沖突的可能性就越大；(2)若哈希函數(shù)選擇得當，就可使哈希地址盡可能均勻地分布在哈希地址空間上，從而減少沖突的發(fā)生；否則，若哈希函數(shù)選擇不當，就可能使哈希地址集中于某些區(qū)域，從而加大沖突的發(fā)生；(3)若哈希沖突函數(shù)選擇得當，可以減少再次發(fā)生哈希沖突的可能性。

25.對含有n個數(shù)據(jù)元素的集合，要找出最大元素和最小元素，請問最少需要多少次比較運算（執(zhí)行if語句的次數(shù)）。

答：我們可以設(shè)立兩個變量max和min用于存放最大元素和最小元素的位置，第一次取兩個元素進行比較，大的放入max，小的放入min,從第2次開始，每次取一個元素先和max比較，如果大于max則以它替換max，并結(jié)束本次比較；若小于max則再與min相比較，在最好的情況下，一路比較下來都不用和min相比較，所以這種情況下，至少要進行n-1次比較就能找到最大元素和最小元素。（最壞情況下，要進行2n-3次比較才能結(jié)果）

26．請問：對有序的單鏈表能否進行折半查找？為什么？

答：有序的單鏈表不能進行折半查找的。因為鏈表無法進行隨機訪問，如果要訪問鏈表的中間結(jié)點，就必須先從頭結(jié)點開始進行依次訪問，這就要浪費很多時間，

4

還不如順序查找，而且，用鏈存儲結(jié)構(gòu)將無法判定折半的過程是否結(jié)束，因此無法用鏈表實現(xiàn)折半查找。

27．設(shè)有序表為(1、23、34、55、56、57、77、87、99)請分別畫出對給定值23，56，98進行折半查找的過程。（并注明每次循環(huán)的各參數(shù)變量的結(jié)果）答：

23的查找過程如下（其中括號表示當前查找區(qū)間，圓括號表示當前比較的關(guān)鍵字）

下標：123456789第一次比較：[1233455（56）57778799]low=1high=9mid