數(shù)據(jù)結(jié)構(gòu)與算法模擬試題六

數(shù)據(jù)結(jié)構(gòu)與算法模擬試題六

您的姓名：［填空題］*

L數(shù)據(jù)結(jié)構(gòu)與算法里，折半查找中，low指向低端的記錄，high指向高端的記錄，

每次計(jì)算中間位置mid的公式是()。［單選題］*

A.(low&high)/2

B.(low+high)/2(正確答案)

C.(low-high)/2

D.low/2+high/2

2.數(shù)據(jù)結(jié)構(gòu)與算法里，折半查找的時(shí)間復(fù)雜度是()o［單選題］*

A.O(l)

B.O(log2n)(正確答案)

C.O(n)

D.O(n*n)

3.數(shù)據(jù)結(jié)構(gòu)與算法里，哈希表的裝填因子()o［單選題］*

A.越大，發(fā)生沖突的可能越小

B.越小，發(fā)生沖突的可能越大

C.與是否發(fā)生沖突無(wú)關(guān)

D.越大，發(fā)生沖突的可能性越大勺答案)

4.數(shù)據(jù)結(jié)構(gòu)與算法里，排序前序列為：11101389間經(jīng)過一趟直接插入排序(按從

小到大排序)后的序列是0o［單選題］*

A.10111389(正確答案)

B.10118913

C.ll108913

D.891()1113

5.數(shù)據(jù)結(jié)構(gòu)與算法里，二叉排序樹的第5層多有多少個(gè)結(jié)點(diǎn)()。［單選題］*

A.4

B.16(正確答案)

C.8

D.32

6.數(shù)據(jù)結(jié)構(gòu)與算法里，就性能而言，希爾排序的時(shí)間復(fù)雜度是()o［單選題］*

A.O(n*n)

B.O(nlog2n)

C.O(n)

D.O(n3/2)(正確答案)

7.數(shù)據(jù)結(jié)構(gòu)與算法里，改進(jìn)的冒泡排序的任一趟排序過程中，如果沒有發(fā)生()，則

說明已經(jīng)有序；排序完畢()。［單選題］*

A.數(shù)據(jù)交換

B.數(shù)據(jù)刪除

C.數(shù)據(jù)刪除

D渚B不對(duì)

8.數(shù)據(jù)結(jié)構(gòu)里，二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以()。［單選題］*

A.它不能用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)

B.它不能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)

C.順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能存儲(chǔ)

D.順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都不能使用

9.某二叉樹的前序遍歷結(jié)果為ABCDEF,中序遍歷結(jié)果為CBAEDF,則該二叉樹的后

序遍歷的結(jié)果為（）o［單選題］*

A.CBEFDA

B.FEDCBA

C.CBEDFA

D.不定

10.有n個(gè)終端結(jié)點(diǎn)的哈夫曼樹的結(jié)點(diǎn)總數(shù)為（）。［單選題］*

A.2n

B.不確定

C.2n+1

D.2n-1（正確答案）

11.已知某完全二叉樹上有結(jié)點(diǎn)1001個(gè)，其中度為0的結(jié)點(diǎn)的個(gè)數(shù)是（）。［單選

題］*

A.250

B.都不對(duì)

C.500

D.505

12.若一棵二叉樹具有15個(gè)度為2的結(jié)點(diǎn)，8個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)

數(shù)是（）o［單選題1*

A.9

B.16（正確答案）

C.15

D.23

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

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

A.快速排序

B.冒泡排序

C.以上都不對(duì)

D.直接插入

14.循環(huán)隊(duì)列的最大容量M,隊(duì)頭f,隊(duì)尾r,用人為浪費(fèi)一個(gè)單元格區(qū)分空和滿，

隊(duì)滿的條件是（）。［單選題］*

A.（r+l）%M==f（正確答案）

B.r%M==f

C.（r-l）%M==f

D.（r+l）==f

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

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

B只能被1和它本身整除

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

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

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

A.N=a+b+c

B.N-l=a+b+c

C.N=a+b-c

D.N=a*b*c

17.數(shù)據(jù)結(jié)構(gòu)與算法里，inti,j;

for(i=l;i<=3;i++)

