數(shù)據(jù)結(jié)構(gòu)與算法周考三1

數(shù)據(jù)結(jié)構(gòu)與算法周考三1

您的姓名：［填空題］*

1.二叉排序樹的葉子結(jié)點個數(shù)為5個，則度為2的結(jié)點的數(shù)目是()。［單選題］*

A、6

B、5

C、4

D、3

2.假定有k個關(guān)鍵字互為同義詞，若用線性探測法把這k個關(guān)鍵字存入散列表中，

至少要進行多少次探測()o［單選題］*

A、k-1次

B、k次

C、k+1次

D、k(k+l)/2次

3.直接插入排序的時間復(fù)雜度和順序查找的時間復(fù)雜度分別是()o［單選題］*

A、0(n)和O(log2n)

B、O(n*n)和0(n)

C、0(1)和)0(n)

D、0(n)和0(1)

4.在排序中，對于關(guān)鍵字相等的記錄，排序前后相對位置不變。這時稱排序為

0o［單選題］*

A、穩(wěn)定排序

B、不穩(wěn)定排序

C、不確定是穩(wěn)定排序還是不穩(wěn)定排序

D、基數(shù)排序

5.就性能而言，希爾排序的時間復(fù)雜度是（）o［單選題］*

A、O（n*n）

B、O（nlog2n）

C、0（n）

D、O（n3/2）E確答案）

6.希爾排序又稱為（）。［單選題］*

A、縮小增量排序（正確答案）

B、二分插入排序

C、多路歸并排序

D、錦標賽排序

7.N個記錄進行冒泡排序最多需要（）趟排序，可以完成排序。［單選題］*

A、N-1（正確答案）

B、N

C、N-2

D、（N+l）/2

8.30個記錄進行冒泡排序，使用未改進的冒泡排序，則需要（）趟排序才能完成

排序。［單選題］*

A、29（正確答案）

B、30

C、28

D、27

9.遞歸概念指的是()。［單選題］*

A、程序調(diào)用自身的編程技巧

B、特定功能的模塊

C、相同數(shù)據(jù)類型的有序的集合

D、從小到大進行排列

1().青蛙過河案例中，如果河中沒有石柱，有y片荷葉的話，那么從左岸到右岸可

以過去()只青蛙。［單選題］*

A、y+1只確答案)

B、y+2只

C、y+3只

D、y+4只

11.一趟快速排序是將記錄一分為(),返回中軸所在的位置。［單選題］*

A、二(正確答案)

B、三

C、四

D、都不對

12.簡單選擇排序中，每一趟選擇最小的記錄的過程，則每一趟排序的時間復(fù)雜度

是0o［單選題】*

A、O(n)

B、O(n*n)

C、0(1)

D、O(n*log2n)

13.N個記錄，采用簡單選擇排序，每趟最多進行（）次交換。［單選題］*

A、1E確答案）

B、2

C、N-2

D、N-1

14.從排序大類上講，簡單選擇排序和冒泡排序是（）排序。［單選題］*

A、同一類

B、不同類（正確答案）

C、不確定

D、都不對

6N個記錄是有序的使用什么查找效率更高（）o［單選題］*

A、順序查找

B、折半查找（正確答案）

C、分塊查找

D、隨機查找

16數(shù)據(jù)結(jié)構(gòu)與算法中，在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排

列次序無關(guān)的是（）。［單選題］*

A、希爾排序

B、冒泡排序

C、直接插入排序

D、簡單選擇排序（正確答案）

17.采用快速排序進行排序，問題規(guī)模為n,則時間復(fù)雜度是（）。［單選題］*

A、O(n3/2)

B、O(n*n)

C、0(n)

D、O(n*log2n)(正確答案)

18.快速排序在()情況下不利于發(fā)揮其長處或優(yōu)勢。［單選題］*

A、記錄有相同的關(guān)鍵字時

B、記錄完全亂序時

C、記錄已經(jīng)基本有序時

D、記錄的關(guān)鍵字較大時

19.ACM算法的素數(shù)和計算中，sum變量用于累加素數(shù)之和，那么它的初值應(yīng)賦值

為0o［單選題］*

A、0(正確答案)

B、1

C、10()

D、不賦初值

20.數(shù)據(jù)結(jié)構(gòu)與算法中，素數(shù)的特點是()。［單選題］*

A、只能被1和本身整除

B、可以被2整除

C、素數(shù)和完數(shù)是相同的概念

D、素數(shù)就是合數(shù)

21下列那個是直接遞歸形式函數(shù)()o［單選題］*

A:voidtell_stroy(){tell_stroy();}

B:voidtell_stroy(){voidtell_stroy();}

C:voidtell_stroy(){stroy();}

D:voidtell_stroy(){tell();}

