《二級公共基礎(chǔ)知識 全國計(jì)算機(jī)等級考試》由會員分享，可在線閱讀，更多相關(guān)《二級公共基礎(chǔ)知識 全國計(jì)算機(jī)等級考試（99頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、全全國國計(jì)計(jì)算算機(jī)機(jī)等等級級考考試試National Computer Rank Examination二級 公共根底知識全國計(jì)算機(jī)等級考試1全國計(jì)算機(jī)等級考試National Computer Rank Examination二二級級公公共共根根底底知知識識考考試試內(nèi)內(nèi)容容 數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu) 和和 算算 法法 程程 序序 設(shè)設(shè) 計(jì)計(jì) 根根 底底 軟軟件件工工程程 數(shù)數(shù) 據(jù)據(jù) 庫庫 設(shè)設(shè) 計(jì)計(jì) 根根 底底全國計(jì)算機(jī)等級考試2全國計(jì)算機(jī)等級考試National Computer Rank Examination1 1、二級公共根底的考試方式為筆、二級公共根底的考試方式為筆 試，與各科語言的

2、筆試局部合試，與各科語言的筆試局部合 為一張?jiān)嚲怼９哺拙植空紴橐粡堅(jiān)嚲?。公共根底局部?全卷的全卷的3030分。分。2 2、公共根底知識有、公共根底知識有1010道選擇題和道選擇題和 5 5道填空題。道填空題。二二級級公公共共根根底底知知識識考考試試方方式式全國計(jì)算機(jī)等級考試3全國計(jì)算機(jī)等級考試National Computer Rank Examination理解根本概念理解根本概念多做練習(xí)多做練習(xí)適當(dāng)記憶一些名詞適當(dāng)記憶一些名詞與所學(xué)程序設(shè)計(jì)語言結(jié)合起來理解與所學(xué)程序設(shè)計(jì)語言結(jié)合起來理解二二級級公公共共根根底底知知識識學(xué)學(xué)習(xí)習(xí)方方法法全國計(jì)算機(jī)等級考試4第第 一一 章章 數(shù)數(shù)據(jù)據(jù)結(jié)結(jié)構(gòu)

3、構(gòu)和和算算法法全國計(jì)算機(jī)等級考試5全國計(jì)算機(jī)等級考試National Computer Rank Examination本章知識要點(diǎn)本章知識要點(diǎn)算法算法算法的定義算法的特征算法復(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)順序表、鏈表、堆棧隊(duì)列、循環(huán)隊(duì)列、樹算法的根本要素全國計(jì)算機(jī)等級考試6全國計(jì)算機(jī)等級考試National Computer Rank Examination算法是對特定問題求解步驟的一種描述。一、算法一、算法算法的特性：1有窮性：算法必須在有限的次數(shù)內(nèi)完成。2確定性：算法的每一步必須是明確的。3可行性：算法的每一步必須是可以實(shí)現(xiàn)的。4擁有足夠的情報(bào)

4、：算法必須有一定的輸入和輸出。全國計(jì)算機(jī)等級考試7全國計(jì)算機(jī)等級考試National Computer Rank Examination算法的根本要素：1對數(shù)據(jù)對象的運(yùn)算和操作：A.算術(shù)運(yùn)算 B.邏輯運(yùn)算 C.關(guān)系運(yùn)算 D.數(shù)據(jù)傳輸 2算法的控制結(jié)構(gòu)：A.順序結(jié)構(gòu) B.選擇結(jié)構(gòu) C.循環(huán)結(jié)構(gòu)全國計(jì)算機(jī)等級考試8全國計(jì)算機(jī)等級考試National Computer Rank Examination算法的復(fù)雜度：衡量算法優(yōu)劣的量。1時間復(fù)雜度：算法的時間消耗。A.算法中根本操作重復(fù)執(zhí)行次數(shù)和算法執(zhí)行時間 同步增長，稱作算法的時間復(fù)雜度。B.算法中根本操作重復(fù)執(zhí)行次數(shù)和問題規(guī)模有關(guān)，是問題規(guī)模的函數(shù)

5、。C.算法的時間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工 作量。2空間復(fù)雜度：執(zhí)行算法所需要的內(nèi)存空間。全國計(jì)算機(jī)等級考試9全國計(jì)算機(jī)等級考試National Computer Rank Examination1 1、問題處理方案的正確而完整的描述稱為、問題處理方案的正確而完整的描述稱為 。2 2、算法的根本特征是可行性、確定性、算法的根本特征是可行性、確定性、和擁有足夠的情報(bào)。和擁有足夠的情報(bào)。3 3、算法具有、算法具有4 4個特性，以下選項(xiàng)中不屬于算法特性的是個特性，以下選項(xiàng)中不屬于算法特性的是 A)A)有窮性有窮性B)B)簡潔性簡潔性C)C)可行性可行性D)D)確定性確定性4 4、算法的時間復(fù)雜

6、度是指、算法的時間復(fù)雜度是指 A)A)執(zhí)行算法程序所需要的時間執(zhí)行算法程序所需要的時間 B)B)算法程序的長度算法程序的長度 C)C)算法執(zhí)行過程中所需要的根本運(yùn)算次數(shù)算法執(zhí)行過程中所需要的根本運(yùn)算次數(shù) D)D)算法程序中的指令條數(shù)算法程序中的指令條數(shù)5 5、算法的空間復(fù)雜度是指、算法的空間復(fù)雜度是指 A)A)算法程序的長度算法程序的長度 B)B)算法程序中的指令條數(shù)算法程序中的指令條數(shù) C)C)算法程序所占的存儲空間算法程序所占的存儲空間 D)D)執(zhí)行過程中所需要的存儲空間執(zhí)行過程中所需要的存儲空間全國計(jì)算機(jī)等級考試10全國計(jì)算機(jī)等級考試National Computer Rank Exam

7、ination6、在計(jì)算機(jī)中，算法是指 A)加工方法B)解題方案的準(zhǔn)確而完整的描述 C)排序方法D)查詢方法7、以下表達(dá)中正確的選項(xiàng)是 A)算法的效率只與問題的規(guī)模有關(guān)，而與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)。B)算法的時間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量。C)數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)是一一對應(yīng)的。D)算法的時間復(fù)雜度與空間復(fù)雜度一定相關(guān)。全國計(jì)算機(jī)等級考試11全國計(jì)算機(jī)等級考試National Computer Rank Examination二、數(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ù)本身數(shù)據(jù)本身數(shù)據(jù)本身數(shù)據(jù)本身數(shù)據(jù)之間的數(shù)據(jù)之間的數(shù)

