全國計算機等級考試二級公共基礎(chǔ)知識課件

1、全國計算機等級考試全國計算機等級考試National Computer Rank Examination+全國計算機等級考試全國計算機等級考試National Computer Rank Examination第一部分 公共基礎(chǔ)知識全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識3二級公共基礎(chǔ)知識考試內(nèi)容二級公共基礎(chǔ)知識考試內(nèi)容 數(shù) 據(jù) 結(jié) 構(gòu) 和 算 法數(shù) 據(jù) 結(jié) 構(gòu) 和 算 法 程 序 設(shè) 計 基 礎(chǔ)程 序 設(shè) 計 基 礎(chǔ) 軟件工程軟件工程 數(shù) 據(jù) 庫 設(shè) 計 基 礎(chǔ)數(shù) 據(jù) 庫 設(shè) 計 基 礎(chǔ)全國計算

2、機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識41 1、二級公共基礎(chǔ)知識不單獨考試，與其他二、二級公共基礎(chǔ)知識不單獨考試，與其他二級科目組合在一起，作為二級科目考核內(nèi)容的級科目組合在一起，作為二級科目考核內(nèi)容的一部分。公共基礎(chǔ)部分占全卷的一部分。公共基礎(chǔ)部分占全卷的2020分。分。2 2、公共基礎(chǔ)知識考查方式為選擇題共、公共基礎(chǔ)知識考查方式為選擇題共2020道。道。二級公共基礎(chǔ)知識考試方式二級公共基礎(chǔ)知識考試方式全國計算機等級考試National Computer Rank Examination全國計算機等級

3、考試全國計算機等級考試二級公共基礎(chǔ)知識5 理解基本概念理解基本概念 多做練習多做練習 適當記憶一些名詞適當記憶一些名詞 與所學程序設(shè)計語言結(jié)合起來理解與所學程序設(shè)計語言結(jié)合起來理解二級公共基礎(chǔ)知識學習方法二級公共基礎(chǔ)知識學習方法第一章第一章 數(shù)據(jù)結(jié)構(gòu)和算法數(shù)據(jù)結(jié)構(gòu)和算法全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識7本章知識要點本章知識要點算法算法算法的定義算法的特征算法復(fù)雜度數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的定義邏輯結(jié)構(gòu) 和 物理結(jié)構(gòu)線性結(jié)構(gòu) 和 非線性結(jié)構(gòu)順序表、鏈表、堆棧隊列、循環(huán)隊列、樹算法的基本要素全

4、國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識8算法是解決方案的準確而完整性描述。一、算法一、算法算法的特性： （1）有窮性：算法必須在有限的次數(shù)內(nèi)完成。有窮性：算法必須在有限的次數(shù)內(nèi)完成。 （2）確定性：算法的每一步必須是明確的。確定性：算法的每一步必須是明確的。 （3）可行性：算法的每一步必須是可以實現(xiàn)的?？尚行裕核惴ǖ拿恳徊奖仨毷强梢詫崿F(xiàn)的。 （4）擁有足夠的情報：算法必須有一定的輸入擁有足夠的情報：算法必須有一定的輸入和輸出。輸出。算法不等于程序，也不等于計算方法。算法不等于程序，也不等于計算方法

5、。全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識9算法的基本要素： （1）對數(shù)據(jù)對象的運算和操作運算和操作： A .算術(shù)運算 B .邏輯運算 C .關(guān)系運算 D .數(shù)據(jù)傳輸 （2）算法的控制結(jié)構(gòu)控制結(jié)構(gòu)： A .順序結(jié)構(gòu) B .選擇結(jié)構(gòu) C .循環(huán)結(jié)構(gòu)一、算法一、算法全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識10算法的復(fù)雜度：衡量算法優(yōu)劣的量。 （1）時間復(fù)雜度：算法的時間耗費。 A .算法中基本操作重復(fù)執(zhí)行

