全國計算機等級考試《二級C++語言程序設計》專

用教材【考綱分析+考點精講+真題演練+強化習

題】

目錄

第一部分公共基礎知識......................................................

第1章數據結構與算法..................................................

考綱分析............................................................

考點精講............................................................

1.1算法.....................................................

1.2數據結構的基本概念.........................................

1.3線性表及其順序存儲結構.....................................

1.4棧和隊列...................................................

1.5線性鏈表..................................................

L6樹與二叉樹.................................................

1.7?找技術..................................................

1.8排序技術..................................................

強化習題............................................................

第2章程序設計基礎....................................................

考綱分析............................................................

考點精講............................................................

2.1程序設計方法與風格.........................................

2.2結構化程序設計.............................................

2.3面向對象的程序設計.........................................

強化習題............................................................

第3章軟件工程基礎....................................................

考綱分析............................................................

考點精講............................................................

3.1軟件工程基本概念...........................................

3.2結構化分析方法.............................................

3.3結構化設計方法.............................................

3.4軟件測試...................................................

3.5程序的調試.................................................

強化習題............................................................

第4章數據庫設計基礎..................................................

考綱分析............................................................

考點精講............................................................

4.1數據庫系統的基本概念.......................................

4.2數據模型...................................................

43關系代數

4：4數［庫設計與管理.二二二二二二二二二二二二二二二

強化習題............................................................

第二部分C++語言程序設計...................................................

第1章C++語言概述.....................................................

考綱分析............................................................

考點精講............................................................

1.1C++語言的發展..............................................

1.2C++語言的特點..............................................

1.3面向對象程序設計...........................................

L4C++語言的基本符號..........................................

1.5C++語言的詞匯..............................................

1.6C++程序的基本框架..........................................

L7C++程序的開發過程..........................................

強化習題............................................................

第2章數據類型、運算符和表達式........................................

考綱分析............................................................

考點精講............................................................

2.1C++語言的數據類型.........................................

2.2常量....................................................

2.3變量....................................................

2.4運算符和表達式.............................................

強化習題............................................................

第3章基本控制結構....................................................

考綱分析............................................................

考點精講............................................................

3.1C++語句...................................................

3.2順序結構...................................................

3.3選擇結構...................................................

3.4循環結構..................................................

3.5跳轉語句..................................................

強化習題............................................................

第4章數組、指針與引用................................................

考綱分析............................................................

考點精講............................................................

4.1數組.....................................................

4.2指針.....................................................

4.3引用.....................................................

4.4動態存儲分配...............................................

強化習題............................................................

第5章函數..........................................................

考綱分析............................................................

考點精講............................................................

5.1函數定義...................................................

5.2函數調用...................................................

5.3函數原型...................................................

5.4函數返回類型...............................................

5.5函數參數...................................................

5.6函數重載...................................................

5.7內聯函數...................................................

5.8遞歸函數...................................................

5.9變量的生存周期.............................................

強化習題............................................................

第6章類和對象........................................................

考綱分析............................................................

考點精講............................................................

6.1類的定義...................................................

6.2對象的定義.................................................

6.3構造函數和析構函數.........................................

6.4自由存儲對象...............................................

6.5this指針..................................................

6.6靜態成員...................................................

6.7常成J..........................................................

6.8友元.....................................................

6.9對象數組...................................................

6.10成員對象..................................................

強化習題............................................................

第7章繼承和派生......................................................

考綱分析............................................................

考點精講............................................................

7.1繼承與派生.................................................

7.2派生類對基類成員的訪問.....................................

7.3派生類的構造函數和析構函數.................................

7.4多繼承與虛基類.............................................

7.5子類型關系.................................................

7.6虛函數與多態性.............................................

強化習題............................................................

第8章運算符重載......................................................

考綱分析............................................................

考點精講............................................................

8.1運算符函數與運算符重載.....................................

8.2典型運算符的重載...........................................

8.3運算符重載應注意的幾個問題.................................

強化習題............................................................

第9章模板..........................................................

考綱分析............................................................

考點精講............................................................

9.1函數模板..................................................

9.2類模板.....................................................

強化習題............................................................

第10章C++流..........................................................

考綱分析............................................................

考點精講............................................................

10.1C++流的概念..............................................

10.2輸入輸出的格式控制........................................

10.3文件流....................................................

強化習題............................................................

第一部分公共基礎知識

第1章數據結構與算法

考綱分析

1.算法的基本概念，算法復雜度的概念和意義（時間復雜度與空間復雜度）。

2.數據結構的定義，數據的邏輯結構與存儲結構；數據結構的圖形表示；