8、據(jù)之間的數(shù)據(jù)之間的前后件關(guān)系前后件關(guān)系前后件關(guān)系前后件關(guān)系數(shù)據(jù)結(jié)構(gòu)表示為：DS=D，S例：D=春，夏，秋，冬 S=(春,夏)，(夏,秋)，(秋,冬)，(冬,春)全國計(jì)算機(jī)等級考試12全國計(jì)算機(jī)等級考試National Computer Rank Examination數(shù)據(jù)的結(jié)構(gòu)分為：數(shù)據(jù)的結(jié)構(gòu)分為：1 1物理結(jié)構(gòu)：數(shù)據(jù)在計(jì)算機(jī)存儲介質(zhì)中真正存儲的結(jié)構(gòu)，物理結(jié)構(gòu)：數(shù)據(jù)在計(jì)算機(jī)存儲介質(zhì)中真正存儲的結(jié)構(gòu)，也被稱為也被稱為“存儲結(jié)構(gòu)存儲結(jié)構(gòu) 2 2邏輯結(jié)構(gòu)：人們所理解的數(shù)據(jù)之間的結(jié)構(gòu)，可以用圖示邏輯結(jié)構(gòu)：人們所理解的數(shù)據(jù)之間的結(jié)構(gòu)，可以用圖示 的方法繪畫出來的數(shù)據(jù)之間的結(jié)構(gòu)。的方法繪畫出來的數(shù)據(jù)之間的

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

10、且僅有一個前件 和一個后件。和一個后件。2 2非線性結(jié)構(gòu)：除了線性結(jié)構(gòu)都是非線性結(jié)構(gòu)。非線性結(jié)構(gòu)：除了線性結(jié)構(gòu)都是非線性結(jié)構(gòu)。全國計(jì)算機(jī)等級考試14全國計(jì)算機(jī)等級考試National Computer Rank Examination全國計(jì)算機(jī)等級考試二級公共根底知識要求掌握的數(shù)據(jù)結(jié)構(gòu)共有以下六種：線性表 堆棧 隊(duì)列 循環(huán)隊(duì)列 線性鏈表 樹和二叉樹線性結(jié)構(gòu)物理結(jié)構(gòu)和邏輯結(jié)構(gòu)相同相同相同相同物理結(jié)構(gòu)和邏輯結(jié)構(gòu)相同相同相同相同物理結(jié)構(gòu)和邏輯結(jié)構(gòu)相同相同相同相同物理結(jié)構(gòu)和邏輯結(jié)構(gòu)相同相同相同相同物理結(jié)構(gòu)和邏輯結(jié)構(gòu)不相同不相同不相同不相同物理結(jié)構(gòu)和邏輯結(jié)構(gòu)不相同不相同不相同不相同非線性結(jié)構(gòu)全國計(jì)算機(jī)等

11、級考試15全國計(jì)算機(jī)等級考試National Computer Rank Examination10102020303040405050606070708080三、順序表：順序表就是數(shù)組三、順序表：順序表就是數(shù)組1、順序表也叫做線性表，屬于線性結(jié)構(gòu)。線性表的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)相同。2、特點(diǎn)：1有且僅有一個頭結(jié)點(diǎn)根節(jié)點(diǎn)和尾結(jié)點(diǎn)。2任意其他結(jié)點(diǎn)至多有一個前件，一個后件。3頭結(jié)點(diǎn)沒有前件，尾結(jié)點(diǎn)沒有后件。全國計(jì)算機(jī)等級考試16全國計(jì)算機(jī)等級考試National Computer Rank Examination四、堆棧四、堆棧棧頂top棧底入棧入棧/壓入壓入出棧出棧/彈出彈出1、定義：只允許在棧頂位

12、置插 入數(shù)據(jù)和刪除數(shù)據(jù)的線性結(jié) 構(gòu)是堆棧，簡稱為“棧。2、堆棧屬于線性結(jié)構(gòu)。3、堆棧的邏輯結(jié)構(gòu)和物理結(jié)構(gòu) 相同。4、特點(diǎn)：先進(jìn)后出，后進(jìn)先出 所以堆棧也叫做先進(jìn)后出表 FILO5、堆棧具備存儲功能：函數(shù)的 遞歸調(diào)用和表達(dá)式求解都用 到了堆棧。全國計(jì)算機(jī)等級考試17全國計(jì)算機(jī)等級考試National Computer Rank Examination入棧順序：a、b、c、d、e、f?？誥bacbabadba.入a入b入c出c入d模擬堆棧的數(shù)據(jù)出入過程：全國計(jì)算機(jī)等級考試18全國計(jì)算機(jī)等級考試National Computer Rank Examination【典型題型】假設(shè)一個堆棧，入棧順序?yàn)閍

13、bcde，認(rèn)為在任何時 刻均允許出棧，以下選項(xiàng)中不可能的出棧順序?yàn)椋篈abcde可能 Bedcba可能 Ccdeba可能 Dcdeab不可能如果進(jìn)棧序列為如果進(jìn)棧序列為e1,e2,e3,e4e1,e2,e3,e4，那么可能的出棧序列是，那么可能的出棧序列是 A)e3,e1,e4,e2 A)e3,e1,e4,e2 B)e2,e4,e3,e1 B)e2,e4,e3,e1 C)e3,e4,e1,e2 C)e3,e4,e1,e2D)D)任意順序任意順序棧底至棧頂依次存放元素棧底至棧頂依次存放元素A A、B B、C C、D D，在第五個元素，在第五個元素E E入棧前，棧中元素入棧前，棧中元素可以出棧，那

14、么出棧序列可能是可以出棧，那么出棧序列可能是 A)ABCED A)ABCED B)DCBEA B)DCBEA C)DBCEA C)DBCEA D)CDABE D)CDABE全國計(jì)算機(jī)等級考試19全國計(jì)算機(jī)等級考試National Computer Rank Examination五、隊(duì)列五、隊(duì)列隊(duì)頭front隊(duì)尾rear入隊(duì)入隊(duì)出隊(duì)出隊(duì)1、隊(duì)列屬于線性結(jié)構(gòu)。2、隊(duì)列的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)相同。3、定義：入隊(duì)操作發(fā)生在隊(duì)尾，出隊(duì)操作發(fā)生在隊(duì)頭。4、特點(diǎn)：先進(jìn)先出，后進(jìn)后出，所以隊(duì)列也叫做先進(jìn)先 出表FIFO。全國計(jì)算機(jī)等級考試20全國計(jì)算機(jī)等級考試National Computer Rank Ex

15、amination1 1、棧和隊(duì)列的共同特點(diǎn)是、棧和隊(duì)列的共同特點(diǎn)是 A)A)都是先進(jìn)先出都是先進(jìn)先出 B)B)都是先進(jìn)后出都是先進(jìn)后出 C)C)只允許在端點(diǎn)處插入和刪除元素只允許在端點(diǎn)處插入和刪除元素 D)D)沒有共同點(diǎn)沒有共同點(diǎn)2 2、一些重要的程序語言、一些重要的程序語言(如如C C語言和語言和PascalPascal語言語言)允許過程的遞歸調(diào)用。而允許過程的遞歸調(diào)用。而 實(shí)現(xiàn)遞歸調(diào)用中的存儲分配通常用實(shí)現(xiàn)遞歸調(diào)用中的存儲分配通常用 A)A)棧棧 B)B)堆堆 C)C)數(shù)組數(shù)組 D)D)鏈表鏈表3 3、以下關(guān)于棧的表達(dá)中正確的選項(xiàng)是、以下關(guān)于棧的表達(dá)中正確的選項(xiàng)是 A)A)在棧中只能插入

