數(shù)據(jù)結(jié)構(gòu)slide2020-黃虎杰-第5章學習指導與習題-答案

第5章查找習題答案

4、習題

一、填空題

(1)順序查找法，表中元素可以任意存放。

(2)在分塊查找方法中，首先杳找索引，然后再查找相應的塊。

(3)順序查找、二分查找、分塊查找都屬于靜態(tài)查找。

(4)靜態(tài)查找表所含元素個數(shù)在查找階段是固定不變的。

(5)對于長度為n的線性表，若進行順序查找，則時間復雜度為O(n)。

(6)對于長度為n的線性表，若采用二分查找,則時間復雜度為：O(log2n)。

(7)理想情況下，在散列表中查找一個元素的時間復雜度為：O(1)

(8)在關(guān)鍵字序列(7,10,12,18,28,36,45,92)中，用二分查找法查找關(guān)

鍵字92,要比較4次才找到。

(9)設有100個元素，用二分查找時，最大的比較次數(shù)是7次。

(10)對二叉排序樹進行查找的方法是用待查的值與根結(jié)點的鍵值進行比較，若比

根結(jié)點小，則繼續(xù)在左子樹中查找。

(11)二叉排序樹是一種動態(tài)查找表。

(12)哈希表是按散列存儲方式構(gòu)造的存儲結(jié)構(gòu)

(13)哈希法既是一種存儲方法，又是一種查找方法。

(14)散列表的查找效率主要取決于散列表造表時選取的散列函數(shù)和處理」

的方法。

(15)設散列函數(shù)H和鍵值kl,k2,若klRk2,且H(kl)=H(k2),則稱這種現(xiàn)

象為沖突。

(16)處理沖突的兩類主要方法是開放定址法和拉鏈法(或鏈地址法)。

(17)散列表(或散列)查找法的平均查找長度與元素個數(shù)n無關(guān)。

(18)在哈希函數(shù)H(key)=key%P中，P一般應取質(zhì)數(shù)。

(19)在查找過程中有插入元素或刪除元素操作的，稱為動態(tài)查找。

(20)各結(jié)點左右子樹深度之差的絕對值至多為的二叉樹稱謂平衡二叉樹。

(21)在10階B一樹中根結(jié)點所包含的關(guān)鍵碼個數(shù)最多為_2_，最少為1。

【分析1m階的B—樹中每個結(jié)點至多有m棵子樹，若根結(jié)點不是終端結(jié)點，

則至少有兩棵子樹，每個結(jié)點中關(guān)鍵碼的個數(shù)為子樹的個數(shù)減lo

(22)一棵5階B—樹中，除根結(jié)點外，每個結(jié)點的子樹樹目最少為3,最多為

5,

【分析】m階的B—樹中每個結(jié)點至多有m棵子樹，除根結(jié)點之外的所有非

終端結(jié)點至少有?而2?棵子樹。

(23)對于包含n個關(guān)鍵碼的m階B一樹，其最小高度是logm(n+l),最大高度是

logm/2(n+l)/2+1。

(24)在一棵B—樹中刪除關(guān)鍵碼，若最終引起樹根結(jié)點的合并，則新樹比原樹的

高度減少1層。

(25)在一棵高度為h的B一樹中，葉子結(jié)點處于第h±L層，當向該B—樹中插入

一個新關(guān)鍵碼時，為查找插入位置需讀取』一個結(jié)點。

【分析】B—樹的葉子結(jié)點可以看作是外部結(jié)點(即查找失敗)的結(jié)點，通常

稱為外結(jié)點。實際上這些結(jié)點不存在，指向這些結(jié)點的指針為空，B一樹將記

錄插入在終端結(jié)點中。

(26)對于長度為n的線性表，若采用分塊查找(假定總塊數(shù)和每塊長度均接近，

用順序查找確定所在塊)，則時間復雜性為O(n~)。

二、選擇題

(1)查找表是以(A)為查找結(jié)構(gòu)。

A.集合B.圖C.樹D.文件

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

A.散列存儲B.順序存儲或鏈接存儲

C.壓縮存儲D.索引存儲

(3)在表長為n的鏈表中進行線性查找，它的平均查找長度為(B)0

A.ASL=n；B.ASL=(n+l)/2;

C.ASL=Vn+1;D.ASD=log2n

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

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

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