線性結構與非線性結構的概念。

3.線性表的定義，線性表的順序存儲結構及其插入與刪除運算。

4.棧和隊列的定義，棧和隊列的順序存儲結構及其基本運算。

5.線性單鏈表、雙向鏈表與循環鏈表的結構及其基本運算。

6.樹的基本概念，二叉樹的定義及其存儲結構；二叉樹的前序、中序和后

序遍歷。

7.順序查找與二分法查找算法，基本排序算法（交換類排序，選擇類排序,

插入類排序）。

考點精講

1.1算法

考點1算法的基本概念

（1）算法的定義

算法是指解題方案的準確而完整的描述，即算法是對特定問題求解步驟的

一種描述。它是一組嚴謹定義運算順序的規則，且每個規則都是明確有效的，

此順序將在有限的次數下終止。需要注意的是：算法不等于程序，也不等于計

算方法。

（2）算法的基本特征

①可行性

a.算法中的每一步驟都必須能夠實現；

b.算法執行的結果要能夠達到預期的目的。

②確定性

確定性是指算法中的每一個步驟都必須有明確的定義，不允許有模棱兩可

的解釋，也不允許有多義性。

③有窮性

有窮性是指算法必須能在有限的時間內做完，即必須能在執行有限個步驟

之后終止，且必須有合理的執行時間。

④擁有足夠的情報

算法是否有效，取決于為算法所提供的情報是否足夠。一般而言，當算法

有足夠的情報時，此算法有效，而當提供的情報不夠時，算法可能無效。

【真題演練】

算法的有窮性是指（）。［2013年9月真題］

A.算法程序的運行時間是有限的

B.算法程序所處理的數據量是有限的

C.算法程序的長度是有限的

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

【答案】A

【解析】算法設計有窮性要求操作步驟有限且必須在有限時間內完成，耗

費太長時間得到的正確結果是沒有意義的。

考點2算法設計基本方法

(1)列舉法

①基本思想

根據提出的問題，列舉所有可能的情況，并用問題中給定的條件檢驗哪些

是需要的，哪些是不需要的。常用于解決“是否存在”或“有多少種可能”等

類型的問題。

②主要特點

算法比較簡單，但列舉情況較多時，算法工作量很大。

③注意事項

例舉算法時，通過對實際問題進行詳細分析，將與問題有關的知識條理化、

完備化、系統化，并從中找出規律，或對所有可能的情況進行分類，從而引出

一些有用的信息，減少列舉量。

(2)歸納法

①基本思想

通過列舉少量的特殊情況，經過分析，最后找出一般的關系。

②主要特點

a.比列舉法更能反映問題的本質，可解決列舉量為無限的問題；

b.可操作性低，不易歸納出一個具體數學模型；

c.歸納得出的結論只是一種猜測，須對這種猜測加以必要的證明。

(3)遞推

①基本思想

從已知的初始條件出發，逐次推出所要求的各中間結果和最后結果。

②主要特點

a.初始條件或問題本身已給定，或通過對問題的分析化簡得到；

b.遞推本質上屬于歸納法，遞推關系式往往是歸納的結果；

c.數值型遞推算法計算過程中必須注意數值計算的穩定性問題。

(4)遞歸

①基本思想

將復雜問題逐層分解，歸結為一些簡單的問題，將簡單問題解決掉，再沿

著原來分解的逆過程逐步進行綜合。

②主要特點

a.遞歸的基礎是歸納，對問題逐層分解的過程實際上并沒有對問題進行求

解；

b.在可計算性理論和算法設計中占有重要地位；

c.遞歸算法比遞推算法清晰易讀，結構簡練；

d.設計遞歸算法比遞推算法容易，但是其執行效率較低。

③分類

a.直接遞歸。一個算法P顯式地調用自己。

b.間接遞歸。算法P調用另一個算法Q,而算法Q又調用算法P。

④遞歸與遞推的區別

遞歸與遞推的區別主要在于二者實現方法的不同，表現為：

a.遞歸是從算法本身到達遞歸的邊界的；

b.遞推是從初始條件出發，逐次推出所需求的結果。

（5）減半遞推技術

減半遞推技術是工程上常用的分治法，其中，“減半”指將問題的規模減

半，而問題的性質不變；“遞推”指重復“減半”的過程。

（6）回溯法

回溯法是指通過對問題的分析，找出一個解決問題的線索，然后沿著這個

線索逐步試探，若試探成功，則問題得到解決，若試探失敗，則逐步回退換別

的路線再進行試探。

【真題演練】

1.下列敘述中正確的是（）。［2013年9月真題］

