全國計算機(jī)等級考試《二級c 語言程序設(shè)計》專用教材【考綱分析 考點精講 真題演練 強(qiáng)化習(xí)題】

全國計算機(jī)等級考試《二級C++語言程序設(shè)計》專

用教材【考綱分析+考點精講+真題演練+強(qiáng)化習(xí)

題】

目錄

第一部分公共基礎(chǔ)知識......................................................

第1章數(shù)據(jù)結(jié)構(gòu)與算法..................................................

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

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

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

1.2數(shù)據(jù)結(jié)構(gòu)的基本概念.........................................

1.3線性表及其順序存儲結(jié)構(gòu).....................................

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

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

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

1.7?找技術(shù)..................................................

1.8排序技術(shù)..................................................

強(qiáng)化習(xí)題............................................................

第2章程序設(shè)計基礎(chǔ)....................................................

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

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

2.1程序設(shè)計方法與風(fēng)格.........................................

2.2結(jié)構(gòu)化程序設(shè)計.............................................

2.3面向?qū)ο蟮某绦蛟O(shè)計.........................................

強(qiáng)化習(xí)題............................................................

第3章軟件工程基礎(chǔ)....................................................

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

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

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

3.2結(jié)構(gòu)化分析方法.............................................

3.3結(jié)構(gòu)化設(shè)計方法.............................................

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

3.5程序的調(diào)試.................................................

強(qiáng)化習(xí)題............................................................

第4章數(shù)據(jù)庫設(shè)計基礎(chǔ)..................................................

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

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

4.1數(shù)據(jù)庫系統(tǒng)的基本概念.......................................

4.2數(shù)據(jù)模型...................................................

43關(guān)系代數(shù)

4：4數(shù)［庫設(shè)計與管理.二二二二二二二二二二二二二二二

強(qiáng)化習(xí)題............................................................

第二部分C++語言程序設(shè)計...................................................

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

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

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

1.1C++語言的發(fā)展..............................................

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

1.3面向?qū)ο蟪绦蛟O(shè)計...........................................

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

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

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

L7C++程序的開發(fā)過程..........................................

強(qiáng)化習(xí)題............................................................

第2章數(shù)據(jù)類型、運(yùn)算符和表達(dá)式........................................

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

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

2.1C++語言的數(shù)據(jù)類型.........................................

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

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

2.4運(yùn)算符和表達(dá)式.............................................

強(qiáng)化習(xí)題............................................................

第3章基本控制結(jié)構(gòu)....................................................

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

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

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

3.2順序結(jié)構(gòu)...................................................

3.3選擇結(jié)構(gòu)...................................................

3.4循環(huán)結(jié)構(gòu)..................................................

3.5跳轉(zhuǎn)語句..................................................

強(qiáng)化習(xí)題............................................................

第4章數(shù)組、指針與引用................................................

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

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

4.1數(shù)組.....................................................

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

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

4.4動態(tài)存儲分配...............................................

強(qiáng)化習(xí)題............................................................

第5章函數(shù)..........................................................

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

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

5.1函數(shù)定義...................................................

5.2函數(shù)調(diào)用...................................................

5.3函數(shù)原型...................................................

5.4函數(shù)返回類型...............................................

5.5函數(shù)參數(shù)...................................................

5.6函數(shù)重載...................................................

5.7內(nèi)聯(lián)函數(shù)...................................................

5.8遞歸函數(shù)...................................................

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

強(qiáng)化習(xí)題............................................................

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

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

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

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

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

6.3構(gòu)造函數(shù)和析構(gòu)函數(shù).........................................

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

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

6.6靜態(tài)成員...................................................

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

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

6.9對象數(shù)組...................................................

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

強(qiáng)化習(xí)題............................................................

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

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

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

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

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

7.3派生類的構(gòu)造函數(shù)和析構(gòu)函數(shù).................................

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

7.5子類型關(guān)系.................................................

7.6虛函數(shù)與多態(tài)性.............................................

強(qiáng)化習(xí)題............................................................

第8章運(yùn)算符重載......................................................

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

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

