數(shù)據(jù)結(jié)構(gòu)棧、隊(duì)列、樹單元測試40題

數(shù)據(jù)結(jié)構(gòu)棧、隊(duì)列、樹單元測試40題

您的姓名：［填空題］*

L當(dāng)利用大小為n的數(shù)組順序存儲(chǔ)一個(gè)隊(duì)列時(shí)，該隊(duì)列的最大長度為()。［單選題］

*

A、n-2

B、n-1(正確答案)

C、n

D、n+l

2.設(shè)鏈棧中結(jié)點(diǎn)的結(jié)構(gòu)為(data,link),且top是指向棧頂?shù)闹羔?。若想在鏈棧?/p>

棧頂插入一個(gè)由指針s所指的結(jié)點(diǎn)，則應(yīng)執(zhí)行()操作。［單選題］*

A、top->link=s;

B、s->link=top->link;top->link=s;

C、s->link=top;top=s;

D、s->link=top;top=top->link;

3.設(shè)循環(huán)隊(duì)列的存儲(chǔ)空間為Q(l：m),初始狀態(tài)為front=rear=m?，F(xiàn)經(jīng)過一系列入隊(duì)

與退隊(duì)運(yùn)算后，front=2(),rear=15,現(xiàn)要在該循環(huán)隊(duì)列中尋找最小值的元素，最壞

情況下需要比較的次數(shù)為()o［單選題］*

A、m-6

B、m-5

C、6

D、5

4.設(shè)循環(huán)隊(duì)歹Ij的結(jié)構(gòu)是typedefstruct{DataTypedatafMaxSize］;intfront,rear;}

Queue;若有一個(gè)Queue類型的隊(duì)列Q,循環(huán)隊(duì)列少用一個(gè)元素空間，試問判斷隊(duì)

列滿的條件應(yīng)為()。［單選題］*

A、Q.front==Q.rear;

B、Q.front-Q.rear==MaxSize;

C、Q.front+Q.rear=MaxSize;

D、Q.front==(Q.rear+1)%MaxSize;假答案)

5.設(shè)有一個(gè)遞歸算法如下intfact(intn){if(n<=0)return1;elsereturnn*fact(n-

1);}則計(jì)算fact(n)需要函數(shù)內(nèi)部調(diào)用的次數(shù)為()次。［單選題］*

A、n(正確答案)

B、n+1

C、n+2

D、n-1

6.下列敘述正確的是()。［單選題］*

A、雙向鏈表是二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

B、非線性結(jié)構(gòu)只能采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

C、有的非線性結(jié)構(gòu)也可以采用順序存儲(chǔ)結(jié)構(gòu)

D、循環(huán)隊(duì)列屬于隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

7.按照“后進(jìn)先出”原則組織數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是()。［單選題］*

A、隊(duì)列

B、棧

C、雙向鏈表

D、二叉樹

8.遞歸調(diào)用時(shí)系統(tǒng)需要利用一個(gè)()來實(shí)現(xiàn)數(shù)據(jù)的傳遞和控制的轉(zhuǎn)移。［單選題］*

A、隊(duì)列

B、優(yōu)先級(jí)隊(duì)列

C、雙端隊(duì)列

D、棧（正確答案）

9.下列對(duì)隊(duì)列的敘述正確的是（）o［單選題］*

A、隊(duì)列屬于非線性表

B、隊(duì)列按“先進(jìn)后出”原則組織數(shù)據(jù)

C、隊(duì)列在隊(duì)尾刪除數(shù)據(jù)

D、隊(duì)列按“先進(jìn)先出”原則組織數(shù)據(jù)

1（）.下列關(guān)于棧的描述正確的是（）o［單選題］*

A、在棧中只能插入元素而不能刪除元素

B、在棧中只能刪除元素而不能插入元素

C、棧是特殊的線性表，只能在一端插入或刪除元素

D、棧是特殊的線性表，只能在一端插入元素，而在另一端刪除元素

11.下列數(shù)據(jù)結(jié)果中，能夠按照“先進(jìn)后出”原則存取數(shù)據(jù)的是（）。［單選題］*