16、數(shù)據(jù)在棧中只能插入數(shù)據(jù) B)B)在棧中只能刪除數(shù)據(jù)在棧中只能刪除數(shù)據(jù) C)C)棧是先進(jìn)先出的線性表?xiàng)Ｊ窍冗M(jìn)先出的線性表 D)D)棧是后進(jìn)先出的線性表?xiàng)Ｊ呛筮M(jìn)先出的線性表4 4、以下關(guān)于隊(duì)列的表達(dá)中正確的選項(xiàng)是、以下關(guān)于隊(duì)列的表達(dá)中正確的選項(xiàng)是 A)A)在隊(duì)列中只能插入數(shù)據(jù)在隊(duì)列中只能插入數(shù)據(jù) B)B)在隊(duì)列中只能刪除數(shù)據(jù)在隊(duì)列中只能刪除數(shù)據(jù) C)C)隊(duì)列是先進(jìn)先出的線性表隊(duì)列是先進(jìn)先出的線性表 D)D)隊(duì)列是后進(jìn)先出的線性表隊(duì)列是后進(jìn)先出的線性表全國計(jì)算機(jī)等級考試21全國計(jì)算機(jī)等級考試National Computer Rank Examination六、循環(huán)隊(duì)列六、循環(huán)隊(duì)列rearfront

17、全國計(jì)算機(jī)等級考試22全國計(jì)算機(jī)等級考試National Computer Rank Examination入隊(duì)順序：a、b、c、d、e、f模擬循環(huán)隊(duì)列的數(shù)據(jù)出入過程：模擬循環(huán)隊(duì)列的數(shù)據(jù)出入過程：循環(huán)隊(duì)列空front=rearrearfrontafrontrear數(shù)據(jù)a入隊(duì)afrontrearb數(shù)據(jù)b入隊(duì)frontrearb數(shù)據(jù)a出隊(duì)全國計(jì)算機(jī)等級考試23全國計(jì)算機(jī)等級考試National Computer Rank Examination七、線性鏈表七、線性鏈表1、鏈表屬于線性結(jié)構(gòu)。2、鏈表的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)不相同。3、線性鏈表由結(jié)點(diǎn)組成：每個結(jié)點(diǎn)有兩個區(qū)域：數(shù)據(jù)域，指針域。A.數(shù)據(jù)域，用

18、來存儲數(shù)據(jù)。B.指針域，用來指向下一個結(jié)點(diǎn)的位置。3、繪畫一個由5個節(jié)點(diǎn)組成的線性鏈表，數(shù)據(jù)為1、2、3、4、5。鏈表的結(jié)點(diǎn)鏈表的結(jié)點(diǎn)數(shù)據(jù)域數(shù)據(jù)域指針域指針域1 12 23 34 45 5單鏈表單鏈表全國計(jì)算機(jī)等級考試24全國計(jì)算機(jī)等級考試National Computer Rank Examination鏈表的種類：單鏈表、循環(huán)鏈表、雙向鏈表。1234512345循環(huán)鏈表雙向鏈表 12345 全國計(jì)算機(jī)等級考試25全國計(jì)算機(jī)等級考試National Computer Rank Examination1 1、鏈表不具有的特點(diǎn)是、鏈表不具有的特點(diǎn)是 A)A)不必事先估計(jì)存儲空間不必事先估計(jì)存儲空

19、間 B)B)可隨機(jī)訪問任一元素可隨機(jī)訪問任一元素 C)C)插入刪除不需要移動元素插入刪除不需要移動元素 D)D)所需空間與線性表長度成正比所需空間與線性表長度成正比2 2、數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)，線性鏈表屬于、數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)，線性鏈表屬于 。3 3、數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的、數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的 A)A)存儲結(jié)構(gòu)存儲結(jié)構(gòu)B)B)物理結(jié)構(gòu)物理結(jié)構(gòu) C)C)邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)D)D)物理和存儲結(jié)構(gòu)物理和存儲結(jié)構(gòu) 4 4、數(shù)據(jù)的邏輯結(jié)構(gòu)有線性結(jié)構(gòu)和、數(shù)據(jù)的邏輯結(jié)構(gòu)有線性結(jié)構(gòu)和 兩大類。兩大類。全國計(jì)算機(jī)等級考試26全國計(jì)算機(jī)等級考試Nat

20、ional Computer Rank Examination八、樹與二叉樹八、樹與二叉樹1、樹屬于非線性結(jié)構(gòu)。2、樹的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)不相同。3、樹有且僅有一個根節(jié)點(diǎn)。根節(jié)點(diǎn)xeoqkbg全國計(jì)算機(jī)等級考試27全國計(jì)算機(jī)等級考試National Computer Rank Examination二叉樹：每個結(jié)點(diǎn)最多分兩叉的有序樹。二叉樹：每個結(jié)點(diǎn)最多分兩叉的有序樹。二叉樹二叉樹的術(shù)語有序樹與無序樹二叉樹的五種根本結(jié)構(gòu)滿二叉樹 和 完全二叉樹二叉樹的計(jì)算二叉樹的遍歷全國計(jì)算機(jī)等級考試28全國計(jì)算機(jī)等級考試National Computer Rank Examination1 1、二叉樹的術(shù)語

21、：、二叉樹的術(shù)語：根節(jié)點(diǎn)xeoqbg葉子節(jié)點(diǎn)A.結(jié)點(diǎn)、根節(jié)點(diǎn)、葉子節(jié)點(diǎn)：1構(gòu)成樹的根本結(jié)構(gòu)是結(jié)點(diǎn)。2沒有父結(jié)點(diǎn)的結(jié)點(diǎn)是根節(jié)點(diǎn)。3沒有子結(jié)點(diǎn)的結(jié)點(diǎn)是葉子節(jié)點(diǎn)度為0的結(jié)點(diǎn)。B.結(jié)點(diǎn)的度：結(jié)點(diǎn)子結(jié)點(diǎn)的個數(shù)。C.樹的度：樹中度數(shù)最大的結(jié)點(diǎn)的度就是樹的度。D.樹的高度/層數(shù)：樹有多少層。E.父結(jié)點(diǎn)、子結(jié)點(diǎn)、雙親結(jié)點(diǎn)、孩子結(jié)點(diǎn)、左孩子、右孩子、兄弟結(jié)點(diǎn)、堂兄結(jié)點(diǎn)。全國計(jì)算機(jī)等級考試29全國計(jì)算機(jī)等級考試National Computer Rank Examination2 2、有序樹與無序樹：、有序樹與無序樹：eABeBA二叉樹和度為二的樹的區(qū)別：A.二叉樹是有序樹，度為二的樹是普通樹，屬于無序樹。B.二