6、次數(shù)和算法執(zhí)行時間 同步增長，稱作算法的時間復(fù)雜度。 B .算法中基本操作重復(fù)執(zhí)行次數(shù)和問題規(guī)模有關(guān)， 是問題規(guī)模的函數(shù)。 C .算法的時間復(fù)雜度是指執(zhí)行算法所需要的計算工 作量。 （2）空間復(fù)雜度：執(zhí)行算法所需要的內(nèi)存空間。一、算法一、算法全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識11一、算法一、算法有窮性有窮性BCD全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識125、在計算機中，算法是指（ ） A) 加

7、工方法B) 解題方案的準確而完整的描述 C) 排序方法D) 查詢方法6、下列敘述中正確的是（ ） 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)。一、算法一、算法BB全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識13二、數(shù)據(jù)結(jié)構(gòu)二、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)主要研究兩方面的問題： （1）數(shù)據(jù)本身。 （2）數(shù)據(jù)之間的前后件關(guān)系。數(shù)據(jù)數(shù)據(jù) 結(jié)構(gòu)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)表示

8、為：DS=D，S例：D=春，夏，秋，冬 S=(春,夏)，(夏,秋)，(秋,冬)，(冬,春)全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識14數(shù)據(jù)的結(jié)構(gòu)分為：數(shù)據(jù)的結(jié)構(gòu)分為： （1 1）物理結(jié)構(gòu)物理結(jié)構(gòu)：數(shù)據(jù)在計算機存儲介質(zhì)中真正存儲的結(jié)構(gòu)，：數(shù)據(jù)在計算機存儲介質(zhì)中真正存儲的結(jié)構(gòu)， 也被稱為也被稱為“存儲結(jié)構(gòu)存儲結(jié)構(gòu)” （2 2）邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)：人們所理解的數(shù)據(jù)之間的結(jié)構(gòu)，可以用圖示：人們所理解的數(shù)據(jù)之間的結(jié)構(gòu)，可以用圖示 的方法繪畫出來的數(shù)據(jù)之間的結(jié)構(gòu)。的方法繪畫出來的數(shù)據(jù)之間的結(jié)構(gòu)。例：一個班由35

9、名同學，他們的座位牌號就是物理結(jié)構(gòu)， 一次考試的排名是邏輯結(jié)構(gòu)。注意：邏輯結(jié)構(gòu)和物理結(jié)構(gòu)沒有必然的聯(lián)系，也不一定是注意：邏輯結(jié)構(gòu)和物理結(jié)構(gòu)沒有必然的聯(lián)系，也不一定是 一一對應(yīng)的。一一對應(yīng)的。二、數(shù)據(jù)結(jié)構(gòu)二、數(shù)據(jù)結(jié)構(gòu)全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識15數(shù)據(jù)的結(jié)構(gòu)分為：數(shù)據(jù)的結(jié)構(gòu)分為： （1 1）線性結(jié)構(gòu)線性結(jié)構(gòu)： 非空數(shù)據(jù)結(jié)構(gòu)同時滿足以下兩個條件就是非空數(shù)據(jù)結(jié)構(gòu)同時滿足以下兩個條件就是線性結(jié)構(gòu)線性結(jié)構(gòu)： A .A .有且僅有一個根結(jié)點；有且僅有一個根結(jié)點； B .B .除頭結(jié)點和尾結(jié)點外，任

10、何結(jié)點有且僅有一個前件除頭結(jié)點和尾結(jié)點外，任何結(jié)點有且僅有一個前件 和一個后件。和一個后件。 （2 2）非線性結(jié)構(gòu)非線性結(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)全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識16全國計算機等級考試二級公共基礎(chǔ)知識要求掌握的數(shù)據(jù)結(jié)構(gòu)共有以下六種全國計算機等級考試二級公共基礎(chǔ)知識要求掌握的數(shù)據(jù)結(jié)構(gòu)共有以下六種： 線性表 堆棧 隊列 循環(huán)隊列 線性鏈表 樹和二叉樹線性結(jié)構(gòu)物理結(jié)構(gòu)和邏輯結(jié)構(gòu)物理結(jié)構(gòu)和邏輯結(jié)構(gòu)物理結(jié)構(gòu)和邏輯結(jié)構(gòu)物理結(jié)