(5)衡量查找算法效率的主要標準是(B

A.元素個數(shù)B.平均查找長度C.所需的存儲量D.算法難易程度

(6)如果要求一個線性表既能較快地查找，又能適應動態(tài)變化的要求，可以采用

(A)查找方法。

A.分塊B.順序C.二分D.散列

(7)鏈表適用于(A)查找。

A.順序B.二分C.隨機D.順序或二分

(8)一個有序表為{1,3,9,12,32,41,45,62,75,77,82,95,10()},當二

分查找值為82的結(jié)點時;(C)次比較后查找成功。

A.2B.3C.4D.5

(9)二分查找有序表{4,6,10,12,20,30,50,70,88,100},若查找表中元素

58,則它將依次與表中(B)比較大小，查找結(jié)果是失敗。

A.3(),88,70,50B.20,70,30,5()C.20,5()D.3(),88,5()

(10)對有14個元素的有序表A[l..14]作二分查找，查找元素A[4]時的被比較元素

依次為(C)?

A.A[l],A[2],A[3],A[4]B.A[l],A[14],A[7],A[4]

C.Af71，A[3],A[5],A[41D.Af7],A[5],A[3],A[4]

(11)有一個長度為12的有序表，按二分查找法對其進行查找，在表內(nèi)各元素等概

率情況下查找成功所需的平均比較次數(shù)為(B)。

A.35/12B.37/12C.39/12D.43/12

(12)采用分塊查找時，若線性表共有625個元素，查找每個元素的概率相等，假

設采用順序查找來確定結(jié)點所在的塊時，每塊分(C)個結(jié)點最佳。

A.6B.10C.25D.625

(13)下列(C)不是利用查找表中數(shù)據(jù)元素的關(guān)系進行查找的方法。

A.平衡二叉樹B.有序表的查找

C.散列查找D.二叉排序樹的查找

(14)設哈希表長m=14,哈希函數(shù)H(key)=key%110表中已有4個結(jié)點：

addr(15)=4

addr(38)=5

addr(61)=6

addr(84)=7

其余地址為空。如用二次探測再散列處理沖突，關(guān)鍵字為49的結(jié)點的地址是

(D)。

A.8B.3C.5D.9

(15)對包含n個元素的散列表進行查找，平均查找長度為(D)。

A.O(n2)B.O(log2n)C.O(n)D.不直接依賴于n

(16)沖突指的是(C)。

A.兩個元素具有相同序號B.兩個元素的鍵值不同

C.不同鍵值對應相同的存儲地址D.兩個元素的鍵值相同

(17)在查找過程中，不做增加、刪除或修改的查找稱為(A)o

A.靜態(tài)查找B.內(nèi)創(chuàng)造C.動態(tài)查找D.外查找

(18)已知8個元素為{34,76,45,18,26,54,92,65},按照依次插入結(jié)點的

方法生成一棵二叉樹(不用平衡)，最后兩層上結(jié)點的總數(shù)為(B)。

A.1B.2C.3D.4

(19)不可能生成下圖二叉排序樹的關(guān)鍵字的序列是(A

A.45312B.42531C.45213D.42315

（20）動態(tài)查找包括（B）查找。

A.順序表B.二叉排序樹

C.有序表D.索引順序表

（21）當向一棵m階的B-樹做插入操作時，若一個結(jié)點中的關(guān)鍵字個數(shù)等于（A）,

則必須分裂為兩個結(jié)點。

A.mB.m-1C.m+1D.m/2

（22）在一個5階的B-樹上，每個非終端結(jié)點所含的子樹數(shù)最少為（B）。

A.2B.3C.4D.5

三、應用題

（1）對于給定結(jié)點的關(guān)鍵字集合K={5,7,3,1,9,6,4,8,2,10）,

1）試構(gòu)造一棵二叉排序樹；

2）求等概率情況下的平均查找長度ASL。

解：1）構(gòu)造二叉排序樹：2）ASL=（l*l+2*2+3*4+4*3）/10=2.9

（2）對于給定結(jié)點的關(guān)鍵字集合K={10,18,3,5,19,2,4,9,7,15},

1）試構(gòu)造一棵二叉排序樹；

2）求等概率情況下的平均查找長度ASL。

解：1）構(gòu)造二叉排序樹：c

49

7

2)ASL=(1*1+2*2+3*4+4*2+5*1)710=3

（3）將數(shù)據(jù)序列：25,73,62,191,325,138,依次插入下圖所示的二叉排序樹,

并畫出最后結(jié)果。

解:

（4）對于給定結(jié)點的關(guān)鍵字集合K={1,12,5,8,3,10,7,13,9),

1）試構(gòu)造一棵二叉排序樹；

2）在二叉樹排序BT中刪除“12”后的樹結(jié)構(gòu):

（5）對于給定結(jié)點的關(guān)鍵字集合K={34,76,45,18,26,54,92,38},

1）試構(gòu)造一棵二叉排序樹；

2）求等概率情況下的平均查找長度ASL。

2）ASL=（1*1+2*2+3*3+4*2）/8=2.75（或=11/4）

（6）對于給定結(jié)點的關(guān)鍵字集合K=[4,8,2,9,1,3,6,7,5）,

1）試構(gòu)造一棵二叉排序樹；

2）求等概率情況下的平均查找長度ASL。

解：

1）構(gòu)造二叉排序樹

（或=25/9）

（7）畫出對長度為1（）的有序表進行折半查找的判定樹，并求其等概率時查找成功

的平均查找長度。

解：長度為10的判定樹：

ASL=1/1O(1*14-2*2+3*4+4*3)=2.9

(8)二叉排序樹如圖所示，分別畫出：

1)畫出刪除關(guān)鍵字15以后的二叉樹，并要求其平均查找長度盡可能小;

2)在原二叉排序樹(即沒有刪除15)上，插入關(guān)鍵字20。

(9)給定結(jié)點的關(guān)鍵字序列為：19,14,10,

79o

設散列表的長度為13,散列函數(shù)為：H(K)=K%13o試畫出線性探測再散列

解決沖突時所構(gòu)造的散列表，并求出其平均查找長度。

解：線性探測再散列解決沖突時所構(gòu)造的散列表：

0123456789101112

14168275519208479231110

①②①④③①①③⑨①①③

平均查找長度ASL=(1*6+2*14-3*3+4*1+9*1)/12=30/3=3

(10)給定結(jié)點的關(guān)鍵字序列為：47,7,29,11,16,92,22,8,3,哈希表的長

度為Ik

設散列函數(shù)為：H(K)=K%llo試畫出平方探測再散列解決沖突時所構(gòu)造

的散列表，并求出其平均查找長度。

解：平方探測再散列解決沖突時所構(gòu)造的散列表。

012345678910

112234792167298

①②②①①①①②②

平均查找長度ASL=(1*5+2*4)/9=13/9=5/3(或1.44)

(11)給定結(jié)點的關(guān)鍵字序列為：19,14,23,1,68,20,84,27,55,11,10,

79o

設散列表的長度為13,散列函數(shù)為：H(K)=K%13o試畫出鏈地址法解決沖

突時所構(gòu)造的哈希表，并求出其平均查找長度。

解：鏈地址法解決沖突時所構(gòu)造的哈希表。

?|1?791A|

?|84|~|

?|10||

平均查找長度ASL=(1*6+2*4+3*1+4*1)/12=21/12=7/4(或1.75)

(12)給定結(jié)點的關(guān)鍵字序列為：47,7,29,11,16,92,22,8,3,哈希表的長

度為Ho

設散列函數(shù)為：H(K)=K%11。試畫出鏈地址法解決沖突時所構(gòu)造的哈希表，

并求出其平均查找長度。

解：

鏈地址法解決沖突時所構(gòu)造的哈希表。

平均查找長度ASL=(1*6+2*3)/9=12/9=4/3(或1.33)

五.算法設計題

(1)設單鏈表的結(jié)點是按關(guān)鍵字從小到大排列的,試寫出對此鏈表進行查找的算法。

如果查找成功，則返回指向關(guān)鍵字為x的結(jié)點的指針，否則返回NULL。

解：//實現(xiàn)本題功能的算法如下，如果查找成功，則返回指向關(guān)鍵字為x的結(jié)點的指

針，否則返回NULL,

node*sqsearch(node*head,intx)

(

node*p=head;

while(p!=NULL)

{if(x>p->key)

p=p->link;

else

if(x==p->key)

returnp;

else

{p=NULL;

returnp;

)

(2)試設計一個在用開放地址法解決從突的散列表上刪除一個指定結(jié)點的算法。

解：〃算法思想是：首先計算要刪除的關(guān)鍵字為k的記錄所在的位置，將