22、叉樹允許為空，度為二的數(shù)至少有三個結(jié)點(diǎn)。【普通樹不允許為空，至少有一個結(jié)點(diǎn)】全國計(jì)算機(jī)等級考試30全國計(jì)算機(jī)等級考試National Computer Rank Examination3 3、二叉樹的五種根本結(jié)構(gòu)：、二叉樹的五種根本結(jié)構(gòu)：aaabcbab空二叉樹只有一個結(jié)點(diǎn)的二叉樹有兩個結(jié)點(diǎn)的二叉樹有三個結(jié)點(diǎn)的二叉樹全國計(jì)算機(jī)等級考試31全國計(jì)算機(jī)等級考試National Computer Rank Examination4 4、滿二叉樹和完全二叉樹：、滿二叉樹和完全二叉樹：A.滿二叉樹：二叉樹的每一層均具備該層最大結(jié)點(diǎn)個數(shù)。即：不具備度為1的結(jié)點(diǎn)B.完全二叉樹：滿二叉樹是一個特殊的完全二叉樹

23、。將所有結(jié)點(diǎn) 自上向下、自左向右編號，結(jié)點(diǎn)編號連續(xù)而不缺失。xeoqkbgxeoqkb滿二叉樹完全二叉樹123456全國計(jì)算機(jī)等級考試32全國計(jì)算機(jī)等級考試National Computer Rank Examination5 5、二叉樹的計(jì)算：、二叉樹的計(jì)算：A.二叉樹第n層的最大結(jié)點(diǎn)個數(shù)：2n-1。B.n層滿二叉樹的結(jié)點(diǎn)個數(shù)：2n-1。C.n層完全二叉樹的最小結(jié)點(diǎn)個數(shù)：2n-1。n層完全二叉樹的最大結(jié)點(diǎn)個數(shù)：2n-1。D.度為0的結(jié)點(diǎn)個數(shù)表示為n0，同理，n1表示度為1的結(jié)點(diǎn)個數(shù)，n2表示度為2的結(jié)點(diǎn)個數(shù)。那么，對于任意二叉樹都有：n0=n2+1。E.結(jié)點(diǎn)編號：任意結(jié)點(diǎn)編號n，其左孩子為2

24、n，其右孩子為2n+1。xeoqkbg1 12 23 34 45 56 67 7全國計(jì)算機(jī)等級考試33全國計(jì)算機(jī)等級考試National Computer Rank Examination填空題：填空題：設(shè)一棵完全二叉樹共有設(shè)一棵完全二叉樹共有700700個結(jié)點(diǎn)，那么在該二叉樹中有個結(jié)點(diǎn)，那么在該二叉樹中有 個葉子結(jié)個葉子結(jié)點(diǎn)點(diǎn)二叉樹的結(jié)點(diǎn)共有三種：度為二叉樹的結(jié)點(diǎn)共有三種：度為0 0的葉子結(jié)點(diǎn)、度為的葉子結(jié)點(diǎn)、度為1 1的結(jié)點(diǎn)和度為的結(jié)點(diǎn)和度為2 2的結(jié)點(diǎn)。的結(jié)點(diǎn)。設(shè)度為設(shè)度為0 0的葉子結(jié)點(diǎn)個數(shù)為的葉子結(jié)點(diǎn)個數(shù)為n0n0，度為，度為1 1的結(jié)點(diǎn)個數(shù)為的結(jié)點(diǎn)個數(shù)為n1n1，度為，度為2 2的

25、結(jié)點(diǎn)個數(shù)為的結(jié)點(diǎn)個數(shù)為n2n2，那么：，那么：n0+n1+n2=700 n0+n1+n2=7001 1根據(jù)二叉樹性質(zhì)：葉子結(jié)點(diǎn)個數(shù)比度為根據(jù)二叉樹性質(zhì)：葉子結(jié)點(diǎn)個數(shù)比度為2 2的結(jié)點(diǎn)個數(shù)多的結(jié)點(diǎn)個數(shù)多1 1，即：，即：n0=n2+1 n0=n2+1 2 2將將2 2式帶入式帶入1 1式，所以：式，所以：n0+n1+n0-1=700 n0+n1+n0-1=700 2n0=701-n1 2n0=701-n1 完全二叉樹總結(jié)點(diǎn)個數(shù)為偶數(shù)，那么度為完全二叉樹總結(jié)點(diǎn)個數(shù)為偶數(shù)，那么度為1 1的結(jié)點(diǎn)個數(shù)為的結(jié)點(diǎn)個數(shù)為1 1；完全二叉樹的總結(jié)點(diǎn)；完全二叉樹的總結(jié)點(diǎn)個數(shù)為奇數(shù)，那么度為個數(shù)為奇數(shù)，那么度為1

26、1的結(jié)點(diǎn)個數(shù)為的結(jié)點(diǎn)個數(shù)為0 0。所以：所以：2n0=701-12n0=701-1，即，即 n0=350 n0=350。全國計(jì)算機(jī)等級考試34全國計(jì)算機(jī)等級考試National Computer Rank Examination6 6、二叉樹的遍歷：、二叉樹的遍歷：A.前/先根序遍歷，GLR?！靖?jié)點(diǎn)為序列開頭】B.中根序遍歷，LGR?！緵]有左子樹，根節(jié)點(diǎn)為開頭；沒有右子樹，根節(jié)點(diǎn)為結(jié)尾】【左右子樹均有，根節(jié)點(diǎn)的位置位于左子樹結(jié)點(diǎn)個數(shù)之和+1】C.后根序遍歷，LRG?！靖?jié)點(diǎn)為序列結(jié)尾】xeoqbg先序序列：xeqbog中序序列：qebxog后序序列：qbegox全國計(jì)算機(jī)等級考試35全國計(jì)算

27、機(jī)等級考試National Computer Rank Examination1 1、二叉樹后序遍歷序列是、二叉樹后序遍歷序列是dabecdabec，中序遍歷序列是，中序遍歷序列是debacdebac，它的前序，它的前序 遍歷序列是遍歷序列是 A)acbed B)decab C)deabc D)cedba A)acbed B)decab C)deabc D)cedba 2 2、一棵二叉樹前序遍歷和中序遍歷分別為、一棵二叉樹前序遍歷和中序遍歷分別為ABDEGCFHABDEGCFH和和DBGEACHFDBGEACHF，那么，那么 該二叉樹的后序遍歷為該二叉樹的后序遍歷為 A)GEDHFBCA A)

28、GEDHFBCA B)DGEBHFCA B)DGEBHFCA C)ABCDEFGH C)ABCDEFGH D)ACBFEDHG D)ACBFEDHG3 3、樹是結(jié)點(diǎn)的集合，它的根結(jié)點(diǎn)數(shù)目是、樹是結(jié)點(diǎn)的集合，它的根結(jié)點(diǎn)數(shù)目是 A)A)有且只有有且只有1 1 B)1 B)1或多于或多于1 1 C)0 C)0或或1 1 D)D)至少至少2 24 4、在深度為、在深度為5 5的滿二叉樹中，葉子結(jié)點(diǎn)的個數(shù)為的滿二叉樹中，葉子結(jié)點(diǎn)的個數(shù)為 A)32 A)32B)31 C)16 B)31 C)16 D)15 D)15 5 5、在樹結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有、在樹結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有 。全國計(jì)算機(jī)等級考試36全國計(jì)