A.所謂算法就是計算方法

B.程序可以作為算法的一種描述方法

C.算法設計只需考慮得到計算結果

D.算法設計可以忽略算法的運算時間

【答案】B

【解析】程序可以作為算法的一種描述方法,算法在實現時需要用具體的程

序設計語言描述。A項錯誤，算法并不等同于計算方法，是指對解題方案的準確

而完整的描述；C項錯誤，算法設計需要考慮可行性、確定性、有窮性與足夠的

情報；D項錯誤，算法設計有窮性要求操作步驟有限且必須在有限時間內完成，

耗費太長時間得到的正確結果是沒有意義的。

2.下列關于算法的描述中錯誤的是（）。［2014年3月真題］

A.算法強調動態的執行過程，不同于靜態的計算公式

B.算法必須能在有限個步驟之后終止

C.算法設計必須考慮算法的復雜度

D.算法的優劣取決于運行算法程序的環境

［答案］D

【解析】算法是指對解題方案的準確而完整的描述。A項正確，算法強調實

現，不同于數學上的計算方法；B項正確，算法的有窮性是指，算法中的操作步

驟為有限個，且每個步驟都能在有限時間內完成；C項正確，算法設計必須考慮

執行算法所需要的資源，即時間復雜度與空間復雜度；D項錯誤，算法的優劣取

決于算法復雜度，只有當算法被編程實現運行時才會受到運行環境影響。

考點3算法復雜度

（1）時間復雜度

①定義

算法的時間復雜度是指執行算法所需要的計算工作量。

算法的工作量用算法所執行的基本運算次數來度量，而算法所執行的基本

運算次數是問題規模的函數，即

算法的工作量=f（n）

其中，n是問題的規模。

②在同一問題規模下，若算法的基本運算次數取決于某一特定輸入，可用

以下兩種方法來分析算法的工作量：

a.平均性態

平均性態分析是指用各種特定輸入下的基本運算次數的加權平均值來度量

算法的工作量。算法的平均性態定義為：

其中，x是所有可能輸入中的某個特定輸入，p（x）是x出現的概率，即輸

入為x的概率，t（x）是算法在輸入為x時所執行的基本運算次數，D”表示當規

模為n時，算法執行時所有可能輸入的集合。

b.最壞情況復雜性

最壞情況分析是指規模為n時，算法所執行的基本運算的最大次數。其定

義為：

（2）空間復雜度

①定義

算法的空間復雜度一般是指執行這個算法所需要的內存空間。

②存儲空間組成

一個算法的存儲空間包括以下幾種：

a.算法程序占用的空間；

b.輸入的初始數據占用的存儲空間；

c.算法執行過程中所需要的額外空間。

額外空間包括算法程序執行過程中的工作單元以及某種數據結構所需要的

附加存儲空間，若額外空間相對于問題規模來說是常數，則稱該算法是原地工

作的。

【真題演練】

1.下列敘述中正確的是（）。［2015年3月真題］

A.算法的效率只與問題的規模有關，而與數據的存儲結構無關

B.算法的時間復雜度是指執行算法所需要的計算工作量

C.數據的邏輯結構與存儲結構是一一對應的

D.算法的時間復雜度與空間復雜度一定相關

［答案］B

【品析?】算法的時間復雜度是指算法在計算機內執行時所需時間的度量；

與時間復雜度類似，空間復雜度是指算法在計算機內執行時所需存儲空間的度

量。

2.算法的空間復雜度是指（）。［2013年9月真題］

A.算法在執行過程中所需要的計算機存儲空間

B.算法所處理的數據量

C.算法程序中的語句或指令條數

D.算法在執行過程中所需要的臨時工作單元數

【答案】A

【解析】空間復雜度是是對一個算法在運行過程中臨時占用存儲空間大小

的量度。

3.算法空間復雜度的度量方法是()。［2014年9月真題］

A.算法程序的長度

B.算法所處理的數據量

C.執行算法所需要的工作單元

D.執行算法所需要的存儲空間

【答案】D

【解析】算法的空間復雜度包括：①輸入數據所占的存儲空間；②程序本

身所占的存儲空間；③算法執行過程中所需要的額外空間，是指執行這個算法

所需要的內存空間，

1.2數據結構的基本概念

考點1概述

(1)數據處理概述

①定義

數據處理是指對數據集合中的各元素以各種方式進行運算，包括插入、刪

除、查找、更改等運算，也包括對數據元素進行分析。

②關鍵問題

大量數據元素在計算機中如何組織，以便提高數據處理的效率，從而節省

