國(guó)家二級(jí)C++機(jī)試（數(shù)據(jù)結(jié)構(gòu)與算法）

模擬試卷第1套

一、選擇題（本題共19題，每題1.0分，共19分。）

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

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

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

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

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

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

知識(shí)之解析A：算法的空間復(fù)雜度是指執(zhí)行這個(gè)算法所需耍的內(nèi)存空間。這個(gè)內(nèi)存空

間包括算法程序所占的空問(wèn)，輸入的初始數(shù)據(jù)所占的存儲(chǔ)空間以及算法執(zhí)行過(guò)程中

所需要的額外空間V

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

A、一個(gè)算法的空間復(fù)雜度大，則其時(shí)間復(fù)雜度也必定大

B、一個(gè)算法的空間復(fù)雜度大，則其時(shí)間復(fù)雜度必定小

C、一個(gè)算法的時(shí)間復(fù)雜度大，則其空間復(fù)雜度必定小

D、算法的時(shí)間復(fù)雜度與空間復(fù)雜度沒(méi)有直接關(guān)系

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

知識(shí)點(diǎn)解析：算法的復(fù)雜度.主要包括時(shí)間復(fù)雜度和空間復(fù)雜度。算法的時(shí)間復(fù)雜度

是指執(zhí)行算法所需要的計(jì)算工作量，算法的工作量用算法所執(zhí)行的基本運(yùn)算次數(shù)來(lái)

度量，而算法所執(zhí)行的基本運(yùn)算次數(shù)是問(wèn)題規(guī)模的函數(shù)，即算法的工作量=4可，

其中n是問(wèn)題的規(guī)模：算法的空間復(fù)雜度，一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空

間。一個(gè)算法所占用的存儲(chǔ)空間包括算法程序所占用的空間、輸入的初始數(shù)據(jù)所占

的存儲(chǔ)空間以及算法執(zhí)行過(guò)程中所需要的額外空間。根據(jù)各自的定義可知，算法的

時(shí)間復(fù)雜度與空間復(fù)雜度并不相關(guān)。

3、下列描述中正確的是（）。

A、線性鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

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

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

D、只有根結(jié)點(diǎn)的二義樹(shù)是線性結(jié)構(gòu)

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

知識(shí)點(diǎn)解析：線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的基本單

位稱為存儲(chǔ)結(jié)點(diǎn)，每個(gè)存儲(chǔ)結(jié)點(diǎn)包括數(shù)據(jù)域和指針域兩個(gè)組成部分。各數(shù)據(jù)元素之

間的前后件關(guān)系是由各結(jié)點(diǎn)的指針域來(lái)指示的，指向線性表中第一結(jié)點(diǎn)的指針

HEAD稱為頭指針，當(dāng)HEAD=NULL時(shí)稱為空表。棧、隊(duì)列和雙向鏈表是線性結(jié)

構(gòu)，樹(shù)是一種簡(jiǎn)單的非線性結(jié)構(gòu)。在樹(shù)這種數(shù)據(jù)結(jié)構(gòu)中，所有數(shù)據(jù)元素的關(guān)系具有

明顯的層次特征。二叉樹(shù)是非線性結(jié)構(gòu)。線性結(jié)構(gòu)和非線性結(jié)構(gòu)是從數(shù)據(jù)的邏輯結(jié)

構(gòu)角度來(lái)講的，與該數(shù)據(jù)結(jié)構(gòu)中有多少個(gè)元素沒(méi)有關(guān)系，即使是空的二叉樹(shù)也是非

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

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

A、棧

B、樹(shù)

C、隊(duì)列

D、二又樹(shù)

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

知識(shí)點(diǎn)解析：棧是一種限定在一端進(jìn)行插入與刪除的線性表。在主函數(shù)調(diào)用予函數(shù)

時(shí)，要首先保存主函數(shù)當(dāng)前的狀態(tài)，然后轉(zhuǎn)去執(zhí)行子函數(shù)，把子函數(shù)的運(yùn)行結(jié)果返

回到主函數(shù)調(diào)用子函數(shù)時(shí)的位在，主函數(shù)再接著往下執(zhí)行，這種過(guò)程符合棧的特

點(diǎn)。所以一般采用棧式存儲(chǔ)方式。

5、下列關(guān)于棧的敘述中，正確的是（"

A、棧底元素一定是最后入棧的元素

B、棧頂元素一定是最先入棧的元素

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

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

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

知識(shí)點(diǎn)解析：棧是限定只能在表的一端進(jìn)行插入和刪除操作的線性表，必須按“后

進(jìn)先出”的規(guī)則操作元素。

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

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

B、隊(duì)列按“先進(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)后出”的線性表。

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

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

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

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

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

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

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

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

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

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ì)列。

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

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)。

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

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ù)量。

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

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ǔ)

空間要大一些。

12、某系統(tǒng)總體結(jié)構(gòu)圖如下圖所示：MU該系統(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)圖是一棵樹(shù)結(jié)構(gòu)，在樹(shù)結(jié)構(gòu)中，根結(jié)點(diǎn)在第1層，

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

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

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

A、10

B、8

C、6

D、4

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

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

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

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

點(diǎn)數(shù)為（）。

A、219

B、221

C、229

D、231

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

知識(shí)點(diǎn)解析：在二叉樹(shù)中，葉子結(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ù)十度為1的結(jié)點(diǎn)數(shù)十度為2的結(jié)點(diǎn)數(shù)=70+80+69=219。

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

子結(jié)點(diǎn)數(shù)為（）。

A、8

B、7

C、6

D、5

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

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

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

A、DYBEAFCZX

B、YDEBFZXCA

C、ABDYECFXZ

D、ABCDEFXYZ

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

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

①訪問(wèn)根結(jié)點(diǎn)；②前序遍歷左子樹(shù)；③前序遍歷石子樹(shù)?？梢?jiàn)，前序遍歷二叉樹(shù)

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

ABDYECFXZo

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

（）o

A、63

B、64

C、6

D、7

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

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

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

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

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

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

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

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

度。

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

確的是()。

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

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

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

D、快速排序?yàn)閚(n—1)/2

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

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

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

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

此，稱為快速排序法。

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

A、冒泡排序

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

C、直接插入排序

D、堆排序

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

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

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

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

國(guó)家二級(jí)C++機(jī)試(數(shù)據(jù)結(jié)構(gòu)與算法)

模擬試卷第2套