11、構(gòu)和邏輯結(jié)構(gòu)物理結(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)全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識1710102020303040405050606070708080三、順序表：順序表就是數(shù)組三、順序表：順序表就是數(shù)組1、順序表也叫做線性表，屬于線性結(jié)構(gòu)。 線性表的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)相同。2、特點： （1）有且僅有一個頭結(jié)點（根節(jié)點）和尾結(jié)點。 （2）任意其他結(jié)點至多有一個前件，一個后件。 （3）頭結(jié)點沒有前件，尾結(jié)點沒有后件。全國計算機等級考試National Compu

12、ter Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識18四、堆棧四、堆棧棧頂top棧底入棧入棧 / 壓入壓入出棧出棧 / 彈出彈出1、定義：只允許在棧頂位置插 入數(shù)據(jù)和刪除數(shù)據(jù)的線性結(jié) 構(gòu)是堆棧，簡稱為“棧”。2、堆棧屬于線性結(jié)構(gòu)。3、堆棧的邏輯結(jié)構(gòu)和物理結(jié)構(gòu) 相同。4、特點：先進后出，后進先出 所以堆棧也叫做先進后出表 （FILO）5、堆棧具備存儲功能：函數(shù)的 遞歸調(diào)用和表達式求解都用 到了堆棧。全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識19入棧順序：a、b

13、、c、d、e、f?？誥bacbabadba.入a入b入c出c入d模擬堆棧的數(shù)據(jù)出入過程：四、堆棧四、堆棧全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識20【典型題型】假設(shè)一個堆棧，入棧順序為abcde，認為在任何時刻均允許出棧，下列選項中不可能的出棧順序為（ ）A）abcde（可能） B）edcba（可能） C）cdeba（可能） D）cdeab（不可能）四、堆棧四、堆棧DBB全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公

14、共基礎(chǔ)知識21五、隊列五、隊列隊頭front隊尾rear入隊入隊出隊出隊1、隊列屬于線性結(jié)構(gòu)。2、隊列的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)相同。3、定義：入隊操作發(fā)生在隊尾，出隊操作發(fā)生在隊頭。4、特點：先進先出，后進后出，所以隊列也叫做先進先 出表（FIFO）。全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識22五、隊列五、隊列CADC全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識23六、循環(huán)隊列六、循環(huán)隊列rearfront全

15、國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識24入隊順序：a、b、c、d、e、f模擬循環(huán)隊列的數(shù)據(jù)出入過程：模擬循環(huán)隊列的數(shù)據(jù)出入過程：循環(huán)隊列空front=rearrearfrontafrontrear數(shù)據(jù)a入隊afrontrearb數(shù)據(jù)b入隊frontrearb數(shù)據(jù)a出隊入隊運算是往隊列隊尾插入一個入隊運算是往隊列隊尾插入一個數(shù)據(jù)元素；退隊運算是從隊列的數(shù)據(jù)元素；退隊運算是從隊列的隊頭刪除一個數(shù)據(jù)元素。隊頭刪除一個數(shù)據(jù)元素。 六、循環(huán)隊列六、循環(huán)隊列全國計算機等級考試National Compute

16、r Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識25七、線性鏈表七、線性鏈表1、鏈表屬于線性結(jié)構(gòu)。2、鏈表的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)不相同。3、線性鏈表由結(jié)點組成： 每個結(jié)點有兩個區(qū)域：數(shù)據(jù)域，指針域。 A .數(shù)據(jù)域，用來存儲數(shù)據(jù)。 B .指針域，用來指向下一個結(jié)點的位置。3、繪畫一個由5個節(jié)點組成的線性鏈表，數(shù)據(jù)為1、2、3、4、5。鏈表的結(jié)點鏈表的結(jié)點數(shù)據(jù)域數(shù)據(jù)域指針域指針域1 12 23 34 45 5單鏈表單鏈表全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識26