(

for(j=l；j<4;j++)

(

printf("*");

}

printf("\n");

}該程序輸出的圖形是()o［單選題］［單選題1*

A.三行四列的矩形方陣

B.三行三列的矩形方陣

C.三行的直角三角形

D.四行的直角三角形

18.數(shù)據(jù)結(jié)構(gòu)與算法里，以下不是回文字符串的是()。［單選題］*

A.aba

B.11811

C.abcabc(正確答案)

D.xyzyx

19.數(shù)據(jù)結(jié)構(gòu)與算法里，以下經(jīng)典著作中，哪本記載了最早的雞兔同籠問題()o

［單選題］*

A.孫子算經(jīng)

B.孫子兵法

C.九章算術(shù)

D.九章算經(jīng)

20.數(shù)據(jù)結(jié)構(gòu)與算法里，循環(huán)語(yǔ)句中加break的作用的是()。［單選題］*

A.break用于循環(huán)語(yǔ)句的作用是結(jié)束本層循環(huán)

B.break用于循環(huán)語(yǔ)句的作用是結(jié)束本次循環(huán)，繼續(xù)下一下循環(huán)

C.break不能用于switch語(yǔ)句

D.break語(yǔ)句不能用do-while語(yǔ)句開會(huì)

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

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

B.二叉排序樹的中序列是升序序列【正確答案?

C.二叉排序樹的左子樹也是二叉排序樹：再答案）

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

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

表中的序號(hào)）M0D11,若輸入順序?yàn)椋ā烦鋈嗽?乂。,1,10（；^）,采用內(nèi)散列表,處理沖

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

的是（）。*

A.4（正確答案）

B.3（正確答案）

C.20/9

D.23/9（正確答案）

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

0o*

A.O（n*log2n）

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

C.O（log2n）

D.O（n*n）悌答案）

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

A.希爾排序是不穩(wěn)定排序：答案）

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

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

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

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

A.冒泡排序

B.直接插入排序

C.折半查找

D.希爾排序

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

A.快速排序是不穩(wěn)定排序:正確答案）

B.快速排序的時(shí)間復(fù)雜度是O（nlog2n）。B確答案）

C.快速排序是一種交換排序（正確答案）

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

27.數(shù)據(jù)結(jié)構(gòu)與算法里，今有雉（雞）兔同籠，上有三十五頭，下有九十四足。問雉兔

各幾何？答案不正確的是（）o*

A.雞23兔12

B.雞12兔23

C.雞22兔13（正確答案）

D.雞13兔22正確答案）

28.數(shù)據(jù)結(jié)構(gòu)與算法里，漢諾塔算法描述正確的是（）。*

A.使用遞歸來(lái)完成算法：:確答案）

B.時(shí)間復(fù)雜度是0（2?）正確答案）

C.遞歸出口是盤子數(shù)量為1時(shí)

D.遞歸出口是盤子數(shù)量為1時(shí)

29.數(shù)據(jù)結(jié)構(gòu)與算法里，求兩個(gè)數(shù)的最大公約數(shù)，依照方式不同其時(shí)間復(fù)雜度可能

是（）。*

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

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

C.O（n*n）

D.O（l）

30.順序隊(duì)存儲(chǔ)在Q中，front是隊(duì)頭，rear是隊(duì)尾，rear總指向隊(duì)尾元素之后的空

間，用e接收出隊(duì)的元素，則出隊(duì)?wèi)?yīng)該記為：（）。*

A.e=Q[front];front++;

B.front++;e=Q[front];

C.Q[frontl=e;front++;

D.e=Q[fix）nt++];（正確答案）

31數(shù)據(jù)結(jié)構(gòu)與算法里，迭代算法的時(shí)間復(fù)雜度不可能是O（n）。[判斷題]*

對(duì)

錯(cuò)（正確答案）

32數(shù)據(jù)結(jié)構(gòu)與算法里，漢諾塔是一類遞歸的算法，也應(yīng)具有算法的可行性。[判斷

題]*

對(duì)

錯(cuò)

33數(shù)據(jù)結(jié)構(gòu)與算法里，字符數(shù)組可能沒有'\0’,但是字符串一定有‘\0'。[判斷題]*

對(duì)

錯(cuò)

34數(shù)據(jù)結(jié)構(gòu)與算法里，strcpy和strcat的返回值類型不一樣。［判斷題］*

對(duì)

錯(cuò)(正確答案)

35二叉排序樹的充要條件：二叉排序樹的任意結(jié)點(diǎn)的關(guān)鍵字都大于其左孩子的關(guān)

鍵字，且小于其右孩子的關(guān)鍵字。［判斷題］*

對(duì)

錯(cuò)(正確答案)

36動(dòng)態(tài)查找表屬于樹形結(jié)構(gòu)，因?yàn)檫@里涉及二叉排序樹。［判斷題］*