一、選擇題(本題共22題，每題1.0分，共22分。)

1算法的有窮性是指

A、算法程序的運(yùn)行時(shí)間是有限的

B、算法程序所處理的數(shù)據(jù)量是有限的

C、算法程序的長(zhǎng)度是有限的

D、算法只能被有限的用戶使用

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

知識(shí)點(diǎn)解析：算法的有窮性，是指算法必須能在有限的時(shí)間內(nèi)做完，即算法必須能

在執(zhí)行有限個(gè)步驟之后終止。

2、下列敘述中正確的是

A、算法就是程序

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

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

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

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

知識(shí)點(diǎn)解析：所謂算法是指解題方案的準(zhǔn)確而完整的描述。是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算

順序的規(guī)則，并且每一個(gè)規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下

終止。算法不等于程序，也不等于計(jì)算方法。設(shè)計(jì)算法時(shí)不僅要考慮對(duì)數(shù)據(jù)對(duì)象的

運(yùn)算和操作，還要考慮算法的控制結(jié)構(gòu)。

3、算法的時(shí)間豆雜度是指

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

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

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

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

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

知識(shí)點(diǎn)解析：算法的時(shí)間復(fù)雜度，是指執(zhí)行算法所需要的計(jì)算工作量。算法的工作

量可以用算法在執(zhí)行過(guò)程中所需基本運(yùn)算的執(zhí)行次數(shù)來(lái)度量。

4、下列敘述中正確的是

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)

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

知識(shí)點(diǎn)解析：算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量。算法的工作量

用算法所執(zhí)行的基本運(yùn)算的次數(shù)來(lái)度量，而算法所執(zhí)行的基本運(yùn)算次數(shù)是問(wèn)題規(guī)模

的函數(shù)；算法的空間復(fù)雜度一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。算法的時(shí)間

復(fù)雜度與空間復(fù)雜度并不相關(guān)c數(shù)據(jù)的邏輯結(jié)構(gòu)就是數(shù)據(jù)元素之間的邏輯關(guān)系.它

是從邏輯上描述數(shù)據(jù)元素之間的關(guān)系，是獨(dú)立于計(jì)算機(jī)的；數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是研究

數(shù)據(jù)元素和數(shù)據(jù)元素之間的關(guān)系如何在計(jì)算機(jī)中表示，它們并非一對(duì)應(yīng)。算法的執(zhí)

行效率不僅與問(wèn)題的規(guī)模有關(guān)，還與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有關(guān)。

5、下列敘述中正確的是

A、一個(gè)算法的空間復(fù)雜度大，則其時(shí)間復(fù)雜度也必定大

B、一個(gè)算法的空間復(fù)雜度大，則其時(shí)間復(fù)雜度必定小

C、一個(gè)算法的時(shí)間復(fù)雜度大，則其空間復(fù)雜度必定小

D、算法的時(shí)間復(fù)雜度與空間復(fù)雜度沒(méi)有直接關(guān)系

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

知識(shí)點(diǎn)解析：算法的復(fù)雜度主要包括時(shí)間復(fù)雜度和空間復(fù)雜度。算法的時(shí)間復(fù)雜度

是指執(zhí)行算法所需要的計(jì)算工作量，算法的工作量用算法所執(zhí)行的基本運(yùn)算次數(shù)來(lái)

度量，而算法所執(zhí)行的基本運(yùn)算次數(shù)是問(wèn)題規(guī)模的函數(shù)，即算法的工作量=的力

其中n是問(wèn)題的規(guī)模；算法的空間復(fù)雜度，一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空

間。一個(gè)算法所占用的存儲(chǔ)空間包括算法程序所占用的空間、輸入的初始數(shù)據(jù)所占

的存儲(chǔ)空間以及算法執(zhí)行過(guò)程中所需要的額外空間。根據(jù)各自的定義可知，算法的

時(shí)間復(fù)雜度與空間復(fù)雜度并不相關(guān)。

6、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指

A、存儲(chǔ)在外存中的數(shù)據(jù)

B、數(shù)據(jù)所占的存儲(chǔ)空間量

C、數(shù)據(jù)在計(jì)算機(jī)中的順序存儲(chǔ)方式

D、數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示

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

知識(shí)點(diǎn)解析：在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即為數(shù)據(jù)

的存儲(chǔ)結(jié)構(gòu)。

7、下列描述中正確的是

A、一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)只能有一種存儲(chǔ)結(jié)構(gòu)

B、數(shù)據(jù)的邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)屬于豐線性結(jié)構(gòu)

C、一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，旦各種存儲(chǔ)結(jié)構(gòu)不影響數(shù)據(jù)處理的效

率

D、一個(gè)邏倡數(shù)據(jù)結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，且各種存儲(chǔ)結(jié)構(gòu)影響數(shù)據(jù)處理的效率

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

知識(shí)點(diǎn)解析：數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系：

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系。數(shù)據(jù)

的存儲(chǔ)結(jié)構(gòu)是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示，一種邏輯結(jié)構(gòu)可以表示成多種

存儲(chǔ)結(jié)構(gòu)；而采用不同的存儲(chǔ)結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。

8、下列描述中正確的是

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

B、由于計(jì)算機(jī)存儲(chǔ)空間是向量式的存儲(chǔ)結(jié)構(gòu)，因此，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)一定是線性

結(jié)構(gòu)

C、程序設(shè)計(jì)語(yǔ)言中的數(shù)據(jù)一般是順序存儲(chǔ)結(jié)構(gòu)，因此，利用數(shù)組只能處理線性結(jié)

構(gòu)

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

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

知識(shí)點(diǎn)解析：數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的

邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（也稱數(shù)據(jù)的物理結(jié)

構(gòu)）。一般來(lái)說(shuō)，一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲(chǔ)結(jié)構(gòu)，常用的

存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引等。

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

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

B、帶鏈隊(duì)列

C、二叉樹(shù)

D、帶鏈棧

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

知識(shí)點(diǎn)解析：根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間的前后件關(guān)系的復(fù)雜程度，一般將數(shù)

據(jù)結(jié)構(gòu)分為兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。循環(huán)隊(duì)列、帶鏈隊(duì)列和帶鏈棧都是線

性結(jié)構(gòu)，而二叉樹(shù)是非線性結(jié)構(gòu)。

10、下列描述中正確的是

A、線性鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

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

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

D、只有根結(jié)點(diǎn)的二叉樹(shù)是線性結(jié)構(gòu)

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