17、鏈表的種類：單鏈表、循環(huán)鏈表、雙向鏈表。 1234512345循環(huán)鏈表雙向鏈表 12345 七、線性鏈表七、線性鏈表全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識27七、線性鏈表七、線性鏈表BA存儲結(jié)構(gòu)存儲結(jié)構(gòu)非線性結(jié)構(gòu)非線性結(jié)構(gòu)全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識28八、樹與二叉樹八、樹與二叉樹1、樹的基本概念樹樹是一種簡單的非線性結(jié)構(gòu)，是n個結(jié)點的有限集合。一般的樹一般的樹R RKKP PQQD D

18、B BE ENNOOT TC CHHX XS SWWZ Z A AY YMMF FGGL L根節(jié)點根節(jié)點全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識29書書第一章第一章第二章第二章第三章第三章第四章第四章1.1節(jié)節(jié)1.2節(jié)節(jié)2.1節(jié)節(jié)2.2節(jié)節(jié)2.3節(jié)節(jié)3.1節(jié)節(jié)3.2節(jié)節(jié)4.1節(jié)節(jié)4.2節(jié)節(jié)書的層次結(jié)構(gòu)書的層次結(jié)構(gòu)注意注意:(1)樹結(jié)構(gòu)具有明顯的層次關(guān)系，即樹是一種層次結(jié)構(gòu)。因此具有層次關(guān)系的數(shù)據(jù)樹結(jié)構(gòu)具有明顯的層次關(guān)系，即樹是一種層次結(jié)構(gòu)。因此具有層次關(guān)系的數(shù)據(jù)都可以用樹這種數(shù)據(jù)結(jié)構(gòu)來描述。都可以

19、用樹這種數(shù)據(jù)結(jié)構(gòu)來描述。(2)在樹結(jié)構(gòu)中分層的原則是：根節(jié)點在第在樹結(jié)構(gòu)中分層的原則是：根節(jié)點在第1層，同一層上所有結(jié)點的所有子結(jié)點層，同一層上所有結(jié)點的所有子結(jié)點都在下一層。都在下一層。(3)在樹中，葉子結(jié)點沒有子樹。在樹中，葉子結(jié)點沒有子樹。八、樹與二叉樹八、樹與二叉樹全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識30（1）根節(jié)點：根節(jié)點：在數(shù)據(jù)結(jié)構(gòu)中，沒有前件的結(jié)點只有一個，稱為樹的根結(jié)點。（2）子節(jié)點：子節(jié)點：在數(shù)據(jù)結(jié)構(gòu)中，每一個結(jié)點可以有多個后件，它們都稱為該節(jié)點的子節(jié)點。沒有后件的結(jié)點稱為葉

20、子結(jié)點。葉子結(jié)點。（3）度：度：在數(shù)據(jù)結(jié)構(gòu)中，一個結(jié)點所擁有的后件的個數(shù)稱為該結(jié)點的度。在樹中，所有結(jié)點中的最大的度稱為該樹的度樹的度。（4）樹的深度樹的深度：樹的最大層次稱為樹的深度。八、樹與二叉樹八、樹與二叉樹2、樹的基本術(shù)語全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識31R RKKP PQQD DB BE ENNOOT TC CHHX XS SWWZ Z A AY YMMF FGGL L根結(jié)點：根結(jié)點：R葉子結(jié)點：葉子結(jié)點：C、M、F、E、XG、S、L、Z、A度為度為4的結(jié)點：的結(jié)點：R度為度為

