全國計算機等級考試《二級MySQL數(shù)據(jù)庫程序設(shè)計》專用教材【考綱分析＋考點精講＋真題演練＋強化習(xí)題】

目錄

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

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

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

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

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

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

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

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

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

1.6樹與二叉樹........................................................................16

1.7查找技術(shù).........................................................................20

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

強化習(xí)題..................................................................................23

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

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

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

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

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

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

強化習(xí)題..................................................................................31

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

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

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

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

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

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

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

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

強化習(xí)題..................................................................................55

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

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

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

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

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

4.3關(guān)系代數(shù).........................................................................69

4.4數(shù)據(jù)庫設(shè)計與管理.................................................................73

強化習(xí)題..................................................................................77

第二部分MySQL數(shù)據(jù)庫程序設(shè)計...................................................................80

第1章數(shù)據(jù)庫技術(shù)的基本概念與方法...........................................................80

考弼分析..................................................................................80

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

1.1基本概念.........................................................................80

1.2數(shù)據(jù)庫系統(tǒng)的特點.................................................................81

1.3數(shù)據(jù)庫系統(tǒng)的結(jié)構(gòu).................................................................81

1.4數(shù)據(jù)模型.........................................................................84

1.5數(shù)據(jù)庫設(shè)計.......................................................................87

強化習(xí)題..................................................................................89

第2章MySQL概述...........................................................................90

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

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

2.1MySQL系統(tǒng)特性..................................................................90

2.2MySQL服務(wù)器的安裝和配置.......................................................90

2.3MySQL服務(wù)器的啟動與關(guān)閉.......................................................97

2.4MySQL客戶端管理工具............................................................98

2.5MySQL語言結(jié)構(gòu).................................................................100

強化習(xí)題..................................................................................102

第3章數(shù)據(jù)庫和，...........................................................................103

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

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

3.1數(shù)據(jù)庫的創(chuàng)建與使用..............................................................103

3.2創(chuàng)建和操縱表....................................................................105

強化習(xí)題..................................................................................117

第4章表數(shù)據(jù)的基本操作.....................................................................119

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

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

4.1插入表數(shù)據(jù).......................................................................119

4.2刪除表數(shù)據(jù).......................................................................122

43修改表數(shù)據(jù).......................................................................123

強化習(xí)題..................................................................................124

第5章數(shù)據(jù)庫的查詢.........................................................................126

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

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

5.1SELECT語句....................................................................126

5.2列的選擇與指定..................................................................128

5.3FROM子句與連接表.............................................................129

5.4WHERE子句....................................................................132

5.5GROUPBY子句與分組數(shù)據(jù).......................................................137

5.6HAVING子句....................................................................138

5.7ORDERBY子句..................................................................139

5.8LIMIT子句......................................................................139

5.9UNION語句與聯(lián)合查詢...........................................................140

強化習(xí)題..................................................................................141

第6章索引................................................................................143

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

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

6.1索引概述.........................................................................143

6.2索引的存儲與分類................................................................143

6.3索引的創(chuàng)建.......................................................................145

6.4索引的查看.......................................................................148

6.5索引的刪除.......................................................................148

6.6對索引的進一步說明..............................................................149

強化習(xí)題..................................................................................149

第7章視圖................................................................................151

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

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

7.1視圖概述.........................................................................151

7.2創(chuàng)建視圖.........................................................................151

7.3刪除視圖.........................................................................153

7.4修改視圖定義....................................................................153

7.5查看視圖定義....................................................................153

7.6更新視圖數(shù)據(jù)....................................................................153

7.7查詢視圖數(shù)據(jù)....................................................................154

7.8對視圖的進一步說明..............................................................155

強化習(xí)題..................................................................................157

第8章數(shù)據(jù)完整性約束與表維護語句...........................................................158

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

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

8.1數(shù)據(jù)完整性約束..................................................................158

8.2表維護語句.......................................................................162

第9章觸發(fā)器................................................................................165

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

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

9.1觸發(fā)器...........................................................................165

9.2創(chuàng)建觸發(fā)器.......................................................................165

93刪除觸發(fā)器.......................................................................166

9.4使用觸發(fā)器.......................................................................166

9.5對觸發(fā)器的進一步說明............................................................167

第10章事件...............................................................................168

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

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

10.1事件............................................................................168

10.2創(chuàng)建事件........................................................................168

103修改事件........................................................................170

10.4刪除事件........................................................................170

第H章存儲過程與存儲函數(shù)..................................................................171

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

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

11.1存儲過程........................................................................171

11.2存儲函數(shù)........................................................................178

第12章訪問控制與安全管理..................................................................180

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

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

12.1用戶賬號管理....................................................................180

12.2賬戶權(quán)限管理...................................................................182

