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

第5章查找習(xí)題答案

4、習(xí)題

一、填空題

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

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

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

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

(5)對(duì)于長(zhǎng)度為n的線性表，若進(jìn)行順序查找，則時(shí)間復(fù)雜度為O(n)。

(6)對(duì)于長(zhǎng)度為n的線性表，若采用二分查找,則時(shí)間復(fù)雜度為：O(log2n)。

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

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

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

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

(10)對(duì)二叉排序樹(shù)進(jìn)行查找的方法是用待查的值與根結(jié)點(diǎn)的鍵值進(jìn)行比較，若比

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

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

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

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

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

的方法。

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

象為沖突。

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

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

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

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

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

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

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

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

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

5,

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

終端結(jié)點(diǎn)至少有?而2?棵子樹(shù)。

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

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

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

高度減少1層。

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

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

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

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

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

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

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

二、選擇題

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

A.集合B.圖C.樹(shù)D.文件

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

A.散列存儲(chǔ)B.順序存儲(chǔ)或鏈接存儲(chǔ)

C.壓縮存儲(chǔ)D.索引存儲(chǔ)

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

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

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

(4)對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須(D)。

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

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

(5)衡量查找算法效率的主要標(biāo)準(zhǔn)是(B

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

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

(A)查找方法。

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

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

A.順序B.二分C.隨機(jī)D.順序或二分

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

分查找值為82的結(jié)點(diǎn)時(shí);(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)對(duì)有14個(gè)元素的有序表A[l..14]作二分查找，查找元素A[4]時(shí)的被比較元素

依次為(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)有一個(gè)長(zhǎng)度為12的有序表，按二分查找法對(duì)其進(jìn)行查找，在表內(nèi)各元素等概

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

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

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

設(shè)采用順序查找來(lái)確定結(jié)點(diǎn)所在的塊時(shí)，每塊分(C)個(gè)結(jié)點(diǎn)最佳。

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

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

A.平衡二叉樹(shù)B.有序表的查找

C.散列查找D.二叉排序樹(shù)的查找

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

addr(15)=4

addr(38)=5

addr(61)=6

addr(84)=7

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

(D)。

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

(15)對(duì)包含n個(gè)元素的散列表進(jìn)行查找，平均查找長(zhǎng)度為(D)。

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

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

A.兩個(gè)元素具有相同序號(hào)B.兩個(gè)元素的鍵值不同

C.不同鍵值對(duì)應(yīng)相同的存儲(chǔ)地址D.兩個(gè)元素的鍵值相同

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

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

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

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

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

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

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

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

A.順序表B.二叉排序樹(shù)

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

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

則必須分裂為兩個(gè)結(jié)點(diǎn)。

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

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

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

三、應(yīng)用題

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

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

2）求等概率情況下的平均查找長(zhǎng)度ASL。

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

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

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

2）求等概率情況下的平均查找長(zhǎng)度ASL。

解：1）構(gòu)造二叉排序樹(shù)：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,依次插入下圖所示的二叉排序樹(shù),

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

解:

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

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

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

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

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

2）求等概率情況下的平均查找長(zhǎng)度ASL。

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

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

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

2）求等概率情況下的平均查找長(zhǎng)度ASL。

解：

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

（或=25/9）

（7）畫出對(duì)長(zhǎng)度為1（）的有序表進(jìn)行折半查找的判定樹(shù)，并求其等概率時(shí)查找成功

的平均查找長(zhǎng)度。

解：長(zhǎng)度為10的判定樹(shù)：

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

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

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

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

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

79o

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

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

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

0123456789101112

14168275519208479231110

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

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

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

度為Ik

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

的散列表，并求出其平均查找長(zhǎng)度。

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

012345678910

112234792167298

①②②①①①①②②

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

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

79o

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

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

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

?|1?791A|

?|84|~|

?|10||

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

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

度為Ho

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

并求出其平均查找長(zhǎng)度。

解：

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

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

五.算法設(shè)計(jì)題

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

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

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

針，否則返回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)試設(shè)計(jì)一個(gè)在用開(kāi)放地址法解決從突的散列表上刪除一個(gè)指定結(jié)點(diǎn)的算法。

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