29、算機(jī)等級考試National Computer Rank Examination6 6、以下表達(dá)中正確的選項(xiàng)是、以下表達(dá)中正確的選項(xiàng)是 A)A)線性表是線性結(jié)構(gòu)線性表是線性結(jié)構(gòu) B)B)棧與隊(duì)列是非線性結(jié)構(gòu)棧與隊(duì)列是非線性結(jié)構(gòu) C)C)線性鏈表是非線性結(jié)構(gòu)線性鏈表是非線性結(jié)構(gòu) D)D)二叉樹是線性結(jié)構(gòu)二叉樹是線性結(jié)構(gòu)7 7、具有、具有3 3個結(jié)點(diǎn)的二叉樹有個結(jié)點(diǎn)的二叉樹有 A)2 A)2種形態(tài)種形態(tài) B)4 B)4種形態(tài)種形態(tài) C)7 C)7種形態(tài)種形態(tài) D)5 D)5種形態(tài)種形態(tài) 8 8、設(shè)一棵二叉樹中有、設(shè)一棵二叉樹中有3 3個葉子結(jié)點(diǎn)，有個葉子結(jié)點(diǎn)，有8 8個度為個度為1 1的結(jié)點(diǎn)，那么

30、該二叉樹中的結(jié)點(diǎn)，那么該二叉樹中總總 的結(jié)點(diǎn)數(shù)為的結(jié)點(diǎn)數(shù)為 A)12 A)12 B)13 C)14 B)13 C)14 D)15 D)15 9 9、設(shè)樹、設(shè)樹T T的深度為的深度為4,4,其中度為其中度為1 1、2 2、3 3、4 4的結(jié)點(diǎn)個數(shù)分別為的結(jié)點(diǎn)個數(shù)分別為4 4、2 2、1 1、1 1。那么那么T T中的葉子結(jié)點(diǎn)數(shù)為中的葉子結(jié)點(diǎn)數(shù)為 A A8 B8 B7 C7 C6 D6 D5 5全國計(jì)算機(jī)等級考試37全國計(jì)算機(jī)等級考試National Computer Rank Examination1010、設(shè)有左側(cè)二叉樹，對此二叉樹前序遍歷的結(jié)果為、設(shè)有左側(cè)二叉樹，對此二叉樹前序遍歷的結(jié)果為

31、A)ZBTTCPXA A)ZBTTCPXA B)ATBZXCTP B)ATBZXCTP C)ZBTACTXP D)ATBZXCPT C)ZBTACTXP D)ATBZXCPT 1111、設(shè)有右側(cè)二叉樹，對此二叉樹的中序遍歷的結(jié)果為、設(shè)有右側(cè)二叉樹，對此二叉樹的中序遍歷的結(jié)果為 A)ABCDEF B)DBEAFC C)ABDECF D)DEBFCA A)ABCDEF B)DBEAFC C)ABDECF D)DEBFCA全國計(jì)算機(jī)等級考試38第二章第二章 程序設(shè)計(jì)根底程序設(shè)計(jì)根底全國計(jì)算機(jī)等級考試39全國計(jì)算機(jī)等級考試National Computer Rank Examination本章知識要點(diǎn)

32、本章知識要點(diǎn)面向過程的程序設(shè)計(jì)面向過程的程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)模塊化程序設(shè)計(jì)面向?qū)ο蟮某绦蛟O(shè)計(jì)面向?qū)ο蟮某绦蛟O(shè)計(jì)對象的定義對象的屬性和方法類和實(shí)例的派生與繼承消息與多態(tài)性全國計(jì)算機(jī)等級考試40全國計(jì)算機(jī)等級考試National Computer Rank Examination一、程序設(shè)計(jì)方法一、程序設(shè)計(jì)方法1、面向過程的程序設(shè)計(jì)：C語言、BASIC語言等。1結(jié)構(gòu)化程序設(shè)計(jì)：順序、選擇、循環(huán)。三大結(jié)構(gòu)順序、選擇、循環(huán)可以解決所有的問題，和 問題的規(guī)模沒有關(guān)系。2模塊化程序設(shè)計(jì)：利用將程序分解的方法，將復(fù)雜的問題 簡單化，將單一的問題分成多個模塊獨(dú)立解決。C語言：模塊就是函數(shù)。VB語言：模塊就是

33、模塊、子例程、子程序。VFP數(shù)據(jù)庫：模塊就是子程序。Access數(shù)據(jù)庫：模塊就是宏、事件代碼。2、面向?qū)ο蟮某绦蛟O(shè)計(jì)：VB、VFP、Java、Delphi等。全國計(jì)算機(jī)等級考試41全國計(jì)算機(jī)等級考試National Computer Rank Examination二、程序設(shè)計(jì)風(fēng)格二、程序設(shè)計(jì)風(fēng)格1.1.源程序文檔化源程序文檔化 選擇標(biāo)示符的名字選擇標(biāo)示符的名字 注釋序言性和功能性注釋注釋序言性和功能性注釋 程序的視覺組織程序的視覺組織2.2.數(shù)據(jù)說明的方法數(shù)據(jù)說明的方法 顯式地說明一切變量顯式地說明一切變量 數(shù)據(jù)說明的次序應(yīng)該標(biāo)準(zhǔn)化數(shù)據(jù)說明的次序應(yīng)該標(biāo)準(zhǔn)化 說明語句中變量安排有序化說明語句中

34、變量安排有序化 對復(fù)雜數(shù)據(jù)結(jié)構(gòu)應(yīng)注釋說明對復(fù)雜數(shù)據(jù)結(jié)構(gòu)應(yīng)注釋說明3.3.語句的結(jié)構(gòu)語句的結(jié)構(gòu) 每條語句簡單明了每條語句簡單明了 盡量不用或少用盡量不用或少用GOTOGOTO語句語句 盡量只采用盡量只采用3 3種根本控制結(jié)構(gòu)編程種根本控制結(jié)構(gòu)編程4.4.輸入和輸出輸入和輸出 對輸入數(shù)據(jù)進(jìn)行校驗(yàn)和合理性檢查對輸入數(shù)據(jù)進(jìn)行校驗(yàn)和合理性檢查 輸入輸出格式保持一致輸入輸出格式保持一致 設(shè)計(jì)良好的輸出報(bào)表設(shè)計(jì)良好的輸出報(bào)表全國計(jì)算機(jī)等級考試42全國計(jì)算機(jī)等級考試National Computer Rank Examination三、結(jié)構(gòu)化程序設(shè)計(jì)三、結(jié)構(gòu)化程序設(shè)計(jì) 20世紀(jì)70年代提出了結(jié)構(gòu)化程序設(shè)計(jì)St