知識(shí)點(diǎn)解析：線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的基本單

位稱為存儲(chǔ)結(jié)點(diǎn)，每個(gè)存儲(chǔ)結(jié)點(diǎn)包括數(shù)據(jù)域和指針域兩個(gè)組成部分。各數(shù)據(jù)元素之

間的前后件關(guān)系是由各結(jié)點(diǎn)的指針域來(lái)指示的，指向線性表中第一結(jié)點(diǎn)的指針

HEAD稱為頭指針，當(dāng)HEAD=NULL時(shí)稱為空表。棧、隊(duì)列和雙向鏈表是線性結(jié)

構(gòu)，樹(shù)是一種簡(jiǎn)單的非線性結(jié)構(gòu)。在樹(shù)這種數(shù)據(jù)結(jié)構(gòu)中，所有數(shù)據(jù)元素的關(guān)系具有

明顯的層次特征。二叉樹(shù)是非線性結(jié)構(gòu)。線性結(jié)構(gòu)和非線性結(jié)構(gòu)是從數(shù)據(jù)的邏輯結(jié)

構(gòu)角度來(lái)講的，與該數(shù)據(jù)結(jié)構(gòu)中有多少個(gè)元素沒(méi)有關(guān)系，即使是空的二叉樹(shù)也是非

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

11、下面敘述中正確的是

A、線性表是線性結(jié)構(gòu)

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

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

D、二叉樹(shù)是線性結(jié)構(gòu)

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

知識(shí)點(diǎn)解析：線性表是最簡(jiǎn)單的、最常用的一種線件結(jié)構(gòu)C所謂線性鏈表指的是采

用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表。棧和隊(duì)列其實(shí)是一種特殊的線性表。樹(shù)是一種簡(jiǎn)單的非

線性結(jié)構(gòu)，二叉樹(shù)是樹(shù)的一種。

12、下列關(guān)于棧的敘述正確的是

A、棧按“先進(jìn)先出”組織數(shù)據(jù)

B、棧按“先進(jìn)后出”組織數(shù)據(jù)

C、只能在棧底插入數(shù)據(jù)

D、不能刪除數(shù)據(jù)

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

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

的一端稱為棧頂，另一端稱為棧底。棧是按照“先進(jìn)后出''的原則組織數(shù)據(jù)的。

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

A^棧

B、樹(shù)

C、隊(duì)列

D、二叉樹(shù)

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

知識(shí)點(diǎn)解析：棧是一種限定在一端進(jìn)行插入與刪除的線性表。在主函數(shù)調(diào)用子函數(shù)

時(shí)，要首先保存主函數(shù)當(dāng)前的狀態(tài)，然后轉(zhuǎn)去執(zhí)行子函數(shù)。把子函數(shù)的運(yùn)行結(jié)果返

回到主函數(shù)調(diào)用了函數(shù)時(shí)的位置，主函數(shù)再接著往下執(zhí)行，這種過(guò)程符合棧的特

點(diǎn)。所以一般采用棧式存儲(chǔ)方式。

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

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

B、棧

C、隊(duì)列

D、二叉樹(shù)

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

知識(shí)點(diǎn)解析：棧按照“先進(jìn)后出”(FILO)或“后進(jìn)先出”(LIFO)組織數(shù)據(jù)；隊(duì)列是“先進(jìn)

先出”F(IFO)或“后進(jìn)后出”(LILO)的線性表。

15、下列關(guān)于棧敘述正確的是

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

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

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

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

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

知識(shí)點(diǎn)解析：棧是先進(jìn)后出的線性表，棧頂?shù)脑刈钕缺粍h除，棧底的元素最后被

刪除。

16、下列關(guān)于棧的敘述中，正確的是

A、棧底元素一定是最后入棧的元素

B、棧頂元素一定是最先入棧的元素

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

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

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

知識(shí)點(diǎn)。析：棧是限定只能在表的一端進(jìn)行插入和刪除操作的線性表，必須按“后

進(jìn)先出”的規(guī)則操作元素。

17、一個(gè)棧的初始狀態(tài)為空?，F(xiàn)將元素1、2、3、4、5、A、B、C、D、E依次入

棧，然后再依次出棧，則元素出棧的順序是

A、12345ABCDE

B、EDCBA54321

C、ABCDE12345

D、54321EDCBA

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

知識(shí)點(diǎn)解析：棧是按照“先進(jìn)后出”或“后進(jìn)先出”的原則組織數(shù)據(jù)的。所以出棧順序

是EDCBA54321。

18、棧的初始狀態(tài)為空?，F(xiàn)將元素1,2,3,A,B,C依次入棧，再依次出棧，

則元素出棧的順序是

A、1,2,3,A,B,C

B、C,B,A,1,2,3

C、C,B,A,3,2,1

D、1,2,3,C,B,A

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

知識(shí)點(diǎn)詞析：棧是按照“先進(jìn)后出''或"后進(jìn)先出”的原則組織數(shù)據(jù)的。所以出棧順序

是CBA321。

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

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

B、隊(duì)列按“先進(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)后出”的線性表。

20、下列敘述中正確的是

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

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

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

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

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

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

構(gòu)。

21、下列敘述中正確的是

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)。

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

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

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

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

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

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

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

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

國(guó)家二級(jí)C++機(jī)試（數(shù)據(jù)結(jié)構(gòu)與算法）

模擬試卷第3套

一、選擇題（本題共24題，每題1.0分，共24分。）

1、下列敘述中正確的是

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)變化也是通過(guò)隊(duì)頭指針和隊(duì)尾指針來(lái)反映的。

2、對(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ì)頭指針front指向隊(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或from等于隊(duì)列的長(zhǎng)度加1時(shí)，就

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

以小于隊(duì)尾指針。

3、下列敘述中正確的是

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ì)列。

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

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

A、15

B、16

C、20

D、0或35

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

知識(shí)析：循環(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。

5、在一個(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)解析:循環(huán)隊(duì)列中，rear表示尾指針，front表示頭指針,當(dāng)有元素入隊(duì)時(shí),

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

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

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

6、下列敘述中正確的是

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)的線性表稱之為線性鏈表。

7、下列與隊(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ì)列中最先插入的元素將最先被刪除，最后插入的元素將最后被刪

除。

8、下列敘述中正確的是

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ì)頭指針from指向隊(duì)頭元素的前一個(gè)位置，因此，隊(duì)列中的

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

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

