國家二級(jí)公共基礎(chǔ)知識(shí)（數(shù)據(jù)結(jié)構(gòu)與算

法）模擬試卷2（共9套）

（共315題）

國家二級(jí)公共基礎(chǔ)知識(shí)（數(shù)據(jù)結(jié)構(gòu)與算

法）模擬試卷第1套

一、單項(xiàng)選擇題（本題共37題，每題，,0分，共37

分。）

1、下列敘述中正確的是

A、循環(huán)隊(duì)列中的元素個(gè)數(shù)隨隊(duì)頭指針與隊(duì)尾指針的變化而動(dòng)態(tài)變化

B、循環(huán)隊(duì)列中的元素個(gè)數(shù)隨隊(duì)頭指針的變化而動(dòng)態(tài)變化

C、循環(huán)隊(duì)列中的元素個(gè)數(shù)隨隊(duì)尾指針的變化而動(dòng)態(tài)變化

D、循環(huán)隊(duì)列中的元素個(gè)數(shù)不會(huì)變化

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析：所謂循環(huán)結(jié)構(gòu)就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置

上，形成邏輯上的環(huán)狀空間，循環(huán)使用。在循環(huán)隊(duì)列中，用隊(duì)尾指針rear指向隊(duì)

列中的隊(duì)尾元素，用隊(duì)頭指針front指向隊(duì)頭元素的前一個(gè)位置，因此，隊(duì)列中的

元素?cái)?shù)等于從隊(duì)頭指針front指向的后一個(gè)位置與隊(duì)尾指針rear指向位置之間的元

素?cái)?shù)量。

2、下列關(guān)于線性鏈表的敘述中，正確的是

A、各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)空間可以不連續(xù)，但它們的存儲(chǔ)順序與邏輯順序必須一致

B、各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與邏輯順序可以不一致，但它們的存儲(chǔ)空間必須連續(xù)

C、進(jìn)行插入與刪除時(shí)，不需要移動(dòng)表中的元素

D、以上都不正確

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，存儲(chǔ)數(shù)據(jù)

結(jié)構(gòu)的存儲(chǔ)空間可以不連續(xù)，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與數(shù)據(jù)元素之間的邏輯關(guān)系可

以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的。

3、下列敘述中正確的是

A、線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)空間一般要少于順序存儲(chǔ)結(jié)構(gòu)

B、線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)空間都是連續(xù)的

C、線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)空間可以是連續(xù)的，也可以是不連續(xù)的

D、以上都不正確

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：線性表的存儲(chǔ)分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。在順序存儲(chǔ)中，所有元素所

占的存儲(chǔ)空間是連續(xù)的。而在鏈?zhǔn)酱鎯?chǔ)的方式中，將存儲(chǔ)空間的每一個(gè)存儲(chǔ)結(jié)點(diǎn)分

為兩部分，一部分用于存儲(chǔ)數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分用于存儲(chǔ)下一個(gè)

元素的存儲(chǔ)序號(hào)，稱為指針域。所以線性表的鏈?zhǔn)酱鎯?chǔ)方式比順序存儲(chǔ)方式的存儲(chǔ)

空間要大一些。

4、下列敘述中正確的是

A、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間是相同的

B、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間一般要多于順序存儲(chǔ)結(jié)構(gòu)

C、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間一般要少于順序存儲(chǔ)結(jié)構(gòu)

D、以上都不正確

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：線性表的存儲(chǔ)分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。在順序存儲(chǔ)中，所有兀素所

占的存儲(chǔ)空間是連續(xù)的。而在鏈?zhǔn)酱鎯?chǔ)的方式中，將存儲(chǔ)空間的每一個(gè)存儲(chǔ)結(jié)煮分

為兩部分，一部分用于存儲(chǔ)數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分用于存儲(chǔ)下一個(gè)

元素的存儲(chǔ)序號(hào)，稱為由針域。所以線性表的鏈?zhǔn)酱鎯?chǔ)方式比順序存儲(chǔ)方式的存儲(chǔ)

空間耍大一些。

5、下列敘述中正確的是

A、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間是相同的

B、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間一般要多于順序存儲(chǔ)結(jié)構(gòu)

C、線忤表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間一般要少于順序存儲(chǔ)結(jié)構(gòu)

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

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：線性表的存儲(chǔ)分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。在順序存儲(chǔ)中，所有元素所

占的存儲(chǔ)空間是連續(xù)的，各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。所以

每個(gè)元素只存儲(chǔ)其值就可以了，而在鏈?zhǔn)酱鎯?chǔ)的方式中，將存儲(chǔ)空間的每一個(gè)存儲(chǔ)

結(jié)點(diǎn)分為兩部分，一部分用于存儲(chǔ)數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分用于存儲(chǔ)

下一個(gè)元素的存儲(chǔ)序號(hào)，稱為指針域。所以線性表的鏈?zhǔn)酱鎯?chǔ)方式比順序存儲(chǔ)方式

的存儲(chǔ)空間要大一些。

6、下列對(duì)于線性鏈表的描述中正確的是

A、存儲(chǔ)空間不一定連續(xù)，且各元素的存儲(chǔ)順序是任意的

B、存儲(chǔ)空間不一定連續(xù)，且前件元素一定存儲(chǔ)在后件元素的前面

C、存儲(chǔ)空間必須連續(xù)，且前件元素一定存儲(chǔ)在后件元素的前面

D、存儲(chǔ)空間必須連續(xù)，且各元素的存儲(chǔ)順序是任意的

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析：一般來說，在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)序號(hào)是不

連續(xù)的，并且各結(jié)點(diǎn)在存儲(chǔ)空間中的位置關(guān)系與邏輯關(guān)系也不一致。在線性鏈表

中，各數(shù)據(jù)元素之間的前后件關(guān)系是由各結(jié)點(diǎn)的指針域來指示的，指向線性表中第

一個(gè)結(jié)點(diǎn)的指針head稱為頭指針，當(dāng)head二NULL（或0）時(shí)稱為空表。

7、下列敘述中正確的是

A、順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)一定是連續(xù)的，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)空間不一定是連續(xù)的

B、順序存儲(chǔ)結(jié)構(gòu)只針對(duì)線性結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)只針對(duì)非線性結(jié)構(gòu)

C、順序存儲(chǔ)結(jié)構(gòu)能存儲(chǔ)有序表，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不能存儲(chǔ)有序表

D、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)比順序存儲(chǔ)結(jié)構(gòu)節(jié)省存儲(chǔ)空間

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析：順序存儲(chǔ)方式主要用于線性的數(shù)據(jù)結(jié)構(gòu)，它把邏輯上相鄰的數(shù)據(jù)元素

存儲(chǔ)在物理上相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)之間的關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來體現(xiàn)。

而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)空間不一定是連續(xù)的。

8、下列鏈表中，其邏輯結(jié)構(gòu)屬于非線性結(jié)構(gòu)的是

A、二叉鏈表

B、循環(huán)鏈表

C^雙向鏈表

D、帶鏈的棧

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析：二叉鏈表作為樹的存儲(chǔ)結(jié)構(gòu)。鏈表中結(jié)點(diǎn)的兩個(gè)鏈域分別指向該結(jié)點(diǎn)

的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)。

9、下列敘述中正確的是

A、有?一個(gè)以上根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)不一定是非線性結(jié)構(gòu)

B、只有一個(gè)根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)不一定是線性結(jié)構(gòu)

C、循環(huán)鏈表是非線性結(jié)構(gòu)

D、雙向鏈表是非線性結(jié)構(gòu)

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：在數(shù)據(jù)結(jié)溝中，樹這類的的數(shù)據(jù)結(jié)構(gòu)只有一個(gè)根結(jié)點(diǎn)，但它不是線性

結(jié)構(gòu)。

10、某系統(tǒng)總體結(jié)構(gòu)圖如下圖所示:該系統(tǒng)總體

結(jié)構(gòu)圖的深度是

A、7

B、6

C、3

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

點(diǎn)數(shù)為

A、219

B、229

C、230

D、231

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：根據(jù)二叉樹的性質(zhì)，在任意二叉樹中，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總

是比度為2的結(jié)點(diǎn)多一個(gè)，故總結(jié)點(diǎn)數(shù)=葉子節(jié)點(diǎn)數(shù)+度為2的節(jié)點(diǎn)數(shù)+度為1的節(jié)

點(diǎn)數(shù)=80+79+70=229。

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

點(diǎn)數(shù)為

A、219

B、221

C、229

D、231

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析：在二叉樹中，葉子結(jié)點(diǎn)個(gè)數(shù)為no，則度為2的結(jié)點(diǎn)數(shù)n2二no—I。本

題中葉子結(jié)點(diǎn)的個(gè)數(shù)為70,所以度為2的結(jié)點(diǎn)個(gè)數(shù)為69,因而總結(jié)點(diǎn)數(shù)=葉子結(jié)

點(diǎn)數(shù)+度為1的結(jié)點(diǎn)數(shù)十度為2的結(jié)點(diǎn)數(shù)=70+80+69=219。

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

