1.2 歷年試題解析

試題1

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

A.循環(huán)鏈表

B.雙向鏈表

C.帶鏈的棧

D.二叉鏈表

【分析】循環(huán)鏈表、雙向鏈表、帶鏈的棧都是線性結(jié)構(gòu)，二叉鏈表是非線性結(jié)構(gòu)二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，所以選D。

【答案】D

試題2

設(shè)循環(huán)隊(duì)列的存儲(chǔ)空間為Q(1：35)，初始狀態(tài)為front=rear=35。現(xiàn)經(jīng)過(guò)一系列入隊(duì)與退隊(duì)運(yùn)算后，front=15，rear=15，則循環(huán)隊(duì)列中的元素個(gè)數(shù)為（ ）。

A.16

B.20

C.0或35

D.15

【分析】在循環(huán)隊(duì)列中，當(dāng)頭指針=尾指針時(shí)，有兩種情況，一個(gè)是隊(duì)空狀態(tài)，一個(gè)是隊(duì)滿狀態(tài)。該循環(huán)隊(duì)列的初始狀態(tài)是隊(duì)頭指針=隊(duì)尾指針=35，經(jīng)過(guò)一系列入隊(duì)與退隊(duì)運(yùn)算后，隊(duì)頭指針和隊(duì)尾指針都發(fā)生了變化，但還是隊(duì)頭指針等于隊(duì)尾指針，隊(duì)空時(shí)，循環(huán)隊(duì)列中的元素個(gè)數(shù)是0，隊(duì)滿時(shí)，元素個(gè)數(shù)是循環(huán)隊(duì)列的最大空間35。

【答案】C

試題3

下列關(guān)于棧的敘述中，正確的是（ ）。

A.棧頂元素一定是最先入棧的元素

B.棧操作遵循先進(jìn)后出的原則

C.棧底元素一定是最后入棧的元素

D.以上三種說(shuō)法都不對(duì)

【分析】棧是限定在一端進(jìn)行插入與刪除的線性表。在棧中，允許插入與刪除的這一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧是按照“先進(jìn)后出”或“后進(jìn)先出”的原則組織數(shù)據(jù)的，因此，棧也被稱為“先進(jìn)后出”表或“后進(jìn)先出”表。

【答案】B

試題4

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

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

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

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

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

【分析】循環(huán)隊(duì)列是一種順序存儲(chǔ)的線性結(jié)構(gòu)。

【答案】C

試題5

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

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

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

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

D.以上三種說(shuō)法都不對(duì)

【分析】棧和隊(duì)列都是線性結(jié)構(gòu)，所以選項(xiàng)C錯(cuò)誤；棧是一種先進(jìn)后出的線性表，故選項(xiàng)A錯(cuò)誤；隊(duì)列是一種先進(jìn)先出的線性表，故選項(xiàng)B錯(cuò)誤，所以選D。

【答案】D

試題6

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

A.4

B.16

C.10

D.6

【分析】由二叉樹(shù)的性質(zhì)3可知，度為0的結(jié)點(diǎn)數(shù)（即葉子結(jié)點(diǎn)數(shù)）總是比度為2的結(jié)點(diǎn)多一個(gè)，此題中葉子結(jié)點(diǎn)數(shù)為5，所以度為2的結(jié)點(diǎn)數(shù)為4，二叉樹(shù)的總結(jié)點(diǎn)數(shù)=葉子結(jié)點(diǎn)數(shù)+度為1的結(jié)點(diǎn)數(shù)+度為2的結(jié)點(diǎn)數(shù)，所以此題度為1的結(jié)點(diǎn)數(shù)為25-5-4=16。

【答案】B

試題7

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

A.算法的效率只與問(wèn)題的規(guī)模有關(guān)，而與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)

B.算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量

C.數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)是一一對(duì)應(yīng)的

D.算法的時(shí)間復(fù)雜度與空間復(fù)雜度一定相關(guān)

