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

全國(guó)計(jì)算機(jī)等級(jí)考試《二級(jí)C++語(yǔ)言程序設(shè)計(jì)》專(zhuān)

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

題】

目錄

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

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

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

考點(diǎn)精講............................................................

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

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

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

1.4棧和隊(duì)列...................................................

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

L6樹(shù)與二叉樹(shù).................................................

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

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

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

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

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

考點(diǎn)精講............................................................

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

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

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

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

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

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

考點(diǎn)精講............................................................

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

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

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

3.4軟件測(cè)試...................................................

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

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

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

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

考點(diǎn)精講............................................................

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

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

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

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

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

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

第1章C++語(yǔ)言概述.....................................................

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

考點(diǎn)精講............................................................

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

1.2C++語(yǔ)言的特點(diǎn)..............................................

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

L4C++語(yǔ)言的基本符號(hào)..........................................

1.5C++語(yǔ)言的詞匯..............................................

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

L7C++程序的開(kāi)發(fā)過(guò)程..........................................

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

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

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

考點(diǎn)精講............................................................

2.1C++語(yǔ)言的數(shù)據(jù)類(lèi)型.........................................

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

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

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

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

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

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

考點(diǎn)精講............................................................

3.1C++語(yǔ)句...................................................

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

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

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

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

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

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

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

考點(diǎn)精講............................................................

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

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

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

4.4動(dòng)態(tài)存儲(chǔ)分配...............................................

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

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

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

考點(diǎn)精講............................................................

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

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

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

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

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

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

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

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

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

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

第6章類(lèi)和對(duì)象........................................................

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

考點(diǎn)精講............................................................

6.1類(lèi)的定義...................................................

6.2對(duì)象的定義.................................................

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

6.4自由存儲(chǔ)對(duì)象...............................................

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

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

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

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

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

6.10成員對(duì)象..................................................

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

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

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

考點(diǎn)精講............................................................

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

7.2派生類(lèi)對(duì)基類(lèi)成員的訪問(wèn).....................................

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

7.4多繼承與虛基類(lèi).............................................

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

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

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

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

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

考點(diǎn)精講............................................................

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

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

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

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

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

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

考點(diǎn)精講............................................................

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

9.2類(lèi)模板.....................................................

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

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

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

考點(diǎn)精講............................................................

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

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

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

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

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

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

考綱分析

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

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

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

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

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

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

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

序遍歷。

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

插入類(lèi)排序）。

考點(diǎn)精講

1.1算法

考點(diǎn)1算法的基本概念

（1）算法的定義

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

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

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

算方法。

（2）算法的基本特征

①可行性

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

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

②確定性

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

的解釋?zhuān)膊辉试S有多義性。

③有窮性

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

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

④擁有足夠的情報(bào)

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

有足夠的情報(bào)時(shí)，此算法有效，而當(dāng)提供的情報(bào)不夠時(shí)，算法可能無(wú)效。

【真題演練】

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

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

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

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

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

【答案】A

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

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

考點(diǎn)2算法設(shè)計(jì)基本方法

(1)列舉法

①基本思想

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

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

類(lèi)型的問(wèn)題。

②主要特點(diǎn)

算法比較簡(jiǎn)單，但列舉情況較多時(shí)，算法工作量很大。

③注意事項(xiàng)

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

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

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

(2)歸納法

①基本思想

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

②主要特點(diǎn)

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

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

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

(3)遞推

①基本思想

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

②主要特點(diǎn)

a.初始條件或問(wèn)題本身已給定，或通過(guò)對(duì)問(wèn)題的分析化簡(jiǎn)得到；

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

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

(4)遞歸

①基本思想

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

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

②主要特點(diǎn)

a.遞歸的基礎(chǔ)是歸納，對(duì)問(wèn)題逐層分解的過(guò)程實(shí)際上并沒(méi)有對(duì)問(wèn)題進(jìn)行求

解；

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

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

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

③分類(lèi)

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

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

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

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

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

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

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

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

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

（6）回溯法

回溯法是指通過(guò)對(duì)問(wèn)題的分析，找出一個(gè)解決問(wèn)題的線索，然后沿著這個(gè)

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

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

【真題演練】

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

A.所謂算法就是計(jì)算方法

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

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

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

【答案】B

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

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

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

情報(bào)；D項(xiàng)錯(cuò)誤，算法設(shè)計(jì)有窮性要求操作步驟有限且必須在有限時(shí)間內(nèi)完成，

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

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

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

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

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

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

［答案］D

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

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

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

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

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

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

（1）時(shí)間復(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ī)模。

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

以下兩種方法來(lái)分析算法的工作量：