計算機的存儲空間，這是進行數據結構處理的關鍵問題。

(2)數據結構研究概述

①研究問題

a.數據集合中各數據元素之間所固有的邏輯關系，即數據的邏輯結構；

b.在對數據進行處理時，各數據元素在計算機中的存儲關系，即數據的存

儲結構；

c.對各種數據結構進行的運算。

②研究目的

數據結構研究和討論上述3個問題的主要目的在于提高數據處理效率，包

括：a.提高數據處理的速度；b,盡量節省在數據處理過程中所占用的計算機

存儲空間。

考點2數據結構的概念

(1)數據結構的定義

數據結構是指相互有關聯的數據元素的集合，即它是反映數據元素之間關

系的數據元素集合的表示。簡言之，數據結構是指帶有結構的數據元素的集合,

這里的“結構”指數據元素之間的前后件關系。一個數據結構應包含以下兩方

面內容：

①表述數據元素的信息；

②表示各數據元素之間的前后件關系。

(2)數據的邏輯結構

①定義

數據的邏輯結構是指反映數據元素之間邏輯關系的數據結構。

②要素：

a.數據元素的集合，通常記為D；

b.D上的關系，通常記為R,它反映了D中各數據元素之間的前后件關系。

③表示

一個數據結構B可表示為：

B=（D,R）

為反映D中個數據元素之間的前后件關系，一般用二元組來表示。

（3）數據的存儲結構

①定義

數據的存儲結構，也稱數據的物理結構，是指數據邏輯結構在計算機存儲

空間中的存放形式。在數據的存儲結構中，不僅要存放各數據元素的信息，而

且要存放各數據元素之間的前后件信息。

②常用的存儲結構：a.順序；b.鏈接；c.索引。

采用不同的存儲結構，數據處理的效率是不同的。

【真題演練】

下列敘述中正確的是（）。［2014年3月真題］

A.有且只有一個根結點的數據結構一定是線性結構

B.每一個結點最多有一個前件也最多有一個后件的數據結構一定是線性結

構

C.有且只有一個根結點的數據結構一定是非線性結構

D.有且只有一個根結點的數據結構可能是線性結構，也可能是非線性結構

［答案］D

【前析】邏輯結構分為線性結構和非線性結構，線性結構的特征有：①集

合中必存在唯一的一個“第一個元素”；②集合中必存在唯一的一個“最后的

元素”；③除第一元素之外，其它數據元素均有唯一的“前驅”；④除最后元

素之外，其它數據元素均有唯一的“后繼”。D項正確，如樹形結構只有一個根

結點，為非線性結構。

考點3數據結構的圖形表示

（1）在數據結構的圖形表示中，數據集合D中每個元素用中間標有元素值

的方框表示，稱為數據結點（簡稱結點）；對關系R中的每一個二元組，用一

條有向線段從前件結點指向后件結點。

（2）在數據結構中，沒有前件的結點稱為根結點，沒有后件的結點稱為終

端結點（也稱葉子結點），其余結點都稱為內部結點。

（3）數據結構中的元素結點可能是在動態變化的，這種變化體現在結點數

量的增減以及各結點之間的前后件關系的動態變化上。

考點4線性結構與非線性結構

根據數據結構中各數據元素之間的前后件關系的復雜程度，可將數據結構

分為：

（1）線性結構（線性表）

一個非空的數據結構滿足下列兩個條件時.，稱其為線性結構：

①有且只有一個根結占,

②每個結點最多只有二個前件，也最多只有一個后件。

線性結構中插入或刪除任何一個結點還應是線性結構，如果不滿足這個條

件就不能稱之為線性結構。

(2)非線性結構

如果一個數據結構不是線性結構，則稱之為非線性結構。

注：線性結構與非線性結構都可以是空的數據結構。一個空的數據結構屬

于線性結構還是非線性結構，需要根據對該數據結構的運算是否按照線性結構

的規則來處理進行判斷。

1.3線性表及其順序存儲結構

考點1線性表的基本概念

(1)線性表是一種最常見最簡單的數據結構，由一組數據元素構成。數據

元素在線性表中的位置值只取決于它們自己的序號，即數據元素之間的相對位

置是線性的。

(2)非空線性表的結構特征：

①有且只有一個根結點a.,它無前件；

②有且只有一個終端結點4,它無后件；

③除根結點與終端結點外，其他所有結點有且只有一個前件，也有且只有

一個后件。

線性表中結點的個數n稱為線性表的長度。當n=0時，稱為空表。

【真題演練】

下列敘述中正確的是()。［2014年9月真題］

A.結點中具有兩個指針域的鏈表一定是二叉鏈表