35、ructured Programming結(jié)構(gòu)化程序設(shè)計(jì)的原那么：1自頂向下。2逐步求精。3模塊化。4限制使用goto語句。結(jié)構(gòu)化程序設(shè)計(jì)的根本結(jié)構(gòu)：1順序結(jié)構(gòu)。2選擇結(jié)構(gòu)。3重復(fù)結(jié)構(gòu)。結(jié)構(gòu)化程序設(shè)計(jì)主要強(qiáng)調(diào)程序的易讀性。全國計(jì)算機(jī)等級考試43全國計(jì)算機(jī)等級考試National Computer Rank Examination利用圖示表示順序結(jié)構(gòu)ABAB程序流程圖N-S圖全國計(jì)算機(jī)等級考試44全國計(jì)算機(jī)等級考試National Computer Rank Examination利用圖示表示選擇結(jié)構(gòu)條件滿足不滿足AB程序流程圖N-S圖AB條件滿足不滿足全國計(jì)算機(jī)等級考試45全國計(jì)算機(jī)等級考試Na

36、tional Computer Rank Examination利用圖示表示重復(fù)結(jié)構(gòu)(1)條件滿足不滿足S條件滿足不滿足S程序流程圖當(dāng)型循環(huán)程序流程圖直到型循環(huán)全國計(jì)算機(jī)等級考試46全國計(jì)算機(jī)等級考試National Computer Rank Examination利用圖示表示重復(fù)結(jié)構(gòu)(2)WHILE 條件SSUNTIL 條件N-S圖當(dāng)型循環(huán)N-S圖直到型循環(huán)全國計(jì)算機(jī)等級考試47全國計(jì)算機(jī)等級考試National Computer Rank Examination三、面向?qū)ο蟮某绦蛟O(shè)計(jì)三、面向?qū)ο蟮某绦蛟O(shè)計(jì) 面向?qū)ο?Object Oriented)的程序設(shè)計(jì)方法已經(jīng)開展成為主流的軟件開發(fā)

37、方法，起源于對面向?qū)ο笳Z言的研究。20世紀(jì)60年代后期首次被提出，80年代開始走向?qū)嵱?。面向?qū)ο蟮某绦蛟O(shè)計(jì)的術(shù)語：對象、屬性、方法、封裝性、事件、類、父類、子類、實(shí)例、派生、繼承、消息、多態(tài)性。全國計(jì)算機(jī)等級考試48全國計(jì)算機(jī)等級考試National Computer Rank Examination面向?qū)ο蠓椒ǖ闹饕獌?yōu)點(diǎn)：1與人類習(xí)慣的思維方法一致。2穩(wěn)定性好。3可重用性好。4易于開發(fā)大型軟件產(chǎn)品。5可維護(hù)性好。全國計(jì)算機(jī)等級考試49全國計(jì)算機(jī)等級考試National Computer Rank Examination1 1、對象的定義、對象的定義對象：現(xiàn)實(shí)生活中存在的可以相互區(qū)分的物體。是

38、屬性和方法的封裝。對象的根本特點(diǎn)：1標(biāo)識唯一性。2分類型。3多態(tài)性。4封裝性。5模塊獨(dú)立型好。全國計(jì)算機(jī)等級考試50全國計(jì)算機(jī)等級考試National Computer Rank Examination2 2、對象的屬性和方法、對象的屬性和方法屬性Property：用來描述對象的狀態(tài)，是對象的靜態(tài)特性。包括屬性名和屬性值兩方面。例如：“顯示器作為對象，具備“顏色屬性，取值為“銀白色。方法Method：用來描述對象的行為，是對象的動態(tài)特性。方法具備方法名。方法必須利用事件來激活。例如:“顯示器作為對象，具備“關(guān)閉的方法，必須用“斷電事件來激活。屬性名屬性值方法名事件封裝性：(Encapsulat

39、ion)對象依靠對象名將自身的屬性和方法封裝。全國計(jì)算機(jī)等級考試51全國計(jì)算機(jī)等級考試National Computer Rank Examination3 3、類和實(shí)例的派生與繼承、類和實(shí)例的派生與繼承1類Class：具有相同屬性和方法的 對象的集合，是對對象屬性和方法的抽 象。2實(shí)例Instances：類的子類派生出 的對象就是該類的一個實(shí)例。類展現(xiàn)對象的共性；實(shí)例展現(xiàn)對象的個性。3派生過程中將發(fā)生屬性和方法的繼承 Inheritance 父類將自身的所有屬性和方法傳遞 給子類，子類繼承父類傳遞的所有屬性 和方法，并產(chǎn)生自身特有的屬性和方 法，再將這些屬性和方法的總和傳遞給 下一級子類。人

40、人好人好人壞人壞人中國人中國人 外國人外國人張三張三全國計(jì)算機(jī)等級考試52全國計(jì)算機(jī)等級考試National Computer Rank Examination4 4、消息與多態(tài)性、消息與多態(tài)性1消息Message：進(jìn)行對象之間的信息傳遞。2多態(tài)性Polymorphism：同樣的消息傳遞給不同的對象，導(dǎo)致 完全不同的行動。消息的組成：A.接收消息的對象名稱。B.消息標(biāo)識符，也叫做“消息名。C.零個或多個參數(shù)。全國計(jì)算機(jī)等級考試53全國計(jì)算機(jī)等級考試National Computer Rank Examination1 1、結(jié)構(gòu)化程序設(shè)計(jì)的三種結(jié)構(gòu)是、結(jié)構(gòu)化程序設(shè)計(jì)的三種結(jié)構(gòu)是 A)A)順序結(jié)構(gòu)

41、、選擇結(jié)構(gòu)、轉(zhuǎn)移結(jié)構(gòu)順序結(jié)構(gòu)、選擇結(jié)構(gòu)、轉(zhuǎn)移結(jié)構(gòu) B)B)分支結(jié)構(gòu)、等價結(jié)構(gòu)、循環(huán)結(jié)構(gòu)分支結(jié)構(gòu)、等價結(jié)構(gòu)、循環(huán)結(jié)構(gòu) C)C)多分支結(jié)構(gòu)、賦值結(jié)構(gòu)、等價結(jié)構(gòu)多分支結(jié)構(gòu)、賦值結(jié)構(gòu)、等價結(jié)構(gòu) D)D)順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)2 2、在設(shè)計(jì)程序時，應(yīng)采納的原那么之一是、在設(shè)計(jì)程序時，應(yīng)采納的原那么之一是 A)A)不限制不限制gotogoto語句的使用語句的使用 B)B)減少或取消注解行減少或取消注解行 C)C)程序越短越好程序越短越好 D)D)程序結(jié)構(gòu)應(yīng)有助于讀者理解程序結(jié)構(gòu)應(yīng)有助于讀者理解3 3、程序設(shè)計(jì)語言的根本成分是數(shù)據(jù)成分、運(yùn)算成分、控制成分和、程序設(shè)計(jì)語言的根