根結(jié)點(diǎn)在第1層）

A、3

B、4

C、6

D,7

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：根據(jù)二叉樹的性質(zhì)，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)

多一個(gè)。題目中的二叉堿的葉子結(jié)點(diǎn)為1,因此度為2的結(jié)點(diǎn)的數(shù)目為0,故該二

叉樹為7層，每層只有一個(gè)結(jié)點(diǎn)。

18、某二叉樹共有12個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)只有1個(gè)。則該二叉樹的深度為（根結(jié)

點(diǎn)在第1層）

A、3

B、6

C、8

D、12

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：根據(jù)二叉樹的性質(zhì)，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)

多一個(gè)。題目中的二叉樹的葉子結(jié)點(diǎn)為1,因此度為2的結(jié)點(diǎn)的數(shù)目為0,故該二

叉樹為12層，每層只有一個(gè)結(jié)點(diǎn)。

19、設(shè)二叉樹T的深度為4,其中度為1,2,3,4的結(jié)點(diǎn)個(gè)數(shù)分別為4,2,1,1。則

T中的葉子結(jié)點(diǎn)數(shù)為

A、8

B、7

C、6

D、5

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：深度為m二叉樹其總結(jié)點(diǎn)數(shù)為2nLi=24一1=15?？偨Y(jié)點(diǎn)數(shù)減去度為

1,2,3,4的結(jié)點(diǎn)個(gè)數(shù)就是葉子結(jié)點(diǎn)數(shù)。15—4-2—1—1二7。

20、設(shè)一棵完全二叉樹共有700個(gè)結(jié)點(diǎn)，則此二叉樹中的葉子結(jié)點(diǎn)數(shù)為

A、85

B、120

C、250

D、350

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：①具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為[k）g2n]+l,計(jì)算出該完全二

叉樹的深度為10。②設(shè)度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）為no，度為1的結(jié)點(diǎn)為2，度

為2的結(jié)點(diǎn)為總結(jié)點(diǎn)數(shù)為n,深度為k。n=m+n2+no,由于n（）=n2+1則【12=n（）-

1,故n=ni+no?l+no=ni+2no?l。由于完全二叉樹中度為1的結(jié)點(diǎn)數(shù)只有兩種可能:

0或1。⑧假設(shè)度為1的結(jié)點(diǎn)數(shù)為0即滿二叉樹，根據(jù)滿二叉樹的定義，其291個(gè)

結(jié)點(diǎn)，根據(jù)以上計(jì)算所得的深度10來計(jì)算，應(yīng)有21°-1=1024-1=1023個(gè)結(jié)點(diǎn)，顯然

與題目中700個(gè)結(jié)點(diǎn)不符。因此，度為1的結(jié)點(diǎn)數(shù)必然為1。故門二小十2。。-

l=l+2no-l=2no?則no=n/2=700/2=350。

21、在深度為7的滿二叉樹中，葉子結(jié)點(diǎn)的個(gè)數(shù)為

A、32

B、31

C、64

D、63

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析?：所謂滿二叉樹是指這樣的一種二叉樹：除最后一層外，每一層上的所

有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。也就是在滿二叉樹中，每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)

數(shù)，即在滿二叉樹的第k層上有21個(gè)結(jié)點(diǎn)，且深度為m的滿二叉樹有2叫1個(gè)結(jié)

點(diǎn)。對(duì)于深度為7的滿二叉樹，葉子結(jié)點(diǎn)所在的是第7層，一共有27-匕64個(gè)葉子

結(jié)點(diǎn)。全部結(jié)點(diǎn)共27-1=127個(gè)。

22、對(duì)下列二叉樹進(jìn)行前序遍歷的結(jié)果是

A、DYBEAFCZX

B、YDEBFZXCA

C、ABDYECFXZ

D、ABCDEFXYZ

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：二叉樹前序遍歷的簡單描述：若二叉樹為空，則結(jié)束返回；否則：

①訪問根結(jié)點(diǎn)；②前序遍歷左子樹：③前序遍歷石子樹?？梢姡靶虮闅v二叉樹

的過程是一個(gè)遞歸的過程。根據(jù)題目中給出的二叉樹的結(jié)構(gòu)可知前序遍歷的結(jié)果是

ABDYECFXZo

23、對(duì)如下二叉樹進(jìn)行后序遍歷的結(jié)果為

A、ABCDEF

B、DBEAFC

C、ABDECF

D、DEBFCA

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：所謂后序遍歷是指在訪問根據(jù)結(jié)點(diǎn)、遍歷左子樹與遍歷右子樹這三者

中，首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點(diǎn)，并旦，在遍歷左、右子

樹時(shí)，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根點(diǎn)。因此，后序遍歷二叉

樹的過程也是一個(gè)遞歸過程。其簡單描述為：若二叉樹為空，則結(jié)束返回；否則，

先后序遍歷左子樹，然后后序遍歷右子樹，最后訪問根結(jié)點(diǎn)。對(duì)于后序遍歷，第一

個(gè)訪問的結(jié)點(diǎn)一定是最左下的結(jié)點(diǎn)，最后一個(gè)訪問的結(jié)點(diǎn)一定是根結(jié)點(diǎn)，所以選項(xiàng)

D）為正確答案。

24、對(duì)長度為n的線性表進(jìn)行順序查找，在最壞情況下所需要的比較次數(shù)為

A、log2n

R、n/2

C、n

D、n+1

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：在進(jìn)行順序查找過程中，如果被查的元素是線性表中的最后一個(gè)元

素，或者被查元素根本不在線性表中，則為了查找這個(gè)元素需要與線性表中的所有

元素進(jìn)行比較，這是順序查找的最壞情況，需要比較的次數(shù)為n次。

25、在長度為64的有序線性表中進(jìn)行順序查找，最壞情況下需要比較的次數(shù)為

A、63

B、64

C、6

D、7

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：順序查找又稱順序搜索。順序查找一般是指在線性表中杳找指定的元

素，其基本方法是：從線性表的第一元素開始，依次將線性表中的元素與被查找的

元素進(jìn)行比較，若相等則表示找到(即查找成功)，若線性表中所有元素都與被查元

素進(jìn)行了比較但都不相等，則表示線性表中沒有要找的元素(即查找失敗)。如果線

性表中的第一個(gè)元素就是要查找的元素，則只需要做一次比較就查找成功：但如果

要查找的元素是線性表中的最后一個(gè)元素，或者要查找元素不在線性表中，則需要

與線性表中所有元素進(jìn)行比較，這是順序杳找的最壞情況，比較次數(shù)為線性表的長

度。

26、下列敘述中正確的是

A、對(duì)長度為n的有序鏈表進(jìn)行查找，最壞情況下需要的比較次數(shù)為n

B、對(duì)長度為n的有序鏈表進(jìn)行對(duì)分查找，最壞情況下需要的比較次數(shù)為(n/2)

C、對(duì)長度為n的有序鏈表進(jìn)行對(duì)分查找，最壞情況下需要的比較次數(shù)為(log2n)

D、對(duì)長度為n的有序鏈表進(jìn)行對(duì)分查找，最壞情況下需要的比較次數(shù)為(nlog2n)

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析：本題主要考查的知識(shí)點(diǎn)為查找技術(shù)。順序查找的使用情況：①線性

表為無序表；②表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。二分法查找只適用于順序存儲(chǔ)的有序表，

并不適用于線性鏈表。

27、在長度為n的有序線性表中進(jìn)行二分查找，最壞情況下需要比較的次數(shù)是

A、0(n)

B、0(/)

C、O(log2n)

D、O(nlog2n)

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：對(duì)于長度為n的有序線性表，在最壞情況下，二分法查找只需比較

log2n次，而順序查找需要比較n次。

28、下列數(shù)據(jù)結(jié)構(gòu)中，能用二分法進(jìn)行查找的是

A、順序存儲(chǔ)的有序線性表

B、線性鏈表

C、二叉鏈表

D、有序線性鏈表

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析：二分法查找只適應(yīng)于順序存儲(chǔ)的有序表。有序表是指線性表中的元素

按值非遞減排序(即從小到大，但允許相鄰元素值相等)的表。

29、冒泡排序在最壞情況下的比較次數(shù)是

A、n(n+l)/2

nlog2n

C、n(n-l)/2

D、n/2

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：對(duì)n個(gè)結(jié)點(diǎn)的線性表采用冒泡排序，在最壞情況下，冒泡排序需要經(jīng)

過n/2遍的從前往后的掃描和n/2遍的從后往前的掃描，需要的比較次數(shù)為

n(n-1)/2o

30、對(duì)長度為10的線性表進(jìn)行冒泡排序，最壞情況下需要比較的次數(shù)為

A、9

B、10

C、45

D、90

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：線性表的長度為n,最壞情況下冒泡排序需要比較的次數(shù)為n(n-l)/

2o

31、對(duì)于長度為n的線性表，在最壞情況下，下列各排序法所對(duì)應(yīng)的比較次數(shù)中正

確的是

A、冒泡排序?yàn)閚/2

B、冒泡排序?yàn)閚