強化習(xí)題..................................................................................186

第13章備份與恢復(fù)..........................................................................187

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

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

13.1數(shù)據(jù)備份與恢復(fù).................................................................187

13.2MySQL數(shù)據(jù)庫備份與恢復(fù)的方法..................................................187

133二進制日志文件的使用...........................................................193

強化習(xí)題..................................................................................194

第14章PHP的MySQL數(shù)據(jù)庫編程...........................................................195

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

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

14.1PHP概述........................................................................195

14.2PHP編程基礎(chǔ)...................................................................195

14.3使用PHP進行MySQL數(shù)據(jù)庫編程.................................................196

第15章開發(fā)實例............................................................................203

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

第一部分公共基礎(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)及其插入與刪除運算。

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

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

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

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

考點精講

1.1算法

考點1算法的基本概念

（1）算法的定義

算法是指解題方案的準(zhǔn)確而完整的描述，即算法是對特定問題求解步驟的一種描述。它是一組嚴(yán)謹(jǐn)定義運算

順序的規(guī)則，且每個規(guī)則都是明確有效的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。需要注意的是：算法不等于程序，也

不等于計算方法。

（2）算法的基本特征

①可行性a.算法中的每一步驟都必須能夠?qū)?/p>

現(xiàn)；b.算法執(zhí)行的結(jié)果要能夠達到預(yù)期的目

的。

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

義性。

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

的執(zhí)行時

間。

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

此算法有效，而

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

【真題演練】

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

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

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

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

【答案】A

【解析】算法設(shè)計有窮性要求操作步驟有限且必須在有限時間內(nèi)完成，耗費太長時間得到的正確結(jié)果是沒有

意義的。

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

（1）列舉法

①基本思想根據(jù)提出的問題，列舉所有可能的情況，并用問題中給定的條件檢驗?zāi)男┦切枰?，哪些是不?/p>

要的。常用

于解決“是否存在”或“有多少種可能”等類型的問題。

②主要特點

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

③注意事項例舉算法時，通過對實際問題進行詳細分析，將與問題有關(guān)的知識條理化、完備化、系統(tǒng)化，并

從中找出規(guī)

律，或?qū)λ锌赡艿那闆r進行分類，從而引出一些有用的信息，減少列舉量。

(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é)為一些簡單的問題，將簡單問題解決掉，再沿著原來分解的逆過程逐

步這行綜合。

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

解；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.遞歸是從算法本身到達遞歸的邊界的；b.遞推是

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

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

質(zhì)不變；“遞推”指

重復(fù)“減半”的過程。

(6)回溯法回溯法是指通過對問題的分析，找出一個解決問題的線索，然后沿著這個線索逐步試探，若試

探成功，則問

題得到解決，若試探失敗，則逐步回退換別的路線再進行試探。

【真題演練】

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

A.所謂算法就是計算方法B.程序可以作為算法的

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

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

【答案】B

【解析】程序可以作為算法的一種描述方法，算法在實現(xiàn)時需要用具體的程序設(shè)計語言描述。A項錯誤，算

法并不等同于計算方法，是指對解題方案的準(zhǔn)確而完整的描述；C項錯誤，算法設(shè)計需要考慮可行性、確定性、

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

到的正確結(jié)果是沒有意義的。

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

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

必須能在有限個步驟之后終止C.算法設(shè)計必須考慮算法的復(fù)雜

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

【答案】D

【解析】算法是指對解題方案的準(zhǔn)確而完整的描述。A項正確，算法強調(diào)實現(xiàn)，不同于數(shù)學(xué)上的計算方法；

B項正確，算法的有窮性是指，算法中的操作步驟為有限個，且每個步驟都能在有限時間內(nèi)完成；C項正確，算

法設(shè)計必須考慮執(zhí)行算法所需要的資源，即時間復(fù)雜度與空間復(fù)雜度；D項錯誤，算法的優(yōu)劣取決于算法復(fù)雜度，

只有當(dāng)算法被編程實現(xiàn)運行時才會受到運行環(huán)境影響。

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

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

①定義算法的時間復(fù)雜度是指執(zhí)行算法所需要的計算

工作量。

算法的工作量用算法所執(zhí)行的基本運算次數(shù)來度量，而算法所執(zhí)行的基本運算次數(shù)是問題規(guī)模的函數(shù)，W

算法的工作量=f(n)

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

②在同一問題規(guī)模下，若算法的基本運算次數(shù)取決于某一特定輸入，可用以下兩種方法來分析算法的工作量：

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

的平均性態(tài)定

義為：

A(n)=Zp(x)t(x)

X€D?

其中，x是所有可能輸入中的某個特定輸入，p(X)是X出現(xiàn)的概率，即輸入為X的概率，t(X)是算法在