【分析】根據(jù)算法時(shí)間復(fù)雜度和空間復(fù)雜度的定義可知，算法的時(shí)間復(fù)雜度就是執(zhí)行該算法所需要的計(jì)算工作量，算法所執(zhí)行的基本運(yùn)算次數(shù)與問(wèn)題的規(guī)模有關(guān)；而算法的空間復(fù)雜度就是執(zhí)行該算法所需要的內(nèi)存空間。通常用時(shí)間復(fù)雜度和空間復(fù)雜度來(lái)衡量算法的效率，但是算法的時(shí)間復(fù)雜度與空間復(fù)雜度并不一定相關(guān)。數(shù)據(jù)的邏輯結(jié)構(gòu)是指各個(gè)數(shù)據(jù)元素之間的邏輯關(guān)系，反映人們對(duì)數(shù)據(jù)含義的理解，與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)沒(méi)有關(guān)系，是獨(dú)立于計(jì)算機(jī)的。算法的執(zhí)行效率不僅與問(wèn)題的規(guī)模有關(guān)，還與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有關(guān)。

【答案】B

試題8

下面對(duì)隊(duì)列的敘述正確的是（ ）。

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

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

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

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

【分析】隊(duì)列是限定了插入和刪除操作的線性表，它只允許在表的一端進(jìn)行插入操作，而在另外一端進(jìn)行刪除操作。在隊(duì)列中，允許插入元素的一端稱為隊(duì)尾，允許刪除元素的一端稱為隊(duì)頭。隊(duì)列按照“先進(jìn)先出”的原則組織數(shù)據(jù)，因此又稱為“先進(jìn)先出”的線性表。

【答案】D

試題9

對(duì)圖1-40的二叉樹(shù)進(jìn)行前序遍歷的結(jié)果為（ ）。

A.DYBEAFCZX

B.YDEBFZXCA

C.ABDYECFXZ

D.ABCDEFXYZ

【分析】前序遍歷二叉樹(shù)的操作定義為：若二叉樹(shù)為空，則空操作；否則1）訪問(wèn)根結(jié)點(diǎn)；2）前序遍歷左子樹(shù)；3）前序遍歷右子樹(shù)。根據(jù)題目可知，該二叉樹(shù)前序遍歷的結(jié)果是：ABDYECFXZ。

【答案】C

試題10

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

A.n+1

B.n-1

C.2n

D.n/2

【分析】根據(jù)二叉樹(shù)的性質(zhì)3：在任意一棵二叉樹(shù)中，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個(gè)。本題中度為2的結(jié)點(diǎn)數(shù)為n，故葉子結(jié)點(diǎn)數(shù)為n+1個(gè)。

【答案】A

試題11

下列敘述正確的是（ ）。

A.算法就是程序

B.設(shè)計(jì)算法時(shí)只需要考慮數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)

C.設(shè)計(jì)算法時(shí)只需要考慮結(jié)果的可靠性

D.以上三種說(shuō)法都不對(duì)

【分析】算法是一系列解決問(wèn)題的清晰指令，也就是說(shuō)，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時(shí)間內(nèi)獲得所要求的輸出。程序（program）是為實(shí)現(xiàn)特定目標(biāo)或解決特定問(wèn)題而用計(jì)算機(jī)語(yǔ)言編寫(xiě)的命令序列的集合。因此，算法不等于程序。因?yàn)槊總€(gè)算法實(shí)際上是按解題要求從環(huán)境能進(jìn)行的所有操作中選擇合適的操作所組成的一組指令序列，所以設(shè)計(jì)算法時(shí)，不僅要考慮算法中對(duì)數(shù)據(jù)的運(yùn)算和操作，同時(shí)還要考慮算法的控制結(jié)構(gòu)。一個(gè)算法的功能不但取決于所選用的操作，而且還與各操作之間的執(zhí)行順序有關(guān)。算法中各操作之間的執(zhí)行順序稱為算法的控制結(jié)構(gòu)。

【答案】D

試題12