a.平均性態(tài)

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

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

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

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

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

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

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

義為：

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

①定義

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

②存儲(chǔ)空間組成

一個(gè)算法的存儲(chǔ)空間包括以下幾種：

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

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

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

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

附加存儲(chǔ)空間，若額外空間相對(duì)于問(wèn)題規(guī)模來(lái)說(shuō)是常數(shù)，則稱(chēng)該算法是原地工

作的。

【真題演練】

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

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)

［答案］B

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

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

量。

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

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

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

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

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

【答案】A

【解析】空間復(fù)雜度是是對(duì)一個(gè)算法在運(yùn)行過(guò)程中臨時(shí)占用存儲(chǔ)空間大小

的量度。

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

A.算法程序的長(zhǎng)度

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

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

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

【答案】D

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

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

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

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

考點(diǎn)1概述

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

①定義

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

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

②關(guān)鍵問(wèn)題

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

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

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

①研究問(wèn)題

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

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

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

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

②研究目的

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

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

存儲(chǔ)空間。

考點(diǎn)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ù)元素集合的表示。簡(jiǎn)言之，數(shù)據(jù)結(jié)構(gòu)是指帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合,

這里的“結(jié)構(gòu)”指數(shù)據(jù)元素之間的前后件關(guān)系。一個(gè)數(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)系。

③表示

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

B=（D,R）

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

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

①定義

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

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

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

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

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

【真題演練】

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

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

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

構(gòu)

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

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

［答案］D

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

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

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

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

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

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

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

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

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

（2）在數(shù)據(jù)結(jié)構(gòu)中，沒(méi)有前件的結(jié)點(diǎn)稱(chēng)為根結(jié)點(diǎn)，沒(méi)有后件的結(jié)點(diǎn)稱(chēng)為終

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

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

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

考點(diǎn)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)（線性表）

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

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

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

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

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

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

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

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

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

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

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

考點(diǎn)1線性表的基本概念

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

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

置是線性的。

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

①有且只有一個(gè)根結(jié)點(diǎn)a.,它無(wú)前件；

②有且只有一個(gè)終端結(jié)點(diǎn)4,它無(wú)后件；

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

一個(gè)后件。

線性表中結(jié)點(diǎn)的個(gè)數(shù)n稱(chēng)為線性表的長(zhǎng)度。當(dāng)n=0時(shí)，稱(chēng)為空表。

【真題演練】

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

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

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

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

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

【答案】B

【解析】A項(xiàng)錯(cuò)誤，具有兩個(gè)指針域的鏈表可能是雙向鏈表；B項(xiàng)正確，如

雙向鏈表是線性結(jié)構(gòu)，二叉樹(shù)為非線性結(jié)構(gòu)，兩者結(jié)點(diǎn)中均有兩個(gè)指針域；C項(xiàng)

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

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

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

(1)概述

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

(2)特點(diǎn)：

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

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

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

且前件元素一定存儲(chǔ)在后件元素的前面。

(3)運(yùn)算

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

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

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

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

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

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

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

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

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

【真題演練】

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

（）。［2014年3月真題］

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

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

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

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

【答案】A

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

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

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

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

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

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

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

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

束；

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

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

（2）從最后一個(gè)元素開(kāi)始，直到第i個(gè)元素，其中每一個(gè)元素均往后移動(dòng)

一個(gè)位置。

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

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

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

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

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

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

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

入。

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

依次往前移動(dòng)一個(gè)位置。

（3）最后將線性表的長(zhǎng)度減小lo

1.4棧和隊(duì)列

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

（1）棧的定義

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

（2）棧的特點(diǎn)：

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

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

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

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

③通常用指針top來(lái)指示棧頂位置，用指針bottom指向棧底，棧頂指針top

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

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

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

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

①入棧運(yùn)算

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

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

說(shuō)明?？臻g已滿，不可能再進(jìn)行入棧操作（這種情況稱(chēng)為棧“上溢”錯(cuò)誤），

算法結(jié)束。

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

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

②退棧運(yùn)算

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

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

作（這種情況稱(chēng)為?！跋乱纭卞e(cuò)誤），算法結(jié)束。

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

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

③讀棧頂元素

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

a.首先判斷棧頂指針是否為0。如果是，則說(shuō)明?？?，讀不到棧頂元素，

算法結(jié)束。

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

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

【真題演練】

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

A.棧

B.樹(shù)

C.隊(duì)列

D.二叉樹(shù)

【答案】A

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

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

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

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

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ù)本身，直到滿足特定條件時(shí)才停

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

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

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