21、3的結(jié)點：的結(jié)點：T度為度為2的結(jié)點：的結(jié)點：K、B、N、H度為度為1的結(jié)點：的結(jié)點：P、Q、D、O、Y、W八、樹與二叉樹八、樹與二叉樹該樹的度為：該樹的度為：4該樹的深度為：該樹的深度為：5全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識323 3、二叉樹、二叉樹八、樹與二叉樹八、樹與二叉樹二叉樹二叉樹也是一種非線性結(jié)構(gòu)，每個結(jié)點最多分兩叉的有序樹。二叉樹具有以下二叉樹具有以下兩個特點：兩個特點： (1)非空二叉樹只有一個根結(jié)點； (2)每一個結(jié)點最多有兩顆子樹，且分別稱為該結(jié)點的左子樹與右子樹。DDD

22、DDDDDD(a)只有根結(jié)點的二叉樹只有根結(jié)點的二叉樹(b)深度為深度為4的二叉樹的二叉樹全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識334 4、有序樹與無序樹：、有序樹與無序樹：八、樹與二叉樹八、樹與二叉樹eABeBA二叉樹和度為二的樹的區(qū)別： A .二叉樹是有序樹，度為二的樹是普通樹，屬于無序樹。 B .二叉樹允許為空，度為二的樹至少有三個結(jié)點。 【普通樹不允許為空，至少有一個結(jié)點】全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等

23、級考試二級公共基礎(chǔ)知識345 5、二叉樹的五種基本結(jié)構(gòu)、二叉樹的五種基本結(jié)構(gòu)aaabcbab空二叉樹只有一個結(jié)點的二叉樹有兩個結(jié)點的二叉樹有三個結(jié)點的二叉樹八、樹與二叉樹八、樹與二叉樹全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識35八、樹與二叉樹八、樹與二叉樹6 6、二叉樹的基本性質(zhì)、二叉樹的基本性質(zhì)全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識367 7、滿二叉樹和完全二叉樹：、滿二叉樹和完全二叉樹： (1)

24、滿二叉樹：滿二叉樹：除最后一層外，每一層上的所有結(jié)點都有兩個子結(jié)點。(2)完全二叉樹：完全二叉樹：除最后一層外，每一層上的結(jié)點數(shù)均達到最大值；在最后一層上只缺少右邊的若干結(jié)點。xeoqkbgxeoqkb滿二叉樹完全二叉樹123456八、樹與二叉樹八、樹與二叉樹全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識37填空題：填空題：設(shè)一棵完全二叉樹共有700個結(jié)點，則在該二叉樹中有 個葉子結(jié)點。經(jīng)典例題經(jīng)典例題350全國計算機等級考試National Computer Rank Examination全國計算機

25、等級考試全國計算機等級考試二級公共基礎(chǔ)知識388 8、二叉樹的遍歷：、二叉樹的遍歷： 二叉樹的遍歷二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有結(jié)點。二叉樹由二叉樹由根根、左子樹、左子樹、右子樹右子樹三部分組成三部分組成 二叉樹的遍歷可以分解為：訪問二叉樹的遍歷可以分解為：訪問根根，遍歷遍歷左子樹左子樹和和遍歷遍歷右子樹右子樹令：令：L L：遍歷左子樹遍歷左子樹 D D：訪問根結(jié)點訪問根結(jié)點 R R：遍歷右子樹遍歷右子樹 有六種遍歷方法：有六種遍歷方法： D DL LR R，L LD DR R，L LR RD D， D DR RL L，R RD DL L，R RL LD D A A F F G G

26、 E E D D C C B B約定先左后右約定先左后右, ,有三種遍歷方法：有三種遍歷方法： D DL LR R，L LD DR R，L LR RD D，分別分別稱為稱為前序前序遍歷遍歷（先先根遍歷）、根遍歷）、中序遍歷中序遍歷（中根遍歷）、中根遍歷）、后序遍歷后序遍歷（后根遍歷）（后根遍歷）八、樹與二叉樹八、樹與二叉樹全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識39(1)(1)先序遍歷（先序遍歷（D DL LR R） 若二叉樹非空若二叉樹非空 訪問根結(jié)點；訪問根結(jié)點； 先序遍歷左子樹；先序遍歷左子