下列關(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.以上三種說(shuō)法都不對(duì)

【分析】線性表是一個(gè)線性結(jié)構(gòu)，它是一個(gè)含有n≥0個(gè)結(jié)點(diǎn)的有限序列。線性表的鏈?zhǔn)酱鎯?chǔ)稱為線性鏈表，指的是用一組任意的存儲(chǔ)單元來(lái)依次存放線性表的結(jié)點(diǎn)，這組存儲(chǔ)單元既可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中的任意位置上的。因此，鏈表中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同。鏈表是通過(guò)每個(gè)結(jié)點(diǎn)的鏈域?qū)⒕€性表的n個(gè)結(jié)點(diǎn)按其邏輯次序鏈接在一起的。在線性鏈表中插入或刪除一個(gè)元素，不需要移動(dòng)表中的數(shù)據(jù)元素，只需要改變被插入或刪除元素所在結(jié)點(diǎn)及其前后結(jié)點(diǎn)的指針域即可。

【答案】C

試題13

下列關(guān)于二叉樹(shù)的敘述中，正確的是（ ）。

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

【分析】根據(jù)二叉樹(shù)的性質(zhì)，對(duì)于任何一棵二叉樹(shù)，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個(gè)。

【答案】B

試題14

下列關(guān)于棧的敘述正確的是（ ）。

A.棧頂元素最先能被刪除

B.棧頂元素最后才能被刪除

C.棧底元素永遠(yuǎn)不能被刪除

D.以上三種說(shuō)法都不對(duì)

【分析】棧是限定只在一端進(jìn)行插入與刪除的特殊線性表。允許進(jìn)行插入和刪除操作的一端稱為棧頂（top），另一端為棧底（bottom）。棧底固定，而棧頂浮動(dòng)。棧按照“后進(jìn)先出”的原則存儲(chǔ)數(shù)據(jù)，先進(jìn)入的數(shù)據(jù)被壓入棧底，最后進(jìn)入的數(shù)據(jù)在棧頂，需要讀數(shù)據(jù)時(shí)，從棧頂開(kāi)始彈出數(shù)據(jù)（最后一個(gè)進(jìn)入的數(shù)據(jù)被第一個(gè)讀出來(lái)）。因此，棧頂?shù)脑刈钕缺粍h除。

【答案】A

試題15

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

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)

【分析】線性結(jié)構(gòu)指的是數(shù)據(jù)元素之間存在“一對(duì)一”線性關(guān)系的數(shù)據(jù)結(jié)構(gòu)，這樣的結(jié)構(gòu)中只有一個(gè)根結(jié)點(diǎn)，如循環(huán)鏈表和雙向鏈表。非線性結(jié)構(gòu)指的是數(shù)據(jù)元素之間存在“一對(duì)一”非線性關(guān)系的數(shù)據(jù)結(jié)構(gòu)，這樣的結(jié)構(gòu)中可能有一個(gè)根結(jié)點(diǎn)，如樹(shù)形結(jié)構(gòu)，也可能有多個(gè)根結(jié)點(diǎn)，如網(wǎng)狀結(jié)構(gòu)。

【答案】B

試題16

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

A.3

B.4

C.6

D.7

【分析】葉子結(jié)點(diǎn)個(gè)數(shù)=度為2的結(jié)點(diǎn)個(gè)數(shù)+1。在此題中，葉子結(jié)點(diǎn)個(gè)數(shù)為1，說(shuō)明度為2的結(jié)點(diǎn)數(shù)為0，即二叉樹(shù)中不存在度為2的結(jié)點(diǎn)，只有度為1的結(jié)點(diǎn)和葉子結(jié)點(diǎn)，那么此二叉樹(shù)就是一棵單分支樹(shù)，樹(shù)中結(jié)點(diǎn)個(gè)數(shù)即為樹(shù)的深度。

【答案】D

試題17

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

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.上述3種說(shuō)法都不對(duì)