9、下列關(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)系是由指針域來(lái)確定的。

10、下列敘述中正確的是

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ǔ)

空間要大一些。

II、下列敘述中正確的是

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ǔ)

空間要大一些。

12,下列敘述中正確的是

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、上述三種說(shuō)法都不對(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ǔ)空間要大一些。

13、下列對(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)解析：一?般來(lái)說(shuō)，在線性表的鏈?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)的指針域來(lái)指示的，指向線性表中第

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

14、下列敘述中正確的是

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)系來(lái)體現(xiàn)。

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

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

A、二叉鏈表

B、循環(huán)鏈表

C、雙向鏈表

D、帶鏈的棧

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

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

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

16、下列敘述中正確的是

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ù)這類的的數(shù)據(jù)結(jié)構(gòu)只有一個(gè)根結(jié)點(diǎn)，但它不是線性

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

17、某系統(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)圖是一棵樹(shù)結(jié)構(gòu)，在樹(shù)結(jié)構(gòu)中，根結(jié)點(diǎn)在第1層，

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

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

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

A^n+1

B、n-1

C、2n

D、n/2

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

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

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

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

A、10

B、8

C、6

D、4

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

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

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

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

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

A、219

B、229

C、230

D、231

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

知識(shí)點(diǎn)解析：根據(jù)二叉樹(shù)的性質(zhì)，在任意二叉樹(shù)中，度為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、一棵二叉樹(shù)中共有70個(gè)葉子結(jié)點(diǎn)與80個(gè)度為1的結(jié)點(diǎn)，則該二叉樹(shù)中的總結(jié)

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

A、219

B、221

C、229

D、231

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

知識(shí)點(diǎn)解析：在二叉樹(shù)中，葉子結(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、某二叉樹(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

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

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

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

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

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

點(diǎn)在第1層）

A、3

B、6

C、8

D、12

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

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

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

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

24、設(shè)樹(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二叉樹(shù)其總結(jié)點(diǎn)數(shù)為2nLi=24-1=150總結(jié)點(diǎn)數(shù)減去度為

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

國(guó)家二級(jí)C++機(jī)試（數(shù)據(jù)結(jié)構(gòu)與算法）

模擬試卷第4套

一、選擇題（本題共24題，每題1.0分，共24分。）

1、算法的有窮性是指

A、算法程序的運(yùn)行時(shí)間是有限的

B、算法程序所處理的數(shù)據(jù)量是有限的

C、算法程序的長(zhǎng)度是有限的

D、算法只能被有限的用戶使用

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

知識(shí)點(diǎn)解析：算法的有窮性，是指算法必須能在有限的時(shí)間內(nèi)做完，即算法必須能

在執(zhí)行有限個(gè)步驟之后終止。

2、下列敘述中正確的是

A、算法就是程序

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

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

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

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

知識(shí)點(diǎn)解析：所謂算法是指解題方案的準(zhǔn)確而完整的描述。是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算

順序的規(guī)則，并且每一個(gè)規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下

終止。算法不等于程序，也不等于計(jì)算方法。設(shè)計(jì)算法時(shí)不僅要考慮對(duì)數(shù)據(jù)對(duì)象的

運(yùn)算和操作，還要考慮算法的控制結(jié)構(gòu)。

3、算法的空間復(fù)雜度是指

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

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

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

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

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

知識(shí)點(diǎn)解析：算法的空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。這個(gè)內(nèi)存空

間包括算法程序所占的空間，輸入的初始數(shù)據(jù)所占的存儲(chǔ)空間以及算法執(zhí)行過(guò)程中

所需要的額外空間。

4、算法的時(shí)間復(fù)雜度是指

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

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

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

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

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

知識(shí)點(diǎn)解析：算法的時(shí)間復(fù)雜度，是指執(zhí)行算法所需要的計(jì)算工作量。算法的工作

量可以用算法在執(zhí)行過(guò)程中所需基本運(yùn)算的執(zhí)行次數(shù)來(lái)度量。

5、下列敘述中正確的是

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)

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

知識(shí)點(diǎn)解析：算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量。算法的工作量

用算法所執(zhí)行的基本運(yùn)算的次數(shù)來(lái)度量，而算法所執(zhí)行的基本運(yùn)算次數(shù)是問(wèn)題規(guī)模

的函數(shù)；算法的空間復(fù)雜度一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。算法的時(shí)間

復(fù)雜度與空間復(fù)雜度并不相關(guān)。數(shù)據(jù)的邏輯結(jié)構(gòu)就是數(shù)據(jù)元素之間的邏輯關(guān)系，它

是從邏輯上描述數(shù)據(jù)元素之間的關(guān)系，是獨(dú)立于計(jì)算機(jī)的：數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是研究

數(shù)據(jù)元素和數(shù)據(jù)元素之間的關(guān)系如何在計(jì)算機(jī)中表示，它們并非一一對(duì)應(yīng)。算法的

執(zhí)行效率不僅與問(wèn)題的規(guī)模有關(guān)，還與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有關(guān)。

6、下列敘述中正確的是

A、一個(gè)算法的空間復(fù)雜度大，則其時(shí)間熨雜度也必定大

B、一個(gè)算法的空間復(fù)雜度大，則其時(shí)間復(fù)雜度必定小

C、一個(gè)算法的時(shí)間復(fù)雜度大，則其空間復(fù)雜度必定小

D、算法的時(shí)間復(fù)雜度與空間復(fù)雜度沒(méi)有直接關(guān)系

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

知識(shí)點(diǎn)解析：算法的復(fù)雜度主要包括時(shí)間復(fù)雜度和空間復(fù)雜度。算法的時(shí)間復(fù)雜度

是指執(zhí)行算法所需要的計(jì)算工作量，算法的工作量用算法所執(zhí)行的基本運(yùn)算次數(shù)來(lái)

度量，而算法所執(zhí)行的基本運(yùn)算次數(shù)是問(wèn)題規(guī)模的函數(shù)，即算法的工作量二f(N，

其中n是問(wèn)題的規(guī)模：算法的空間復(fù)雜度，一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空

間。一個(gè)算法所占用的存儲(chǔ)空間包括算法程序所占用的空間、輸入的初始數(shù)據(jù)所占

的存儲(chǔ)空間以及算法執(zhí)行過(guò)程中所需要的額外空間。根據(jù)各自的定義可知，算法的

時(shí)間復(fù)雜度與空間復(fù)雜度并不相關(guān)。

7、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指

A、存儲(chǔ)在外存中的數(shù)據(jù)

B、數(shù)據(jù)所占的存儲(chǔ)空間量

C、數(shù)據(jù)在計(jì)算機(jī)中的順序存儲(chǔ)方式

D、數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示

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

知識(shí)點(diǎn)解析：在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即為數(shù)據(jù)

的存儲(chǔ)結(jié)構(gòu)。

8、下列描述中正確的是

A、一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)只能有一種存儲(chǔ)結(jié)構(gòu)

B、數(shù)據(jù)的邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)屬于非線性結(jié)構(gòu)

C、一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，且各種存儲(chǔ)結(jié)構(gòu)不影響數(shù)據(jù)處理的效

率

D、一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，且各種存儲(chǔ)結(jié)構(gòu)影響數(shù)據(jù)處理的效率

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

知識(shí)之解析D：數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系；

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系。數(shù)據(jù)

的存儲(chǔ)結(jié)構(gòu)是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示，一種邏輯結(jié)構(gòu)可以表示成多種

存儲(chǔ)結(jié)構(gòu)；而采用不同的存儲(chǔ)結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。

9、下列描述中正確的是

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

B、由于計(jì)算機(jī)存儲(chǔ)空間是向量式的存儲(chǔ)結(jié)構(gòu)，因此，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)一定是線性

