數(shù)據(jù)結(jié)構(gòu)第九章查找作業(yè)及答案

第九章查找

一、填空題

1.在數(shù)據(jù)的存放無規(guī)律而言的線性表中進(jìn)行檢索的最佳方法是

2.線性有序表(al,a2,a3,,a256)是從小到大羅列的,對(duì)一個(gè)給

定的值k,用二分法檢索表中與k相等的元素，在查找不成功的情況下，

最多需要檢索次。設(shè)有100個(gè)結(jié)點(diǎn)，用二分法查找時(shí)，最大比較次數(shù)是

3.假設(shè)在有序線性表a[l..20]上進(jìn)行折半查找，則比較一次查找成

功的結(jié)點(diǎn)數(shù)為1;比較兩次查找成功的結(jié)點(diǎn)數(shù)為2；比較四次查找成功的

結(jié)點(diǎn)數(shù)為,其下標(biāo)從小到大挨次是—，平均查找長(zhǎng)度為

4.折半查找有序表(4,6,12,20,28,38,50,70,88,100),

若查找表中元素20,它將挨次與表中元素比較大小。

5.在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無關(guān)的查找方法是

6.散列法存儲(chǔ)的基本思想是由決定數(shù)據(jù)的存儲(chǔ)地址。

7.有一個(gè)表長(zhǎng)為m的散列表，初始狀態(tài)為空，現(xiàn)將n(n

8、設(shè)一哈希表表長(zhǎng)M為100,用除留余數(shù)法構(gòu)造哈希函數(shù)，即H(K)

=KM0DP(P〈=M),為使函數(shù)具有較好性能，P應(yīng)選

9、在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)無關(guān)的是

10、對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須以方式存儲(chǔ)，且結(jié)點(diǎn)

按關(guān)鍵字羅列。11在分塊查找方法中，首先查找索引，然后再查找相應(yīng)

的

12.順序查找n個(gè)元素的順序表，若查找成功，則比較關(guān)鍵字的次數(shù)

最多為一次；當(dāng)使用監(jiān)視哨時(shí)，若查找失敗，則比較關(guān)鍵字的次數(shù)為…

13.在有序表中，采用二分查找算法查等于A[12]的元素，

所比較的元素下標(biāo)挨次為

14.在有序表A[L.20]中，按二分查找方法進(jìn)行查找，查找長(zhǎng)度為5

的元素個(gè)數(shù)是15.已知二叉排序樹的擺布子樹均不為空，則—上所有

結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)值，上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值。

16、中序遍歷二叉排序樹得到的序列是序列(填有序或者無序)o

17、從有序表(10,16,25,40,61,28,80,93)中挨次二分查找

40和61元素時(shí)，其查找長(zhǎng)度分別為和?

二、單項(xiàng)選擇題

1.在表長(zhǎng)為n的鏈表中進(jìn)行順序查找，它的平均查找長(zhǎng)度為()A.

ASL=n;B.ASL=(n+1)/2;C.ASL=n+1;D.ASL

%log2(n+1)—1

2.折半查找有序表(4,6,10,12,20,30,50,70,88,100)o

若查找表中元素58,則

它將挨次與表中。比較大小，查找結(jié)果是失敗。

A.20,70,30,50B.30,88,70,50C.20,50D.30,88,

503.對(duì)22個(gè)記錄的有序表作折半查找，當(dāng)查找失敗時(shí)，至少需要比較0

次關(guān)鍵字。A.3B.4C.5D.64.鏈表合用于()查找

A.順序B.二分法C.順序，也能二分法D.隨機(jī)5.折半搜索與二叉

搜索樹的時(shí)間性能0。

A.相同B.徹底不同C.有時(shí)不相同D.數(shù)量級(jí)都是0(log2n)6.散列

表的地址區(qū)間為0-17,散列函數(shù)為H(K)=Kmodl70采用線性探測(cè)法處理沖

突，并將關(guān)鍵字序列26,25,72,38,8,18,59挨次存儲(chǔ)到散列表中。

元素59存放在散列表中的地址是()。

A.8B.9C.10D.117.當(dāng)采用分快查找時(shí)，數(shù)據(jù)的組織方式為()A.數(shù)據(jù)

分成若干塊，每塊內(nèi)數(shù)據(jù)有序

B.數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)不必有序，但塊間必須有序，每塊

內(nèi)最大(或者最小)的數(shù)據(jù)組成索引塊

C.數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序，每塊內(nèi)最大(或者最小)的數(shù)