C、快速排序?yàn)閚

D、快速排序?yàn)閚(n-l)/2

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：假設(shè)線性表的長度為n,則在最壞情況下，冒泡排序需要經(jīng)過n/2

遍的從前往后的掃描和n/2遍的從后往前的掃描，需要的比較次數(shù)為n(n-l)/2。

快速排序法也是一種互疾類的排序方法，但由于它比冒泡排序法的速度快，因此，

稱為快速排序法。

32、對(duì)長度為n的線性表作快速排序，在最壞情況卜，比較次數(shù)為

A、n

B、n—1

C、n(n―1)

D、n(n-1)/2

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：假設(shè)線性表的長度為n,則在最壞情況下，冒泡排序需要經(jīng)過n/2

遍的從前往后的掃描和n/2遍的從后往前的掃描，需要的比較次數(shù)為n(n-l)/2?？?/p>

速排序法也是一種互換類的排序方法，但由于它比冒泡排序法的速度快，因此，稱

為快速排序法。

33、對(duì)長度為n的線性表排序，在最壞情況下，比較次數(shù)不是n(n-l)/2的排序方

法是

A、快速排序

B、冒泡排序

C、直接插入排序

D、堆排序

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：各種排序方法中最壞情況下需要比較的次數(shù)分別為：冒泡排序一

1)/2、快速排序n(n-l)/2、簡單插入排序n(n-l)/2、希爾排序0(，$)、簡單選擇

排序n(n-l)/2、堆排序O(nlog2n)o

34、下列排序方法中，最壞情況下比較次數(shù)最少的是

A、冒泡排序

B、簡單選擇排序

C、直接插入排序

D、堆排序

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：冒泡排序、簡單選擇排序和直接插入排序法在最壞的情況下比較次數(shù)

為：n(n—1)/2。而堆排序法在最壞的情況下需要比較的次數(shù)為O(nlog2n)。其中

堆排序的比較次數(shù)最少。

35、下列數(shù)據(jù)結(jié)構(gòu)中，不能采用順序存儲(chǔ)結(jié)構(gòu)的是

A^棧

B、堆

C、隊(duì)列

D、非完全二叉樹

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：堆中某個(gè)結(jié)點(diǎn)的值總是不大于或不小于其父結(jié)點(diǎn)的值、堆總是一棵完

全二叉樹，可以以順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)；隊(duì)列的存儲(chǔ)結(jié)構(gòu)分為鏈?zhǔn)酱鎯?chǔ)、順序存儲(chǔ)兩

種；棧作為一種數(shù)據(jù)結(jié)溝，是一種只能在一端進(jìn)行插入和刪除操作的特殊線性表，

可以以順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)c

36、設(shè)二義樹共有375個(gè)結(jié)點(diǎn)，其中度為2的結(jié)點(diǎn)有187個(gè)。則度為1的結(jié)點(diǎn)個(gè)數(shù)

是

A、0

B、1

C、188

D、不可能有這樣的二叉樹

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析：二叉樹的每個(gè)結(jié)點(diǎn)至多只有二棵子樹（不存在度大于2的結(jié)點(diǎn)），二叉

樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有個(gè)結(jié)點(diǎn)；深度為

k的二叉樹至多有個(gè)結(jié)點(diǎn)；對(duì)任何一棵二叉樹T,如果其終端結(jié)點(diǎn)數(shù)為no,度

為2的結(jié)點(diǎn)數(shù)為112，則no=n2+l。本題中，度為2的結(jié)點(diǎn)有187個(gè)，葉子結(jié)點(diǎn)應(yīng)該

有187+1=188個(gè)，度為1的結(jié)點(diǎn)個(gè)數(shù)=375—187-188=0。

37、在帶鏈隊(duì)列中，經(jīng)過一系列正常的操作后，如果front=rcar,則隊(duì)列中的元素

個(gè)數(shù)為

A、0或1

B、0

C、1

D、隊(duì)列滿

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析：隊(duì)列是一種特殊的線性表，特殊之處在于它只允許在表的前端（舶nt）

進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作，和棧一樣，隊(duì)列是一種操作受

限制的線性表。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。隊(duì)列的

鏈?zhǔn)酱鎯?chǔ)也稱為鏈隊(duì)列。為了便于操作，可給鏈隊(duì)列添加1個(gè)頭結(jié)點(diǎn)，并令頭指針

指向頭結(jié)點(diǎn)。隊(duì)列為空的判斷條件是頭指針和尾指針的值相同，且均指向頭結(jié)點(diǎn)。

當(dāng)隊(duì)列為空（0）或1時(shí)，front=rear。

國家二級(jí)公共基礎(chǔ)知識(shí)（數(shù)據(jù)結(jié)構(gòu)與算

法）模擬試卷第2套

一、單項(xiàng)選擇題（本題共30題，每題1.0分，共30

分。）

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

入隊(duì)與退隊(duì)運(yùn)算后，from=15,rear=15,則循環(huán)隊(duì)列中的元素個(gè)數(shù)為

A、15

B、16

C、20

D、0或35

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：循環(huán)隊(duì)列的隊(duì)頭指針和尾指針都等于15,此循環(huán)隊(duì)列中元素的個(gè)數(shù)

有兩種情況，第一種情況是隊(duì)頭指針和尾指針都是第一次到達(dá)15,此時(shí)元素個(gè)數(shù)

為0；第二種情況是隊(duì)頭指針第一次到達(dá)15,而尾指針第二次到達(dá)15,此時(shí)元素

個(gè)數(shù)為35。

2、在一個(gè)容量為15的循環(huán)隊(duì)列中，若頭指針fronl=6,尾指針rear=9,則循環(huán)隊(duì)

列中的元素個(gè)數(shù)為

A、2

B、3

C、4

D、5

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：循號(hào)隊(duì)列中，rear表示尾指針，front表示頭指針，當(dāng)有元素入隊(duì)時(shí)，

rear=rear+1,而元素出隊(duì)的時(shí)候，front=front+l,當(dāng)rear值大于front值時(shí)，隊(duì)列中

的元素個(gè)數(shù)為rear-front,當(dāng)rear的值小于front時(shí)，列隊(duì)中的元素個(gè)數(shù)為rear-

front+m（m表示隊(duì)列的容量）。

3、下列敘述中正確的是

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

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

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

D、棧與隊(duì)列都是線性結(jié)構(gòu)

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：棧是先進(jìn)后出，隊(duì)列是先進(jìn)先出。棧和隊(duì)列都是一種線性表，屬于線

性結(jié)構(gòu)。

4、下列敘述中正確的是

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

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

C、循環(huán)隊(duì)列是非線性結(jié)構(gòu)

D、有序線性表既可以采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：棧是“先進(jìn)后出”，隊(duì)列”是先進(jìn)先出L棧和隊(duì)列都是一種線性表，屬

于線性結(jié)構(gòu)。有序線性表既可以采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。采

用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表稱之為線性鏈表。

5、下列與隊(duì)列結(jié)構(gòu)有關(guān)聯(lián)的是

A、函數(shù)的遞歸調(diào)用

B、數(shù)組元素的引用

C、多重循環(huán)的執(zhí)行

D、先到先服務(wù)的作業(yè)調(diào)度

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：隊(duì)列中最先插入的元素將最先被刪除，最后插入的元素將最后被刪

除。

6、下列敘述中正確的是

A、循環(huán)隊(duì)列中的元素個(gè)數(shù)隨隊(duì)頭指針與隊(duì)尾指針的變化而動(dòng)態(tài)變化

B、循環(huán)隊(duì)列中的元素個(gè)數(shù)隨隊(duì)頭指針的變化而動(dòng)態(tài)變化

C、循環(huán)隊(duì)列中的元素個(gè)數(shù)隨隊(duì)尾指針的變化而動(dòng)態(tài)變化

D、循環(huán)隊(duì)列中的元素個(gè)數(shù)不會(huì)變化

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析：所謂循環(huán)結(jié)構(gòu)就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到笫一個(gè)位置

上，形成邏輯上的環(huán)狀空間，循環(huán)使用。在循環(huán)隊(duì)列中，用隊(duì)尾指針rear指向隊(duì)

列中的隊(duì)尾元素，用隊(duì)頭指針fron1指向隊(duì)頭元素的前一個(gè)位置，因此，隊(duì)列中的

元素?cái)?shù)等于從隊(duì)頭指針front指向的后一個(gè)位置與隊(duì)尾指針rear指向位置之間的元

素?cái)?shù)量。

7、下列關(guān)于線性鏈表的敘述中，正確的是

A、各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)空間可以不連續(xù)，但它們的存儲(chǔ)順序與邏輯順序必須一致

B、各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與邏輯順序可以不一致，但它們的存儲(chǔ)空間必須連續(xù)

C、進(jìn)行插入與刪除時(shí)，不需要移動(dòng)表中的元素

D、以上都不正確

標(biāo)準(zhǔn)答案：c

知識(shí)點(diǎn)謁析：線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，存儲(chǔ)數(shù)據(jù)