B.結點中具有兩個指針域的鏈表可以是線性結構，也可以是非線性結構

C.二叉樹只能采用鏈式存儲結構

D.循環鏈表是非線性結構

【答案】B

【解析】A項錯誤，具有兩個指針域的鏈表可能是雙向鏈表；B項正確，如

雙向鏈表是線性結構，二叉樹為非線性結構，兩者結點中均有兩個指針域；C項

錯誤，二叉樹通常采用鏈式存儲結構，也可采用其他結構；D項錯誤，循環鏈表

是線性結構，邏輯概念線性非線性與實際存儲結構無關。

考點2線性表的順序存儲結構

(1)概述

順序存儲是一種最簡單的在計算機中存放線性表的方法，也稱順序分配。

(2)特點：

①線性算中所有元素所占的存儲空間是連續的；

②線性表中各數據元素在存儲空間中是按邏輯順序依次存放的。

在線性表的順序存儲結構中，其前后件兩個元素在存儲空間中是緊鄰的，

且前件元素一定存儲在后件元素的前面。

(3)運算

在線性表的順序存儲結構下，可對線性表進行以下運算：

①插入：在線性表的指定位置處加入一個新的元素；

②刪除：在線性表中刪除指定的元素；

③查找：在線性表中查找某個（或某些）特定的元素；

④排序：對線性表中的元素進行整序；

⑤分解：按要求將一個線性表分解成多個線性表；

⑥合并：按要求將多個線性表合并成一個線性表；

⑦復制：復制一個線性表；

⑧逆轉：逆轉一個線性表等。

【真題演練】

在線性表的順序存儲結構中，其存儲空間連續，各個元素所占的字節數

（）。［2014年3月真題］

A.相同，元素的存儲順序與邏輯順序一致

B.相同，但其元素的存儲順序可以與邏輯順序不一致

C.不同，但元素的存儲順序與邏輯順序一致

D.不同，且其元素的存儲順序可以與邏輯順序不一致

【答案】A

【解析】在順序表中，每個元素占有相同的存儲單元。順序表具有特征：

①線性表中所有元素所占的存儲空間是連續的；②線性表中各數據元素在存儲

空間中是按邏輯順序依次存放的。

考點3順序表的插入運算

假設線性表的存儲空間為V（1：m）,線性表的長度為n（nWm）,插入的

位置為i（表示在第i個位置插入元素），則順序表插入新元素過程如下：

（1）首先處理以下三種異常情況：

①當存儲空間已滿（即n=m）時為“上溢”錯誤，不能進行插入，算法結

束；

②當i>n時，認為在最后一個元素之后（即第n+1個元素之前）插入；

③當i<l時，認為在第1個元素之前插入。

（2）從最后一個元素開始，直到第i個元素，其中每一個元素均往后移動

一個位置。

（3）最后將新元素插入到第i個位置，并且將線性表的長度增加1。

考點4順序表的刪除運算

假設線性表的存儲空間為V（1：m）,線性表的長度為n（nWm）,刪除的

位置為i（表示刪除第i個元素），則順序表刪除元素的過程如下：

（1）首先處理以下兩種異常情況：

①當線性表為空（即n=0）時為“上溢”錯誤，不能進行插入，算法結束;

②當i<l或i>n時，認為在最后一個元素之后（即第n+1個元素之前）插

入。

（2）然后從第i+1個元素開始，直到最后一個元素，其中每一個元素均

依次往前移動一個位置。

（3）最后將線性表的長度減小lo

1.4棧和隊列

考點1棧及其基本運算

（1）棧的定義

棧是限定在一端進行插入與刪除的線性表。

（2）棧的特點：

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

棧頂元素總是最后被插入的元素，也是最先被刪除的元素；棧底元素總是最先

被插入也是最后被刪除的。

②棧遵循“先進后出”或“后進先出”的原則，具有記憶功能。

③通常用指針top來指示棧頂位置，用指針bottom指向棧底，棧頂指針top

動態反映了棧中元素的變化情況。

（3）棧的順序存儲及其運算

在棧的順序存儲空間S（l:m）中，top=0表示棧空；top=m表示棧滿。

棧的三種運算：

①入棧運算

人棧運算是指在棧頂位置插入一個新元素。操作過程如下：

a.首先判斷棧頂指針是否已經指向存儲空間的最后一個位置。如果是，則

說明棧空間已滿，不可能再進行入棧操作（這種情況稱為棧“上溢”錯誤），

算法結束。

b.然后將棧頂指針進一（即top加1）。

c.最后將新元素x插入棧頂指針指向的位置。