42、本成分是數(shù)據(jù)成分、運(yùn)算成分、控制成分和 A)A)對象成分對象成分 B)B)變量成分變量成分 C)C)語句成分語句成分 D)D)傳輸成分傳輸成分4 4、結(jié)構(gòu)化程序設(shè)計(jì)主要強(qiáng)調(diào)的是、結(jié)構(gòu)化程序設(shè)計(jì)主要強(qiáng)調(diào)的是 A)A)程序的規(guī)模程序的規(guī)模 B)B)程序的效率程序的效率 C)C)程序設(shè)計(jì)語言的先進(jìn)性程序設(shè)計(jì)語言的先進(jìn)性 D)D)程序易讀性程序易讀性全國計(jì)算機(jī)等級考試54全國計(jì)算機(jī)等級考試National Computer Rank Examination5 5、以下不屬于對象的根本特點(diǎn)的是、以下不屬于對象的根本特點(diǎn)的是 A)A)分類性分類性 B)B)多態(tài)性多態(tài)性 C)C)繼承性繼承性D)D)封裝性封

43、裝性 6 6、對建立良好的程序設(shè)計(jì)風(fēng)格，下面描述正確的選項(xiàng)是、對建立良好的程序設(shè)計(jì)風(fēng)格，下面描述正確的選項(xiàng)是 A)A)程序應(yīng)簡單、清晰、可讀性好程序應(yīng)簡單、清晰、可讀性好 B)B)符號名的命名只要符合語法符號名的命名只要符合語法 C)C)充分考慮程序的執(zhí)行效率充分考慮程序的執(zhí)行效率 D)D)程序的注釋可有可無程序的注釋可有可無7 7、在結(jié)構(gòu)化程序設(shè)計(jì)思想提出之前，在程序設(shè)計(jì)中曾強(qiáng)調(diào)程序的效率，現(xiàn)、在結(jié)構(gòu)化程序設(shè)計(jì)思想提出之前，在程序設(shè)計(jì)中曾強(qiáng)調(diào)程序的效率，現(xiàn)在，與程序的效率相比，人們更重視程序的在，與程序的效率相比，人們更重視程序的 A)A)平安性平安性 B)B)一致性一致性 C)C)可理解性

44、可理解性 D)D)合理性合理性8 8、程序的、程序的3 3種根本控制結(jié)構(gòu)是種根本控制結(jié)構(gòu)是 A)A)過程、子過程和分程序過程、子過程和分程序B)B)順序、選擇和重復(fù)順序、選擇和重復(fù) C)C)遞歸、堆棧和隊(duì)列遞歸、堆棧和隊(duì)列 D)D)調(diào)用、返回和轉(zhuǎn)移調(diào)用、返回和轉(zhuǎn)移9 9、以下表達(dá)中，不屬于結(jié)構(gòu)化程序設(shè)計(jì)方法的主要原那么的是、以下表達(dá)中，不屬于結(jié)構(gòu)化程序設(shè)計(jì)方法的主要原那么的是 A)A)自頂向下自頂向下 B)B)由底向上由底向上 C)C)模塊化模塊化 D)D)限制使用限制使用gotogoto語句語句全國計(jì)算機(jī)等級考試55全國計(jì)算機(jī)等級考試National Computer Rank Examin

45、ation1010、對象實(shí)現(xiàn)了數(shù)據(jù)和操作的結(jié)合，是指對數(shù)據(jù)和數(shù)據(jù)的操作進(jìn)行、對象實(shí)現(xiàn)了數(shù)據(jù)和操作的結(jié)合，是指對數(shù)據(jù)和數(shù)據(jù)的操作進(jìn)行 A)A)結(jié)合結(jié)合 B)B)隱藏隱藏 C)C)封裝封裝 D)D)抽象抽象1111、在面向?qū)ο蠓椒ㄖ校粋€對象請求另一個對象為其效勞的方式是通過發(fā)、在面向?qū)ο蠓椒ㄖ?，一個對象請求另一個對象為其效勞的方式是通過發(fā) 送送 A A調(diào)用語句調(diào)用語句 B B命令命令 C C口令口令 D D消息消息1212、以下對象概念描述錯誤的選項(xiàng)是、以下對象概念描述錯誤的選項(xiàng)是 A A任何對象都必須有繼承性任何對象都必須有繼承性 B B對象是屬性和方法的封裝體對象是屬性和方法的封裝體 C C

46、對象間的通訊靠消息傳遞對象間的通訊靠消息傳遞 D D操作是對象的動態(tài)屬性操作是對象的動態(tài)屬性1313、在面向?qū)ο蟮某绦蛟O(shè)計(jì)中，類描述的是具有相似性質(zhì)的一組、在面向?qū)ο蟮某绦蛟O(shè)計(jì)中，類描述的是具有相似性質(zhì)的一組 。1414、在面向?qū)ο蠓椒ㄖ校愔g共享屬性和操作的機(jī)制稱為、在面向?qū)ο蠓椒ㄖ?，類之間共享屬性和操作的機(jī)制稱為 。1515、面向?qū)ο蟮哪Ｐ椭?，最根本的概念是對象和、面向?qū)ο蟮哪Ｐ椭?，最根本的概念是對象?。1616、類是一個支持集成的抽象數(shù)據(jù)類型，而對象是類的、類是一個支持集成的抽象數(shù)據(jù)類型，而對象是類的 。1717、是一種信息隱蔽技術(shù)，目的在于將對象的使用者和對象的設(shè)是一種信息隱蔽技術(shù)

47、，目的在于將對象的使用者和對象的設(shè) 計(jì)者分開。計(jì)者分開。1818、源程序文檔化要求程序應(yīng)加注釋。注釋一般分為序言性注釋和、源程序文檔化要求程序應(yīng)加注釋。注釋一般分為序言性注釋和 。全國計(jì)算機(jī)等級考試56第三章第三章 軟件工程基礎(chǔ)軟件工程基礎(chǔ)軟件（Software）=程序+文檔 全國計(jì)算機(jī)等級考試57全國計(jì)算機(jī)等級考試National Computer Rank Examination本章知識要點(diǎn)本章知識要點(diǎn)軟件危機(jī)軟件危機(jī)軟件生命周期軟件生命周期需求分析概要設(shè)計(jì)詳細(xì)設(shè)計(jì)測試調(diào)試軟件工程軟件工程全國計(jì)算機(jī)等級考試58全國計(jì)算機(jī)等級考試National Computer Rank Examinat

48、ion一、軟件危機(jī)一、軟件危機(jī)軟件危機(jī)主要表現(xiàn)在：1軟件需求的增長得不到滿足。2軟件開發(fā)本錢和進(jìn)度無法控制。3軟件質(zhì)量難以保證。4軟件不可維護(hù)或可維護(hù)度非常低。5軟件的本錢不斷提高。6軟件開發(fā)生產(chǎn)率的提高趕不上硬件的開展和應(yīng)用需求的增長。總之，可以將軟件危機(jī)歸結(jié)為本錢、質(zhì)量、生產(chǎn)率問題全國計(jì)算機(jī)等級考試59全國計(jì)算機(jī)等級考試National Computer Rank Examination二、軟件工程二、軟件工程 軟件工程是為了擺脫軟件危機(jī)而誕生的，主要思想是在軟件開發(fā)過程中應(yīng)用工程化原那么。軟件工程的三要素：方法、工具、工程。軟件工程的主要內(nèi)容：軟件開發(fā)技術(shù)、軟件工程管理。軟件工程的原那么