8.1運(yùn)算符函數(shù)與運(yùn)算符重載.....................................

8.2典型運(yùn)算符的重載...........................................

8.3運(yùn)算符重載應(yīng)注意的幾個問題.................................

強(qiáng)化習(xí)題............................................................

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

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

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

9.1函數(shù)模板..................................................

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

強(qiáng)化習(xí)題............................................................

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

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

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

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

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

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

強(qiáng)化習(xí)題............................................................

第一部分公共基礎(chǔ)知識

第1章數(shù)據(jù)結(jié)構(gòu)與算法

考綱分析

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

2.數(shù)據(jù)結(jié)構(gòu)的定義，數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)的圖形表示；

線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念。

3.線性表的定義，線性表的順序存儲結(jié)構(gòu)及其插入與刪除運(yùn)算。

4.棧和隊列的定義，棧和隊列的順序存儲結(jié)構(gòu)及其基本運(yùn)算。

5.線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算。

6.樹的基本概念，二叉樹的定義及其存儲結(jié)構(gòu)；二叉樹的前序、中序和后

序遍歷。

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

插入類排序）。

考點精講

1.1算法

考點1算法的基本概念

（1）算法的定義

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

一種描述。它是一組嚴(yán)謹(jǐn)定義運(yùn)算順序的規(guī)則，且每個規(guī)則都是明確有效的，

此順序?qū)⒃谟邢薜拇螖?shù)下終止。需要注意的是：算法不等于程序，也不等于計

算方法。

（2）算法的基本特征

①可行性

a.算法中的每一步驟都必須能夠?qū)崿F(xiàn)；

b.算法執(zhí)行的結(jié)果要能夠達(dá)到預(yù)期的目的。

②確定性

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

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

③有窮性

有窮性是指算法必須能在有限的時間內(nèi)做完，即必須能在執(zhí)行有限個步驟

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

④擁有足夠的情報

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

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

【真題演練】

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

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

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

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

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

【答案】A

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

費(fèi)太長時間得到的正確結(jié)果是沒有意義的。

考點2算法設(shè)計基本方法

(1)列舉法

①基本思想

根據(jù)提出的問題，列舉所有可能的情況，并用問題中給定的條件檢驗?zāi)男?/p>

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

類型的問題。

②主要特點

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

③注意事項

例舉算法時，通過對實際問題進(jìn)行詳細(xì)分析，將與問題有關(guān)的知識條理化、

完備化、系統(tǒng)化，并從中找出規(guī)律，或?qū)λ锌赡艿那闆r進(jìn)行分類，從而引出

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

(2)歸納法

①基本思想

通過列舉少量的特殊情況，經(jīng)過分析，最后找出一般的關(guān)系。

②主要特點

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

b.可操作性低，不易歸納出一個具體數(shù)學(xué)模型；

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

(3)遞推

①基本思想

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

②主要特點

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

b.遞推本質(zhì)上屬于歸納法，遞推關(guān)系式往往是歸納的結(jié)果；

c.數(shù)值型遞推算法計算過程中必須注意數(shù)值計算的穩(wěn)定性問題。

(4)遞歸

①基本思想

將復(fù)雜問題逐層分解，歸結(jié)為一些簡單的問題，將簡單問題解決掉，再沿

著原來分解的逆過程逐步進(jìn)行綜合。

②主要特點

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

解；

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

c.遞歸算法比遞推算法清晰易讀，結(jié)構(gòu)簡練；

d.設(shè)計遞歸算法比遞推算法容易，但是其執(zhí)行效率較低。

③分類

a.直接遞歸。一個算法P顯式地調(diào)用自己。

b.間接遞歸。算法P調(diào)用另一個算法Q,而算法Q又調(diào)用算法P。

④遞歸與遞推的區(qū)別

遞歸與遞推的區(qū)別主要在于二者實現(xiàn)方法的不同，表現(xiàn)為：

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

b.遞推是從初始條件出發(fā)，逐次推出所需求的結(jié)果。

（5）減半遞推技術(shù)

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

半，而問題的性質(zhì)不變；“遞推”指重復(fù)“減半”的過程。

