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

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

單項(xiàng)選擇題

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

A遞增或遞減

B遞增

C遞減

D無序

正確答案:A

單項(xiàng)選擇題

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

A判定樹是對(duì)有序序列進(jìn)行二分查找得到的樹

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

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

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

正確答案:C

單項(xiàng)選擇題

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

A2

B3

C4

D5

正確答案:C

單項(xiàng)選擇題

4.對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表需要____

A以順次方式存儲(chǔ)

B以順次方式存儲(chǔ)且元素有序

C以鏈?zhǔn)椒绞酱鎯?chǔ)

D以鏈?zhǔn)椒绞酱鎯?chǔ)且元素有序

正確答案:B

單項(xiàng)選擇題

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

AO(n2)

BO(n)

CO(log2n)

DO(nlog2n)

正確答案:C

單項(xiàng)選擇題

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

A該中間位置

B該中間位置－1

C該中間位置＋1

D該中間位置／2

正確答案:B

單項(xiàng)選擇題

7.對(duì)包含N個(gè)元素的散列表進(jìn)行查找，平均查找長(zhǎng)度____

A為O(log2N)

B為O(N)

C不徑直依靠于N

D上述三者都不是

正確答案:D

單項(xiàng)選擇題

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

An/2

Bn

C(n+1)/2

Dn+1

正確答案:B

單項(xiàng)選擇題

9.分別以以下序列構(gòu)造二叉排序樹，那么與其它幾個(gè)序列構(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

單項(xiàng)選擇題

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

A正確

B不正確

正確答案:A

單項(xiàng)選擇題

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

A正確

B不正確

正確答案:A

單項(xiàng)選擇題

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

A正確

B不正確

正確答案:A

單項(xiàng)選擇題

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

A起泡排序

B快速排序

C堆排序

D基數(shù)排序

正確答案:C

單項(xiàng)選擇題

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

A快速排序

B堆排序

C歸并排序

D基數(shù)排序

正確答案:C

單項(xiàng)選擇題

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

A

冒泡排序

B希爾排序

C簡(jiǎn)約選擇排序

D歸并排序

正確答案:D

單項(xiàng)選擇題

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

A插入排序

B冒泡排序

C選擇排序

D堆排序

正確答案:C

單項(xiàng)選擇題

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

A正確

B不正確

正確答案:B

單項(xiàng)選擇題

18.已知10個(gè)數(shù)據(jù)元素為〔54，28，16，34，73，62，95，60，26，43〕，對(duì)該數(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

單項(xiàng)選擇題

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

A正確

B不正確

正確答案:B

單項(xiàng)選擇題

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

A希爾排序

B冒泡排序

C插入排序

D選擇排序

正確答案:C

單項(xiàng)選擇題

21.一組記錄的關(guān)鍵字為〔46,79,56,38,40,84〕,那么利用快速排序的方法，以第一個(gè)記錄為基準(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

單項(xiàng)選擇題

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

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

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

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

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

正確答案:C

單項(xiàng)選擇題

23.用某種排序方法對(duì)線性表(25,84,21,47,15,27,68,35,20)進(jìn)行排序時(shí),元素序列的改變狀況如下(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

單項(xiàng)選擇題

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

A插入排序

B快速排序

C歸并排序

D選擇排序

正確答案:A

單項(xiàng)選擇題

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

單項(xiàng)選擇題

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

A正

B反

C正和反

D無

正確答案:B

單項(xiàng)選擇題

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

單項(xiàng)選擇題

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

A希爾排序

B歸并排序

C插入排序

D選擇排序

正確答案:D判斷題

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

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

31.對(duì)二叉排序樹進(jìn)行中序遍歷得到的序列肯定有序表正確錯(cuò)誤正確答案:對(duì)判斷題

32.二叉排序樹一般用于查找某個(gè)元素正確錯(cuò)誤正確答案:對(duì)判斷題

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

34.通過比

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

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

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

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

單項(xiàng)選擇題

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

A遞增或遞減

B遞增

C遞減

D無序

正確答案:A

單項(xiàng)選擇題

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

A判定樹是對(duì)有序序列進(jìn)行二分查找得到的樹

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

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

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

正確答案:C

單項(xiàng)選擇題

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

A2

B3

C4

D5

正確答案:C

單項(xiàng)選擇題

4.對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表需要____

A以順次方式存儲(chǔ)

B以順次方式存儲(chǔ)且元素有序

C以鏈?zhǔn)椒绞酱鎯?chǔ)

D以鏈?zhǔn)椒绞酱鎯?chǔ)且元素有序

正確答案:B

單項(xiàng)選擇題

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

AO(n2)

BO(n)

CO(log2n)

DO(nlog2n)

正確答案:C

單項(xiàng)選擇題

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

A該中間位置

B該中間位置－1

C該中間位置＋1

D該中間位置／2

正確答案:B

單項(xiàng)選擇題

7.對(duì)包含N個(gè)元素的散列表進(jìn)行查找，平均查找長(zhǎng)度____

A為O(log2N)

B為O(N)

C不徑直依靠于N

D上述三者都不是

正確答案:D

單項(xiàng)選擇題

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

An/2

Bn

C(n+1)/2

Dn+1

正確答案:B

單項(xiàng)選擇題

9.分別以以下序列構(gòu)造二叉排序樹，那么與其它幾個(gè)序列構(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

單項(xiàng)選擇題

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

A正確

B不正確

正確答案:A

單項(xiàng)選擇題

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

A正確

B不正確

正確答案:A

單項(xiàng)選擇題

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

A正確