結(jié)構(gòu)的存儲(chǔ)卒間可以不連續(xù)，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與數(shù)據(jù)元素之間的邏輯關(guān)系可

以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的。

8、下列敘述中正確的是

A、線性表鏈武存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)空間?般要少于順序存儲(chǔ)結(jié)構(gòu)

B、線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)空間都是連續(xù)的

C、線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)空間可以是連續(xù)的，也可以是不連續(xù)的

D、以上都不正確

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：線性表的存儲(chǔ)分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。在順序存儲(chǔ)中，所有元素所

占的存儲(chǔ)空間是連續(xù)的。而在鏈?zhǔn)酱鎯?chǔ)的方式中，將存儲(chǔ)空間的每一個(gè)存儲(chǔ)結(jié)點(diǎn)分

為兩部分，一部分用于存儲(chǔ)數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分用于存儲(chǔ)下一個(gè)

元素的存儲(chǔ)序號(hào)，稱為指針域。所以線性表的鏈?zhǔn)酱鎯?chǔ)方式比順序存儲(chǔ)方式的存儲(chǔ)

空間要大一些。

9、下列敘述中正確的是

A、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間是相同的

B、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間一般要多于順序存儲(chǔ)結(jié)構(gòu)

C、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間一般要少于順序存儲(chǔ)結(jié)構(gòu)

D、以上都不正確

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：線性表的存儲(chǔ)分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。在順序存儲(chǔ)中，所有元素所

占的存儲(chǔ)空間是連續(xù)的。而在鏈?zhǔn)酱鎯?chǔ)的方式中，將存儲(chǔ)空間的每一個(gè)存儲(chǔ)結(jié)點(diǎn)分

為兩部分，一部分用于存儲(chǔ)數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分用于存儲(chǔ)下一個(gè)

元素的存儲(chǔ)序號(hào)，稱為指針域。所以線性表的鏈?zhǔn)酱鎯?chǔ)方式比順序存儲(chǔ)方式的存儲(chǔ)

空間要大一些。

10、下列敘述中正確的是

A、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間是相同的

B、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間一般要多于順序存儲(chǔ)結(jié)構(gòu)

C、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間一般要少于順序存儲(chǔ)結(jié)構(gòu)

D、上述三種說法都不劉

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：線性表的存儲(chǔ)分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。在順序存儲(chǔ)中，所有元素所

占的存儲(chǔ)空間是連續(xù)的，各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。所以

每個(gè)元素只存儲(chǔ)其值就可以了，而在鏈?zhǔn)酱鎯?chǔ)的方式中，將存儲(chǔ)空間的每一個(gè)存儲(chǔ)

結(jié)點(diǎn)分為兩部分，一部分用于存儲(chǔ)數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分用于存儲(chǔ)

下一個(gè)元素的存儲(chǔ)序號(hào)，稱為指針域。所以線性表的鏈?zhǔn)酱鎯?chǔ)方式比順序存儲(chǔ)方式

的存儲(chǔ)空間要大一些。

11、下列對(duì)于線性鏈表的描述中正確的是

A、存儲(chǔ)空間不一定連續(xù)，且各元素的存儲(chǔ)順序是任意的

B、存儲(chǔ)空間不一定連續(xù)，且前件冗素一定存儲(chǔ)在后件元素的前面

C、存儲(chǔ)空間必須連續(xù)，且前件元素一定存儲(chǔ)在后件元素的前面

D、存儲(chǔ)空間必須連續(xù)，且各元素的存儲(chǔ)順序是任意的

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析：一般來說，在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)序號(hào)是不

連續(xù)的,并且各結(jié)點(diǎn)在存儲(chǔ)空間中的位置關(guān)系與邏輯關(guān)系也不一一致.在線性鏈表

中，各數(shù)據(jù)元素之間的前后件關(guān)系是由各結(jié)點(diǎn)的指針域來指示的，指向線性表中第

一個(gè)結(jié)點(diǎn)的指針head稱為頭指針，當(dāng)head=NULL（或0）時(shí)稱為空表。

12、下列敘述中正確的是

A、順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)一定是連續(xù)的，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)空間不一定是連續(xù)的

B、順序存儲(chǔ)結(jié)構(gòu)只針對(duì)線性結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)只針對(duì)非線件結(jié)構(gòu)

C、順序存儲(chǔ)結(jié)構(gòu)能存儲(chǔ)有序表，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不能存儲(chǔ)有序表

D、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)比順序存儲(chǔ)結(jié)構(gòu)節(jié)省存儲(chǔ)空間

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析：順序存儲(chǔ)方式主要用于線性的數(shù)據(jù)結(jié)構(gòu)，它把邏輯上相鄰的數(shù)據(jù)元素

存儲(chǔ)在物理上相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)之間的關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來體現(xiàn)。

而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)空間不一定是連續(xù)的。

13、下列鏈表中，其邏輯結(jié)構(gòu)屬于非線件結(jié)構(gòu)的是

A、二叉鏈表

B、循環(huán)鏈表

C、雙向鏈表

D、帶鏈的棧

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析：二叉鏈表作為樹的存儲(chǔ)結(jié)構(gòu)。鏈表中結(jié)點(diǎn)的兩個(gè)鏈域分別指向該結(jié)點(diǎn)

的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)。

14、下列敘述中正確的是

A、有一個(gè)以上根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)不一定是非線性結(jié)構(gòu)

B、只有一個(gè)根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)不一定是線性結(jié)構(gòu)

C、循環(huán)鏈表是非線性結(jié)構(gòu)

D、雙向鏈表是非線性結(jié)構(gòu)

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：在數(shù)據(jù)結(jié)陶中，樹這類的的數(shù)據(jù)結(jié)構(gòu)只有一個(gè)根結(jié)點(diǎn)，但它不是線性

結(jié)構(gòu)。

15、某系統(tǒng)總體結(jié)構(gòu)圖如下圖所示:

該系統(tǒng)總體結(jié)構(gòu)圖的深度是

A、7

B、6

C、3

D、2

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：這個(gè)系統(tǒng)總體結(jié)構(gòu)圖是一棵樹結(jié)構(gòu)，在樹結(jié)構(gòu)中，根結(jié)點(diǎn)在第1層，

同一層上所有子結(jié)點(diǎn)都在下一層，由系統(tǒng)總體結(jié)構(gòu)圖可知，這棵樹共3層。在樹結(jié)

構(gòu)中，樹的最大層次稱為樹的深度。所以這棵樹的深度為3。

16、下列關(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ù)的兩倍

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：由二叉樹的性質(zhì)可以知道在二叉樹中葉子結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)多

一個(gè)。

17、某二叉樹中有n個(gè)度為2的結(jié)點(diǎn)，則該二叉樹中的葉子結(jié)點(diǎn)數(shù)為

A^n+1

B、n-1

C、2n

D、n/2

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析：在任意一裸二叉樹中，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)

點(diǎn)多一個(gè)。所以該二叉樹的葉子結(jié)點(diǎn)數(shù)等于n+1。

18、某二叉樹有5個(gè)度為2的結(jié)點(diǎn)，則該二叉樹中的葉子結(jié)點(diǎn)數(shù)是

A、10

B、8

C、6

D、4

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：根據(jù)二叉樹的性質(zhì)，在任意二叉樹中，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總

是比度為2的結(jié)點(diǎn)多一個(gè)。

19、一棵二叉樹共有25個(gè)結(jié)點(diǎn)，其中5個(gè)是葉子結(jié)點(diǎn)，則度為1的結(jié)點(diǎn)數(shù)為

A、16

B、10

C、6

D、4

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析：根據(jù)二叉樹的性質(zhì)，在任意二叉樹中，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總

是比度為2的結(jié)點(diǎn)多一個(gè)，故此度為1的結(jié)點(diǎn)個(gè)數(shù):總結(jié)點(diǎn)數(shù)-葉子節(jié)點(diǎn)數(shù)-度為2

的節(jié)點(diǎn)數(shù)=25—54=16。

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

點(diǎn)數(shù)為

A、219

B、229

C、230

D、231

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：根據(jù)二叉樹的性質(zhì)，在任意二叉樹中，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總

是比度為2的結(jié)點(diǎn)多一個(gè)，故總結(jié)點(diǎn)數(shù)二葉子節(jié)點(diǎn)數(shù)十度為2的節(jié)點(diǎn)數(shù)十度為1的節(jié)

點(diǎn)數(shù)=80+79+70=229。

21、一棵二叉樹中共有70個(gè)葉子結(jié)點(diǎn)與80個(gè)度為I的結(jié)點(diǎn)，則該二叉樹中的總結(jié)

點(diǎn)數(shù)為

A、219

B、221

C、229

D、231

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析：在二叉樹中，葉子結(jié)點(diǎn)個(gè)數(shù)為no,則度為2的結(jié)點(diǎn)數(shù)n2=no-l。本題

中葉子結(jié)點(diǎn)的個(gè)數(shù)為70,所以度為2的結(jié)點(diǎn)個(gè)數(shù)為69,因而總結(jié)點(diǎn)數(shù)二葉子結(jié)點(diǎn)