（6）回溯法

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

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

的路線再進(jìn)行試探。

【真題演練】

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

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

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

C.算法設(shè)計只需考慮得到計算結(jié)果

D.算法設(shè)計可以忽略算法的運(yùn)算時間

【答案】B

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

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

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

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

耗費(fèi)太長時間得到的正確結(jié)果是沒有意義的。

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

A.算法強(qiáng)調(diào)動態(tài)的執(zhí)行過程，不同于靜態(tài)的計算公式

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

C.算法設(shè)計必須考慮算法的復(fù)雜度

D.算法的優(yōu)劣取決于運(yùn)行算法程序的環(huán)境

［答案］D

【解析】算法是指對解題方案的準(zhǔn)確而完整的描述。A項正確，算法強(qiáng)調(diào)實

現(xiàn)，不同于數(shù)學(xué)上的計算方法；B項正確，算法的有窮性是指，算法中的操作步

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

執(zhí)行算法所需要的資源，即時間復(fù)雜度與空間復(fù)雜度；D項錯誤，算法的優(yōu)劣取

決于算法復(fù)雜度，只有當(dāng)算法被編程實現(xiàn)運(yùn)行時才會受到運(yùn)行環(huán)境影響。

考點3算法復(fù)雜度

（1）時間復(fù)雜度

①定義

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

算法的工作量用算法所執(zhí)行的基本運(yùn)算次數(shù)來度量，而算法所執(zhí)行的基本

運(yùn)算次數(shù)是問題規(guī)模的函數(shù)，即

算法的工作量=f（n）

其中，n是問題的規(guī)模。

②在同一問題規(guī)模下，若算法的基本運(yùn)算次數(shù)取決于某一特定輸入，可用

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

a.平均性態(tài)

平均性態(tài)分析是指用各種特定輸入下的基本運(yùn)算次數(shù)的加權(quán)平均值來度量

算法的工作量。算法的平均性態(tài)定義為：

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

入為x的概率，t（x）是算法在輸入為x時所執(zhí)行的基本運(yùn)算次數(shù)，D”表示當(dāng)規(guī)

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

b.最壞情況復(fù)雜性

最壞情況分析是指規(guī)模為n時，算法所執(zhí)行的基本運(yùn)算的最大次數(shù)。其定

義為：

（2）空間復(fù)雜度

①定義

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

②存儲空間組成

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

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

b.輸入的初始數(shù)據(jù)占用的存儲空間；

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

額外空間包括算法程序執(zhí)行過程中的工作單元以及某種數(shù)據(jù)結(jié)構(gòu)所需要的

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

作的。

【真題演練】

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

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

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

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

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

［答案］B

【品析?】算法的時間復(fù)雜度是指算法在計算機(jī)內(nèi)執(zhí)行時所需時間的度量；

與時間復(fù)雜度類似，空間復(fù)雜度是指算法在計算機(jī)內(nèi)執(zhí)行時所需存儲空間的度

量。

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

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

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

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

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

【答案】A

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

的量度。

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

A.算法程序的長度

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

C.執(zhí)行算法所需要的工作單元

D.執(zhí)行算法所需要的存儲空間

【答案】D

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

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

所需要的內(nèi)存空間，

1.2數(shù)據(jù)結(jié)構(gòu)的基本概念

考點1概述

(1)數(shù)據(jù)處理概述

①定義

數(shù)據(jù)處理是指對數(shù)據(jù)集合中的各元素以各種方式進(jìn)行運(yùn)算，包括插入、刪

除、查找、更改等運(yùn)算，也包括對數(shù)據(jù)元素進(jìn)行分析。

②關(guān)鍵問題

大量數(shù)據(jù)元素在計算機(jī)中如何組織，以便提高數(shù)據(jù)處理的效率，從而節(jié)省

計算機(jī)的存儲空間，這是進(jìn)行數(shù)據(jù)結(jié)構(gòu)處理的關(guān)鍵問題。

(2)數(shù)據(jù)結(jié)構(gòu)研究概述

①研究問題

a.數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；