【分析】順序存儲(chǔ)結(jié)構(gòu)是存儲(chǔ)結(jié)構(gòu)類型中的一種，該結(jié)構(gòu)把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置上相鄰的存儲(chǔ)單元中，結(jié)點(diǎn)之間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)。由此得到的存儲(chǔ)結(jié)構(gòu)為順序存儲(chǔ)結(jié)構(gòu)，通常順序存儲(chǔ)結(jié)構(gòu)借助于計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言的數(shù)組來(lái)描述。順序存儲(chǔ)結(jié)構(gòu)的主要優(yōu)點(diǎn)是節(jié)省存儲(chǔ)空間，因?yàn)榉峙浣o數(shù)據(jù)的存儲(chǔ)單元全用于存放結(jié)點(diǎn)的數(shù)據(jù)，而結(jié)點(diǎn)之間的邏輯關(guān)系沒(méi)有占用額外的存儲(chǔ)空間。

線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素（這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的）。因此，為了表示每個(gè)數(shù)據(jù)元素與其直接后繼數(shù)據(jù)元素之間的邏輯關(guān)系，對(duì)數(shù)據(jù)元素來(lái)說(shuō)，除了存儲(chǔ)數(shù)據(jù)外，還需要存儲(chǔ)一個(gè)到多個(gè)指針，而順序存儲(chǔ)不需要存儲(chǔ)地址，所以從存儲(chǔ)大小來(lái)看，自然是鏈表占空間大，不過(guò)訪問(wèn)靈活鏈表有很大的優(yōu)勢(shì)。

【答案】B

試題18

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

A.在棧中，棧中元素隨棧底指針與棧頂指針的變化而動(dòng)態(tài)變化

B.在棧中，棧頂指針不變，棧中元素隨棧底指針的變化而動(dòng)態(tài)變化

C.在棧中，棧底指針不變，棧中元素隨棧頂指針的變化而動(dòng)態(tài)變化

D.上述3種說(shuō)法都不對(duì)

【分析】棧是一種特殊的線性表，這種線性表只能在固定的一端進(jìn)行插入和刪除操作，允許插入和刪除的一端稱為棧頂，另一端稱為棧底。一個(gè)新元素只能從棧頂一端進(jìn)入，刪除時(shí)，只能刪除棧頂?shù)脑兀磩倓偙徊迦氲脑亍Ｋ詶Ｓ址Q“后進(jìn)先出”表，因此，在棧中，棧底指針不變，棧中元素隨棧頂指針的變化而動(dòng)態(tài)變化。

【答案】C

試題19

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

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

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

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

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

【分析】對(duì)長(zhǎng)度為n的有序鏈表進(jìn)行查找，最壞情況是從最小值開(kāi)始查找最大值（或從最大值開(kāi)始查找最小值），這個(gè)過(guò)程需要比較的次數(shù)為n，故選項(xiàng)A正確。對(duì)分查找只能針對(duì)隨機(jī)存取的有序表進(jìn)行，而有序鏈表只能進(jìn)行順序存取，不能進(jìn)行隨機(jī)存取，因此在有序鏈表上不能進(jìn)行對(duì)分查找，故B、C、D選項(xiàng)都錯(cuò)誤。

【答案】A

試題20

算法的時(shí)間復(fù)雜度是指（ ）。

A.算法的執(zhí)行時(shí)間

B.算法所處理的數(shù)據(jù)量

C.算法程序中的語(yǔ)句或指令條數(shù)

D.算法在執(zhí)行過(guò)程中所需要的基本運(yùn)算次數(shù)

【分析】所謂算法的時(shí)間復(fù)雜度，是指執(zhí)行算法所需要的計(jì)算工作量。為了能夠比較客觀地反映出一個(gè)算法的效率，一個(gè)算法的工作量不僅應(yīng)該與所使用的計(jì)算機(jī)、程序設(shè)計(jì)語(yǔ)言以及程序編制者無(wú)關(guān)，而且還應(yīng)該與算法實(shí)現(xiàn)過(guò)程中的許多細(xì)節(jié)無(wú)關(guān)。為此，可以用算法在執(zhí)行過(guò)程中所需基本運(yùn)算的執(zhí)行次數(shù)來(lái)度量算法的工作量。

【答案】D

試題21