輸入為x時所執(zhí)行的基本運算次數(shù)，Dn表示當(dāng)規(guī)模為n時，算法執(zhí)行時所有可能輸入的集合。

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

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

W(n)=max{t(x)}

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

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

空間。

②存儲空間組成一個算法的存儲空間包

括以下幾種：a.算法程序占用的空間；

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

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

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

問題規(guī)模來說是常數(shù)，則稱該算法是原地工作的。

【真題演練】

I.下列敘述中正確的是()。［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ù)雜度是指算法在計算機內(nèi)執(zhí)行時所需時間的度量；與時間復(fù)雜度類似，空間復(fù)雜度是

指算法在計算機內(nèi)執(zhí)行時所需存儲空間的度量。

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

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

法所處理的數(shù)據(jù)量C.算法程序中的語句或指令條數(shù)

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

【答案】A

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

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

A.算法程序的長度R.算法所處理的

數(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ù)集合中的各元素以各種方式迸行運算，包括插入、刪除、查找、更改等運算，也

包括對

數(shù)據(jù)元素進行分析。

②關(guān)鍵問題大量數(shù)據(jù)元素在計算機中如何組織，以便提高數(shù)據(jù)處理的效率，從而節(jié)省計算機的存儲空間，這

是進行數(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ù)進行處理時，各數(shù)據(jù)

元素在計算機中的存儲關(guān)系,即數(shù)據(jù)的存儲結(jié)構(gòu)：c.對各種數(shù)據(jù)結(jié)構(gòu)進行的運算.

②研究目的

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

量節(jié)省在數(shù)據(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)在計算機存儲空間中的存放形式。在數(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)的圖形表示

（I）在數(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)的運算是否按照線性結(jié)構(gòu)的規(guī)則來處理進行判斷。

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é)點ai.它無前件；

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

③除根結(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）概述順序存儲是一種最簡單的在計算機中存放線性表的方法，也稱順序分

配。

（2）特點：

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

②線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。在線性表的順序存儲結(jié)構(gòu)中，其前后件兩個

元素在存儲空間中是緊鄰的，且前件元素一定存儲在后件元素的

前面。

（3）運算在線性表的順序存儲結(jié)構(gòu)下，可對線性表進行以下運算：

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

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

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

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

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

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

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

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

【真題演練】

在線性表的順序存儲結(jié)構(gòu)中，其存儲空間連續(xù)，各個元素所占的字節(jié)數(shù)（）。［2014年3月真題］

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

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

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

【答案】A

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

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

考點3順序表的插入運算

假設(shè)線性表的存儲空間為V（1：m）,線性表的長度為n（n《m）,插入的位置為i（表示在第i個位置插入

元素），則順序表插入新元素過程如下：

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

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

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

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

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

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

考點4順序表的刪除運算

假設(shè)線性表的存儲空間為V（1：m）,線性表的長度為n（nWm）,刪除的位置為i（表示刪除第i個元素），

則順序表刪除元素的過程如下：

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

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

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

（2）然后從第i+1個元素開始，直到最后一個元素，其中每一個元素均依次往前移動一個位置。

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

1.4棧和隊列

考點1棧及其基本運算

（1）棧的定義棧是限定在一端進行插入與刪除的線

性表。

（2）棧的特點：

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

也是最先被刪除的元素；枝底元素總是最先被插入也是最后被刪除的。

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

③通常用指針top來指示棧頂位置，用指針bottom指向棧底，棧頂指針top動態(tài)反映了棧中元素的變化情況。

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

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

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

下：

a.首先判斷棧頂指針是否已經(jīng)指向存儲空間的最后一個位置。如果是，則說明?？臻g已滿，不可能再進行

入棧操作（這種情況稱為?！吧弦纭卞e誤），算法結(jié)束。

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

新元素X插入棧頂指針指向的位置。

②退棧運算退棧運算是指取出棧頂元素并賦給一個指定的變量。操

作過程如下：

a.首先判斷棧頂指針是否為0。如果是，則說明?？眨豢赡苓M行退棧操作（這種情況稱為?！跋乱纭卞e

誤），算法結(jié)束。

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

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

③讀棧頂元素讀棧頂元素是指將棧頂元素賦給一個指定的變量。操

作過程如下：

a.首先判斷棧頂指針是否為0。如果是，則說明棧空，讀不到棧頂元素，算法結(jié)束。b.然后將棧頂元素賦

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

【真題演練】

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

A.棧

B.樹

C.隊列

D.二叉樹

【答案】A

【解析】棧和隊列都是受限的線性表，其中棧按照“先進后出”的原則組織數(shù)據(jù)，插入與刪除操作被限制在

棧頂一端進行。棧支持子程序調(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)的進程調(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)