b.在對數(shù)據(jù)進(jìn)行處理時，各數(shù)據(jù)元素在計算機(jī)中的存儲關(guān)系，即數(shù)據(jù)的存

儲結(jié)構(gòu)；

c.對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。

②研究目的

數(shù)據(jù)結(jié)構(gòu)研究和討論上述3個問題的主要目的在于提高數(shù)據(jù)處理效率，包

括：a.提高數(shù)據(jù)處理的速度；b,盡量節(jié)省在數(shù)據(jù)處理過程中所占用的計算機(jī)

存儲空間。

考點2數(shù)據(jù)結(jié)構(gòu)的概念

(1)數(shù)據(jù)結(jié)構(gòu)的定義

數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合，即它是反映數(shù)據(jù)元素之間關(guān)

系的數(shù)據(jù)元素集合的表示。簡言之，數(shù)據(jù)結(jié)構(gòu)是指帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合,

這里的“結(jié)構(gòu)”指數(shù)據(jù)元素之間的前后件關(guān)系。一個數(shù)據(jù)結(jié)構(gòu)應(yīng)包含以下兩方

面內(nèi)容：

①表述數(shù)據(jù)元素的信息；

②表示各數(shù)據(jù)元素之間的前后件關(guān)系。

(2)數(shù)據(jù)的邏輯結(jié)構(gòu)

①定義

數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。

②要素：

a.數(shù)據(jù)元素的集合，通常記為D；

b.D上的關(guān)系，通常記為R,它反映了D中各數(shù)據(jù)元素之間的前后件關(guān)系。

③表示

一個數(shù)據(jù)結(jié)構(gòu)B可表示為：

B=（D,R）

為反映D中個數(shù)據(jù)元素之間的前后件關(guān)系，一般用二元組來表示。

（3）數(shù)據(jù)的存儲結(jié)構(gòu)

①定義

數(shù)據(jù)的存儲結(jié)構(gòu)，也稱數(shù)據(jù)的物理結(jié)構(gòu)，是指數(shù)據(jù)邏輯結(jié)構(gòu)在計算機(jī)存儲

空間中的存放形式。在數(shù)據(jù)的存儲結(jié)構(gòu)中，不僅要存放各數(shù)據(jù)元素的信息，而

且要存放各數(shù)據(jù)元素之間的前后件信息。

②常用的存儲結(jié)構(gòu)：a.順序；b.鏈接；c.索引。

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

【真題演練】

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

A.有且只有一個根結(jié)點的數(shù)據(jù)結(jié)構(gòu)一定是線性結(jié)構(gòu)

B.每一個結(jié)點最多有一個前件也最多有一個后件的數(shù)據(jù)結(jié)構(gòu)一定是線性結(jié)

構(gòu)

C.有且只有一個根結(jié)點的數(shù)據(jù)結(jié)構(gòu)一定是非線性結(jié)構(gòu)

D.有且只有一個根結(jié)點的數(shù)據(jù)結(jié)構(gòu)可能是線性結(jié)構(gòu)，也可能是非線性結(jié)構(gòu)

［答案］D

【前析】邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，線性結(jié)構(gòu)的特征有：①集

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

元素”；③除第一元素之外，其它數(shù)據(jù)元素均有唯一的“前驅(qū)”；④除最后元

素之外，其它數(shù)據(jù)元素均有唯一的“后繼”。D項正確，如樹形結(jié)構(gòu)只有一個根

結(jié)點，為非線性結(jié)構(gòu)。

考點3數(shù)據(jù)結(jié)構(gòu)的圖形表示

（1）在數(shù)據(jù)結(jié)構(gòu)的圖形表示中，數(shù)據(jù)集合D中每個元素用中間標(biāo)有元素值

的方框表示，稱為數(shù)據(jù)結(jié)點（簡稱結(jié)點）；對關(guān)系R中的每一個二元組，用一

條有向線段從前件結(jié)點指向后件結(jié)點。

（2）在數(shù)據(jù)結(jié)構(gòu)中，沒有前件的結(jié)點稱為根結(jié)點，沒有后件的結(jié)點稱為終