A、循環(huán)隊(duì)列

B、棧（正確答案）

C、隊(duì)列

D、二叉樹

12.下列敘述中正確的是（）。［單選題］*

A、棧是一種先進(jìn)先出的線性表

B、隊(duì)列是一種后進(jìn)先出的線性表

C、棧和隊(duì)列都是非線性結(jié)構(gòu)

D、以上三種說法都不對(duì)

13.一個(gè)棧的初始狀態(tài)為空?，F(xiàn)將元素L2.3.45A.B.C.D.E依次入棧，然后再依次

出棧，則元素出棧的順序是（）o［單選題］*

A、12345ABCDE

B、EDCBA54321

C、ABCDE12345

D、54321EDCBA

14.當(dāng)利用大小為n的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top==n表示?？?，則向這個(gè)

棧插入一個(gè)元素時(shí)，首先應(yīng)執(zhí)行（）語句修改top指針。［單選題］*

A、top++;

B.top-;

C、top=0;

D、top;

15.假定一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列的隊(duì)頭和隊(duì)尾指針分別為front和rear,循環(huán)隊(duì)列

少用一個(gè)元素空間，則判斷隊(duì)空的條件為（）。［單選題］*

A、front+l==rear

B、rear+1==front

C、front==0

D、front==rear（正確答案）

16.若讓元素1,2,3依次進(jìn)棧，則出棧次序不可能出現(xiàn)（）種情況。［單選題］*

A、3,2,1

B、2,1,3

C、3,1,2

D、1,3,2

17.設(shè)循環(huán)隊(duì)歹（J的結(jié)構(gòu)是constintMaxSize=10（）;typedefintDataType;typedefstruct

{DataTypedatafMaxSize］;intfront,rear;}Queue;若有一個(gè)Queue類型的隊(duì)列Q,

循環(huán)隊(duì)列少用一個(gè)元素空間，則應(yīng)用（）表達(dá)式計(jì)算隊(duì)列元素的個(gè)數(shù)。［單選題］*

A、（Q.rear-Q.front+MaxSize）%MaxSize;

B、Q.rear-Q.front+1;

C、Q.rear-Q.front-1;

D、Q.rear-Qfront;

18.設(shè)棧的順序存儲(chǔ)空間為S（0:49）,棧底指針bottom=49,棧頂指針top=3（）（指向

棧頂元素），則棧中的元素個(gè)數(shù)是（）。［單選題］*

A、30

B、19

C、20

D、29

19.下列敘述正確的是（）o［單選題］*

A、帶鏈隊(duì)列的存儲(chǔ)空間可以不連續(xù)，且隊(duì)頭指針可以大于也可以小于隊(duì)尾指針

（正確答案）

B、帶鏈隊(duì)列的存儲(chǔ)空間可以不連續(xù)，但隊(duì)頭指針必須小于隊(duì)尾指針

C、帶鏈隊(duì)列的存儲(chǔ)空間可以不連續(xù)，但隊(duì)頭指針必須大于隊(duì)尾指針

20.下列敘述中正確的是（）。［單選題］*

A、循環(huán)隊(duì)列有隊(duì)頭和隊(duì)尾兩個(gè)指針，因此，循環(huán)隊(duì)列是非線性結(jié)構(gòu)

B、在循環(huán)隊(duì)列中，只需要隊(duì)頭指針就能反映隊(duì)列中元素的動(dòng)態(tài)變化情況

C、在循環(huán)隊(duì)列中，只需要隊(duì)尾指針就能反映隊(duì)列中元素的動(dòng)態(tài)變化情況

D、循環(huán)隊(duì)列中元素的個(gè)數(shù)是由隊(duì)頭指針和隊(duì)尾指針共同決定

21.下列敘述中正確的是（）o［單選題］*

A、循環(huán)鏈表是循環(huán)隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

B、棧與隊(duì)列都只能順序存儲(chǔ)

C、循環(huán)隊(duì)列是隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)

22.利用3,6,8,12這四個(gè)值作為葉子結(jié)點(diǎn)的權(quán)，生成一棵哈夫曼樹，該樹的帶權(quán)路