22冒泡排序最好的情況是，記錄完全有序，20個記錄待排序只需要比較（）次即

可完成排序。［單選題］*

A:20

B:19（正確答案）

C:18

D:190

23.排序前序列為：3415886672問經(jīng)過一趟直接插入排序（按從小到大排序）后的

序列是（）。［單選題】*

A:1534886672（正確答案）

B:3415886672

C:1534667288

D:1534668872

24.裝填因子又稱為（）。［單選題］*

A:負載因子（正確答案）

B:平衡因子

C:外力因子

D:合力因子

25.以下屬于哈希函數(shù)的構(gòu)造方法的是（）。［單選題］*

A:直接定址法

B:哈希再散列法

C:線性探測再散列法

D:二次探測再散列法

26.數(shù)據(jù)結(jié)構(gòu)與算法里，數(shù)據(jù)序列（2,1,4,9,8,10,6,20）只能是下列排序算法

中的（）的兩趟排序后的結(jié)果。［單選題］*

A.快速排序

B.冒泡排序

C.以上都不對

D.直接插入

27.數(shù)據(jù)結(jié)構(gòu)與算法里，完數(shù)是完美數(shù)，它等于（）。［單選題］*

A.所有因子之和（正確答案）

B只能被1和它本身整除

C.是該范圍內(nèi)最大的質(zhì)數(shù)

D.所有小于它的數(shù)之和

28.數(shù)據(jù)結(jié)構(gòu)與算法里，完數(shù)N的因子（真因子）為a,b,c,則有（）o［單選題］*

A.N=a+b+c（正確答案）

B.N-l=a+b+c

C.N=a+b-c

D.N=a*b*c

29.關(guān)于希爾排序描述正確的是（）o*

A、希爾排序是不穩(wěn)定排序

B、希爾排序是屬于插入排序

C、希爾排序的時間復(fù)雜度是O（n3/2）

D、希爾排序又稱為縮小增量排序

3（）.下列排序中是不穩(wěn)定排序的是（）。*

A、希爾排序

B、快速排序

C、直接插入排序

D、冒泡排序

31.從排序大類上看，屬于選擇排序的是（）。*

A、簡單選擇排序（正確答案）

B、堆排序

C、快速排序

D、冒泡排序

32.switch語句中，在（）中的表達式類型可以是（）o*

A、整型（正確答案）

B、字符型答案）

C、字符串

D、浮點型

33.6是完數(shù)，其因子包括（）o*

A、1（正確答案）

B、2（正確答案）

C、3（正確答案）

D、6（正確答案）

33.哈希表的平均查找長度與哪些（）因素有關(guān)。*

A、處理沖突的方法

B、哈希函數(shù)答案）

C、裝填因子

D、待存記錄的大小

34.排序可以分為四大類，主要包含有（）。*

A、插入排序

B、交換排序"

C、選擇排序（正確答案）

D、歸并排序（正確答案）

35.排序是穩(wěn)定排序或不穩(wěn)排序的插入排序是（）。*

A、希爾排序

B、直接插入排序

C、堆排序

D、快速排序

36關(guān)于冒泡排序的比較次數(shù)和排序趟數(shù)描述正確的是（）。*

A:N個記錄最多N-1趟排序即可完成

B:N個記錄最少比較N-1次，可完成排序，這是記錄完全有序的情況

C:N個記錄最多比較N*（N-l）/2次可完成排序，這是記錄完全逆序的情況。

答案）

D:在一趟排序中若無記錄交換，就會停止排序。

37關(guān)于快速排序描述不正確的是（）。*

A:快速排序是穩(wěn)定排序

B:快速排序的時間復(fù)雜度是O（nlog2n）

C:快速排序不存在不相鄰的記錄之間的交換

D:快速排序的時間復(fù)雜度是O（n*n）

38下列排序中是穩(wěn)定排序的是（）o*

A:希爾排序

B：快速排序

C：直接插入排序

D:冒泡排序前答案）

39動態(tài)查找表：邊查找，邊改變集合中的元素，改變的方式可以是（）o*

A:增加（正確答案）

B:刪除（正確答案）

C:交換

D:移動

40.數(shù)據(jù)結(jié)構(gòu)與算法里，關(guān)于哈希表的裝填因子，以下正確的有（）o*

A:裝填因子的值越小，發(fā)生沖突的概率越小”答案）

B:裝填因子越大，表中填入的記錄越多，在填入的時候發(fā)生沖突的可能性就越

大，在進行查找時候，查找的次數(shù)也就越多。

C:裝填因子=表中填入的記錄數(shù)/哈希表的總長度腕捽至）

D:裝填因子的值越小，就可以避免沖突的發(fā)生