端結(jié)點（也稱葉子結(jié)點），其余結(jié)點都稱為內(nèi)部結(jié)點。

（3）數(shù)據(jù)結(jié)構(gòu)中的元素結(jié)點可能是在動態(tài)變化的，這種變化體現(xiàn)在結(jié)點數(shù)

量的增減以及各結(jié)點之間的前后件關(guān)系的動態(tài)變化上。

考點4線性結(jié)構(gòu)與非線性結(jié)構(gòu)

根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間的前后件關(guān)系的復(fù)雜程度，可將數(shù)據(jù)結(jié)構(gòu)

分為：

（1）線性結(jié)構(gòu)（線性表）

一個非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個條件時.，稱其為線性結(jié)構(gòu)：

①有且只有一個根結(jié)占,

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

線性結(jié)構(gòu)中插入或刪除任何一個結(jié)點還應(yīng)是線性結(jié)構(gòu)，如果不滿足這個條

件就不能稱之為線性結(jié)構(gòu)。

(2)非線性結(jié)構(gòu)

如果一個數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱之為非線性結(jié)構(gòu)。

注：線性結(jié)構(gòu)與非線性結(jié)構(gòu)都可以是空的數(shù)據(jù)結(jié)構(gòu)。一個空的數(shù)據(jù)結(jié)構(gòu)屬

于線性結(jié)構(gòu)還是非線性結(jié)構(gòu)，需要根據(jù)對該數(shù)據(jù)結(jié)構(gòu)的運(yùn)算是否按照線性結(jié)構(gòu)

的規(guī)則來處理進(jìn)行判斷。

1.3線性表及其順序存儲結(jié)構(gòu)

考點1線性表的基本概念

(1)線性表是一種最常見最簡單的數(shù)據(jù)結(jié)構(gòu)，由一組數(shù)據(jù)元素構(gòu)成。數(shù)據(jù)

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

置是線性的。

(2)非空線性表的結(jié)構(gòu)特征：

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

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

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

一個后件。

線性表中結(jié)點的個數(shù)n稱為線性表的長度。當(dāng)n=0時，稱為空表。

【真題演練】

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

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

B.結(jié)點中具有兩個指針域的鏈表可以是線性結(jié)構(gòu)，也可以是非線性結(jié)構(gòu)

C.二叉樹只能采用鏈?zhǔn)酱鎯Y(jié)構(gòu)

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

【答案】B

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

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

錯誤，二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，也可采用其他結(jié)構(gòu)；D項錯誤，循環(huán)鏈表

是線性結(jié)構(gòu)，邏輯概念線性非線性與實際存儲結(jié)構(gòu)無關(guān)。

考點2線性表的順序存儲結(jié)構(gòu)

(1)概述

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

(2)特點：

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

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

在線性表的順序存儲結(jié)構(gòu)中，其前后件兩個元素在存儲空間中是緊鄰的，

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

(3)運(yùn)算

在線性表的順序存儲結(jié)構(gòu)下，可對線性表進(jìn)行以下運(yùn)算：

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

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

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

④排序：對線性表中的元素進(jìn)行整序；

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

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

⑦復(fù)制：復(fù)制一個線性表；

⑧逆轉(zhuǎn)：逆轉(zhuǎn)一個線性表等。

【真題演練】

在線性表的順序存儲結(jié)構(gòu)中，其存儲空間連續(xù)，各個元素所占的字節(jié)數(shù)

（）。［2014年3月真題］

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

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

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

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

【答案】A

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

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

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

考點3順序表的插入運(yùn)算

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

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

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

①當(dāng)存儲空間已滿（即n=m）時為“上溢”錯誤，不能進(jìn)行插入，算法結(jié)

束；

②當(dāng)i>n時，認(rèn)為在最后一個元素之后（即第n+1個元素之前）插入；

③當(dāng)i<l時，認(rèn)為在第1個元素之前插入。

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

一個位置。

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

考點4順序表的刪除運(yùn)算

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

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

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

①當(dāng)線性表為空（即n=0）時為“上溢”錯誤，不能進(jìn)行插入，算法結(jié)束;

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

入。

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