數(shù)+度為I的結(jié)點(diǎn)數(shù)+度為2的結(jié)點(diǎn)數(shù)=70+80+69=219。

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

根結(jié)點(diǎn)在第1層）

A、3

B、4

C、6

D、7

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：根據(jù)二叉對(duì)的性質(zhì)，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)

多一個(gè)。題目中的二叉樹的葉子結(jié)點(diǎn)為1,因此度為2的結(jié)點(diǎn)的數(shù)目為0,故該二

叉樹為7層，每層只有一個(gè)結(jié)點(diǎn)。

23、某二叉樹共有12個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)只有1個(gè)。則該二叉樹的深度為（根結(jié)

點(diǎn)在第1層）

A、3

B、6

C、8

D、12

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：根據(jù)二叉樹的性質(zhì)，度為O的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)

多一個(gè)v題目中的二叉對(duì)的葉子結(jié)點(diǎn)為1,因此度為2的結(jié)點(diǎn)的數(shù)目為0,故該二

叉樹為12層，每層只有一個(gè)結(jié)點(diǎn)。

24、設(shè)樹T的深度為4,其中度為1,2,3,4的結(jié)點(diǎn)個(gè)數(shù)分別為4,2,1,1。則

T中的葉子結(jié)點(diǎn)數(shù)為

A、8

B、7

C、6

D、5

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：深度為m二義樹其總結(jié)點(diǎn)數(shù)為2m—1=24—1=15?？偨Y(jié)點(diǎn)數(shù)減去度

為1,2,3,4的結(jié)點(diǎn)個(gè)數(shù)就是葉子結(jié)點(diǎn)數(shù)。15-4-2-l-l=7o

25、設(shè)一棵完全二叉樹共有700個(gè)結(jié)點(diǎn)，則此二叉樹中的葉子結(jié)點(diǎn)數(shù)為

A、85

B、120

C、250

D、350

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：①具有n個(gè)結(jié)點(diǎn)的完全二.叉樹的深度為［long2n］+l，計(jì)算出該完全二

叉樹的深度為10。②設(shè)度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）為no,度為1的結(jié)點(diǎn)為n】，度

為2的結(jié)點(diǎn)為02，總結(jié)點(diǎn)數(shù)為n,深度為k。n=ni+n2+no，由于no=n2+l,貝U

n2=no—1,故n=ni+no—l+no=ni+2no—1。由于完全二叉樹中度為1的結(jié)點(diǎn)數(shù)只有

兩種可能；0或1。③假設(shè)度為］的結(jié)點(diǎn)數(shù)為。即滿二叉樹，根據(jù)滿二叉樹的定

義，其2m—1個(gè)結(jié)點(diǎn)，跟據(jù)以上計(jì)算所得的深度10來計(jì)算，應(yīng)有2KM=1024—

1=1023個(gè)結(jié)點(diǎn)，顯然與題目中700個(gè)結(jié)點(diǎn)不符。氏此，度為1的結(jié)點(diǎn)數(shù)必然為1。

故n=n1+2n（）-1=1+2n（）-1=2n（）?則n（）=n/2=700/2=350o

26、在深度為7的滿二叉樹中，葉子結(jié)點(diǎn)的個(gè)數(shù)為

A、32

B、31

C、64

D、63

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：所渭滿二叉樹是指這樣的一種二叉樹：除最后一層外，每一層上的所

有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。也就是在滿二叉樹中，每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)

數(shù)，即在滿二叉樹的第k層上有個(gè)結(jié)點(diǎn)，且深度為m的滿二義樹有2叫1個(gè)結(jié)

點(diǎn)。對(duì)于深度為7的滿二叉樹，葉子結(jié)點(diǎn)所在的是第7層，一共有27-匚64個(gè)葉子

結(jié)點(diǎn)。全部結(jié)點(diǎn)共27-1=127個(gè)。

27、對(duì)下列二叉樹進(jìn)行前序遍歷的結(jié)果是

A、DYBEAFCZX

B、YDEBFZXCA

C、ABDYECFXZ

D、ABCDEFXYZ

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：二叉樹前序遍歷的簡單描述：若二叉樹為空，則結(jié)束返回：甭則：

①訪問根結(jié)點(diǎn)；②前序遍歷左子樹；③前序遍歷石子樹。可見，前序遍歷二叉樹

的過程是一個(gè)遞歸的過程。根據(jù)題目中給出的二叉樹的結(jié)構(gòu)可知前序遍歷的結(jié)果是

ABDYECFXZo

B

DE

28、對(duì)如下二叉樹進(jìn)行后序遍歷的結(jié)果為

A、ABCDEF

B、DBEAFC

C、ABDECF

D、DEBFCA

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：所謂后序遍歷是指在訪問根據(jù)結(jié)點(diǎn)、遍歷左子樹與遍歷右予樹這三者

中，首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點(diǎn)，并且，在遍歷左、右子

樹時(shí)，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根點(diǎn)。因此，后序遍歷二叉

樹的過程也是一個(gè)遞歸過程。其簡單描述為：若二叉樹為空，則結(jié)束返回；否則，

先后序遍歷左子樹，然后后序遍歷右子樹，最后訪問根結(jié)點(diǎn)。對(duì)于后序遍歷，第一

個(gè)訪問的結(jié)點(diǎn)一定是最左下的結(jié)點(diǎn)，最后一個(gè)訪問的結(jié)點(diǎn)一定是根結(jié)點(diǎn)，所以選項(xiàng)

D）為正確答案。

29、對(duì)長度為n的線性表進(jìn)行順序查找，在最壞情況下所需要的比較次數(shù)為

A、log2n

B、n/2

C^n

D、n+1

標(biāo)準(zhǔn)答案：c

知識(shí)點(diǎn)3析：在進(jìn)行順序查找過程中，如果被查的元素是線性表中的最后一個(gè)元

素，或者被查元素根本不在線性表中，則為查找這個(gè)元素需要與線性表中的所有元

素進(jìn)行比較，這是順序查找的最壞情況，需要比較的次數(shù)為n次。

30、在長度為64的有序線性表中進(jìn)行順序查找，最壞情況下需要比較的次數(shù)為

A、63

B、64

C、6

D、7

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)露析：順序查找又稱順序搜索。順序查找一般是指在線性表中查找指定的元

素，其基本方法是：從線性表的第一元素開始，依次將線性表中的元素與被查找的

元素進(jìn)行比較，若相等則表示找到（即查找成功），若線性表中所有元素都與被杳元

素進(jìn)行了比較但都不相等，則表示線性表中沒有要找的元素（即查找失?。?。如果線

性表中的第一個(gè)元素就是要查找的元素，則只需要做一次比較就查找成功；但如果

要查找的元素是線性表中的最后一個(gè)元素，或者要查找元素不在線性表中，則需要

與線性表中所有元素進(jìn)行比較，這是順序查找的最壞情況，比較次數(shù)為線性表的長

度。

國家二級(jí)公共基礎(chǔ)知識(shí)（數(shù)據(jù)結(jié)構(gòu)與算

法）模擬試卷第3套

一、單項(xiàng)選擇題（本題共36題，每題1.0分，共36

分。）

1、對(duì)下列二叉樹進(jìn)行前序遍歷的

結(jié)果是（）。

A、DYBEAFCZX

B、YDEBFZXCA

C、ABDYECFXZ

D、ABCDEFXYZ

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：二叉樹前序遍歷的簡單描述：若二叉樹為空，則結(jié)束返回；否則：

①訪問根結(jié)點(diǎn)：②前序遍歷左子樹；⑤前序遍歷右子樹?？梢姡靶虮闅v二叉樹

的過程是一個(gè)遞歸的過程。根據(jù)題目中給出的二叉樹的結(jié)構(gòu)可知前序遍歷的結(jié)果是

ABDYECFXZo

2、對(duì)如下二叉樹進(jìn)行后序遍歷的結(jié)果為（）。

A、ABCDEF

B、DBEAFC

C、ABDECF

D、DEBFCA

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：所謂后序遍歷是指在訪問根據(jù)結(jié)點(diǎn)、遍歷左子樹與遍歷右子樹這三者

巾，首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點(diǎn)，并且，在遍歷左、右子

樹時(shí)，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根點(diǎn)。因此，后序遍歷二叉

樹的過程也是一個(gè)遞歸過程。其簡單描述為：若二叉樹為空，則結(jié)束返回；否則，

先后序遍歷左子樹，然后后序遍歷右子樹，最后訪問根結(jié)點(diǎn)。對(duì)于后序遍歷，第一

個(gè)訪問的結(jié)點(diǎn)一定是最左下的結(jié)點(diǎn)，最后一個(gè)訪問的結(jié)點(diǎn)一定是根結(jié)點(diǎn)，所以選項(xiàng)

D為正確答案。

3、對(duì)長度為n的線性表進(jìn)行順序查找，在最壞情況下所需要的比較次數(shù)為（）。

A、Iog2n

B、n/2

C、n