下列數(shù)據(jù)結(jié)構(gòu)中，屬于非線性結(jié)構(gòu)的是（ ）。

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

B.帶鏈隊(duì)列

C.二叉樹(shù)

D.帶鏈棧

【分析】線性結(jié)構(gòu)滿足兩個(gè)條件：有且僅有一個(gè)根結(jié)點(diǎn)；每個(gè)結(jié)點(diǎn)最多有一個(gè)直接前驅(qū)，也最多有一個(gè)直接后繼。棧和隊(duì)列均滿足這兩個(gè)條件，屬于線性結(jié)構(gòu)。二叉樹(shù)屬于非線性結(jié)構(gòu)，因?yàn)槌巳~子結(jié)點(diǎn)外，其他每個(gè)結(jié)點(diǎn)都可以有兩個(gè)直接后繼，不滿足線性結(jié)構(gòu)的條件。

【答案】C

試題22

下列數(shù)據(jù)結(jié)構(gòu)中，能按照“先進(jìn)后出”原則存取數(shù)據(jù)的是（ ）。

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

B.棧

C.隊(duì)列

D.二叉樹(shù)

【分析】棧是一種特殊的線性表，其插入或者刪除運(yùn)算都在表的一端進(jìn)行，即按照“先進(jìn)后出”原則存取數(shù)據(jù)。

【答案】B

試題23

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

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

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

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

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

【分析】在循環(huán)隊(duì)列中用隊(duì)尾指針（rear）指向隊(duì)列中的隊(duì)尾元素，用隊(duì)頭指針（front）指向隊(duì)頭元素的前一個(gè)位置。在循環(huán)隊(duì)列結(jié)構(gòu)中，一般情況下rear>front。當(dāng)存儲(chǔ)空間的最后一個(gè)位置已被使用，而要進(jìn)行入隊(duì)操作時(shí)，只要存儲(chǔ)空間的第一個(gè)位置空閑，便可將元素加入第一個(gè)位置，即存儲(chǔ)空間的第一個(gè)位置為隊(duì)尾，此時(shí)便有front>rear。

【答案】D

試題24

算法的空間復(fù)雜度是指（ ）。

A.算法在執(zhí)行過(guò)程中所需要的計(jì)算機(jī)存儲(chǔ)空間

B.算法所處理的數(shù)據(jù)量

C.算法程序中的語(yǔ)句或指令條數(shù)

D.算法在執(zhí)行過(guò)程中所需要的臨時(shí)工作單元數(shù)

【分析】算法的空間復(fù)雜度是指算法在執(zhí)行過(guò)程中所需要的計(jì)算機(jī)存儲(chǔ)空間。

【答案】A

試題25

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

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)

【分析】棧是限定僅在表尾進(jìn)行插入和刪除操作的線性表，又稱為“后進(jìn)先出”的線性表。隊(duì)列是限定了插入和刪除操作的線性表，又稱為“先進(jìn)先出”的線性表。循環(huán)隊(duì)列是隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)。線性表（無(wú)論有序還是無(wú)序）既可以采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

【答案】D

試題26

支持子程序調(diào)用的數(shù)據(jù)結(jié)構(gòu)是（ ）。

A.棧

B.樹(shù)

C.隊(duì)列

D.二叉樹(shù)

【分析】棧是一種只允許在一端進(jìn)行插入和刪除的線性表，它是一種操作受限的線性表；隊(duì)列是一種只允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的線性表，它也是一種操作受限的線性表；二叉樹(shù)是有限元素的集合，該集合或者為空，或者由一個(gè)稱為根的元素及兩個(gè)不相交的、被分別稱為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。這里只有棧支持子程序調(diào)用。

【答案】A

試題27

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

A.10

B.8

C.6

D.4

【分析】在任意一棵二叉樹(shù)中，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個(gè)。本題中度為2的結(jié)點(diǎn)數(shù)為5，故葉子結(jié)點(diǎn)數(shù)為5+1=6個(gè)。

【答案】C

試題28

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

A.冒泡排序

B.簡(jiǎn)單選擇排序

