數(shù)據(jù)結(jié)構(gòu)與算法第5次

第第頁數(shù)據(jù)結(jié)構(gòu)與算法第5次您的本次作業(yè)分?jǐn)?shù)為：97分

單項選擇題

1.從原理上講，折半查找法要求查找表中各元素的鍵值需要是____

A遞增或遞減

B遞增

C遞減

D無序

正確答案:A

單項選擇題

2.關(guān)于判定樹，以下說法不正確的選項是____

A判定樹是對有序序列進行二分查找得到的樹

Bn個結(jié)點的判定樹的深度為[log2n]+1

C判定樹的葉子結(jié)點都在同一層

D判定樹除去最末一層結(jié)點以后是滿二叉樹或空二叉樹

正確答案:C

單項選擇題

3.在順次表{2、5、7、10、14、15、18、23、35、41、52}中，用二分法查找關(guān)鍵碼12需做____次關(guān)鍵碼比較

A2

B3

C4

D5

正確答案:C

單項選擇題

4.對線性表進行二分查找時，要求線性表需要____

A以順次方式存儲

B以順次方式存儲且元素有序

C以鏈?zhǔn)椒绞酱鎯?/p>

D以鏈?zhǔn)椒绞酱鎯η以赜行?/p>

正確答案:B

單項選擇題

5.折半查找算法的時間繁復(fù)度是____

AO(n2)

BO(n)

CO(log2n)

DO(nlog2n)

正確答案:C

單項選擇題

6.假設(shè)用二分查找法取得的中間位置元素鍵值大于被查找值，說明被查找值位于中間值的前面，下次的查找區(qū)間為從原開始位置至____

A該中間位置

B該中間位置－1

C該中間位置＋1

D該中間位置／2

正確答案:B

單項選擇題

7.對包含N個元素的散列表進行查找，平均查找長度____

A為O(log2N)

B為O(N)

C不徑直依靠于N

D上述三者都不是

正確答案:D

單項選擇題

8.假設(shè)構(gòu)造一棵具有n個結(jié)點的二叉排序樹，最壞的狀況下其深度不會超過____

An/2

Bn

C(n+1)/2

Dn+1

正確答案:B

單項選擇題

9.分別以以下序列構(gòu)造二叉排序樹，那么與其它幾個序列構(gòu)造的結(jié)果不同的是____

A〔80，70，60，75，90，85，100，10〕

B〔80，90，85，70，60，10，75，100〕

C〔80，90，70，85，10，60，75，100〕

D〔80，90，100，70，85，60，10，75〕

正確答案:C

單項選擇題

10.假如某二叉樹的左右子樹的高度差的絕對值不大于1，那么肯定是平衡二叉樹

A正確

B不正確

正確答案:A

單項選擇題

11.AVL樹的任何子樹都是AVL樹。

A正確

B不正確

正確答案:A

單項選擇題

12.在散列表中，所謂同義詞就是具有相同散列地址的兩個元素

A正確

B不正確

正確答案:A

單項選擇題

13.設(shè)有1000個無序的元素,盼望用最快的速度選擇出其中前10個最大的元素,最好____排序法

A起泡排序

B快速排序

C堆排序

D基數(shù)排序

正確答案:C

單項選擇題

14.假設(shè)要求盡可能快地對實數(shù)數(shù)組進行穩(wěn)定的排序，那么應(yīng)選____

A快速排序

B堆排序

C歸并排序

D基數(shù)排序

正確答案:C

單項選擇題

15.以下排序算法的時間繁復(fù)度最小的是____

A

冒泡排序

B希爾排序

C簡約選擇排序

D歸并排序

正確答案:D

單項選擇題

16.在以下排序算法中，時間繁復(fù)度不受數(shù)據(jù)初始特性影響，恒為O(n2)的是____

A插入排序

B冒泡排序

C選擇排序

D堆排序

正確答案:C

單項選擇題

17.插入排序算法在每一趟都能選取出一個元素放在其最終的位置上。

A正確

B不正確

正確答案:B

單項選擇題

18.已知10個數(shù)據(jù)元素為〔54，28，16，34，73，62，95，60，26，43〕，對該數(shù)列按從小到大排序，經(jīng)過一趟冒泡排序后的序列為____

A16，28，34，54，73，62，60，26，43，95

B28，16，34，54，62，73，60，26，43，95

C28，16，34，54，62，60，73，26，43，95

D16，28，34，54，62，60，73，26，43，95

正確答案:B

單項選擇題

19.徑直插入排序是不穩(wěn)定的排序方法。

A正確

B不正確

正確答案:B

單項選擇題

20.排序方法中，從未排序序列中依次取出元素與已排序序列〔初始時為空〕中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為____

A希爾排序

B冒泡排序

C插入排序

D選擇排序

正確答案:C

單項選擇題

21.一組記錄的關(guān)鍵字為〔46,79,56,38,40,84〕,那么利用快速排序的方法，以第一個記錄為基準(zhǔn)元素得到的一次劃分結(jié)果為

A38,40,46,56,79,84

B40,38,46,79,56,84

C40,38,46,56,79,84

D40,38,46,84,56,79

正確答案:C

單項選擇題

22.快速排序方法在____狀況下最不利于發(fā)揮其優(yōu)點

A要排序的數(shù)據(jù)量太大

B要排序的數(shù)據(jù)在含有多個相同值

C要排序的數(shù)據(jù)已基本有序

