算法與數(shù)據(jù)結(jié)構(gòu)第8章 查找

第8章查找

一、單選題（共10題，35分）

1、在表長為n的鏈表中進(jìn)行線性查找，它的平均查找長度為（）。

A、ASL=n;

B、ASL=（n+1）/2;

C、ASL=+1;

D>ASL^log2（n+1）—1

正確答案：B

2、折半查找有序表（4,6,10,12,20,30,50,70,88,100）.若查找表中元素58,

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

A、20,70,30,50

B、30,88,70,50

C、20,50

D、30,88,50

正確答案：A

3、對(duì)22個(gè)記錄的有序表作折半查找，當(dāng)查找失敗時(shí)，至少需要比較（）次關(guān)鍵字。

A、3

B、4

C、5

D、6

正確答案：C

4、鏈表適用于（）查找。

A、順序

B、二分法

C、順序，也能二分法

D、隨機(jī)

正確答案：A

5、對(duì)具有n個(gè)元素的有序表采用折半查找，則算法的時(shí)間復(fù)雜度為()。

A、0(n)

B、0(n2)

C、0(1)

D、O(logan)

正確答案：D

6、從具有n個(gè)結(jié)點(diǎn)的二叉排序樹中查找一個(gè)元素時(shí)，在平均情況下的時(shí)間復(fù)雜度大致為

()o

A、0(n)

B、0(1)

C、Odogan)

D、0(n2)

正確答案：C

7、在一棵平衡二叉排序樹中，每個(gè)結(jié)點(diǎn)的平衡因子的取值范圍是().

A、-1~1

B、-2-2

C、1~2

D、0~1

正確答案：A

8、若根據(jù)查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K%13計(jì)算哈希

地址，則元素64的哈希地址為()。

A、4

B、8

C、12

D、13

正確答案：C

9、若根據(jù)查找表(23,44,36,48,52,73,64,58)建立哈希表，采用

h(K)=K%7計(jì)算哈希地址，則哈希地址等于3的元素個(gè)數(shù)()o

A、1

B、2

C、3

D、4

正確答案：B

10、若根據(jù)查找表建立長度為m的哈希表，采用線性探測法處理沖突,

假定對(duì)一個(gè)元素第一次計(jì)算的哈希地址為d,則下一次的哈希地址為

()。

A、d

B、d+1

C、(d+1)/m

D、(d+l)%m

正確答案：D

二、填空題(共14題，51分)

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

正確答案：

第1空：

順序查找(線性查找)

2、折半查找有序表(4,6,12,20,28,38,50,70,88,100),若查找表中元素20,

它將依次與表中元素比較大小。

正確答案：

第1空：

28,6,12,20

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

正確答案：

第1空：

散列查找

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

正確答案：

第1空：

關(guān)鍵字的值

5、以折半查找方法在一個(gè)查找表上進(jìn)行查找時(shí)，該查找表必須組織成

存儲(chǔ)的表。

正確答案：

第1空：

順序

第2空：

有序

6^從有序表(12,18,3(),43,56,78,82,95)中分別折半查找43和56元素時(shí)，其比較次數(shù)分別為

和,

正確答案：

第1空：

1

第2空：

3

7、假定對(duì)長度n=50的有序表進(jìn)行折半查找，則對(duì)應(yīng)的判定樹高度為，最后一

層的結(jié)點(diǎn)數(shù)為。

正確答案：

第1空：

6

第2空：

19

8、對(duì)一棵二叉排序樹進(jìn)行中序遍歷時(shí)，得到的結(jié)點(diǎn)序列是一個(gè).

正確答案：

第1空：

有序序列

9、從一棵二叉排序樹中查找一個(gè)元素時(shí)，若元素的值等于根結(jié)點(diǎn)的值，則表明，

若元素的值小于根結(jié)點(diǎn)的值，則繼續(xù)向_______查找，若元素的值大于根結(jié)點(diǎn)的值，則繼

續(xù)向________查找。

正確答案：

第1空：

查找成功

第2空：

左子樹

第3空：

右子樹

10、在一棵平衡二叉排序樹中，每個(gè)結(jié)點(diǎn)的左子樹高度與右子樹高度之差的絕對(duì)值不超過

正確答案:

第1空：

11、假定對(duì)線性表(38,25,74,52,48)進(jìn)行哈希存儲(chǔ)，采用H(K)=K%7作為哈希函數(shù)，采用

線性探測法處理沖突，則在建立哈希表的過程中，將會(huì)碰到次存儲(chǔ)沖突。

正確答案：

第1空：

5

12、對(duì)線性表(18,25,63,50,42,32,90)進(jìn)行哈希存儲(chǔ)時(shí)，若選用H(K)=K%9作為哈希函數(shù),

則哈希地址為0的元素有個(gè)，哈希地址為5的元素有個(gè)。

正確答案：

第1空：

3

第2空：

2

13、數(shù)據(jù)結(jié)構(gòu)反映了數(shù)據(jù)元素之間的結(jié)構(gòu)關(guān)系。鏈表是一種，它對(duì)于

數(shù)據(jù)元素的插入和刪除o

正確答案：

第1空：

非順序存儲(chǔ)線性表

第2空：

不需要移動(dòng)結(jié)點(diǎn)，只需改變結(jié)點(diǎn)指針

14、散列法存儲(chǔ)的基本思想是根據(jù)來決

定，碰撞（沖突）指的是,

處理碰撞的兩類主要方法是。

正確答案：

第1空：

關(guān)鍵碼值

第2空：

存儲(chǔ)地址

第3空：

不同關(guān)鍵碼值對(duì)應(yīng)到相同的存儲(chǔ)地址

第4空：

拉鏈法和開地址法

三、計(jì)算題（共4題，14分）

1、已知一個(gè)順序存儲(chǔ)的有序表為（15,26,34,39,45,56,58,63,74,76）,

試畫出對(duì)應(yīng)的折半查找判定樹，求出其平均查找長度。

正確答案：

答:平均查找長度等于29/10,折半查找判定樹如下：

2、假定一個(gè)線性表為(38,52,25,74,68,16,30,54,90,72),畫出按線性表中元素的次序生成的

一棵二叉排序樹，求出其平均查找長度。

正確答案：

解：二叉排序樹如下圖所示，平均查找長度等于32/10。

3、假定一個(gè)待哈希存儲(chǔ)的線性表為(32,75,29,63,48,94,25,46,18,70),哈希地址空間為

HT[13],若采用除留余數(shù)法構(gòu)造哈希函數(shù)和線性探測法處理沖突，試求出每一元素在哈希

表中的初始哈希地址和最終哈希地址，畫出最后得到的哈希表，求出平均查找長度。

正確答案：

H(K)=K%13平均