C.直接插入排序

D.堆排序

【分析】對(duì)于長(zhǎng)度為n的線性表，在最壞情況下，快速排序所需要的比較次數(shù)為n*(n-1)/2；冒泡排序所需要的比較次數(shù)為n*(n-1)/2；直接插入排序所需要的比較次數(shù)為n*(n-1)/2；堆排序所需要的比較次數(shù)為O(nlog2n)。

【答案】D

試題29

一個(gè)棧的初始狀態(tài)為空。現(xiàn)將元素1、2、3、4、5、A、B、C、D、E依次入棧，然后再依次出棧，則元素出棧的順序是（ ）。

A.12345ABCDE

B.EDCBA54321

C.ABCDE12345

D.54321EDCBA

【分析】棧是一種特殊的線性表，這種線性表只能在固定的一端進(jìn)行插入和刪除操作，允許插入和刪除的一端稱為棧頂，另一端稱為棧底。一個(gè)新元素只能從棧頂一端進(jìn)入，刪除時(shí)，只能刪除棧頂?shù)脑兀磩倓偙徊迦氲脑亍＿@表明棧的運(yùn)算規(guī)則是“先進(jìn)后出”或稱“后進(jìn)先出”。在棧頂進(jìn)行插入運(yùn)算，稱為進(jìn)棧（或入棧），在棧頂進(jìn)行刪除運(yùn)算，稱為退棧（或出棧）。本題中，依次進(jìn)棧，即依次插入元素1、2、3、4、5、A、B、C、D、E，依次出棧，即依次刪除元素，根據(jù)棧“先進(jìn)后出”的規(guī)則，應(yīng)該以倒序出棧，即元素出棧順序?yàn)镋DCBA54321。

【答案】B

試題30

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

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

【分析】所謂循環(huán)隊(duì)列，就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第1個(gè)位置，形成邏輯上的環(huán)狀空間，供隊(duì)列循環(huán)使用。循環(huán)隊(duì)列的頭指針front指向隊(duì)列第一個(gè)元素的前一位置，隊(duì)尾指針rear指向隊(duì)列最后一個(gè)元素，循環(huán)隊(duì)列的動(dòng)態(tài)變化需要頭尾指針共同反映。因?yàn)檠h(huán)隊(duì)列的長(zhǎng)度是(rear-front+MaxSize)%MaxSize，所以循環(huán)隊(duì)列的長(zhǎng)度由隊(duì)頭和隊(duì)尾指針共同決定。

【答案】D

試題31

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

A.O(n)

B.O(n2)

C.O(log2n)

D.O(nlog2n)

【分析】二分法檢索要求線性表結(jié)點(diǎn)按關(guān)鍵值排序，且以順序方式存儲(chǔ)。在查找時(shí)，應(yīng)與表的中間位置上結(jié)點(diǎn)的關(guān)鍵值比較，若相等則檢索成功；否則根據(jù)比較結(jié)果確定下一步在表的前半部分或后半部分繼續(xù)進(jìn)行。二分法檢索的效率比較高，設(shè)線性表有n個(gè)元素，則最多的檢索次數(shù)為大于log2n的最小整數(shù)，最少的檢索次數(shù)為1。

【答案】C

試題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ǔ)有續(xù)表，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不能存儲(chǔ)有序表

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

【分析】順序存儲(chǔ)結(jié)構(gòu)就是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)該線性表中的各個(gè)元素；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)序號(hào)是不連續(xù)的，并且各結(jié)點(diǎn)在存儲(chǔ)空間中的位置關(guān)系與邏輯關(guān)系也不一致。兩者都可以存儲(chǔ)線性的、有序的邏輯結(jié)構(gòu)。順序結(jié)構(gòu)使用的是連續(xù)物理空間，鏈?zhǔn)浇Y(jié)構(gòu)可以使用零散的物理空間存儲(chǔ)，鏈?zhǔn)浇Y(jié)構(gòu)更靈活，不存在哪個(gè)更節(jié)約空間的說(shuō)法。

【答案】A