②退棧運算

退棧運算是指取出棧頂元素并賦給一個指定的變量。操作過程如下：

a.首先判斷棧頂指針是否為0。如果是，則說明棧空，不可能進行退棧操

作（這種情況稱為棧“下溢”錯誤），算法結束。

b.然后將棧頂元素（棧頂指針指向的元素）賦給一個指定的變量。

c.最后將棧頂指針退一（即top減1）。

③讀棧頂元素

讀棧頂元素是指將棧頂元素賦給一個指定的變量。操作過程如下：

a.首先判斷棧頂指針是否為0。如果是，則說明棧空，讀不到棧頂元素，

算法結束。

b.然后將棧頂元素賦給指定的變量y。

這個運算不刪除棧頂元素，只是將它的值賦給一個變量，棧頂指針不會變。

【真題演練】

1.支持子程序調用的數據結構是（）。［2013年9月真題］

A.棧

B.樹

C.隊列

D.二叉樹

【答案】A

【解析】棧和隊列都是受限的線性表，其中棧按照“先進后出”的原則組

織數據，插入與刪除操作被限制在棧頂一端進行。棧支持子程序調用，在主程

序調用子函數時，要首先保存主程序當前的狀態，然后轉去執行子程序，結束

調用后返回到主程序中調用子程序的位置，繼續執行，這種調用符合棧的特點。

2.下列與棧結構有關聯的是（）。［2013年3月真題］

A.數組的定義域使用

B.操作系統的進程調度

C.函數的遞歸調用

D.選擇結構的執行

【答案】C

【解析】遞歸調用的本質就是函數調用函數本身，直到滿足特定條件時才停

止，然后從最后被遞歸調用處返回。遞歸函數是通過棧來實現的，所以調用原

則和棧的實現相一致。

3.設棧的順序存儲空間為S（1：50）,初始狀態為top=0。現經過一系列

入棧與退棧運算后，top=20,則當前棧中的元素個數為（）。［2014年3月

真題］

A.30

B.29

C.20

D.19

【答案】c

【解析】棧按照“先進后出”的原則組織數據，插入與刪除操作被限制在

棧頂一端進行，入棧使棧頂位置進1,退棧使棧頂退1。top=0表示棧為空，在

運算過程中，指針始終指向棧頂元素。top=20,說明當前棧中有20個元素。

4.一個棧的初始狀態為空。現將元素1、2、3、4、5、A、B、C、D、E依次

入棧，然后再依次出棧，則元素出棧的順序是（）。［2013年9月真題］

A.12345ABCDE

B.EDCBA54321

C.ABCDE12345

D.54321FDCBA

【答案】B

【解后】棧中數據的插入和刪除都在棧頂按照“先進后出”的原則進行操

作。

考點2隊列及其基本運算

（1）什么是隊列

隊列（Queue）是指允許在一端進行插入、而在另一端進行刪除的線性表。

（2）隊列的特點

①允許插入的一端稱為隊尾，用隊尾指針指向隊尾元素；允許刪除的一端

稱為隊頭，用排頭指針指向排頭元素的前一個位置。

②最先插入的元素最先被刪除，最后插入的元素最后被刪除，遵循“先進

先出”或“后進后出”原則。

③隊尾指針rear和排頭指針front共同反映隊列中元素變動情況。

④入隊運算指只涉及隊尾指針rear變化，退隊運算只涉及排頭指針front

變化。

（3）循環隊列及其運算

循環隊列是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上

的環狀空間，供隊列循環使用。在循環隊列中，用隊尾指針rear指向隊尾元素,

用排頭指針front指向排頭元素的前一個位置，從排頭指針front指向的后一

個位置到隊尾指針rear指向的位置均是隊列中元素。隊列空的條件是s=0；隊

列滿的條件是s=l且front=rearo

隊列的兩種運算

假設循環隊列的初始狀態為空，即：s=0,且front=rear=m。

①入隊運算

入隊運算是指在循環隊列的隊尾加入一個新元素。操作過程如下：

a.首先判斷循環隊列是否滿。當循環隊列非空（S=l）且隊尾指針等于排

頭指針時，說明循環隊列已滿，不能進行入隊運算。這種情況稱為“上溢”。

此時算法結束。

b.然后將隊尾指針進一（即rear=rear+l）,并當rear=m+l時置rear

——1O

c.最后將新元素x插入隊尾指針指向的位置，并且置循環隊列非空標志。

②退隊運算

退隊運算是指在循環隊列的排頭位置退出一個元素并賦給指定的變量。操

作過程如下：