27、樹； 先序遍歷右子樹先序遍歷右子樹； A A F F G G E E D D C C B B先序遍歷序列結(jié)果：先序遍歷序列結(jié)果：A A, ,B,D,E,G,B,D,E,G,C,FC,F八、樹與二叉樹八、樹與二叉樹全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識40八、樹與二叉樹八、樹與二叉樹(2)(2)中序遍歷（中序遍歷（L LD DR R） 若二叉樹非空若二叉樹非空中序遍歷左子樹中序遍歷左子樹; ;訪問根結(jié)點訪問根結(jié)點; ;中序遍歷右子樹中序遍歷右子樹; ; A A F F G G E E D D C

28、C B B中序遍歷序列：中序遍歷序列： D,B,G,E,D,B,G,E,A A, ,C,FC,F全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識41八、樹與二叉樹八、樹與二叉樹(3)(3)后序遍歷（后序遍歷（L LR RD D） 若二叉樹非空若二叉樹非空后序遍歷左子樹后序遍歷左子樹后序遍歷右子樹后序遍歷右子樹訪問根結(jié)點訪問根結(jié)點 A A F F G G E E D D C C B B 后序遍歷序列：后序遍歷序列： D,G,E,B,D,G,E,B,F,C,F,C,A A全國計算機等級考試National C

29、omputer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識42CAA經(jīng)典例題講解經(jīng)典例題講解ABCDEYFXZ全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識43經(jīng)典例題講解經(jīng)典例題講解全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識44經(jīng)典例題講解經(jīng)典例題講解第二章第二章 程序設(shè)計基礎(chǔ)程序設(shè)計基礎(chǔ)全國計算機等級考試National Computer Rank Examina

30、tion全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識46本章知識要點本章知識要點面向過程的程序設(shè)計面向過程的程序設(shè)計結(jié)構(gòu)化程序設(shè)計模塊化程序設(shè)計面向?qū)ο蟮某绦蛟O(shè)計面向?qū)ο蟮某绦蛟O(shè)計對象的定義對象的屬性和方法類和實例的派生與繼承消息與多態(tài)性全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識47一、程序設(shè)計方法一、程序設(shè)計方法1、面向過程的程序設(shè)計：C語言、BASIC語言等。 （1）結(jié)構(gòu)化程序設(shè)計：順序、選擇、循環(huán)。 三大結(jié)構(gòu)（順序、選擇、循環(huán)）可以解決所有的問題，和 問題的規(guī)模沒有關(guān)系。 （2）模塊化

31、程序設(shè)計：利用將程序分解的方法，將復(fù)雜的問題 簡單化，將單一的問題分成多個模塊獨立解決。 C語言：模塊就是函數(shù)。 VB語言：模塊就是模塊、子例程、子程序。 VFP數(shù)據(jù)庫：模塊就是子程序。 Access數(shù)據(jù)庫：模塊就是宏、事件代碼。2、面向?qū)ο蟮某绦蛟O(shè)計：VB、VFP、Java、Delphi等。全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識48二、程序設(shè)計風格二、程序設(shè)計風格1.1.源程序文檔化源程序文檔化 選擇標示符的名字 注釋（序言性和功能性注釋） 程序的視覺組織2.2.數(shù)據(jù)說明的方法數(shù)據(jù)說明的方法

32、顯示地說明一切變量 數(shù)據(jù)說明的次序應(yīng)該規(guī)范化 說明語句中變量安排有序化 對復(fù)雜數(shù)據(jù)結(jié)構(gòu)應(yīng)注釋說明3.3.語句的結(jié)構(gòu)語句的結(jié)構(gòu) 每條語句簡單明了 盡量不用或少用GOTO語句 盡量只采用3種基本控制結(jié)構(gòu)編程4.4.輸入和輸出輸入和輸出 對輸入數(shù)據(jù)進行校驗和合理性檢查 輸入輸出格式保持一致 設(shè)計良好的輸出報表全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識49三、結(jié)構(gòu)化程序設(shè)計三、結(jié)構(gòu)化程序設(shè)計20世紀70年代提出了結(jié)構(gòu)化程序設(shè)計（Structured Programming）結(jié)構(gòu)化程序設(shè)計的原則：（1）自頂向