41數(shù)據(jù)結(jié)構(gòu)與算法里，設(shè)哈希表長度為11,哈希函數(shù)H（K）=（K的第一個字母在字母

表中的序號）MOD11,若輸入順序為（口用人月?4可?,1,10（；^）,采用內(nèi)散列表,處理沖

突方法為線性探測法，要求構(gòu)造哈希表，在等概率情況下查找成功平均查找長度錯誤

的是（）。*

A:4（正確答案）

B:3（正確答案）

C:20/9

D:23/9（正確答案）

42關(guān)于二叉排序樹描述有誤的是（）。*

A:二叉排序的右子樹上結(jié)點的關(guān)鍵字小于左子樹上的結(jié)點的關(guān)鍵字用答案）

B:二叉排序的左子樹上結(jié)點的關(guān)鍵字小于右子樹上的結(jié)點的關(guān)鍵字

C：二叉排序的根節(jié)點的關(guān)鍵大于右子樹上結(jié)點的關(guān)鍵字:確答案」

D:二叉排序的根節(jié)點的關(guān)鍵大于左子樹上結(jié)點的關(guān)鍵字

43下列關(guān)于查找表描述正確的是（）o*

A:查找表分為靜態(tài)查找表和動態(tài)查找表

B:動態(tài)查找表邊查找，邊改變集合內(nèi)的元素

C:靜態(tài)查找表只查找不改變集合中的元素

D:其它選項說法都正確

44.數(shù)據(jù)結(jié)構(gòu)與算法里，直接插入排序最好、最壞兩種情況的時間復(fù)雜度分別是

0o*

A.O（n*log2n）

B.O（n）（正確答案）

C.O（log2n）

D.O（n*n）（正確答案）

45.二叉樹的先序遍歷和中序遍歷如下：先序遍歷:EFHIGJK；中序遍歷：HFIEJKG

該二叉樹根的右子樹的根不可能是:（）。［多選題］*

占位符不用管

A、E（正確答案）

B、F（正確答案）

C、G

D、H（正確答案）

46.裝填因子的計算方法是（）。*

A、1-俵中未填入記錄的數(shù)目/哈希表的總長度）

B、表中未填入記錄的數(shù)目/哈希表的總長度

C、(表中未填入的記錄數(shù)/)/哈希表的總長度

D、表中填入的記錄數(shù)/哈希表的總長

47.數(shù)據(jù)結(jié)構(gòu)與算法里，關(guān)于希爾排序描述正確的是()o*

A.希爾排序是不穩(wěn)定排序

B.希爾排序是屬于插入排序正確答案)

C.希爾排序的時間復(fù)雜度是O(n3/2)

D.希爾排序又稱為縮小增量排序

48.數(shù)據(jù)結(jié)構(gòu)與算法里，以下算法時間復(fù)雜度是O(n*n)的是()o*

A.冒泡排序

B.直接插入排序

C.折半查找

D.希爾排序

49.數(shù)據(jù)結(jié)構(gòu)與算法里，關(guān)于快速排序描述正確的是()o*

A.快速排序是不穩(wěn)定排序;正確等案)

B.快速排序的時間復(fù)雜度是O(nlog2n)。

C.快速排序是一種交換排序(正確答案)

D.快速排序是內(nèi)排序的一種

50.數(shù)據(jù)結(jié)構(gòu)與算法里，關(guān)于二叉排序樹相關(guān)描述正確的是()o*

A.二叉排序樹是應(yīng)用于動態(tài)查找的結(jié)構(gòu)

B.二叉排序樹的中序列是升序序列

C.二叉排序樹的左子樹也是二叉排序樹而答案)

D.二叉排序樹的定義具有遞歸性

51.數(shù)組在內(nèi)存中是連續(xù)存放的，不會被間隔開。［判斷題］*

對

錯

52.數(shù)據(jù)結(jié)構(gòu)與算法里，研究完數(shù)最早的是中國的《九章算術(shù)》。［判斷題］*

對

錯（正確答案）

53.數(shù)據(jù)結(jié)構(gòu)與算法里，完數(shù)N的所有因子為x,y,z,則必有N等于x+y+z。］判

斷題］*

對（正確答案）

錯

54從未排序序列中挑選元素，并將其依次插入已排序序列（初始時為空）的一端的方

法，稱為冒泡排序。［判斷題］*

對

錯（正確答案）

55簡單選擇排序的穩(wěn)定性與快速排序的穩(wěn)定性不一樣。［判斷題］*

對

錯（正確答案）

56動態(tài)查找表屬于樹形結(jié)構(gòu)，因為這里涉及二叉排序樹。［判斷題］*

對

錯（正確答案）

57哈希函數(shù)是一個映像。［判斷題］*

對（正確答案）