依次往前移動一個位置。

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

1.4棧和隊列

考點1棧及其基本運(yùn)算

（1）棧的定義

棧是限定在一端進(jìn)行插入與刪除的線性表。

（2）棧的特點：

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

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

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

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

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

動態(tài)反映了棧中元素的變化情況。

（3）棧的順序存儲及其運(yùn)算

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

棧的三種運(yùn)算：

①入棧運(yùn)算

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

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

說明?？臻g已滿，不可能再進(jìn)行入棧操作（這種情況稱為?！吧弦纭卞e誤），

算法結(jié)束。

b.然后將棧頂指針進(jìn)一（即top加1）。

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

②退棧運(yùn)算

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

a.首先判斷棧頂指針是否為0。如果是，則說明?？?，不可能進(jìn)行退棧操

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

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

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

③讀棧頂元素

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

a.首先判斷棧頂指針是否為0。如果是，則說明?？眨x不到棧頂元素，

算法結(jié)束。

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

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

【真題演練】

1.支持子程序調(diào)用的數(shù)據(jù)結(jié)構(gòu)是（）。［2013年9月真題］

A.棧

B.樹

C.隊列

D.二叉樹

【答案】A

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

織數(shù)據(jù)，插入與刪除操作被限制在棧頂一端進(jìn)行。棧支持子程序調(diào)用，在主程

序調(diào)用子函數(shù)時，要首先保存主程序當(dāng)前的狀態(tài)，然后轉(zhuǎn)去執(zhí)行子程序，結(jié)束

調(diào)用后返回到主程序中調(diào)用子程序的位置，繼續(xù)執(zhí)行，這種調(diào)用符合棧的特點。

2.下列與棧結(jié)構(gòu)有關(guān)聯(lián)的是（）。［2013年3月真題］

A.數(shù)組的定義域使用

B.操作系統(tǒng)的進(jìn)程調(diào)度

C.函數(shù)的遞歸調(diào)用

D.選擇結(jié)構(gòu)的執(zhí)行

【答案】C

【解析】遞歸調(diào)用的本質(zhì)就是函數(shù)調(diào)用函數(shù)本身，直到滿足特定條件時才停

止，然后從最后被遞歸調(diào)用處返回。遞歸函數(shù)是通過棧來實現(xiàn)的，所以調(diào)用原

則和棧的實現(xiàn)相一致。

3.設(shè)棧的順序存儲空間為S（1：50）,初始狀態(tài)為top=0。現(xiàn)經(jīng)過一系列

入棧與退棧運(yùn)算后，top=20,則當(dāng)前棧中的元素個數(shù)為（）。［2014年3月

真題］

A.30

B.29

C.20

D.19

【答案】c

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

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

運(yùn)算過程中，指針始終指向棧頂元素。top=20,說明當(dāng)前棧中有20個元素。

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

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

A.12345ABCDE

B.EDCBA54321

C.ABCDE12345

D.54321FDCBA

【答案】B

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

作。

考點2隊列及其基本運(yùn)算

（1）什么是隊列

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

（2）隊列的特點

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

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

②最先插入的元素最先被刪除，最后插入的元素最后被刪除，遵循“先進(jìn)

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

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

④入隊運(yùn)算指只涉及隊尾指針rear變化，退隊運(yùn)算只涉及排頭指針front

變化。

（3）循環(huán)隊列及其運(yùn)算

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

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

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

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

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

隊列的兩種運(yùn)算

假設(shè)循環(huán)隊列的初始狀態(tài)為空，即：s=0,且front=rear=m。

①入隊運(yùn)算

入隊運(yùn)算是指在循環(huán)隊列的隊尾加入一個新元素。操作過程如下：

a.首先判斷循環(huán)隊列是否滿。當(dāng)循環(huán)隊列非空（S=l）且隊尾指針等于排

頭指針時，說明循環(huán)隊列已滿，不能進(jìn)行入隊運(yùn)算。這種情況稱為“上溢”。

此時算法結(jié)束。

b.然后將隊尾指針進(jìn)一（即rear=rear+l）,并當(dāng)rear=m+l時置rear