49、：1抽象。2信息隱蔽。3模塊化。4局部化。5確定性。6一致性。7完備性。8可驗(yàn)證性。全國計(jì)算機(jī)等級考試60全國計(jì)算機(jī)等級考試National Computer Rank Examination二、軟件生命周期二、軟件生命周期軟件生命周期Software Life Cycle，SLC：將軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過程稱為“軟件生命周期?？尚行匝芯啃枨蠓治龈乓O(shè)計(jì)詳細(xì)設(shè)計(jì)實(shí)現(xiàn)測試使用退役維護(hù)定義階段開發(fā)階段維護(hù)階段全國計(jì)算機(jī)等級考試61全國計(jì)算機(jī)等級考試National Computer Rank Examination軟件工程步驟軟件工程步驟用到的方法用到的方法用到的工具用到

50、的工具生成的文檔生成的文檔需求分析結(jié)構(gòu)化分析SA數(shù)據(jù)流圖DFD數(shù)據(jù)字典DD判定表判定樹軟件需求規(guī)格說明書SRS概要設(shè)計(jì)結(jié)構(gòu)化設(shè)計(jì)SD軟件結(jié)構(gòu)圖SC概要設(shè)計(jì)說明書數(shù)據(jù)庫設(shè)計(jì)說明書集成測試計(jì)劃詳細(xì)設(shè)計(jì)結(jié)構(gòu)化編程SP程序流程圖N-S圖問題分析圖PAD偽碼PDL-全國計(jì)算機(jī)等級考試62全國計(jì)算機(jī)等級考試National Computer Rank Examination三、需求分析三、需求分析需求與需求分析需求分析的方法結(jié)構(gòu)化分析方法數(shù)據(jù)流圖與數(shù)據(jù)字典判定樹與判定表軟件需求規(guī)格說明書全國計(jì)算機(jī)等級考試63全國計(jì)算機(jī)等級考試National Computer Rank Examination1 1、需求

51、與需求分析、需求與需求分析需求：用戶對目標(biāo)軟件系統(tǒng)在功能、行為、性能、設(shè)計(jì) 約束等方面的期望。需求分析：發(fā)現(xiàn)用戶需求的過程需求分析階段的工作：1需求獲取 2需求分析 3編寫需求規(guī)格說明書 4需求評審 全國計(jì)算機(jī)等級考試64全國計(jì)算機(jī)等級考試National Computer Rank Examination2 2、需求分析的方法、需求分析的方法A.面向數(shù)據(jù)流的結(jié)構(gòu)化分析方法 SA。B.面向數(shù)據(jù)結(jié)構(gòu)的Jackson方法 JSD。C.面向數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)化數(shù)據(jù)系統(tǒng)開發(fā)方法 DSSD。D.面向?qū)ο蟮姆治龇椒?OOA。全國計(jì)算機(jī)等級考試65全國計(jì)算機(jī)等級考試National Computer Rank

52、Examination3 3、結(jié)構(gòu)化分析方法：數(shù)據(jù)流圖、結(jié)構(gòu)化分析方法：數(shù)據(jù)流圖DFDDFD數(shù)據(jù)流圖DFD中的主要圖形元素：加工/轉(zhuǎn)換數(shù)據(jù)流存儲文件/數(shù)據(jù)源源/潭全國計(jì)算機(jī)等級考試66全國計(jì)算機(jī)等級考試National Computer Rank Examination結(jié)構(gòu)化分析方法：數(shù)據(jù)字典結(jié)構(gòu)化分析方法：數(shù)據(jù)字典DDDD數(shù)據(jù)字典數(shù)據(jù)字典DDDD是結(jié)構(gòu)化分析方法的核心。是結(jié)構(gòu)化分析方法的核心。數(shù)據(jù)字典的作用：對數(shù)據(jù)流圖DFD中出現(xiàn)的被命名圖形元素進(jìn) 行確切的解釋。全國計(jì)算機(jī)等級考試67全國計(jì)算機(jī)等級考試National Computer Rank Examination結(jié)構(gòu)化分析方法：判定樹

53、與判定表結(jié)構(gòu)化分析方法：判定樹與判定表判定樹 條件1 條件2 結(jié)果計(jì) 7月9月 訂票量20:15%算 12月 訂票量20:30%量 10月 11月 訂票量20%20%C(R)AC(R)【對關(guān)系的橫向分解】【對關(guān)系的橫向分解】2 2投影：投影：A,C(R)A,C(R)【對關(guān)系的縱向分解】【對關(guān)系的縱向分解】AC(R)ABC560924A,C(R)AC1519245094RABC125149284560924全國計(jì)算機(jī)等級考試95全國計(jì)算機(jī)等級考試National Computer Rank Examination3 3 3 3、連接：、連接：、連接：、連接：1 1連接：連接：R T.BAR.BC

54、DT.BE560125560349i=j全國計(jì)算機(jī)等級考試96全國計(jì)算機(jī)等級考試National Computer Rank ExaminationRABC125149560TDBE125349R TAR.BCDT.BE125125149349全國計(jì)算機(jī)等級考試97全國計(jì)算機(jī)等級考試National Computer Rank Examination七、數(shù)據(jù)庫設(shè)計(jì)與管理：七、數(shù)據(jù)庫設(shè)計(jì)與管理：七、數(shù)據(jù)庫設(shè)計(jì)與管理：七、數(shù)據(jù)庫設(shè)計(jì)與管理：1、數(shù)據(jù)庫設(shè)計(jì)的四個階段：需求分析運(yùn)行與維護(hù)概念設(shè)計(jì)邏輯設(shè)計(jì)物理設(shè)計(jì)編碼測試建立概念數(shù)據(jù)模型：E-R模型將E-R圖轉(zhuǎn)換為關(guān)系模式：實(shí)體和聯(lián)系均轉(zhuǎn)換為關(guān)系。對數(shù)據(jù)庫內(nèi)部物理結(jié)構(gòu)作出調(diào)整并選擇合理的存儲路徑全國計(jì)算機(jī)等級考試98全國計(jì)算機(jī)等級考試National Computer Rank Examination2、數(shù)據(jù)庫管理：實(shí)施人：數(shù)據(jù)庫管理員DBA 數(shù)據(jù)庫管理的特點(diǎn)：實(shí)現(xiàn)數(shù)據(jù)共享 管理內(nèi)容：1數(shù)據(jù)庫的建立 2數(shù)據(jù)庫的調(diào)整 3數(shù)據(jù)庫的重組 4數(shù)據(jù)平安控制與完整性控制 5數(shù)據(jù)庫的故障校復(fù) 6數(shù)據(jù)庫監(jiān)控全國計(jì)算機(jī)等級考試99