對(duì)

錯(cuò)(正確答案)

37荷蘭國(guó)旗算法的時(shí)間復(fù)雜度是0(n)。［判斷題］*

對(duì)

錯(cuò)

38小明的煩惱問題要用二維字符串?dāng)?shù)組存儲(chǔ)代表電話號(hào)碼的字母。［判斷題］*

對(duì)

錯(cuò)

39數(shù)據(jù)結(jié)構(gòu)與算法里，對(duì)不同的關(guān)鍵字可能得到同一哈希地址，即keyrkey2面

f(keyl)=f(key2)這種現(xiàn)象稱沖突(collision)。具有相同函數(shù)值的關(guān)鍵詞對(duì)該哈希函數(shù)

來(lái)說稱作同義詞。［判斷題］*

對(duì)

錯(cuò)

40.若輸入序列為1,2,3,4,5,6,則通過一個(gè)?？梢暂敵鲂蛄?25,6,3,1。［判斷題］*

對(duì)

錯(cuò)（正確答案）

1.以下算法中時(shí)間復(fù)雜度最高的是（）。［單選題］*

A:冒泡排序算法

B:順序表的插入算法

C:快速排序算法

D:漢諾塔問題算法

2.#include"windows.h"

voidtell_story（）

（

printf（"從前有座山，山上有座廟，廟里有一個(gè)老和尚和一個(gè)小和尚\(zhòng)n"）；

printf（"老和尚正在給小和尚講故事。講的是什么故事呢？他說:\n"）；

tell_story（）;

}

voidmain（）

（

tell_story（）;

}函數(shù)的這種調(diào)用方式屬于（）。［單選題］［單選題］*

A窮舉

B遞歸（正確答案）

C迭代

D分治

3.漢諾塔的算法使用遞歸算完成，那么遞歸是（）。［單選題］

A:嵌套調(diào)用的典型代表

B:函數(shù)自身調(diào)用自身的編程技巧

C:函數(shù)的普通調(diào)用

D:以上選項(xiàng)都不對(duì)

4.從算法的設(shè)計(jì)要求上講，漢諾塔應(yīng)具有（）。［單選題］*

A:有窮性

B:確定性

C:可行性

D:可讀性

5.對(duì)于漢諾塔問題，最早的來(lái)源于哪個(gè)國(guó)家（）。［單選題］*

A:古埃及

B:印度（正確答案）

C:波斯

D:羅馬帝國(guó)

6.n個(gè)盤子的漢諾塔問題，移動(dòng)步數(shù)是（）。［單選題］*

A:2的n次鬲減1

B:2*n-l

C:2*n+l

D:log2n

7.漢諾塔的算法是遞歸算法解決的，所謂遞歸即（）。［單選題］*

A:函數(shù)自身調(diào)用自身的編程技巧。（正確答案）

B:函數(shù)嵌套調(diào)用的方式

C:函數(shù)調(diào)用的普通方式

D:無(wú)參函數(shù)是不能使用遞歸的

8.break語(yǔ)句可以用于下列語(yǔ)法中的那個(gè)語(yǔ)法（）。［單選題］*

A:if-else

B:for（正確答案）

C:if

D:if-else—if

9.do{printf（"Tobeornottobeisaquestion\n"）;}while（3>=3）;對(duì)于本程序段描述正確

的是（）o［單選題］*

A:該程序是一個(gè)死循環(huán)程序

B:輸出一遍Tobeornottobeisaquestion

C:do-while是先判斷后執(zhí)行，條件成立繼續(xù)執(zhí)行循環(huán)體

D:該程序不能執(zhí)行，因?yàn)榈谝淮螚l件就不滿足