33、下。（2）逐步求精。（3）模塊化。（4）限制使用goto語句。結(jié)構(gòu)化程序設(shè)計的基本結(jié)構(gòu)：（1）順序結(jié)構(gòu)。（2）選擇結(jié)構(gòu)。（3）重復(fù)結(jié)構(gòu)。結(jié)構(gòu)化程序設(shè)計主要強調(diào)程序的易讀性。全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識50利用圖示表示順序結(jié)構(gòu)ABAB程序流程圖N-S圖全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識51利用圖示表示選擇結(jié)構(gòu)條件滿足不滿足AB程序流程圖N-S圖AB條件滿足不滿足全國計算機等級考試Nat

34、ional Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識52利用圖示表示重復(fù)結(jié)構(gòu)(1)條件滿足不滿足S條件滿足不滿足S程序流程圖當型循環(huán)程序流程圖直到型循環(huán)全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識53利用圖示表示重復(fù)結(jié)構(gòu)(2)WHILE 條件SSUNTIL 條件N-S圖當型循環(huán)N-S圖直到型循環(huán)全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識54三、面

35、向?qū)ο蟮某绦蛟O(shè)計三、面向?qū)ο蟮某绦蛟O(shè)計 面向?qū)ο?Object Oriented)的程序設(shè)計方法已經(jīng)發(fā)展成為主流的軟件開發(fā)方法，起源于對面向?qū)ο笳Z言的研究。20世紀60年代后期首次被提出，80年代開始走向?qū)嵱?。面向?qū)ο蟮某绦蛟O(shè)計的術(shù)語： 對象、屬性、方法、封裝性、事件、類、父類、子類、實例、派生、繼承、消息、多態(tài)性。全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識55面向?qū)ο蠓椒ǖ闹饕獌?yōu)點：（1）與人類習慣的思維方法一致。（2）穩(wěn)定性好。（3）可重用性好。（4）易于開發(fā)大型軟件產(chǎn)品。（5）可維護性好。三、

36、面向?qū)ο蟮某绦蛟O(shè)計三、面向?qū)ο蟮某绦蛟O(shè)計全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識561 1、對象的定義、對象的定義對象：現(xiàn)實生活中存在的可以相互區(qū)分的物體。 是屬性和方法的封裝。對象的基本特點：（1）標識唯一性。（2）分類型。（3）多態(tài)性。（4）封裝性。（5）模塊獨立型好。全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識572 2、對象的屬性和方法、對象的屬性和方法屬性（Property）：用來描述對象的狀態(tài)

37、，是對象的靜態(tài)特性。 包括屬性名和屬性值兩方面。 例如：“顯示器”作為對象，具備“顏色”屬性，取值為“銀白色”。方法（Method）：用來描述對象的行為，是對象的動態(tài)特性。 方法具備方法名。 方法必須利用事件來激活。 例如:“顯示器”作為對象，具備“關(guān)閉”的方法，必須用“斷電”事件來激活。屬性名屬性值方法名事件封裝性：(Encapsulation)對象依靠對象名將自身的屬性和方法封裝。全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識583 3、類和實例的派生與繼承、類和實例的派生與繼承（1）類（Class

38、）：具有相同屬性和方法的 對象的集合，是對對象屬性和方法的抽 象。（2）實例（Instances）：類的子類派生出 的對象就是該類的一個實例。 類展現(xiàn)對象的共性；實例展現(xiàn)對象的個性。（3）派生過程中將發(fā)生屬性和方法的繼承 （Inheritance） 父類將自身的所有屬性和方法傳遞 給子類，子類繼承父類傳遞的所有屬性 和方法，并產(chǎn)生自身特有的屬性和方 法，再將這些屬性和方法的總和傳遞給 下一級子類。人人好人好人壞人壞人中國人中國人 外國人外國人張三張三全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識594