據(jù)組成索引塊D.數(shù)據(jù)分成若干塊，每塊(除最后一塊外)中數(shù)據(jù)個(gè)數(shù)需

相同

8.散列函數(shù)有一個(gè)共同的性質(zhì)，即函數(shù)值應(yīng)當(dāng)以()取其值域的每一個(gè)值。

A.最大概率B.最小概率C,平均概率D.同等概率

9.假定有k個(gè)關(guān)鍵字互為同義詞，若用線性探測(cè)法把這k個(gè)關(guān)鍵字存

入散列表中，至少要進(jìn)行多少次探測(cè)？()

A.k-1次B.k次C.k+1次D.k(k+1)/2次

10、哈希查找中k個(gè)關(guān)鍵字具有同一哈希值，若用線性探測(cè)法將這k

個(gè)關(guān)鍵字對(duì)應(yīng)的記錄存入哈希表中，至少要進(jìn)行()次探測(cè)。

A.kB.k+1C.k(k+1)/2D.1+k(k+1)/2

11、在平衡二叉樹中插入一個(gè)結(jié)點(diǎn)后造成為了不平衡，設(shè)最低的不平

衡結(jié)點(diǎn)為A,并已知A的左孩子的平衡因子為0右孩子的平衡因子為1,則

應(yīng)作()型調(diào)整以使其平衡。A.LLB.LRC.RLD.RR

12、二叉查找樹的查找效率與二叉樹的()有關(guān)，在())時(shí)其查找效率

最低

(1)：A.高度B.結(jié)點(diǎn)的多少C.樹型D.結(jié)點(diǎn)的位置(2):A.結(jié)點(diǎn)太多B.完

全二叉樹C.呈單枝樹D,結(jié)點(diǎn)太復(fù)雜。13、順序表

(3,6,8,10,12,15,16,18,21,25,30)中,用折半查找算法查找關(guān)鍵

碼值11,所需的關(guān)鍵碼比較次數(shù)為0A)2B)3C)4D)5

14、對(duì)包含n個(gè)元素的哈希表進(jìn)行查找，平均查找長(zhǎng)度為()

A)0(log2n)B)0(n)C)0(nlog2n)D)不直接依賴于n

15、若查找每一個(gè)記錄的概率均等，則在具有n個(gè)記錄的連續(xù)順敘文

件中采用順序查找法查找一個(gè)記錄，其平均查找長(zhǎng)度ASL為()。

A.(n-l)/2B.n/2C.(n+l)/2D.nl6.下面關(guān)于二分查找的敘述正確的是

0

A.表必須有序，表可以順序方式存儲(chǔ)，也可以鏈表方式存儲(chǔ)C.表必

須有序，而且只能從小到大羅列

B.表必須有序且表中數(shù)據(jù)必須是整型，實(shí)型或者字符型D.表必須有序,

且表只能以順序方式存儲(chǔ)

17.對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須()A.以順序方式存

儲(chǔ)C.以鏈接方式存儲(chǔ)

B.以順序方式存儲(chǔ),且數(shù)據(jù)元素有序D.以鏈接方式存儲(chǔ),且數(shù)據(jù)元素

有序

18.合用于折半查找的表的存儲(chǔ)方式及元素羅列要求為()A.鏈接方

式存儲(chǔ)，元素?zé)o序B.鏈接方式存儲(chǔ)，元素有序

C.順序方式存儲(chǔ)，元素?zé)o序D.順序方式存儲(chǔ)，元素有序19.用二分

(對(duì)半)查找表的元素的速度比用順序法()A.必然快B.必然慢C.相等D.

不能確定

20.當(dāng)在一個(gè)有序的順序存儲(chǔ)表上查找一個(gè)數(shù)據(jù)時(shí)，即可用折半查找,

也可用順序查找，但前者比后者的查找速度()

A.必然快B.不一定C.在大部份情況下要快D.取決于表遞增還是遞

減21.具有12個(gè)關(guān)鍵字的有序表，折半查找的平均查找長(zhǎng)度()

A.3.IB.4C.2.5D.522.折半查找的時(shí)間復(fù)雜性為()

A.0(n2)B.0(n)C.0(nlogn)D.0(logn)

23.設(shè)順序線性表的長(zhǎng)度為30,分成5塊，每塊6個(gè)元素，如果采用分

塊查找，則其平均查找長(zhǎng)度為(D)o(A)6

(B)11

(0)5

(D)6.5