10.折紙算法是一種（）方法解決的問題。［單選題］*

A:迭代（正確答案）

B：窮舉

C:遞推

D:分治

11.漢諾塔問題的遞歸分為（）幾部分。*

A:遞歸前進(jìn)段

B:遞歸返回段

C:遞歸出口（正確答案）

D:遞歸問題

12.漢諾塔問題的求解方式不屬于以下哪類算法（）。*

A:窮舉（正確答案）

B:分治

C:遞歸

D:迭代（正確答案）

13.漢諾塔問題是算法的一種，因此具有算法的特性（）。*

A:有窮性（正確答案）

B:確定性（正確答案）

C:可行性（正確答案）

D:輸入、輸出

14.遞歸問題經(jīng)常使用棧幫助實(shí)現(xiàn)，棧的應(yīng)用有（）。*

A:八皇后問題

B:漢諾塔問題

C:迷宮問題

D:表達(dá)式求值問題

15.修公路問題算法：

voidmain（）

（

inth=l（）（）（）,count=0;

printf（"一條待修公路1000公里，每天修55公里，問多少天后還有不足60公里未

修?\n"）;

while（h>=60）

（

printf（"%d\t",h）;

（填空）；

count++；

printf（"\n總計(jì)需要％d天后還有不足60公里未修\n",count）;

｝則填空處可以填寫（）。［多選題］*

A:h-=55（正確答案）

B:h=h-55正確答案）

C:h=h*2

D:h*=2

16.蝸牛爬井問題和折紙問題是一類問題，都是可以用迭代法解決的。［判斷題］

對(duì)（正確答案）

錯(cuò)

17.漢諾塔算法具有可讀性，這是算法的特性之一。［判斷題］*

對(duì)

錯(cuò)（正確答案）

18.折紙超珠峰問題的時(shí)間復(fù)雜度是O（n*n）。［判斷題］*

對(duì)

錯(cuò)（正確答案）

19.漢諾塔問題的時(shí)間復(fù)雜度上講，應(yīng)為O（2M）（人表示鬲）。［判斷題］*

對(duì)（正確答案）

錯(cuò)

20.漢諾塔問題的求解方式，是用分治算法，一步一步計(jì)算而得的。［判斷題］*

對(duì)

錯(cuò)（正確答案）

1.下面程序執(zhí)行后的結(jié)果是0

#include"stdio.hn

voidmain()

intarr[4][4]={{2,2,3,4},{5,6,7,8},{9,10,ll,12},{13,14,15,15}),i,sum=0;

for(i=0;i<4;i++)

(

sum=sum+arr[i][i];

)

printf("%d",sum);

}o[單選題][單選題]*

A28

B34(正確答案)

C40

D10

2.已知二維數(shù)組inta[3][3]={l,2,7,4,10,6,3,8,9};printf("%d",a[l][l]);則程序輸出的結(jié)

果是(C)。[單選題][單選題]*

占位不用管

A:1

B:2

C:10(正確答案)

D:7

3.字符串處理函數(shù)是字符串連接的是()。[單選題]*

A:strcat

B:strcpy

C:strcmp

D:strlen

4.回文字符串存與字符數(shù)組中，若求字符串的長(zhǎng)度可以使用函數(shù)（）o［單選題］*

A:strlen

B:strcat

C:strcpy

D:strcmp

5.strcat的參數(shù)個(gè)數(shù)是（）o［單選題］*

A:2（正確答案）

B:1

C:3

D:4

6.回文字符串之非遞歸循環(huán)解決方案，設(shè)置flag標(biāo)志位的作用是（）。［單選題］*

A:保存：判定是否存在這樣的一對(duì)第i個(gè)字符與倒數(shù)第i個(gè)字符不等的情況

答案）

B:沒有關(guān)鍵性作用

C:標(biāo)志位不可以賦值為0、1以外的數(shù)。

D:標(biāo)志位flag的作用是判斷回文字符串的長(zhǎng)度的

7.chars［100］="abc";則執(zhí)行strcpy（s,streams,"123"））;后s的結(jié)果是（）。［單選題］*

A:abc123A答案）

B:123abc

C:abc

D:123

8.字符串處理函數(shù)是字符串比較的是（）。［單選題］*