徑長度為（）。［單選題］*

A、55（正確答案）

B、29

C、58

D、38

23.某二叉樹的前序序列為ABCDEFG,中序序歹為DCBAEFG,該二叉樹的深度

（根結(jié)點(diǎn)在第1層）為（）o［單選題］*

A、4（正確答案）

B、2

C、3

D、5

24.某二叉樹共有7個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)只有1個(gè)，則該二叉樹的深度為（）

（假設(shè)根結(jié)點(diǎn)在第1層）。［單選題］*

A、3

B、4

C、6

D、7

25.一棵二叉樹中共有70個(gè)葉子結(jié)點(diǎn)與8（）個(gè)度為1的結(jié)點(diǎn)，則該二叉樹中的總結(jié)

點(diǎn)數(shù)為0o［單選題］*

A、219角答案）

B、221

C、229

D、231

26.在一棵高度為h+1的完全二叉樹中，所含結(jié)點(diǎn)個(gè)數(shù)不小于（）。［單選題］*

A、2的h-1次方

B、2的h+1次方

C、2的h次方-1

D、2的h次方

27.樹中所有結(jié)點(diǎn)的度之和等于所有結(jié)點(diǎn)數(shù)加（）。［單選題］*

A、0

B、1

C、

D、2

28.在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹的第i層上（假定根結(jié)點(diǎn)為第1層），最多具有（）個(gè)

結(jié)點(diǎn)。［單選題］*

A、2的i次方

B、2的i+1次方

C、2的i-l次方

D、2的n次方

29.在一棵樹中，（）沒有前驅(qū)結(jié)點(diǎn)。［單選題］*

A、樹枝結(jié)點(diǎn)

B、葉子結(jié)點(diǎn)

c、樹根結(jié)點(diǎn)正確答案）

D、空結(jié)點(diǎn)

30.在一棵完全二叉樹中，若編號(hào)為i的結(jié)點(diǎn)存在左孩子,則左孩子結(jié)點(diǎn)的編號(hào)為

（）。假定樹根結(jié)點(diǎn)的編號(hào)為1。［單選題］*

A、2i（正確答案）

B、2i-l

C、2i+l

D、2i+2

w

31.對(duì)如下二叉樹進(jìn)行后序遍歷的結(jié)果為（）o回LUL±J［單選題］

*

A、ABCDEF

B、DBEAFC

C、ABDECF

D、DEBFCA（正確答案）

F"

一

0

—Vn

S［

32.對(duì)下列二叉樹進(jìn)行中序遍歷的結(jié)果是（）。［單選題］

*

A、ACBDFEG：正今

B、ACBDFGE

C、ABDCGEF

D、FCADBEG

33.某二叉樹有5個(gè)度為2的結(jié)點(diǎn)，則該二叉樹中的葉子結(jié)點(diǎn)數(shù)是（）o［單選題］

*

A、10

B、8

C、6

D、4

34.某二叉樹中有n個(gè)葉子結(jié)點(diǎn)，則該二叉樹中度為2的結(jié)點(diǎn)數(shù)為（）。［單選題］

*

A、n/2

B、n+1

C、2n

D、n-1E確答案）

35.設(shè)某二叉樹的前序序列為ABC,中序序列為CBA,則該二叉樹的后序序列為

（）o［單選題］*

A、CAB

B、CBA

C、ABC

D、BCA

36.下列關(guān)于二叉樹的敘述中，正確的是（）。［單選題］*

A、葉子結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)少一個(gè)

B、葉子結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)多一個(gè)

c、葉子結(jié)點(diǎn)數(shù)是度為2的結(jié)點(diǎn)數(shù)的兩倍

D、度為2的結(jié)點(diǎn)數(shù)是度為1的結(jié)點(diǎn)數(shù)的兩倍

37.一棵具有35個(gè)結(jié)點(diǎn)的完全二叉樹的高度為（）。假定空樹的高度為-lo［單選題］

A、5

B、6

C、7

D、8

38.在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹中，所有結(jié)點(diǎn)的空子樹個(gè)數(shù)等于（）。［單選題］*

A、n

B、n