結(jié)構(gòu)

C、程序設(shè)計(jì)語(yǔ)言中的數(shù)據(jù)一般是順序存儲(chǔ)結(jié)構(gòu)，因此，利用數(shù)組只能處理線性結(jié)

構(gòu)

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

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

知識(shí)點(diǎn)解析：數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的

邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（也稱數(shù)據(jù)的物理結(jié)

構(gòu)）。一般來(lái)說(shuō)，一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲(chǔ)結(jié)構(gòu)，常用的

存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引等。

10、下列敘述中正確的是

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ù)這類的數(shù)據(jù)結(jié)構(gòu)只有一個(gè)根結(jié)點(diǎn)，但它不是線性結(jié)

構(gòu)。

11、下列描述中正確的是

A、線性鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

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

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

D、只有根結(jié)點(diǎn)的二叉樹(shù)是線性結(jié)構(gòu)

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

知識(shí)點(diǎn)解析：線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的基本單

位稱為存儲(chǔ)結(jié)點(diǎn)，每個(gè)存儲(chǔ)結(jié)點(diǎn)包括數(shù)據(jù)域和指針域兩個(gè)組成部分。各數(shù)據(jù)元素之

間的前后件關(guān)系是由各結(jié)點(diǎn)的指針域來(lái)指示的，指向線性表中第一結(jié)點(diǎn)的指針

HEAD稱為頭指針，當(dāng)HEAD=NULL時(shí)稱為空表。棧、隊(duì)列和雙向鏈表是線性結(jié)

構(gòu)，樹(shù)是一種簡(jiǎn)單的非線性結(jié)構(gòu)。在樹(shù)這種數(shù)據(jù)結(jié)構(gòu)中，所有數(shù)據(jù)元素的關(guān)系具有

明顯的層次特征。二叉樹(shù)是非線性結(jié)構(gòu)。線性結(jié)構(gòu)和非線性結(jié)構(gòu)是從數(shù)據(jù)的邏輯結(jié)

構(gòu)角度來(lái)講的，與該數(shù)據(jù)結(jié)構(gòu)中有多少個(gè)元素沒(méi)有關(guān)系，即使是空的二叉樹(shù)也是非

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

12、下面敘述中正確的是

A、線性表是線性結(jié)構(gòu)

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

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

D、二叉樹(shù)是線性結(jié)構(gòu)

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

知識(shí)點(diǎn)解析：線性表是最簡(jiǎn)單的、最常用的一種線性結(jié)構(gòu)。所謂線性鏈表指的是采

用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表。棧和隊(duì)列其實(shí)是一種特殊的線性表。樹(shù)是一種簡(jiǎn)單的非

線性結(jié)構(gòu)，二叉樹(shù)是樹(shù)的一種。

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

A、棧

B、樹(shù)

C、隊(duì)列

D、二叉樹(shù)

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

知識(shí)點(diǎn)解析：棧是一種限定在一端進(jìn)行插入與刪除的線性表。在主函數(shù)調(diào)用子函數(shù)

時(shí)?，要首先保存主函數(shù)當(dāng)前的狀態(tài)，然后轉(zhuǎn)去執(zhí)行子函數(shù)，把子函數(shù)的運(yùn)行結(jié)果返

回到主函數(shù)調(diào)用子函數(shù)時(shí)的位置，主函數(shù)再接著往下執(zhí)行，這種過(guò)程符合棧的特

點(diǎn)。所以一般采用棧式存儲(chǔ)方式。

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

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

B、棧

C、隊(duì)列

D、二叉樹(shù)

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

知識(shí)點(diǎn)解析：棧按照“先進(jìn)后出”(FILO)或“后進(jìn)先出”(LIFO)組織數(shù)據(jù)；隊(duì)列是“先進(jìn)

先出”F(IFO)或“后進(jìn)后出”(LILO)的線性表。

15、下列關(guān)于棧敘述正確的是

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

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

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

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

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

知識(shí)點(diǎn)解析：棧是先進(jìn)后出的線性表，棧頂?shù)脑刈钕缺粍h除，棧底的元素最后被

刪除。

16、下列關(guān)于棧的敘述中，正確的是

A、棧底元素一定是最后入棧的元素

B、棧頂元素一定是最先入棧的元素

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

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

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

知識(shí)點(diǎn)解析：棧是限定只能在表的一端進(jìn)行插入和刪除操作的線性表，必須按“后

進(jìn)先出”的規(guī)則操作元素。

17、下列敘述中正確的是

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

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

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

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

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

知識(shí)點(diǎn)解析：在棧中，允許插入與刪除的一端稱為棧頂，而不允許插入與刪除的另

一端稱為棧底。棧跟隊(duì)列不同，元素只能在棧項(xiàng)壓入或彈出，棧底指針不變，棧中

元素隨棧頂指針的變化而動(dòng)態(tài)變化，遵循后進(jìn)先出的規(guī)則。

18、一個(gè)棧的初始狀態(tài)為空?，F(xiàn)將元素1、2、3、4、5、A、B、C、D、E依次入

棧，然后再依次出棧，則元素出棧的順序是