D、n+1

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：在進(jìn)行順序查找過程中，如果被查的兀素是線性表中的最后一個(gè)元

索，或者被查元素根本不在線性表中，則為了瓷找這個(gè)元素需要與線性表中的所有

元素進(jìn)行比較，這是順序查找的最壞情況，需要比較的次數(shù)為n次。

4、在長度為64的有序線性表中進(jìn)行順序查找，最壞情況下需要比較的次數(shù)為（）。

A、63

B、64

C、6

D、7

標(biāo)準(zhǔn)答案：R

知識(shí)點(diǎn)解析：順序查找又稱順序搜索。順序查找一般是指在線性表中查找指定的元

素，其基本方法是：從線性表的第一元素開始，依次將線性表中的元素與被查找的

元素進(jìn)行比較，若相等則表示找到（即查找成功），若線性表中所有元素都與被查元

素進(jìn)行了比較但都不相等，則表示線性表中沒有要找的元素（即查找失?。?。如果線

性表中的第一個(gè)元素就是要查找的元素，則只需要做一次比較就查找成功：但如果

要查找的元素是線性表中的最后一個(gè)元素，或者要查找元素不在線性表中，則需要

與線性表中所有元素進(jìn)行比較，這是順序查找的最壞情況，比較次數(shù)為線性表的長

度。

5、下列敘述中正確的是（）。

A、對(duì)長度為n的有序鏈表進(jìn)行查找，最壞情況下需要的比較次數(shù)為n

B、對(duì)長度為n的有序鏈表進(jìn)行對(duì)分查找，最壞情況下需要的比較次數(shù)為（n/2）

C、對(duì)長度為n的有序鏈表進(jìn)行對(duì)分查找，最壞情況下需要的比較次數(shù)為（logzn）

D、對(duì)長度為n的有序鏈表進(jìn)行對(duì)分查找，最壞情況下需要的比較次數(shù)為

(nlog2n.)

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析：本題主要考查的知識(shí)點(diǎn)為查找技術(shù)。順序查找的使用情況：①線性

表為無序表；②表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。二分法查找只適用于順序存儲(chǔ)的有序表，

并不適用于線性鏈表。

6、在長度為n的有序線性表中進(jìn)行二分查找，最坎情況下需要比較的次數(shù)是()。

A、0(n)

B、0(1?)

C、O(log2n)

D、O(nlog2n)

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：對(duì)于長度為n的有序線性表，在最壞情況下，二分法查找只需比較

log2n次，而順序查找需要比較n次。

7、下列數(shù)據(jù)結(jié)構(gòu)中，能用二分法進(jìn)行查找的是()。

A、順序存儲(chǔ)的有序線性表

B、線性鏈表

C、二叉鏈表

D、有序線性鏈表

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析：二分法查找只適應(yīng)于順序存儲(chǔ)的有序表。有序表是指線性表中的元素

按值非遞減排序(即從小到大，但允許相鄰元素值相等)的表。

8、冒泡排序在最壞情況下的比較次數(shù)是()。

A、n(n4-1)/2

B、nlog2n

C^n(n—1)/2

D、n/2

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：對(duì)n個(gè)結(jié)點(diǎn)的線性表采用冒泡排序，在最壞情況下，冒泡排序需要經(jīng)

過n/2遍的從前往后的掃描和n/2遍的從后往前的掃描，需要的比較次數(shù)為n(n

—1)/2o

9、對(duì)長度為1。的線性表進(jìn)行冒泡排序，最壞情況下需要比較的次數(shù)為()。

A、9

B、10

C、45

D、90

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：線性表的長度為n,最壞情況下冒泡排序需要比較的次數(shù)為n(n—l)

/2o

10、對(duì)于長度為n的線性表，在最壞情況下，下列各排序法所對(duì)應(yīng)的比較次數(shù)中正

確的是()。

A、冒泡排序?yàn)閚/2

B、冒泡排序?yàn)閚

C、快速排序?yàn)閚

D、快速排序?yàn)閚(n-l)/2

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：假設(shè)線性表的長度為n,則在最壞情況下，冒泡排序需要經(jīng)過n/2

遍的從前往后的掃描和n/2遍的從后往前的掃描，需要的比較次數(shù)為n(n—l)/

2o快速排序法也是一種互換類的排序方法，但由于它比冒泡排序法的速度快，因

此，稱為快速排序法。

11、對(duì)長度為n的線性表作快速排序，在最壞情況下，比較次數(shù)為()。

A、n

B、n—1

C、n(n—1)

D、n(n-l)/2

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：假設(shè)線性表的長度為n,則在最壞情況下，冒泡排序需要經(jīng)過n/2

遍的從前往后的掃描和n/2遍的從后往前的掃描，需要的比較次數(shù)為n(n—1)/

2?？焖倥判蚍ㄒ彩且环N互換類的排序方法，但由于它比冒泡排序法的速度快，因

此，稱為快速排序法。

12、對(duì)長度為n的線性表排序，在最壞情況下，比較次數(shù)不是n(n—1)/2的排序

方法是()。

A、快速排序

B、冒泡排序

C、直接插入排序

D、堆排序

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：各種排序方法中最壞情況下需要比較的次數(shù)分別為：冒泡排序

1)/2、快速排序n(n—1)/2、簡單插入排序n(n—1)/2、希爾排序O(n")、簡單

選擇排序n(n—1)/2＞堆排序O(nlog2n)0

13、下列排序方法中，最壞情況下比較次數(shù)最少的是()。

A、冒泡排序

B、簡單選擇排序

C、直接插入排序

D、堆排序

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：冒泡排序、簡單選擇排序和直接插入排序法在最壞的情況下比較次數(shù)

為：n(n—1)/2。而堆排序法在最壞的情況下需要比較的次數(shù)為O(nlog2n)。其中堆

排序的比較次數(shù)最少。

14、下列對(duì)隊(duì)列的描述中正確的是()。

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

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

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

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

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：隊(duì)列(queue)是指允許在一端進(jìn)行插入、而在另一端進(jìn)行刪除的線性

表。允許插入的一端稱為隊(duì)尾；允許刪除的一端稱為隊(duì)頭。在隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)

中，最先插入的元素將最先能夠被刪除；反之，最后插入的元素將最后才能被刪

除。因此，隊(duì)列又稱“先進(jìn)先出”或“后進(jìn)后出”的線性表。

15、下列敘述中正確的是()。

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

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

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

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

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：棧是先進(jìn)后出的線性表，隊(duì)列是先進(jìn)先出的線性表，二者均為線性結(jié)

構(gòu)。

16、下列敘述中正確的是()。

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

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

C、循環(huán)隊(duì)列是非線性結(jié)構(gòu)

D、有序線性表既可以采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：本題主要考查了棧、隊(duì)列、循環(huán)隊(duì)列的概念，棧是先進(jìn)后出的線性

表，隊(duì)列是先進(jìn)先出的線性表。根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間的前后件關(guān)系的復(fù)

雜程度，一般將數(shù)據(jù)結(jié)溝分為兩大類型：線性結(jié)構(gòu)與非線性結(jié)構(gòu)。有序線性表既可

以采用順序存儲(chǔ)結(jié)構(gòu)，又可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

17、下列關(guān)于棧的描述中正確的是()。

A、在棧中只能插入兀索而不能刪除兀索

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

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

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

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：棧是限定在一端進(jìn)行插入與刪除的線性表，在棧中，允許插入與刪除

的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。

18、下列敘述中正確的是（）。

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ì)尾指針共同決定

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：循環(huán)隊(duì)列中元素的個(gè)數(shù)是由隊(duì)頭指針和隊(duì)尾指針共同決定的，元素的

動(dòng)態(tài)變化也是通過隊(duì)頭指針和隊(duì)尾指針來反映的。

19、對(duì)于循環(huán)隊(duì)列，下列敘述中正確的是（）。

A、隊(duì)頭指針是固定不變的

B、隊(duì)頭指針一定大于隊(duì)尾指針

C、隊(duì)頭指針一定小于隊(duì)尾指針

D、隊(duì)頭指針可以大于隊(duì)尾指針，也可以小于隊(duì)尾指針

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：所謂循環(huán)隊(duì)列，就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位

置，形成邏輯上的環(huán)狀空間，供隊(duì)列循環(huán)使用。在循環(huán)隊(duì)列中，用隊(duì)尾指針rear

指向隊(duì)列中的隊(duì)尾元素，用隊(duì)頭指針from指向隊(duì)頭元素的前一個(gè)位置。循環(huán)隊(duì)列

的主要操作是：入隊(duì)運(yùn)算和退隊(duì)運(yùn)算。每進(jìn)行一次入隊(duì)運(yùn)算，隊(duì)尾指針就進(jìn)一。每

進(jìn)行一次退隊(duì)運(yùn)算，隊(duì)頭指針就進(jìn)一。當(dāng)rear或front等于隊(duì)列的長度加1時(shí)，就

把rear?或from值置為I°所以在循環(huán)隊(duì)列中，隊(duì)頭指針可以大于隊(duì)尾指針，也可以

小于隊(duì)尾指針。