入棧與退棧運(yùn)算后，top=20,則當(dāng)前棧中的元素個(gè)數(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)算過(guò)程中，指針始終指向棧頂元素。top=20,說(shuō)明當(dāng)前棧中有20個(gè)元素。

4.一個(gè)棧的初始狀態(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)行操

作。

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

（1）什么是隊(duì)列

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

（2）隊(duì)列的特點(diǎn)

①允許插入的一端稱(chēng)為隊(duì)尾，用隊(duì)尾指針指向隊(duì)尾元素；允許刪除的一端

稱(chēng)為隊(duì)頭，用排頭指針指向排頭元素的前一個(gè)位置。

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

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

③隊(duì)尾指針rear和排頭指針front共同反映隊(duì)列中元素變動(dòng)情況。

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

變化。

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

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

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

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

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

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

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

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

①入隊(duì)運(yùn)算

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

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

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

此時(shí)算法結(jié)束。

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

——1O

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

②退隊(duì)運(yùn)算

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

作過(guò)程如下：

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

隊(duì)運(yùn)算。這種情況稱(chēng)為“下溢”。此時(shí)算法結(jié)束。

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

front=lo

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

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

志（即s=0）。

【真題演練】

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

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)

【答案】D

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

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

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

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

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

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

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

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

【答案】A

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

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

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

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

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

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

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

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

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

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

［答案］D

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

尾指針要加進(jìn)1,每次出隊(duì)操作隊(duì)頭指針要%m進(jìn)1。因?yàn)榇嬖谌邕\(yùn)算，所以隊(duì)

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

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

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

［答案］D

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

入隊(duì)使得隊(duì)尾指針變化，出隊(duì)使得隊(duì)頭指針變化。

1.5線性鏈表

考點(diǎn)1線性鏈表的基本概念

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

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

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

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

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

(2)鏈?zhǔn)酱鎯?chǔ)結(jié)點(diǎn)組成：

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

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

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

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

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

鏈?zhǔn)酱鎯?chǔ)方式既可用于表示線性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。在用鏈

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

(3)線性鏈表

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

②特點(diǎn)

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

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

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

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

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

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

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

(4)帶鏈的棧

帶鏈的?？梢杂脕?lái)收集計(jì)算機(jī)存儲(chǔ)空間中所有空閑的存儲(chǔ)結(jié)點(diǎn)。

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

①棧的初始化：建立一個(gè)空棧的順序存儲(chǔ)空間；

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

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

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

(5)帶鏈的隊(duì)列

與順序隊(duì)列一樣，帶鏈隊(duì)列的基本操作有以下幾個(gè)：

①隊(duì)列的初始化：建立一個(gè)空隊(duì)列的順序存儲(chǔ)空間；

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

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

【真題演練】

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

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

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

C.有序表可以用鏈?zhǔn)酱鎯?chǔ)方式存儲(chǔ)在不連續(xù)的存儲(chǔ)空間內(nèi)

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

【答案】C

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

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

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

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

()o［2014年9月真題］

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

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

C.便于查找

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

【答案】B

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

類(lèi)型|優(yōu)點(diǎn)|缺點(diǎn)

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

①方便隨機(jī)存取

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

②無(wú)需額外的存儲(chǔ)空間來(lái)表示

表③不便于對(duì)存儲(chǔ)空間的動(dòng)態(tài)分

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

配

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

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

鏈表

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

易實(shí)現(xiàn)空間的動(dòng)態(tài)分配

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

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

【答案】A

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

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

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

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

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

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

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

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

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

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

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

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

⑦線性鏈表的排序；

⑧線性鏈表的查找。

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

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

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

一個(gè)結(jié)點(diǎn)的數(shù)據(jù)域?yàn)閤為止。因此，由這種方法找到的結(jié)點(diǎn)p有兩種可能：當(dāng)

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

的前一個(gè)結(jié)點(diǎn)序號(hào)；當(dāng)線性鏈表中不存在包含元素x的結(jié)點(diǎn)時(shí)，則找到的p為

線性鏈表中的最后一個(gè)結(jié)點(diǎn)號(hào)。

(3)線性鏈表的插入

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

素。

②插入過(guò)程：

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

a.從可利用棧取得一個(gè)結(jié)點(diǎn)，設(shè)該結(jié)點(diǎn)號(hào)為p,并置結(jié)點(diǎn)p的數(shù)據(jù)域?yàn)椴?/p>

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

存儲(chǔ)序號(hào)為q。

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

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

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

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

③插入特點(diǎn)：

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

b.可方便實(shí)現(xiàn)存儲(chǔ)空間動(dòng)態(tài)分配；

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

(