a.首先判斷循環隊列是否為空。當循環隊列為空（s=0）時，不能進行退

隊運算。這種情況稱為“下溢”。此時算法結束。

b.然后將排頭指針進一（即front=front+l）,并當front=m+l時置

front=lo

c.再將排頭指針指向的元素賦給指定的變量。

d.最后判斷退隊后循環隊列是否為空。當front=rear時置循環隊列空標

志（即s=0）。

【真題演練】

1.下列敘述中正確的是（）。［2013年9月真題］

A.棧是“先進先出”的線性表

B.隊列是“先進后出”的線性表

C.循環隊列是非線性結構

D.有序線性表既可以采用順序存儲結構，也可以采用鏈式存儲結構

【答案】D

【解析】棧和隊列都是受限的線性表，其中棧按照“先進后出”的原則組織

數據，插入與刪除操作被限制在棧頂一端進行；隊列采用“先進先出”的原則

組織數據。循環隊列是隊列的一種特殊形式，是線性結構。

2.下列敘述中正確的是（）。［2014年3月真題］

A.循環隊列是順序存儲結構

B.循環隊列是鏈式存儲結構

C.循環隊列是非線性結構

D.循環隊列的插入運算不會發生溢出現象

【答案】A

【解析】B項錯誤，循環隊列是一種順序存儲結構的隊列；C項錯誤，線性

結構是一個非空序列：除第一個元素外，每個元素，有且只有一個前件；除最

后一個元素外，每個元素有且只有一個后件，所以循環隊列是線性結構；D項錯

誤，當循環隊列的元素個數等于存儲長度后，入隊會發生溢出現象，覆蓋前面

的數據。

3.對于循環隊列，下列敘述中正確的是()。［2013年9月真題］

A.隊頭指針是固定不變的

B.隊頭指針一定大于隊尾指針

C.隊頭指針一定小于隊尾指針

D.隊頭指針可以大于隊尾指針，也可以小于隊尾指針

［答案］D

【力析】循環隊列的隊頭指針與隊尾指針都不是固定的，每次入隊操作隊

尾指針要加進1,每次出隊操作隊頭指針要%m進1。因為存在如運算，所以隊

頭指針與隊尾指針大小關系不確定。

4.下列敘述中正確的是()。［2013年9月真題］

A.循環隊列有隊頭和隊尾兩個指針，因此，循環隊列是非線性結構

B.在循環隊列中，只需要隊頭指針就能反映隊列中元索的動態變化情況

C.在循環隊列中，只需要隊尾指針就能反映隊列中元素的動態變化情況

D.循環隊列中元素的個數是由隊頭指針和隊尾指針共同決定

［答案］D

【漏焦】在循環隊列中元素的個數是由隊頭指針和隊尾指針共同決定的，

入隊使得隊尾指針變化，出隊使得隊頭指針變化。

1.5線性鏈表

考點1線性鏈表的基本概念

(1)線性表的順序存儲結構存在的缺陷：

①在插入或刪除元素時，為保證操作后的線性表仍然是順序存儲，需要大

量移動數據元素，效率很低。

②在順序存儲結構下，線性表的存儲空間不便于擴充，易產生上溢現象。

③線性表的順序存儲結構不便于對存儲空間的動態分配。

(2)鏈式存儲結點組成：

①數據域：用于存放數據元素值；

②指針域：用于存放指針。

指針用于指向該結點的前一個或后一個結點，存儲數據結構的存儲空間可

以不連續，各數據結點的存儲順序與數據元素之間的邏輯關系可以不一致，而

數據元素之間的邏輯關系是由指針域來確定的。

鏈式存儲方式既可用于表示線性結構，也可用于表示非線性結構。在用鏈

式結構表示較復雜的非線性結構時，其指針域的個數要多一些。

(3)線性鏈表

①定義：線性鏈表是線性表的鏈式存儲結構。

②特點

a.各數據結點的存儲序號是不連續的，各結點在存儲空間中的位置關系與

邏輯關系也不一致；

b.各數據元素之間的前后件關系是由各結點的指針域來指示的；

c.每一個結點只有一個指針域，由這個指針只能找到后件結點，不能找到

前件結點，只能順指針向鏈尾進行掃描。

為了彌補線性單鏈表的缺陷，在某些應用中為線性鏈表每個結點設置兩個

指針，左指針用以指向其前件結點，右指針指向其后件結點。

(4)帶鏈的棧

帶鏈的棧可以用來收集計算機存儲空間中所有空閑的存儲結點。

與順序棧一樣，帶鏈棧的基本操作有以下幾個：

①棧的初始化：建立一個空棧的順序存儲空間；