20、下列敘述中正確的是（）。

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

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

C、循環(huán)隊(duì)列是非線性結(jié)構(gòu)

D、循環(huán)隊(duì)列是一種邏輯結(jié)構(gòu)

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：本題主要考查循環(huán)隊(duì)列的概念，循環(huán)隊(duì)列作為隊(duì)列的一種也應(yīng)該是線

性結(jié)構(gòu)。隊(duì)列是一種邏輯結(jié)構(gòu)，而循環(huán)隊(duì)列是一種順序存儲(chǔ)結(jié)構(gòu)的隊(duì)列。

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

列入隊(duì)與退隊(duì)運(yùn)算后，front=15,rear=15,則循環(huán)隊(duì)列中的元素個(gè)數(shù)為（）。

A、15

B、16

C、20

D、0或35

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：循環(huán)隊(duì)列的隊(duì)頭指針和尾指針都等于15,此循環(huán)隊(duì)列中元素的個(gè)數(shù)

有兩種情況，第一種情況是隊(duì)頭指針和尾指針都是第一次到達(dá)15,此時(shí)元素個(gè)數(shù)

為0；第二種情況是隊(duì)頭指針第一次到達(dá)15,而尾指針第二次到達(dá)15,此時(shí)元素

個(gè)數(shù)為35。

22在一個(gè)容量為15的循環(huán)隊(duì)列中，若頭指針fron=6,尾指針rear=9,則循環(huán)

隊(duì)列中的元素個(gè)數(shù)為（卜

A、2

B、3

C、4

D、5

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：循環(huán)多列中，rear表示尾指針，front表示頭指針，當(dāng)有元素入隊(duì)時(shí)，

rear=rear+10而元素出隊(duì)的時(shí)候，front=front+1,當(dāng)rear值大于fronl值時(shí)，隊(duì)

列中的元素個(gè)數(shù)為rear—front,當(dāng)rear的值小于fr31t時(shí)，列隊(duì)中的元素個(gè)數(shù)為rear

—front+m（m表示隊(duì)列的容量）。

23、下列敘述中正確的是（）。

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

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

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

D、棧與隊(duì)列都是線性結(jié)構(gòu)

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：棧是先進(jìn)后出，隊(duì)列是先進(jìn)先出。棧和隊(duì)列都是一種線性表，屬于線

性結(jié)構(gòu)。

24、下列敘述中正確的是（）。

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

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

C、循環(huán)隊(duì)列是非線性結(jié)構(gòu)

D、有序線性表既可以采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：棧是“先進(jìn)后出”，隊(duì)列”是先進(jìn)先出“0棧和隊(duì)列都是一種線性表，屬

于線性結(jié)構(gòu)。有序線性表既可以采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。采

用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表稱之為線性鏈表。

25、下列與隊(duì)列結(jié)構(gòu)有關(guān)聯(lián)的是（）。

A、函數(shù)的遞歸調(diào)用

B、數(shù)組元素的引用

C、多重循環(huán)的執(zhí)行

D、先到先服務(wù)的作業(yè)調(diào)度

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：隊(duì)列中最先插入的元素將最先被刪除，最后插入的元素將最后被刪

除。

26、下列敘述中正確的是（）。

A、循環(huán)隊(duì)列中的元素個(gè)數(shù)隨隊(duì)頭指針與隊(duì)尾指針的變化而動(dòng)態(tài)變化

B、循環(huán)隊(duì)列中的元素個(gè)數(shù)隨隊(duì)頭指針的變化而動(dòng)態(tài)變化

C、循環(huán)隊(duì)列中的元素個(gè)數(shù)隨隊(duì)尾指針的變化而動(dòng)態(tài)變化

D、循環(huán)隊(duì)列中的元素個(gè)數(shù)不會(huì)變化

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析：所謂循環(huán)結(jié)構(gòu)就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置

上，形成邏輯上的環(huán)狀空間，循環(huán)使用。在循環(huán)隊(duì)列中，用隊(duì)尾指針rear指向隊(duì)

列中的隊(duì)尾元素，用隊(duì)頭指針front指向隊(duì)頭元素的前一個(gè)位置，因此，隊(duì)列中的

元素?cái)?shù)等于從隊(duì)頭指針front指向的后一個(gè)位置與隊(duì)尾指針rear指向位置之間的元

素?cái)?shù)量。

27、下列關(guān)于線性鏈表的敘述中，正確的是（）。

A、各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)空間可以不連續(xù)，但它們的存儲(chǔ)順序與邏輯順序必須一致

B、各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與邏輯順序可以不一致，但它們的存儲(chǔ)空間必須連續(xù)

C,進(jìn)行插入與刪除時(shí)，不需要移動(dòng)表中的元素

D、以上都不正確

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，存儲(chǔ)數(shù)據(jù)

結(jié)構(gòu)的存儲(chǔ)空間可以不連續(xù)，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與數(shù)據(jù)元素之間的邏輯關(guān)系可

以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的。

28、下列敘述中正確的是（）。

A、線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)空間一般要少于順序存儲(chǔ)結(jié)構(gòu)

B、線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)空間都是連續(xù)的

C、線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)空間可以是連續(xù)的，也可以是不連續(xù)的

D、以上都不正確

標(biāo)準(zhǔn)答案：c

知識(shí)點(diǎn)解析：線性表的存儲(chǔ)分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。在順序存儲(chǔ)中，所有元素所

占的存儲(chǔ)空間是連續(xù)的。而在鏈?zhǔn)酱鎯?chǔ)的方式中，將存儲(chǔ)空間的每一個(gè)存儲(chǔ)結(jié)點(diǎn)分

為兩部分，一部分用于存儲(chǔ)數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分用于存儲(chǔ)下一個(gè)

元素的存儲(chǔ)序號(hào)，稱為指針域。所以線性表的鏈?zhǔn)酱鎯?chǔ)方式比順序存儲(chǔ)方式的存儲(chǔ)

空間要大一些。

29、下列敘述中正確的是（）。

A、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間是相同的

B、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間一般要多于順序存儲(chǔ)結(jié)構(gòu)

C、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間一般要少于順序存儲(chǔ)結(jié)構(gòu)

D、以上都不正確

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：線性表的存儲(chǔ)分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。在順序存儲(chǔ)中，所有元素所

占的存儲(chǔ)空間是連續(xù)的。而在鏈?zhǔn)酱鎯?chǔ)的方式中，將存儲(chǔ)空間的每一個(gè)存儲(chǔ)結(jié)點(diǎn)分

為兩部分，一部分用于存儲(chǔ)數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分用于存儲(chǔ)下一個(gè)

元素的存儲(chǔ)序號(hào)，稱為市針域。所以線性表的鏈?zhǔn)酱鎯?chǔ)方式比順序存儲(chǔ)方式的存儲(chǔ)

空間要大一些。

30、下列敘述中正確的是（）。

A、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間是相同的

B、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間一般要多于順序存儲(chǔ)結(jié)構(gòu)

C、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間一般要少于順序存儲(chǔ)結(jié)構(gòu)

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

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：線性表的存儲(chǔ)分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。在順序存儲(chǔ)中，所有元素所

占的存儲(chǔ)空間是連續(xù)的，各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。所以

每個(gè)元素只存儲(chǔ)其值就可以了，而在鏈?zhǔn)酱鎯?chǔ)的方式中，將存儲(chǔ)空間的每一個(gè)存儲(chǔ)

結(jié)點(diǎn)分為兩部分，一部分用于存儲(chǔ)數(shù)據(jù)元素的值，稱為數(shù)據(jù)域：另一部分用于存儲(chǔ)

下一個(gè)元素的存儲(chǔ)序號(hào)，稱為指針域。所以線性表的鏈?zhǔn)酱鎯?chǔ)方式比順序存儲(chǔ)方式

的存儲(chǔ)空間要大一些。

31、下列對(duì)于線性鏈表的描述中正確的是（）。

A、存儲(chǔ)空間不一定連續(xù)，且各元素的存儲(chǔ)順序是任意的

B、存儲(chǔ)空間不一定連續(xù)，且前件元素一定存儲(chǔ)在后件元素的前面

C、存儲(chǔ)空間必須連續(xù)，且前件元素一定存儲(chǔ)在后件元素的前面

D、存儲(chǔ)空間必須連續(xù)，且各元素的存儲(chǔ)順序是任意的

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析：一般來說，在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)序號(hào)是不

連續(xù)的,并且各結(jié)點(diǎn)在存儲(chǔ)空間中的位置關(guān)系與邏輯關(guān)系也不一致°在線件鏈表

中，各數(shù)據(jù)元素之間的前后件關(guān)系是由各結(jié)點(diǎn)的指針域來指示的，指向線性表中第

一個(gè)結(jié)點(diǎn)的指針head稱為頭指針，當(dāng)head=NuLL］或0）時(shí)稱為空表。

32、下列敘述中正確的是（）。

A、順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)一定是連續(xù)的，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)空間不一定是連續(xù)的