——1O

c.最后將新元素x插入隊尾指針指向的位置，并且置循環(huán)隊列非空標(biāo)志。

②退隊運(yùn)算

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

作過程如下：

a.首先判斷循環(huán)隊列是否為空。當(dāng)循環(huán)隊列為空（s=0）時，不能進(jìn)行退

隊運(yùn)算。這種情況稱為“下溢”。此時算法結(jié)束。

b.然后將排頭指針進(jìn)一（即front=front+l）,并當(dāng)front=m+l時置

front=lo

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

d.最后判斷退隊后循環(huán)隊列是否為空。當(dāng)front=rear時置循環(huán)隊列空標(biāo)

志（即s=0）。

【真題演練】

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

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

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

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

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

【答案】D

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

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

組織數(shù)據(jù)。循環(huán)隊列是隊列的一種特殊形式，是線性結(jié)構(gòu)。

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

A.循環(huán)隊列是順序存儲結(jié)構(gòu)

B.循環(huán)隊列是鏈?zhǔn)酱鎯Y(jié)構(gòu)

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

D.循環(huán)隊列的插入運(yùn)算不會發(fā)生溢出現(xiàn)象

【答案】A

【解析】B項錯誤，循環(huán)隊列是一種順序存儲結(jié)構(gòu)的隊列；C項錯誤，線性

結(jié)構(gòu)是一個非空序列：除第一個元素外，每個元素，有且只有一個前件；除最

后一個元素外，每個元素有且只有一個后件，所以循環(huán)隊列是線性結(jié)構(gòu)；D項錯

誤，當(dāng)循環(huán)隊列的元素個數(shù)等于存儲長度后，入隊會發(fā)生溢出現(xiàn)象，覆蓋前面

的數(shù)據(jù)。

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

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

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

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

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

［答案］D

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

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

頭指針與隊尾指針大小關(guān)系不確定。

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

A.循環(huán)隊列有隊頭和隊尾兩個指針，因此，循環(huán)隊列是非線性結(jié)構(gòu)

B.在循環(huán)隊列中，只需要隊頭指針就能反映隊列中元索的動態(tài)變化情況

C.在循環(huán)隊列中，只需要隊尾指針就能反映隊列中元素的動態(tài)變化情況

D.循環(huán)隊列中元素的個數(shù)是由隊頭指針和隊尾指針共同決定

［答案］D

【漏焦】在循環(huán)隊列中元素的個數(shù)是由隊頭指針和隊尾指針共同決定的，

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

1.5線性鏈表

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

(1)線性表的順序存儲結(jié)構(gòu)存在的缺陷：

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

量移動數(shù)據(jù)元素，效率很低。

②在順序存儲結(jié)構(gòu)下，線性表的存儲空間不便于擴(kuò)充，易產(chǎn)生上溢現(xiàn)象。

③線性表的順序存儲結(jié)構(gòu)不便于對存儲空間的動態(tài)分配。

(2)鏈?zhǔn)酱鎯Y(jié)點組成：

①數(shù)據(jù)域：用于存放數(shù)據(jù)元素值；

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

指針用于指向該結(jié)點的前一個或后一個結(jié)點，存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可

以不連續(xù)，各數(shù)據(jù)結(jié)點的存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而

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

鏈?zhǔn)酱鎯Ψ绞郊瓤捎糜诒硎揪€性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。在用鏈

式結(jié)構(gòu)表示較復(fù)雜的非線性結(jié)構(gòu)時，其指針域的個數(shù)要多一些。

(3)線性鏈表

①定義：線性鏈表是線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。

②特點

a.各數(shù)據(jù)結(jié)點的存儲序號是不連續(xù)的，各結(jié)點在存儲空間中的位置關(guān)系與

邏輯關(guān)系也不一致；

b.各數(shù)據(jù)元素之間的前后件關(guān)系是由各結(jié)點的指針域來指示的；

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

前件結(jié)點，只能順指針向鏈尾進(jìn)行掃描。

為了彌補(bǔ)線性單鏈表的缺陷，在某些應(yīng)用中為線性鏈表每個結(jié)點設(shè)置兩個

