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

目錄

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5.1SELECT語(yǔ)句....................................................................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語(yǔ)句與聯(lián)合查詢...........................................................140

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

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

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

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

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

6.2索引的存儲(chǔ)與分類................................................................143

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

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

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

6.6對(duì)索引的進(jìn)一步說(shuō)明..............................................................149

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

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

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

考點(diǎn)精講..................................................................................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對(duì)視圖的進(jìn)一步說(shuō)明..............................................................155

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

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

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

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

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

8.2表維護(hù)語(yǔ)句.......................................................................162

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

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

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

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

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

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

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

9.5對(duì)觸發(fā)器的進(jìn)一步說(shuō)明............................................................167

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

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

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

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

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

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

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

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

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

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

11.1存儲(chǔ)過(guò)程........................................................................171

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

第12章訪問(wèn)控制與安全管理..................................................................180

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

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

12.1用戶賬號(hào)管理....................................................................180

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

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

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

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

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

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

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

133二進(jìn)制日志文件的使用...........................................................193

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

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

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

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

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

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

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

第15章開(kāi)發(fā)實(shí)例............................................................................203

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

第一部分公共基礎(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.樹的基本概念，二叉樹的定義及其存儲(chǔ)結(jié)構(gòu)；二叉樹的前序、中序和后序遍歷。

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

考點(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ū)?/p>

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

的。

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

義性。

③有窮性有窮性是指算法必須能在有限的時(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>

要的。常用

于解決“是否存在”或“有多少種可能”等類型的問(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)行分類，從而引出一些有用的信息，減少列舉量。

(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ò)程逐

步這行綜合。

②主要特點(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í)行效率較低。

③分類

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ù)，W

算法的工作量=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)定

義為：

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

X€D?

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

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

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

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

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

(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ù)，則稱該算法是原地工作的。

【真題演練】

I.下列敘述中正確的是()。［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ù)雜度類似，空間復(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)度R.算法所處理的

數(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ù)集合中的各元素以各種方式迸行運(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)，也稱數(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)正確，如樹形結(jié)構(gòu)只有一個(gè)根結(jié)點(diǎn)，為非線性結(jié)構(gòu)。

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

（I）在數(shù)據(jù)結(jié)構(gòu)的圖形表示中，數(shù)據(jù)集合D中每個(gè)元素用中間標(biāo)有元素值的方框表示，稱為數(shù)據(jù)結(jié)點(diǎn)（簡(jiǎn)

稱結(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)稱為根結(jié)點(diǎn)，沒(méi)有后件的結(jié)點(diǎn)稱為終端結(jié)點(diǎn)（也稱葉子結(jié)點(diǎn)），其余結(jié)

點(diǎn)都稱為內(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í)，稱其為線性結(jié)構(gòu)：

①有且只有一個(gè)根結(jié)點(diǎn)；

②每個(gè)結(jié)點(diǎn)最多只有一個(gè)前件，也最多只有一個(gè)后件。線性結(jié)構(gòu)中插入或刪除任何一個(gè)結(jié)點(diǎn)還應(yīng)是線性結(jié)

構(gòu)，如果不滿足這個(gè)條件就不能稱之為線性結(jié)構(gòu)。

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

性結(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)ai.它無(wú)前件；

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

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

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

【真題演練】

下列敘述中正確的是（）。［2014年9月真題］A.結(jié)點(diǎn)中具有兩個(gè)

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

線性結(jié)構(gòu)，也可以是非線性結(jié)構(gòu)C.二叉樹只能采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

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

【答案】B

【解析】A項(xiàng)錯(cuò)誤，具有兩個(gè)指針域的旌表可能是雙向鏈表；B項(xiàng)正確，如雙向鏈表是線性結(jié)構(gòu)，二叉樹為

非線性結(jié)構(gòu)，兩者結(jié)點(diǎn)中均有兩個(gè)指針域；C項(xiàng)錯(cuò)誤，二叉樹通常采用鏈?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ī)中存放線性表的方法，也稱順序分

配。

（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（n《m）,插入的位置為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)度減小1。

1.4棧和隊(duì)列

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

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

性表。

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

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

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

②棧遵循“先進(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)行

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

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

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

②退棧運(yùn)算退棧運(yùn)算是指取出棧頂元素并賦給一個(gè)指定的變量。操

作過(guò)程如下：

a.首先判斷棧頂指針是否為0。如果是，則說(shuō)明?？?，不可能進(jìn)行退棧操作（這種情況稱為?！跋乱纭卞e(cuò)

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

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

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

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

作過(guò)程如下：

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

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

【真題演練】

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

A.棧

B.樹

C.隊(duì)列

D.二叉樹

【答案】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)