1.2 歷年試題分析

試題1

下列關于棧敘述正確的是（ ）。

A.棧頂元素最先被刪除
B.棧頂元素最后才能被刪除
C.棧底元素永遠不能被刪除
D.以上三種說法都不對

【分析】棧是允許在同一端進行插入和刪除操作的特殊線性表。允許進行插入和刪除操作的一端稱為棧頂（Top），另一端為棧底（Bottom）；棧底固定，而棧頂浮動；棧中元素個數為0時稱為空棧。插入一般稱為進棧（PUSH），刪除則稱為退棧（POP）。棧也稱為先進后出表。

【答案】A

試題2

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

A.有一個以上根節點的數據結構不一定是非線性結構
B.只有一個根節點的數據結構不一定是線性結構
C.循環鏈表是非線性結構
D.雙向鏈表是非線性結構

【分析】循環鏈表是另一種形式的鏈式存儲結構。它的特點是表中最后一個節點的指針域指向頭節點，整個鏈表形成一個環。雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數據節點中都有兩個指針，分別指向直接后繼和直接前驅。所以，從雙向鏈表中的任意一個節點開始，都可以很方便地訪問它的前驅節點和后繼節點；循環鏈表和雙向鏈表都是線性結構。有一個以上根節點的結構一定是非線性結構。

【答案】B

試題3

某二叉樹共有7個節點，其中葉子節點只有1個，則該二叉樹的深度為（ ）（假設根節點在第1層）。

A.3
B.4
C.6
D.7

【分析】二叉樹是一種很有用的非線性結構，它具有以下兩個特點：

1）非空二叉樹只有一個根節點；

2）每一個節點最多有兩棵子樹，且分別稱為該節點的左子樹與右子樹。

根據二叉樹的概念可知，二叉樹的度可以為0（葉子節點）、1（只有一棵子樹）或2（有2棵子樹）。由于只有一個葉子節點，所以該二叉樹沒有分叉，7個節點連成一線，深度為7。

【答案】D

試題4

下列敘述正確的是（ ）。

A.算法就是程序
B.設計算法時只需要考慮數據結構的設計
C.設計算法時只需要考慮結果的可靠性
D.以上三種說法都不對

【分析】算法是求解問題的方法。程序設計時要設計算法，但算法不是程序。設計算法除了要考慮數據結構外，還要考慮算法的可行性、可靠性等。

【答案】D

試題5

下列關于線性鏈表的敘述中，正確的是（ ）。

A.各數據節點的存儲空間可以不連續，但它們的存儲順序與邏輯順序必須一致
B.各數據節點的存儲順序與邏輯順序可以不一致，但它們的存儲空間必須連續
C.進行插入與刪除時，不需要移動表中的元素
D.以上三種說法都不對

【分析】節點的存儲順序和邏輯順序不一定一致，存儲空間也不一定連續。插入和刪除元素的時候，不需要移動表中的元素。

【答案】C

試題6

下列關于二叉樹的敘述中，正確的是（ ）。

A.葉子節點總是比度為2的節點少一個
B.葉子節點總是比度為2的節點多一個
C.葉子節點數是度為2的節點數的兩倍
D.度為2的節點數是度為1的節點數的兩倍

【分析】二叉樹葉子節點總是比度為2的節點多一個，這是二叉樹的性質。

【答案】B

試題7

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

A.棧是一種先進先出的線性表
B.隊列是一種后進先出的線性表
C.棧與隊列都是非線性結構
D.以上三種說法都不對

【分析】棧和隊列都是特殊的線性表，棧（Stack）只能在表的一端進行插入和刪除運算，所以，棧是一種“先進后出”的線性表；而隊列（Queue）只允許在一端刪除，在另一端插入，所以，隊列是一種“先進先出”的線性表。

【答案】D

試題8

一棵二叉樹共有25個節點，其中5個是葉子節點，則度為1的節點數為（ ）。

A.4
B.10
C.6
D.16

【分析】從題干中我們知道，在該二叉樹中有5個葉子節點，由二叉樹的性質之一：任何一棵二叉樹，度為0的節點（也就是葉子節點）總是比度為2的節點多一個。可以得出，該二叉樹度為2（有2棵子樹）的節點數為4個，而該二叉樹總共有25個節點，所以，度為1的節點數為：25-5-4＝16個。

【答案】D

試題9

下列鏈表中，其邏輯結構屬于非線性結構的是（ ）。

A.二叉鏈表
B.循環鏈表
C.雙向鏈表
D.帶鏈的棧

【分析】此題目主要考查數據結構中的非線性結構的基本知識。其中，循環鏈表、雙向鏈表、帶鏈的棧都是線性結構，二叉鏈表是非線性鏈表。

【答案】A

試題10

設循環隊列的存儲空間為Q（1:35），初始狀態為front=rear=35。現經過一系列入隊與出隊運算后，front=15，rear=15，則循環隊列中的元素個數為（ ）。

A.15
B.16
C.20
D.0或35

【分析】此題目主要考查數據結構中隊列的存儲規則，隊列的元素個數為rear-front，如果差是非正數，加隊列的長度。當隊首與隊尾指向同一空間時，隊列可能為空，也可能為滿，所以選擇D。

【答案】D

試題11

下列關于棧的敘述中，正確的是（ ）。

A.棧底元素一定是最后入棧的元素
B.棧頂元素一定是最先入棧的元素
C.棧操作遵循先進后出的原則
D.以上三種說法都不對

【分析】棧的存儲原則是先進后出，所以選擇C。

【答案】C