A:strcat

B:strcpy

C:strcmp

D:strlen

9.計(jì)算字符串的長(zhǎng)度的函數(shù)是（）。[單選題]*

A:strcpy

B:strcat

C:strcmp

D:strlen

10.若有說明:inta[3][4];,則對(duì)a數(shù)組元素的非法引用是:（）。[單選題]*

A:a[0][2*l]

B：a[l][3]

C:a[4-2][0]

D:a[0][4],E確答案）

11.在C語(yǔ)言中，系統(tǒng)函數(shù)strcmp的返回值類型不是（）。*

A:int

B:char（正確答案）

C:char*

D:floatE確答案）

12.荷蘭國(guó)旗的算法使用的到的技術(shù)有（）o*

A:循環(huán)

B:分支判斷

C:一維數(shù)組（正確答案）

D:循環(huán)嵌套

13.以下是回文字符串的是（）。*

A:aba

B:11811E確答案）

C:abcabc

D:xyzyx

14.回文字符串的判斷可以使用的方法有（）。*

A:遞歸方式（正確答案）

B:非遞歸方式利用循環(huán)解決

C:非遞歸方式用系統(tǒng)函數(shù)解決

D:以上答案都正確與答案）

15.以下字符串中，是回文字符串的是（）。*

A:abcba

B:12321（正確答案）

C:1221（正確答案）

D:abcdef

16.荷蘭國(guó)旗算法的基本寫法循環(huán)中套分支結(jié)構(gòu)。［判斷題］*

對(duì)

錯(cuò)

17.C語(yǔ)言中，數(shù)組是具有不相同數(shù)據(jù)類型的有序集合。［判斷題］*

對(duì)

錯(cuò)（正確答案）

18.如有定義inta⑵⑶;則數(shù)組a的最后一個(gè)元素為a［ll［2］o［判斷題］*

對(duì)（正國(guó)

錯(cuò)

19.在C語(yǔ)言中，實(shí)現(xiàn)求字符串長(zhǎng)度的函數(shù)是strlen()。［判斷題］*

對(duì)(正確答案)

錯(cuò)

20.引用數(shù)組元素時(shí)，其數(shù)組下標(biāo)的數(shù)據(jù)類型允許的是：整型常量或整型表達(dá)式。

［判斷題］*

對(duì)(正確答案)

錯(cuò)

L數(shù)據(jù)結(jié)構(gòu)與算法內(nèi)，從時(shí)間復(fù)雜度的角度來(lái)看，快速排序的時(shí)間復(fù)雜度是0o

［單選題］*

A:O(n*n)

B:O(nlog2n)(正確答案)

C:0(1)

D:都不對(duì)

2.荷蘭國(guó)旗問題，需要使用一維數(shù)組存儲(chǔ)(),1,2；那么一維數(shù)組的元素在內(nèi)存中

()o［單選題］*

A:占有一片連續(xù)的存儲(chǔ)空間

B:是不連續(xù)的存儲(chǔ)空間

C:可能是連續(xù)的也可能是不連續(xù)的

D:都不對(duì)

3.以下英文字符串中是回文字符串的是()o［單選題］*

A:aabbaa

B:aabbccdd

C:ABCABC

D:AABBB

4.數(shù)據(jù)結(jié)構(gòu)與算法內(nèi)，哈希表的裝填因子()o［單選題］*

A:越大，發(fā)生沖突的可能越小

B:越小，發(fā)生沖突的可能越大

C:與是否發(fā)生沖突無(wú)關(guān)

D:越大，發(fā)生沖突的可能性越大;正確答案)

5.數(shù)據(jù)結(jié)構(gòu)與算法內(nèi)，折半查找的時(shí)間復(fù)雜度是()o［單選題］*

A:0(1)

B:O(log2n)

C:0(n*n)

D:O(n)

6.雞與兔共有100只，雞腳比兔腳多80只，問雞有()只。［單選題］*

A:80(正確答案)

B:75

C:70

D:65

7.15和10的最小公倍數(shù)是()o［單選題］*

A:10

B:15

C:150

D:3()

8.完數(shù)又稱完美數(shù)，下面的整數(shù)中是完數(shù)的是()o［單選題］

A:28皤答案）

B