24.二叉排序樹的查找效率與二叉樹的()有關(guān)。

A.高度B.結(jié)點(diǎn)的多少C.樹型D.結(jié)點(diǎn)的位置25.在等概率情況下，一

棵平衡樹的ASL為()。

A.0(l)B.0(log2n)C.0((log2n)2)D.0(nlog2n)

26.分別以下列序列構(gòu)造二叉排序樹，與用其它三個(gè)序列所構(gòu)造的結(jié)

果不同的是0A.(100,80,90,60,120,110,130)B.(100,120,

110,130,80,60,90)C.(100,60,80,90,120,110,130)D.(100,

80,60,90,120,130,110)

27.在平衡二叉樹中插入一個(gè)結(jié)點(diǎn)后造成為了不平衡，設(shè)最低的不平

衡結(jié)點(diǎn)為A,并已知A的左孩子的平衡因子為0右孩子的平衡因子為1,

則應(yīng)作0型調(diào)整以使其平衡。A.LLB.LRC.RLD.RR28、下列二叉排序樹中,

滿足平衡二叉樹定義的是。。

29.下列關(guān)于m階B-樹的說法錯(cuò)誤的是()。A.根結(jié)點(diǎn)至多有m棵子

樹B.所有葉子都在同一層次上

C.非葉結(jié)點(diǎn)至少有m/2(m為偶數(shù))或者m/2+1(m為奇數(shù))棵子樹D.

根結(jié)點(diǎn)中的數(shù)據(jù)是有序的

30.下面關(guān)于m階B樹說法正確的是()

①每一個(gè)結(jié)點(diǎn)至少有兩棵非空子樹；②樹中每一個(gè)結(jié)點(diǎn)至多有m—1

個(gè)關(guān)鍵字;③所有葉子在同一層上;④當(dāng)插入一個(gè)數(shù)據(jù)項(xiàng)引起B(yǎng)樹結(jié)點(diǎn)分

裂后，樹長(zhǎng)高一層。A.①②③B.②③C.②③④D.③31.下面關(guān)于B和B+

樹的敘述中，不正確的是()

A.B樹和B+樹都是平衡的多叉樹。B.B樹和B+樹都可用于文件的索引

結(jié)構(gòu)。CB樹和B+樹都能有效地支持順序檢索。D.B樹和B+樹都能有效地

支持隨機(jī)檢索。32、下列敘述中，不符合m階B樹定義要求的是()

A.根節(jié)點(diǎn)最多有m棵子樹B.所有葉結(jié)點(diǎn)都在同一層上C.各結(jié)點(diǎn)內(nèi)關(guān)鍵

字均升序或者降序羅列D.葉結(jié)點(diǎn)之間通過指針鏈接

33、設(shè)散列表中有m個(gè)存儲(chǔ)單元，散列函數(shù)H(key)=key%p,則p最

好選擇。。(A)小于等于m的最大奇數(shù)

(B)小于等于m的最大素?cái)?shù)

A、

B、C、D、（C）小于等于m的最大偶數(shù)⑻小于等于m的最大合數(shù)

34、適于對(duì)動(dòng)態(tài)查找表進(jìn)行高效率查找的組織結(jié)構(gòu)是。。

A.有序表B.分塊有序表C.二叉排序樹D.線性鏈表

三、判斷題

1、查找相同結(jié)點(diǎn)的效率折半查找總比順序查找高。（）2、索引順序表

的特點(diǎn)是塊內(nèi)可無序，塊間要有序。（）

3、在采用線性探測(cè)法處理沖突的散列表中，所有同義詞在表中一定

相鄰。（）4、在平衡二叉樹中，任意結(jié)點(diǎn)擺布子樹的高度差（絕對(duì)值）不

超過lo（）5、若查找表的長(zhǎng)度為n,則順序查找法的平均查找長(zhǎng)度為

（n+1）12。（）6、折半搜索合用于有序表，包括有序的順序表和有序的

鏈表。0

7.采用線性探測(cè)法處理散列時(shí)的沖突，當(dāng)從哈希表刪除一個(gè)記錄時(shí)，

不應(yīng)將這個(gè)記錄的所在位置置空，因?yàn)檫@會(huì)影響以后的查找。（）

8.在散列檢索中，“比較”操作普通也是不可避免的。（）

9.在m階B-樹中每一個(gè)結(jié)點(diǎn)上至少有個(gè)關(guān)鍵字，最多有m個(gè)關(guān)鍵字。

0

10.負(fù)載因子（裝填