A、12345ABCDE

B、EDCBA54321

C、ABCDE12345

D、54321EDCBA

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

知識(shí)點(diǎn)解析：棧是按照“先進(jìn)后出”或“后進(jìn)先出”的原則組織數(shù)據(jù)的。所以出棧順序

是EDCBA54321o

19、一個(gè)棧的初始狀態(tài)為空。現(xiàn)將元素1,2,3,A,B,C依次入棧，然后再依

次出棧，則元素出棧的順序是

A、1,2,3,A,B,C

B、C,B,A,1,2,3

C、C,B,A,3,2,1

D、1,2,3,C,B,A

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

知識(shí)點(diǎn)解析：棧是按照“先進(jìn)后出”或“后進(jìn)先出”的原則組織數(shù)據(jù)的「所以出棧順序

是CBA321。

20、下列關(guān)于棧的描述中錯(cuò)誤的是

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

B、棧只能順序存儲(chǔ)

C、棧具有記憶作用

D、對(duì)棧的插入與刪除操作中，不需要改變棧底指針

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

知識(shí)點(diǎn)解析：棧是限定在一端進(jìn)行插入與刪除的線性表。棧頂(lop)：插入數(shù)據(jù)(即

入棧)的一端；棧底(boltom)：不能入棧也不能出棧的一端。棧存儲(chǔ)數(shù)據(jù)的原則：

“先進(jìn)后出”或“后進(jìn)先出'棧的特性是具有記憶作用。

21、按照“后進(jìn)先出”原則組織數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是

A、隊(duì)列

B、棧

C、雙向鏈表

D、二叉樹(shù)

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

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

的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧頂元素總是最后被插入

的元素，也是最先被刪除的元素：棧底元素總是最先被插入的元素，也是最后才能

被刪除的元素。即棧是按照“后進(jìn)先出”(LastinFirstOut,簡(jiǎn)稱LIFO)或“先進(jìn)后

出“(FirstInLastOut,優(yōu)稱FILO)的原則組織數(shù)據(jù)的。因此，棧也稱為“后進(jìn)先出

表”或“先進(jìn)后出”表。

22、下列敘述中正確的是

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

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

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

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

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

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

構(gòu)。

23、下列敘述中正確的是

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)先出的線性表c根據(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)。

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

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

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

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

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

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

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

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

國(guó)家二級(jí)C++機(jī)試（數(shù)據(jù)結(jié)構(gòu)與算法）

模擬試卷第5套

一、選擇題（本題共18題，每題1.0分，共18分。）

1、算法的有窮性是指（）。

A、算法程序的運(yùn)行時(shí)間是有限的

B、算法程序所處理的數(shù)據(jù)量是有限的

C、算法程序的長(zhǎng)度是有限的

D、算法只能被有限的用戶使用

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

知識(shí)點(diǎn)解析：算法的有窮性，是指算法必須能在有限的時(shí)間內(nèi)做完，即算法必須能

在執(zhí)行有限個(gè)步驟之后終止。

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

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

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

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

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

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

知識(shí)點(diǎn)解析：算法的空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。這個(gè)內(nèi)存空

間包括算法程序所占的空間，輸入的初始數(shù)據(jù)所占的存儲(chǔ)空間以及算法執(zhí)行過(guò)程中

所需要的額外空間。

3、算法的時(shí)間復(fù)雜度是指（工

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

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

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

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

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

知識(shí)點(diǎn)解析：算法的時(shí)間復(fù)雜度，是指執(zhí)行算法所需要的計(jì)算工作量。算法的工作

量可以用算法在執(zhí)行過(guò)程中所需基本運(yùn)算的執(zhí)行次數(shù)來(lái)度量。

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

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)

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

知識(shí)點(diǎn)解析：算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量。算法的工作量

用算法所執(zhí)行的基本運(yùn)算的次數(shù)來(lái)度量，而算法所執(zhí)行的基本運(yùn)算次數(shù)是問(wèn)題規(guī)模

的函數(shù)；算法的空間復(fù)雜度一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。算法的時(shí)間

復(fù)雜度與空間復(fù)雜度并不相關(guān)。數(shù)據(jù)的邏輯結(jié)構(gòu)就是數(shù)據(jù)元素之間的邏輯關(guān)系，它

是從邏輯上描述數(shù)據(jù)元素之間的關(guān)系，是獨(dú)立于計(jì)算機(jī)的：數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是研究

數(shù)據(jù)元素和數(shù)據(jù)元素之間的關(guān)系如何在計(jì)算機(jī)中表示，它們并非一一對(duì)應(yīng)。算法的

執(zhí)行效率不僅與問(wèn)題的規(guī)模有關(guān)，還與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有關(guān)。

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

A、一個(gè)算法的空間復(fù)雜度大，則其時(shí)間復(fù)雜度也必定大

B、一個(gè)算法的空間復(fù)雜度大，則其時(shí)間復(fù)雜度必定小

C、一個(gè)算法的時(shí)間復(fù)雜度大，則其空間復(fù)雜度必定小

D、算法的時(shí)間復(fù)雜度與空間復(fù)雜度沒(méi)有直接關(guān)系

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

知識(shí)點(diǎn)解析：算法的復(fù)雜度主要包括時(shí)間復(fù)雜度和空間復(fù)雜度。算法的時(shí)間復(fù)雜度

是指執(zhí)行算法所需要的計(jì)算工作量，算法的工作量用算法所執(zhí)行的基本運(yùn)算次數(shù)來(lái)

度量，而算法所執(zhí)行的基本運(yùn)算次數(shù)是問(wèn)題規(guī)模的函數(shù)，即算法的工作量=f（nj,

其中n是問(wèn)題的規(guī)模；算法的空間復(fù)雜度，一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空

間。一個(gè)算法所占用的存儲(chǔ)空間包拈算法程序所占用的空間、輸入的初始數(shù)據(jù)所占

的存儲(chǔ)空間以及算法執(zhí)行過(guò)程中所需要的額外空間。根據(jù)各自的定義可知，算法的

時(shí)間復(fù)雜度與空間復(fù)雜度并不相關(guān)。

6、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指（）。

A、存儲(chǔ)在外存中的數(shù)據(jù)

B、數(shù)據(jù)所占的存儲(chǔ)空間量

C、數(shù)據(jù)在計(jì)算機(jī)中的順序存儲(chǔ)方式

D、數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示

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