39、4、消息與多態(tài)性、消息與多態(tài)性（1）消息（Message）：進行對象之間的信息傳遞。（2）多態(tài)性（Polymorphism）：同樣的消息傳遞給不同的對象，導致 完全不同的行動。消息的組成：A .接收消息的對象名稱。B .消息標識符，也叫做“消息名”。C .零個或多個參數(shù)。全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識60結(jié)構(gòu)化程序設(shè)計主要強調(diào)的是（ ） A) 程序的規(guī)模 B) 程序的效率 C) 程序設(shè)計語言的先進性 練習題練習題DDDD全國計算機等級考試National Computer Rank Ex

40、amination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識61練習題練習題AACBB全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識62練習題練習題CDA第三章第三章 軟件工程基礎(chǔ)軟件工程基礎(chǔ)軟件（Software）= 程序 + 文檔 全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識64本章知識要點本章知識要點軟件危機軟件危機軟件生命周期軟件生命周期需求分析概要設(shè)計詳細設(shè)計測試調(diào)試軟件工程軟件工程全國計算

41、機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識65一、軟件危機一、軟件危機軟件危機主要表現(xiàn)在：（1）軟件需求的增長得不到滿足。（2）軟件開發(fā)成本和進度無法控制。（3）軟件質(zhì)量難以保證。（4）軟件不可維護或可維護度非常低。（5）軟件的成本不斷提高。（6）軟件開發(fā)生產(chǎn)率的提高趕不上硬件的發(fā)展和應(yīng)用需求的增長。總之，可以將軟件危機歸結(jié)為成本、質(zhì)量、生產(chǎn)率問題全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識66二、軟件工程二、軟件

42、工程 軟件工程是為了擺脫軟件危機而誕生的，主要思想是在軟件開發(fā)過程中應(yīng)用工程化原則。 軟件工程的三要素：方法、工具、工程。 軟件工程的主要內(nèi)容：軟件開發(fā)技術(shù)、軟件工程管理。 軟件工程的原則： （1）抽象。 （2）信息隱蔽。 （3）模塊化。 （4）局部化。 （5）確定性。 （6）一致性。 （7）完備性。 （8）可驗證性。全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識67二、軟件生命周期二、軟件生命周期軟件生命周期（Software Life Cycle，SLC）：將軟件產(chǎn)品從提出、實現(xiàn)、使用維護到停止使用

43、退役的過程稱為“軟件生命周期”。可行性研究需求分析概要設(shè)計詳細設(shè)計實現(xiàn)測試使用退役維護定義階段開發(fā)階段維護階段全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識68軟件工程步驟軟件工程步驟用到的方法用到的方法用到的工具用到的工具生成的文檔生成的文檔需求分析結(jié)構(gòu)化分析SA數(shù)據(jù)流圖DFD數(shù)據(jù)字典DD判定表判定樹軟件需求規(guī)格說明書SRS概要設(shè)計結(jié)構(gòu)化設(shè)計SD軟件結(jié)構(gòu)圖SC概要設(shè)計說明書數(shù)據(jù)庫設(shè)計說明書集成測試計劃詳細設(shè)計結(jié)構(gòu)化編程SP程序流程圖N-S圖問題分析圖PAD偽碼PDL-二、軟件生命周期二、軟件生命周期全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識69三、需求分析三、需求分析需求與需求分析需求分析的方法結(jié)構(gòu)化分析方法數(shù)據(jù)流圖與數(shù)據(jù)字典判定樹與判定表軟件需求規(guī)格說明書全國計算機等級考試National Computer Rank Examination全國計算機等級考試全國計算機等級考試二級公共基礎(chǔ)知識701 1、需求與需求分析、需求與需求分析需求：用戶對