B、順序存儲(chǔ)結(jié)構(gòu)只針對(duì)線性結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)只針對(duì)非線性結(jié)構(gòu)

C、順序存儲(chǔ)結(jié)構(gòu)能存儲(chǔ)有序表，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不能存儲(chǔ)有序表

D、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)比順序存儲(chǔ)結(jié)構(gòu)節(jié)省存儲(chǔ)空間

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析：順序存儲(chǔ)方式主要用于線性的數(shù)據(jù)結(jié)構(gòu)，它把邏輯上相鄰的數(shù)據(jù)元素

存儲(chǔ)在物理上相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)之間的關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來體現(xiàn)。

而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)空間不一定是連續(xù)的。

33、下列鏈表中，其邏輯結(jié)構(gòu)屬于非線性結(jié)構(gòu)的是（）。

A、二叉鏈表

B、循環(huán)鏈表

C、雙向鏈表

D、帶鏈的棧

標(biāo)準(zhǔn)答案：

知識(shí)之解析A：二叉鏈表作為樹的存儲(chǔ)結(jié)構(gòu)。鏈表中結(jié)點(diǎn)的兩個(gè)鏈域分別指向該結(jié)點(diǎn)

的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)。

34、下列敘述中正確的是（）。

A、有一個(gè)以上根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)不一定是非線性結(jié)構(gòu)

B、只有一個(gè)根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)不一定是線性結(jié)構(gòu)

C、循環(huán)鏈表是非線性結(jié)構(gòu)

D、雙向鏈表是非線性結(jié)構(gòu)

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析?：在數(shù)據(jù)結(jié)溝中，樹這類的的數(shù)據(jù)結(jié)構(gòu)只有一個(gè)根結(jié)點(diǎn)，但它不是線性

結(jié)構(gòu)。

35、某系統(tǒng)總體結(jié)構(gòu)圖如下圖所示:該系統(tǒng)

總體結(jié)構(gòu)圖的深度是（），

A、7

B、6

C、3

D、2

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：這個(gè)系統(tǒng)總體結(jié)構(gòu)圖是一棵樹結(jié)構(gòu)，在樹結(jié)構(gòu)中，根結(jié)點(diǎn)在第1層，

同一層上所有子結(jié)點(diǎn)都在下一層，由系統(tǒng)總體結(jié)構(gòu)圖可知，這棵樹共3層。在樹結(jié)

構(gòu)中，樹的最大層次稱為樹的深度。所以這棵樹的深度為3。

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ù)的兩倍

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：由二叉樹的性質(zhì)可以知道在二叉樹中葉子結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)多

一個(gè)。

國家二級(jí)公共基礎(chǔ)知識(shí)（數(shù)據(jù)結(jié)構(gòu)與算

法）模擬試卷第4套

一、單項(xiàng)選擇題（本題共35題，每題1.0分，共35

分。）

1、下列與隊(duì)列結(jié)構(gòu)有關(guān)聯(lián)的是

A、函數(shù)的遞歸調(diào)用

B、數(shù)組元素的引用

C、多重循環(huán)的執(zhí)行

D、先到先服務(wù)的作業(yè)調(diào)度

標(biāo)準(zhǔn)答案：D

知識(shí)點(diǎn)解析：隊(duì)列中最先插入的元素將最先被刪除，最后插入的元素將最后被刪

除。

2、下列敘述中正確的是

A、循環(huán)隊(duì)列中的元素個(gè)數(shù)隨隊(duì)頭指針與隊(duì)尾指針的變化而動(dòng)態(tài)變化

B、循環(huán)隊(duì)列中的元素個(gè)數(shù)隨隊(duì)頭指針的變化而動(dòng)態(tài)變化

C、循環(huán)隊(duì)列中的元素個(gè)數(shù)隨隊(duì)尾指針的變化而動(dòng)態(tài)變化

D、循環(huán)隊(duì)列中的元素個(gè)數(shù)不會(huì)變化

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析：所謂循環(huán)結(jié)構(gòu)就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置

上，形成邏輯上的環(huán)狀空間，循環(huán)使用。在循環(huán)隊(duì)列中，用隊(duì)尾指針rear指向隊(duì)

列中的隊(duì)尾元素，用隊(duì)頭指針fron【指向隊(duì)頭元素的前一個(gè)位置，因此，隊(duì)列中的

元素?cái)?shù)等于從隊(duì)頭指針front指向的后一個(gè)位置與隊(duì)尾指針rear指向位置之間的元

素?cái)?shù)量。

3、下列關(guān)于線性鏈表的敘述中，正確的是

A、各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)空間可以不連續(xù)，但它們的存儲(chǔ)順序與邏輯順序必須一致

B、各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與邏輯順序可以不一致，但它們的存儲(chǔ)空間必須連續(xù)

C、進(jìn)行插入與刪除時(shí)，不需要移動(dòng)表中的元素

D、以上都不正確

標(biāo)準(zhǔn)答案：C

知識(shí)點(diǎn)解析：線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，存儲(chǔ)數(shù)據(jù)

結(jié)構(gòu)的存儲(chǔ)空間可以不連續(xù)，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與數(shù)據(jù)元素之間的邏輯關(guān)系可

以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的。

4、下列敘述中正確的是

A、線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)空間一般要少于順序存儲(chǔ)結(jié)構(gòu)

B、線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)空間都是連續(xù)的

C、線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)空間可以是連續(xù)的，也可以是不連續(xù)的

D、以上都不正確

標(biāo)準(zhǔn)答案：c

知識(shí)點(diǎn)解析：線性表的存儲(chǔ)分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。在順序存儲(chǔ)中，所有元素所

占的存儲(chǔ)空間是連續(xù)的。而在鏈?zhǔn)酱鎯?chǔ)的方式中，將存儲(chǔ)空間的每一個(gè)存儲(chǔ)結(jié)點(diǎn)分

為兩部分，一部分用于存儲(chǔ)數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分用于存儲(chǔ)下一個(gè)

元素的存儲(chǔ)序號(hào)，稱為指針域。所以線性表的鏈?zhǔn)酱鎯?chǔ)方式比順序存儲(chǔ)方式的存儲(chǔ)

空間要大一些。

5、下列敘述中正確的是

A、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間是相同的

B、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間一般要多于順序存儲(chǔ)結(jié)構(gòu)

C、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間一般要少于順序存儲(chǔ)結(jié)構(gòu)

D、以上都不正確

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：線性表的存儲(chǔ)分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。在順序存儲(chǔ)中，所有元素所

占的存儲(chǔ)空間是連續(xù)的。而在鏈?zhǔn)酱鎯?chǔ)的方式中，將存儲(chǔ)空間的每一個(gè)存儲(chǔ)結(jié)點(diǎn)分

為兩部分，一部分用于存儲(chǔ)數(shù)據(jù)元素的值，稱為數(shù)據(jù)域：另一部分用于存儲(chǔ)下一個(gè)

元素的存儲(chǔ)序號(hào)，稱為指針域。所以線性表的鏈?zhǔn)酱鎯?chǔ)方式比順序存儲(chǔ)方式的存儲(chǔ)

空間要大一些。

6、下列敘述中正確的是

A、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間是相同的

B、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間一般要多于順序存儲(chǔ)結(jié)構(gòu)

C、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間一般要少于順序存儲(chǔ)結(jié)構(gòu)

D、卜述二種說法都不對(duì)

標(biāo)準(zhǔn)答案：B

知識(shí)點(diǎn)解析：線性表的存儲(chǔ)分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。在順序存儲(chǔ)中，所有元素所

占的存儲(chǔ)空間是連續(xù)的，各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。所以

每個(gè)元素只存儲(chǔ)其值就可以了，而在鏈?zhǔn)酱鎯?chǔ)的方式中，將存儲(chǔ)空間的每一個(gè)存儲(chǔ)

結(jié)點(diǎn)分為兩部分，一部分用于存儲(chǔ)數(shù)據(jù)元素的值，稱為數(shù)據(jù)域：另一部分用于存儲(chǔ)

下一個(gè)元素的存儲(chǔ)序號(hào)，稱為指針域。所以線性表的鏈?zhǔn)酱鎯?chǔ)方式比順序存儲(chǔ)方式

的存儲(chǔ)空間要大一些。

7、下列對(duì)于線性鏈表的描述中正確的是

A、存儲(chǔ)空間不一定連續(xù)，且各元素的存儲(chǔ)順序是任意的

B、存儲(chǔ)空間不一定連續(xù)，且前件元素一定存儲(chǔ)在后件元素的前面

C、存儲(chǔ)空間必須連續(xù)，且前件元素一定存儲(chǔ)在后件元素的前面

D、存儲(chǔ)空間必須連續(xù)，且各元素的存儲(chǔ)順序是任意的

標(biāo)準(zhǔn)答案：A

知識(shí)點(diǎn)解析：一般來說，在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)序號(hào)是不

連續(xù)的，并且各結(jié)點(diǎn)在存儲(chǔ)空間中的位置關(guān)系與邏輯關(guān)系也不一致。在線性鏈中，

各數(shù)據(jù)元素之間的前后件