②入棧運算：在棧頂位置插入一個新元素；

③退棧運算：取出棧頂元素并賦給一個指定的變量；

④讀棧頂元素：將棧頂元素賦給一個指定的變量。

(5)帶鏈的隊列

與順序隊列一樣，帶鏈隊列的基本操作有以下幾個：

①隊列的初始化：建立一個空隊列的順序存儲空間；

②入隊運算：在循環隊列的隊尾加入一個新元素；

③退隊運算：在循環隊列的排頭位置退出一個元素并賦給指定的變量。

【真題演練】

1.下列敘述中正確的是()。［2014年9月真題］

A.所謂有序表是指在順序存儲空間內連續存放的元素序列

B.有序表只能順序存儲在連續的存儲空間內

C.有序表可以用鏈式存儲方式存儲在不連續的存儲空間內

D.任何存儲方式的有序表均能采用二分法進行查找

【答案】C

【解析】“有序”是指線性表中的元素按照升序或降序(允許相鄰元素相同)

的方式排列。有序是一個邏輯概念，與物理存儲無關。二分法查找時涉及下標

運算，要求有序表必須順序存儲。

2.線性表的鏈式存儲結構與順序存儲結構相比，鏈式存儲結構的優點有

()o［2014年9月真題］

A.節省存儲空間

B.插入與刪除運算效率高

C.便于查找

D.排序時減少元素的比較次數

【答案】B

【解析】線性表的鏈式存儲結構與順序存儲結構的優缺點比較如下：

類型|優點|缺點

①插入和刪除運算效率很低

①方便隨機存取

順序②存儲空間不便于擴充

②無需額外的存儲空間來表示

表③不便于對存儲空間的動態分

結點間的邏輯關系

配

①在進行插入和刪除操作時，只

需要改變指針需要額外的空間來表示數據元

鏈表

②鏈表的存儲空間易于擴充，容素之間的邏輯關系，存儲密度低

易實現空間的動態分配

3.下列敘述中正確的是()。［2013年9月真題］

A.順序存儲結構的存儲一定是連續的，鏈式存儲結構的存儲空間不一定是

連續的

B.順序存儲結構只針對線性結構，鏈式存儲結構只針對非線性結構

C.順序存儲結構能存儲有序表，鏈式存儲結構不能存儲有序表

D.鏈式存儲結構比順序存儲結構節省存儲空間

【答案】A

【藍析】BC兩項錯誤，邏輯概念上的線性非線性是否有序與存儲結構為順序

還是鏈式沒有直接關系；D項錯誤，鏈式存儲結構比順序存儲結構更耗費存儲空

間，因為鏈式存儲結構中除了要存儲順序結構中的數據外還要存儲指針。

考點2線性鏈表的基本運算

(1)常見的線性表的運算

線性鏈表的運算主要有以下幾個：

①在線性鏈表中包含指定元素的結點之前插入一個新元素；

②在線性鏈表中刪除包含指定元素的結點；

③將兩個線性鏈表按要求合并成一個線性鏈表；

④將一個線性鏈表按要求進行分解；

⑤逆轉線性鏈表；

⑥復制線性鏈表；

⑦線性鏈表的排序；

⑧線性鏈表的查找。

(2)在線性鏈表中查找指定元素

非空線性鏈表中尋找包含指定元素值x的前一個結點p的基本方法：

從頭指針指向的結點開始往后沿指針進行掃描，直到后面已沒有結點或下

一個結點的數據域為x為止。因此，由這種方法找到的結點p有兩種可能：當

線性鏈表中存在包含元素x的結點時，則找到的p為第一次遇到的包含元素x

的前一個結點序號；當線性鏈表中不存在包含元素x的結點時，則找到的p為

線性鏈表中的最后一個結點號。

(3)線性鏈表的插入

①定義：線性鏈表的插入是指在鏈式儲存結構下的線性表中插入一個新元

素。

②插入過程：

在線性鏈表中包含元素x的結點之前插入一個新元素bo

a.從可利用棧取得一個結點，設該結點號為p,并置結點p的數據域為插

入的元素值b。b.在線性鏈表中尋找包含元素x的前一個結點，設該結點的

存儲序號為q。

c.最后將結點p插入到結點q之后。為了實現這一步，只要改變以下兩個

結點的指針域內容：

第一，使結點P指向包含元素x的結點；

第二，使結點q的指針域內容改為指向結點P。

③插入特點：

a.不會發生上溢現象；

b.可方便實現存儲空間動態分配；

c.不發生數據元素移動現象，只改變結點指針，提高插入效率。

(