D要排序的數(shù)據(jù)個數(shù)為奇數(shù)

正確答案:C

單項選擇題

23.用某種排序方法對線性表(25,84,21,47,15,27,68,35,20)進行排序時,元素序列的改變狀況如下(1)20,15,21,25,47,27,68,35,84(2)15,20,21,25,35,27,47,68,84(3)15,20,21,25,27,35,47,68,84那么所采納的排序方法是____

A選擇排序

B希爾排序

C歸并排序

D快速排序

正確答案:D

單項選擇題

24.在待排序的元素序列基本有序的前提下，效率最高的排序方法是____

A插入排序

B快速排序

C歸并排序

D選擇排序

正確答案:A

單項選擇題

25.以下關(guān)鍵碼序列中，屬于堆的是____

A〔15，30，22，93，52，71〕

B〔15，71，30，22，93，52〕

C〔15，52，22，93，30，71〕

D〔93，30，52，22，15，71〕

正確答案:A

單項選擇題

26.徑直插入排序的最壞狀況是初始序列為____序

A正

B反

C正和反

D無

正確答案:B

單項選擇題

27.一組記錄的排序碼為〔20,29,1

1,74,35,3,8,56〕，那么利用堆排序方法建立的初始(小頂)堆為____

A20,29,11,74,35,3,8,56

B3,29,8,56,35,20,11,74

C3,8,11,20,29,35,56,74

D20,29,3,8,11,35,

74,56

正確答案:B

單項選擇題

28.排序方法中，從未排序序列中選擇元素，并將其依次放入已排序序列〔初始時為空〕的一端的方法，稱為____

A希爾排序

B歸并排序

C插入排序

D選擇排序

正確答案:D判斷題

29.一般來說，二分查找比順次查找快,但二分查找有時候不能實施正確錯誤正確答案:對判斷題

30.n(n0)個結(jié)點的二叉排序樹至多有l(wèi)og2n層正確錯誤正確答案:錯判斷題

31.對二叉排序樹進行中序遍歷得到的序列肯定有序表正確錯誤正確答案:對判斷題

32.二叉排序樹一般用于查找某個元素正確錯誤正確答案:對判斷題

33.哈希表是用于排序的技術(shù)之一正確錯誤正確答案:錯判斷題

34.通過比

較的方法進行排序，其時間繁復(fù)性至少是O(log2n)正確錯誤正確答案:對判斷題

35.堆的結(jié)構(gòu)是完全二叉樹正確錯誤正確答案:對判斷題

36.序列｛12,23,15,24,22,18,16,30,27｝是一個堆正確錯誤正確答案:錯

您的本次作業(yè)分?jǐn)?shù)為：97分

單項選擇題

1.從原理上講，折半查找法要求查找表中各元素的鍵值需要是____

A遞增或遞減

B遞增

C遞減

D無序

正確答案:A

單項選擇題

2.關(guān)于判定樹，以下說法不正確的選項是____

A判定樹是對有序序列進行二分查找得到的樹

Bn個結(jié)點的判定樹的深度為[log2n]+1

C判定樹的葉子結(jié)點都在同一層

D判定樹除去最末一層結(jié)點以后是滿二叉樹或空二叉樹

正確答案:C

單項選擇題

3.在順次表{2、5、7、10、14、15、18、23、35、41、52}中，用二分法查找關(guān)鍵碼12需做____次關(guān)鍵碼比較

A2

B3

C4

D5

正確答案:C

單項選擇題

4.對線性表進行二分查找時，要求線性表需要____

A以順次方式存儲

B以順次方式存儲且元素有序

C以鏈?zhǔn)椒绞酱鎯?/p>

D以鏈?zhǔn)椒绞酱鎯η以赜行?/p>

正確答案:B

單項選擇題

5.折半查找算法的時間繁復(fù)度是____

AO(n2)

BO(n)

CO(log2n)

DO(nlog2n)

正確答案:C

單項選擇題

6.假設(shè)用二分查找法取得的中間位置元素鍵值大于被查找值，說明被查找值位于中間值的前面，下次的查找區(qū)間為從原開始位置至____

A該中間位置

B該中間位置－1

C該中間位置＋1

D該中間位置／2

正確答案:B

單項選擇題

7.對包含N個元素的散列表進行查找，平均查找長度____

A為O(log2N)

B為O(N)

C不徑直依靠于N

D上述三者都不是

正確答案:D

單項選擇題

8.假設(shè)構(gòu)造一棵具有n個結(jié)點的二叉排序樹，最壞的狀況下其深度不會超過____

An/2

Bn

C(n+1)/2

Dn+1

正確答案:B

單項選擇題

9.分別以以下序列構(gòu)造二叉排序樹，那么與其它幾個序列構(gòu)造的結(jié)果不同的是____

A〔80，70，60，75，90，85，100，10〕

B〔80，90，85，70，60，10，75，100〕

C〔80，90，70，85，10，60，75，100〕

D〔80，90，100，70，85，60，10，75〕

正確答案:C

單項選擇題

10.假如某二叉樹的左右子樹的高度差的絕對值不大于1，那么肯定是平衡二叉樹

A正確

B不正確

正確答案:A

單項選擇題

11.AVL樹的任何子樹都是AVL樹。

A正確

B不正確

正確答案:A

單項選擇題

12.在散列表中，所謂同義詞就是具有相同散列地址的兩個元素

A正確