指針，左指針用以指向其前件結(jié)點，右指針指向其后件結(jié)點。

(4)帶鏈的棧

帶鏈的?？梢杂脕硎占嬎銠C(jī)存儲空間中所有空閑的存儲結(jié)點。

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

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

②入棧運(yùn)算：在棧頂位置插入一個新元素；

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

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

(5)帶鏈的隊列

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

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

②入隊運(yùn)算：在循環(huán)隊列的隊尾加入一個新元素；

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

【真題演練】

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

A.所謂有序表是指在順序存儲空間內(nèi)連續(xù)存放的元素序列

B.有序表只能順序存儲在連續(xù)的存儲空間內(nèi)

C.有序表可以用鏈?zhǔn)酱鎯Ψ绞酱鎯υ诓贿B續(xù)的存儲空間內(nèi)

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

【答案】C

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

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

運(yùn)算，要求有序表必須順序存儲。

2.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)與順序存儲結(jié)構(gòu)相比，鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)點有

()o［2014年9月真題］

A.節(jié)省存儲空間

B.插入與刪除運(yùn)算效率高

C.便于查找

D.排序時減少元素的比較次數(shù)

【答案】B

【解析】線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)與順序存儲結(jié)構(gòu)的優(yōu)缺點比較如下：

類型|優(yōu)點|缺點

①插入和刪除運(yùn)算效率很低

①方便隨機(jī)存取

順序②存儲空間不便于擴(kuò)充

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

表③不便于對存儲空間的動態(tài)分

結(jié)點間的邏輯關(guān)系

配

①在進(jìn)行插入和刪除操作時，只

需要改變指針需要額外的空間來表示數(shù)據(jù)元

鏈表

②鏈表的存儲空間易于擴(kuò)充，容素之間的邏輯關(guān)系，存儲密度低

易實現(xiàn)空間的動態(tài)分配

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

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

連續(xù)的

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

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

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

【答案】A

【藍(lán)析】BC兩項錯誤，邏輯概念上的線性非線性是否有序與存儲結(jié)構(gòu)為順序

還是鏈?zhǔn)經(jīng)]有直接關(guān)系；D項錯誤，鏈?zhǔn)酱鎯Y(jié)構(gòu)比順序存儲結(jié)構(gòu)更耗費(fèi)存儲空

間，因為鏈?zhǔn)酱鎯Y(jié)構(gòu)中除了要存儲順序結(jié)構(gòu)中的數(shù)據(jù)外還要存儲指針。

考點2線性鏈表的基本運(yùn)算

(1)常見的線性表的運(yùn)算

線性鏈表的運(yùn)算主要有以下幾個：

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

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

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

④將一個線性鏈表按要求進(jìn)行分解；

⑤逆轉(zhuǎn)線性鏈表；

⑥復(fù)制線性鏈表；

⑦線性鏈表的排序；

⑧線性鏈表的查找。

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

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

從頭指針指向的結(jié)點開始往后沿指針進(jìn)行掃描，直到后面已沒有結(jié)點或下

一個結(jié)點的數(shù)據(jù)域為x為止。因此，由這種方法找到的結(jié)點p有兩種可能：當(dāng)

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

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

線性鏈表中的最后一個結(jié)點號。

(3)線性鏈表的插入

①定義：線性鏈表的插入是指在鏈?zhǔn)絻Υ娼Y(jié)構(gòu)下的線性表中插入一個新元

素。

②插入過程：

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

a.從可利用棧取得一個結(jié)點，設(shè)該結(jié)點號為p,并置結(jié)點p的數(shù)據(jù)域為插

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

存儲序號為q。

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

結(jié)點的指針域內(nèi)容：

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

第二，使結(jié)點q的指針域內(nèi)容改為指向結(jié)點P。

③插入特點：

a.不會發(fā)生上溢現(xiàn)象；

b.可方便實現(xiàn)存儲空間動態(tài)分配；

c.不發(fā)生數(shù)據(jù)元素移動現(xiàn)象，只改變結(jié)點指針，提高插入效率。

(