數(shù)據(jù)結(jié)構(gòu)期末測驗(yàn)

數(shù)據(jù)結(jié)構(gòu)期末測驗(yàn)

1.使用雙鏈表存儲(chǔ)線性表，其優(yōu)點(diǎn)是可以()［單選題］*

A.提高查找速度

B.更方便數(shù)據(jù)的插入和刪除

C.節(jié)約存儲(chǔ)空間

D很快回收存儲(chǔ)空間

2.下面幾種算法時(shí)間復(fù)雜度中，時(shí)間復(fù)雜度最高的是()。［單選題］*

A.O(nlog2n)

B.O(n2)

C.O(n)

D.0(2n)(正確答案)

3.線性表(al,a2,…,an)以鏈接方式存儲(chǔ)時(shí)，若指針指向頭結(jié)點(diǎn)，則訪問第i個(gè)元

素的時(shí)間復(fù)雜度為(”單選題］*

A.0⑴

B.O(1)

C.O(n)(正確答案)

D.O(i-1)

4.串是一種()［單選題］*

A.鏈?zhǔn)酱鎯?chǔ)的線性結(jié)構(gòu)

B.鏈?zhǔn)酱鎯?chǔ)的非線性結(jié)構(gòu)

C.限制元素類型的線性結(jié)構(gòu)

D.限制存取點(diǎn)的非線性結(jié)構(gòu)

5.設(shè)順序線性表中有n個(gè)數(shù)據(jù)元素，則刪除表中第i個(gè)（從1開始計(jì)數(shù)）元素需要

移動(dòng)（）個(gè)元素。［單選題］*

A.n-i（正確答案）

B.n+1-i

C.n-1-i

D.i

6.從19個(gè)元素中查找其中某個(gè)元素，如果最多進(jìn)行5次元素之間的比較，則采用

的查找方法只可能是（）。［單選題］*

A.折半查找,箜案?

B.分塊查找

C.順序查找

D渚R不可能

7.在含有12個(gè)結(jié)點(diǎn)的平衡二叉樹上，查找關(guān)鍵字為35（存在該結(jié)點(diǎn)）的結(jié)點(diǎn)，則

依次比較的關(guān)鍵字有可能是（）。［單選題］*

A.46,36,18,20,28,35

B.47,37,18,27,36

C.27,48,39,43,37

D.15,45,25,351確答案）

8.一個(gè)遞增表為RO.11］,采用折半查找方法，在某次成功查找到指定的記錄時(shí)，

以下0是可能的記錄比較序列。［單選題］*

A.R[0],R[5]、R[2]

B.RfOKR[6]、Rf9]

C.R[5]、R[8],RflOl

D.R[5]XR[2]sR[4]

9.當(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ù)必須相同

10.設(shè)待查找元素為47,且已存入變量k中，如果在查找過程中，和k進(jìn)行比較的

元素依次是47、32、46、25、47,則所采用的查找方法（）。［單選題］*

A.是一種錯(cuò)誤的方法

B.可能是分塊查找弓答案）

C.可能是順序查找

D.可能是折半查找

H.用n個(gè)關(guān)鍵字構(gòu)造的一棵二叉排序樹，經(jīng)過i次關(guān)鍵字比較成功找到的元素個(gè)

數(shù)最多為（）。［單選題］*

A.i

B.2i

C.2i-1（正確答案）

D.2i-1

12.對于下列關(guān)鍵字序列，不可能構(gòu)成某二叉排序樹中一條查找路徑的序列是

（）o［單選題］*

A.95,22,91,24,94,71正確答案）

B.92,20,91,34,88,35

C.21,89,77,29,36,38

D.12,25,71,68,33,34

13.以下關(guān)于哈希查找的敘述中錯(cuò)誤的是（）。［單選題］*

A.用拉鏈法解決沖突易引起堆積現(xiàn)象

B.用線性探測法解決沖突易引起堆積現(xiàn)象

C.哈希函數(shù)選得好可以減少?zèng)_突現(xiàn)象

D.哈希函數(shù)H（k）=kMODp,p通常取小于等于表長的素?cái)?shù)

14.一棵高度為h的并且只有h個(gè)結(jié)點(diǎn)的二叉樹，采用順序存儲(chǔ)結(jié)構(gòu)存放在R［l..n］

中，則n應(yīng)該至少是（）o［單選題］*

A.2h

B.2h-1

C.2h-1（正確答案）

D.2h

15.一棵哈夫曼樹中共有199個(gè)結(jié)點(diǎn)，它用于（）個(gè)字符的編碼。［單選題］*

A.99

B.100（正確答案）

C.101

D.199

16設(shè)哈夫曼編碼的長度不超過4,若已對兩個(gè)字符編碼為1和01,則最多還可對

（）個(gè)字符編碼。［單選題］*

A.2

B.3

C.4-:確答窠）

D.5

17.有一棵含有8