知識(shí)點(diǎn)解析：在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即為數(shù)據(jù)

的存儲(chǔ)結(jié)構(gòu)。

7、下列描述中正確的是（）。

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

B、由于計(jì)算機(jī)存儲(chǔ)空間是向量式的存儲(chǔ)結(jié)構(gòu)，因此，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)一定是線性

結(jié)構(gòu)

C、程序設(shè)計(jì)語(yǔ)言中的數(shù)據(jù)一般是順序存儲(chǔ)結(jié)構(gòu)，因此，利用數(shù)組只能處理線性結(jié)

構(gòu)

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

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

知識(shí)點(diǎn)解析：數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的

邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（也稱數(shù)據(jù)的物理結(jié)

構(gòu)）。一般來(lái)說(shuō)，一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲(chǔ)結(jié)構(gòu)，常用的

存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引等。

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

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ù)這類的數(shù)據(jù)結(jié)構(gòu)只有一個(gè)根結(jié)點(diǎn)，但它不是線性結(jié)

構(gòu)。

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

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

B、帶鏈隊(duì)列

C、二又樹(shù)

D、帶鏈棧

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

知識(shí)點(diǎn)解析：根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間的前后件關(guān)系的復(fù)雜程度，一般將數(shù)

據(jù)結(jié)構(gòu)分為兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。循環(huán)隊(duì)列、帶鏈隊(duì)列和帶鏈棧都是線

性結(jié)構(gòu)，而二叉樹(shù)是非線性結(jié)構(gòu)。

10、下列描述中正確的是（）。

A、線性鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

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

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

D、只有根結(jié)點(diǎn)的二叉樹(shù)是線性結(jié)構(gòu)

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

知識(shí)點(diǎn)解析：線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的基本單

位稱為存儲(chǔ)結(jié)點(diǎn)，每個(gè)存儲(chǔ)結(jié)點(diǎn)包括數(shù)據(jù)域和指針域兩個(gè)組成部分。各數(shù)據(jù)元素之

間的前后件關(guān)系是由各結(jié)點(diǎn)的指針域來(lái)指示的，指向線性表中第一結(jié)點(diǎn)的指針

HEAD稱為頭指針，當(dāng)HEAD=NULL時(shí)稱為空表。棧、隊(duì)列和雙向鏈表是線性結(jié)

構(gòu)，樹(shù)是一種簡(jiǎn)單的非線性結(jié)構(gòu)。在樹(shù)這種數(shù)據(jù)結(jié)構(gòu)中，所有數(shù)據(jù)元素的關(guān)系具有

明顯的層次特征。二叉樹(shù)是非線性結(jié)構(gòu)。線性結(jié)構(gòu)和非線性結(jié)構(gòu)是從數(shù)據(jù)的邏輯結(jié)

構(gòu)角度來(lái)講的，與該數(shù)據(jù)結(jié)構(gòu)中有多少個(gè)元素沒(méi)有關(guān)系，即使是空的二叉樹(shù)也是非

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

11、下面敘述中正確的是（）。

A、線性表是線性結(jié)構(gòu)

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

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

D、二叉樹(shù)是線性結(jié)構(gòu)

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

知識(shí)點(diǎn)解析：線性表是最簡(jiǎn)單的、最常用的一種線性結(jié)構(gòu)。所謂線性鏈表指的是采

用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表。棧和隊(duì)列其實(shí)是一種特殊的線性表。樹(shù)是一種簡(jiǎn)單的非

線性結(jié)構(gòu)，二叉樹(shù)是樹(shù)的一種。

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

A、棧按“先進(jìn)先出”組織數(shù)據(jù)

B、棧按“先進(jìn)后出”組織數(shù)據(jù)

C、只能在棧底插入數(shù)據(jù)

D、不能刪除數(shù)據(jù)

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

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

的一端稱為棧頂，另一端稱為棧底。棧是按照“先進(jìn)后出”的原則組織數(shù)據(jù)的。

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

A^棧

B、樹(shù)

C、隊(duì)列

D、二義樹(shù)

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

知識(shí)點(diǎn)解析：棧是一種限定在一端進(jìn)行插入與刪除的線性表。在主函數(shù)調(diào)用子函數(shù)

時(shí)，要首先保存主函數(shù)當(dāng)前的狀態(tài)，然后轉(zhuǎn)去執(zhí)行子函數(shù)，把子函數(shù)的運(yùn)行結(jié)果返

回到主函數(shù)調(diào)用子函數(shù)時(shí)的位置，主函數(shù)再接著往下執(zhí)行，這種過(guò)程符合棧的特

點(diǎn)。所以一般采用棧式存儲(chǔ)方式。

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

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

B、棧

C、隊(duì)列

D、二叉樹(shù)

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

知識(shí)點(diǎn)解析：棧按照“先進(jìn)后出”（FILO）或“后進(jìn)先出”（LIFO）組織數(shù)據(jù)：隊(duì)列是“先

進(jìn)先出飛FIFO）或“后進(jìn)后出”（L1LO）的線性表。

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

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

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

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

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

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

知識(shí)點(diǎn)解析：棧是先進(jìn)后出的線性表，棧頂?shù)脑刈钕缺粍h除，棧底的元素最后被

刪除。

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

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

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

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

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

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

知識(shí)點(diǎn)解析：在棧中，允許插入與刪除的一端稱為棧頂，而不允許插入與刪除的另

一端稱為棧底。棧跟隊(duì)列不同，元素只能在棧頂壓入或彈出，棧底指針不變，棧中

元素隨棧頂指針的變化而動(dòng)態(tài)變化，遵循后進(jìn)先出的規(guī)則。

17、一個(gè)棧的初始狀態(tài)為空?，F(xiàn)將元素1、2、3、4、5、A、B、C、D、E依次入

棧，然后再依次出棧，則元素出棧的順序是（）。

A、12345ABCDE

B、EDCBA54321

C、ABCDE12345

D、54321EDCBA

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

知識(shí)點(diǎn)解析?：棧是按照“先進(jìn)后出”或“后進(jìn)先出”的原則組織數(shù)據(jù)的。所以出棧順序

是EDCBA54321o

18、下列關(guān)于棧的描述中錯(cuò)誤的是（）。

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

B、棧只能順序存儲(chǔ)

C、棧具有記憶作用

D、對(duì)棧的插入與刪除操作中，不需要改變棧底指針

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

知識(shí)點(diǎn)解析：棧是限定在一端進(jìn)行插入與刪除的線性表。棧頂（lop）：插入數(shù)據(jù)（即

入棧）的一端：棧底（hotmm）：不能入棧也不能出棧的一端。棧存儲(chǔ)數(shù)據(jù)的原則：

“先進(jìn)后出”或“后進(jìn)先出”。棧的特性是具有記憶作用。

國(guó)家二級(jí)C++機(jī)試（數(shù)據(jù)結(jié)構(gòu)與算法）

模擬試卷第6套

一、選擇題（本題共23題，每題1.0分，共23分。）

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

A、棧

B、堆

C、隊(duì)列

D、非完全二叉樹(shù)

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

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

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

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

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

2、設(shè)二叉樹(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、不可能有這樣的二叉樹(shù)

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

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

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

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

為2的結(jié)點(diǎn)數(shù)為】12，貝iJnO=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。

3、在帶鏈隊(duì)列中，經(jīng)過(guò)一系列正常的操作后，如果front=rear,則隊(duì)列中的元素個(gè)

數(shù)為

A、0或1

B、0

C、1

D、隊(duì)列滿

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

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

進(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。

4、設(shè)一棵樹(shù)的度為3,其中沒(méi)有度為2的結(jié)點(diǎn)，且葉子結(jié)點(diǎn)數(shù)為5。該樹(shù)中度為3

的結(jié)點(diǎn)數(shù)為

A、1

B、2

C、3

D、不可能有這樣的樹(shù)

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

知識(shí)點(diǎn)解析：樹(shù)的度是指一棵樹(shù)中，最大的結(jié)點(diǎn)的度稱為樹(shù)的度。本題中樹(shù)的度為

3,那么樹(shù)中最少有一個(gè)結(jié)點(diǎn)的度為3。而樹(shù)中沒(méi)有度為2的結(jié)點(diǎn)，葉子結(jié)點(diǎn)數(shù)為

5,度為1的結(jié)點(diǎn)下面只有一個(gè)葉子結(jié)點(diǎn)。因此，該樹(shù)中含2個(gè)度為3的結(jié)點(diǎn)滿足

題目要求。

5、設(shè)二叉樹(shù)共有500個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)有250個(gè)。則度為2的結(jié)點(diǎn)個(gè)數(shù)是

A、0

B、1

C、249

D、不可能有這樣的二叉樹(shù)

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

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

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

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

為2的結(jié)點(diǎn)數(shù)為112，則n0=n2+l。本題中，葉子結(jié)點(diǎn)有250個(gè)，度為2的結(jié)點(diǎn)數(shù)為

n2=no-1=250-1=249。

6、T列敘述中正確的是

A、帶鏈棧的棧底指針是固定的

B、帶鏈棧的棧底指針是隨棧的操作而動(dòng)態(tài)變化的

C、若帶鏈隊(duì)列的隊(duì)頭指針與隊(duì)尾指針相同，則隊(duì)列為空

D、若帶鏈隊(duì)列的隊(duì)頭指針與隊(duì)尾指針相同，則隊(duì)列中至少有一個(gè)元素

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

知識(shí)點(diǎn)解析：棧(stack)又名堆棧，它是一種運(yùn)算受限的線性表。其限制是僅允許在

表的一端進(jìn)行插入和刪除運(yùn)算。這一端被稱為棧頂，相對(duì)地，把另一端稱為棧底。

向一個(gè)棧插入新元素又禰作進(jìn)棧、入?；驂簵?，它是把新元素放到棧頂元素的上

面，使之成為新的棧頂元素；從一個(gè)棧刪除元素又稱作出?；蛲藯＃前阎斣?/p>

素刪除掉，使其相鄰的元素成為新的棧頂元素。帶鏈棧的棧底指針是隨棧的操作而

動(dòng)態(tài)變化的；若帶鏈隊(duì)列的隊(duì)頭指針與隊(duì)尾指針相同，則隊(duì)列可能為0也可能為

lo

7、帶鏈隊(duì)列空的條件是

A、front=rear=NULL

B、front=rear-=-1

C、front=NULL且rear=-1

D、front--1且rear_NULL

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

知識(shí)點(diǎn)解析：帶鏈隊(duì)列空的條件有兩個(gè)：一個(gè)是front=rcar,一個(gè)是他們都等于

空。

8、設(shè)一棵樹(shù)的度為3,其中沒(méi)有度為2的結(jié)點(diǎn)，且葉子結(jié)點(diǎn)數(shù)為6。該樹(shù)中度為3

的結(jié)點(diǎn)數(shù)為

A、1

B、2

C、3

D、不可能有這樣的樹(shù)

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

知識(shí)點(diǎn)0析：樹(shù)的度是由一棵樹(shù)中，最大的結(jié)點(diǎn)的度稱為樹(shù)的度。本題中樹(shù)的度為

3,也就是最少有一個(gè)度為3的結(jié)點(diǎn)。要求沒(méi)有度為2的結(jié)點(diǎn)，且葉子結(jié)點(diǎn)為6,

如果要有度為3的結(jié)點(diǎn)，那么最多只有5個(gè)葉子結(jié)點(diǎn)，而畫(huà)不出6個(gè)葉子結(jié)點(diǎn)。因

此這樣的樹(shù)是沒(méi)有的。

9、下列敘述中正確的是

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

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

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

D、循環(huán)隊(duì)列是非線性存儲(chǔ)結(jié)構(gòu)

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

知識(shí)點(diǎn)解析：為充分利用向量空間，克服“假溢出、,現(xiàn)象的方法是：將向星空間想象

為一個(gè)首尾相接的圓環(huán)，并稱這種向量為循環(huán)向量。存儲(chǔ)在其中的隊(duì)列稱為循環(huán)隊(duì)

列（CircularQueue）。線性結(jié)構(gòu)是一個(gè)有序數(shù)據(jù)元素的集合。常用的線性結(jié)構(gòu)有：線

性表，棧，隊(duì)列，雙隊(duì)列，數(shù)組，串。常見(jiàn)的非線性結(jié)構(gòu)有：二維數(shù)組，多維數(shù)

組，廣義表，樹(shù)（二叉樹(shù)等），圖。

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

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

A、7

R、8

C、6

D、不可能有這樣的樹(shù)

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

知識(shí)點(diǎn)解析：樹(shù)的度是由一棵樹(shù)中，最大的結(jié)點(diǎn)的度稱為“樹(shù)