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

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

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

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

4、：算法必須有一定的輸入和輸出。全國(guó)計(jì)算機(jī)等級(jí)考試7全國(guó)計(jì)算機(jī)等級(jí)考試National Computer Rank Examination算法的根本要素：1對(duì)數(shù)據(jù)對(duì)象的運(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)全國(guó)計(jì)算機(jī)等級(jí)考試8全國(guó)計(jì)算機(jī)等級(jí)考試National Computer Rank Examination算法的復(fù)雜度：衡量算法優(yōu)劣的量。1時(shí)間復(fù)雜度：算法的時(shí)間消耗。A.算法中根本操作重復(fù)執(zhí)行次數(shù)和算法執(zhí)行時(shí)間 同步增長(zhǎng)，稱作算法的時(shí)間復(fù)雜度。B.算法中根本操作重復(fù)執(zhí)行次數(shù)和問(wèn)題規(guī)模有關(guān)，是問(wèn)題規(guī)模的函數(shù)

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

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

7、ination6、在計(jì)算機(jī)中，算法是指 A)加工方法B)解題方案的準(zhǔn)確而完整的描述 C)排序方法D)查詢方法7、以下表達(dá)中正確的選項(xiàng)是 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)。全國(guó)計(jì)算機(jī)等級(jí)考試11全國(guó)計(jì)算機(jī)等級(jí)考試National Computer Rank Examination二、數(shù)據(jù)結(jié)構(gòu)二、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)主要研究?jī)煞矫娴膯?wèn)題：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=(春,夏)，(夏,秋)，(秋,冬)，(冬,春)全國(guó)計(jì)算機(jī)等級(jí)考試12全國(guó)計(jì)算機(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ī)存儲(chǔ)介質(zhì)中真正存儲(chǔ)的結(jié)構(gòu)，物理結(jié)構(gòu)：數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)介質(zhì)中真正存儲(chǔ)的結(jié)構(gòu)，也被稱為也被稱為“存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu) 2 2邏輯結(jié)構(gòu)：人們所理解的數(shù)據(jù)之間的結(jié)構(gòu)，可以用圖示邏輯結(jié)構(gòu)：人們所理解的數(shù)據(jù)之間的結(jié)構(gòu)，可以用圖示 的方法繪畫(huà)出來(lái)的數(shù)據(jù)之間的結(jié)構(gòu)。的方法繪畫(huà)出來(lái)的數(shù)據(jù)之間的

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

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

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

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

13、bcde，認(rèn)為在任何時(shí) 刻均允許出棧，以下選項(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，在第五個(gè)元素，在第五個(gè)元素E E入棧前，棧中元素入棧前，棧中元素可以出棧，那

14、么出棧序列可能是可以出棧，那么出棧序列可能是 A)ABCED A)ABCED B)DCBEA B)DCBEA C)DBCEA C)DBCEA D)CDABE D)CDABE全國(guó)計(jì)算機(jī)等級(jí)考試19全國(guó)計(jì)算機(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。全國(guó)計(jì)算機(jī)等級(jí)考試20全國(guó)計(jì)算機(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)沒(méi)有共同點(diǎn)沒(méi)有共同點(diǎn)2 2、一些重要的程序語(yǔ)言、一些重要的程序語(yǔ)言(如如C C語(yǔ)言和語(yǔ)言和PascalPascal語(yǔ)言語(yǔ)言)允許過(guò)程的遞歸調(diào)用。而允許過(guò)程的遞歸調(diào)用。而 實(shí)現(xiàn)遞歸調(diào)用中的存儲(chǔ)分配通常用實(shí)現(xiàn)遞歸調(diào)用中的存儲(chǔ)分配通常用 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)先出的線性表全國(guó)計(jì)算機(jī)等級(jí)考試21全國(guó)計(jì)算機(jī)等級(jí)考試National Computer Rank Examination六、循環(huán)隊(duì)列六、循環(huán)隊(duì)列rearfront

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

18、來(lái)存儲(chǔ)數(shù)據(jù)。B.指針域，用來(lái)指向下一個(gè)結(jié)點(diǎn)的位置。3、繪畫(huà)一個(gè)由5個(gè)節(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單鏈表單鏈表全國(guó)計(jì)算機(jī)等級(jí)考試24全國(guó)計(jì)算機(jī)等級(jí)考試National Computer Rank Examination鏈表的種類：?jiǎn)捂湵怼⒀h(huán)鏈表、雙向鏈表。1234512345循環(huán)鏈表雙向鏈表 12345 全國(guó)計(jì)算機(jī)等級(jí)考試25全國(guó)計(jì)算機(jī)等級(jí)考試National Computer Rank Examination1 1、鏈表不具有的特點(diǎn)是、鏈表不具有的特點(diǎn)是 A)A)不必事先估計(jì)存儲(chǔ)空間不必事先估計(jì)存儲(chǔ)空

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

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

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

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

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

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

25、結(jié)點(diǎn)個(gè)數(shù)為的結(jié)點(diǎn)個(gè)數(shù)為n2n2，那么：，那么：n0+n1+n2=700 n0+n1+n2=7001 1根據(jù)二叉樹(shù)性質(zhì)：葉子結(jié)點(diǎn)個(gè)數(shù)比度為根據(jù)二叉樹(shù)性質(zhì)：葉子結(jié)點(diǎn)個(gè)數(shù)比度為2 2的結(jié)點(diǎn)個(gè)數(shù)多的結(jié)點(diǎn)個(gè)數(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 完全二叉樹(shù)總結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)，那么度為完全二叉樹(shù)總結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)，那么度為1 1的結(jié)點(diǎn)個(gè)數(shù)為的結(jié)點(diǎn)個(gè)數(shù)為1 1；完全二叉樹(shù)的總結(jié)點(diǎn)；完全二叉樹(shù)的總結(jié)點(diǎn)個(gè)數(shù)為奇數(shù)，那么度為個(gè)數(shù)為奇數(shù)，那么度為1

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

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

28、GEDHFBCA B)DGEBHFCA B)DGEBHFCA C)ABCDEFGH C)ABCDEFGH D)ACBFEDHG D)ACBFEDHG3 3、樹(shù)是結(jié)點(diǎn)的集合，它的根結(jié)點(diǎn)數(shù)目是、樹(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的滿二叉樹(shù)中，葉子結(jié)點(diǎn)的個(gè)數(shù)為的滿二叉樹(shù)中，葉子結(jié)點(diǎn)的個(gè)數(shù)為 A)32 A)32B)31 C)16 B)31 C)16 D)15 D)15 5 5、在樹(shù)結(jié)構(gòu)中，樹(shù)根結(jié)點(diǎn)沒(méi)有、在樹(shù)結(jié)構(gòu)中，樹(shù)根結(jié)點(diǎn)沒(méi)有 。全國(guó)計(jì)算機(jī)等級(jí)考試36全國(guó)計(jì)

29、算機(jī)等級(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)二叉樹(shù)是線性結(jié)構(gòu)二叉樹(shù)是線性結(jié)構(gòu)7 7、具有、具有3 3個(gè)結(jié)點(diǎn)的二叉樹(shù)有個(gè)結(jié)點(diǎn)的二叉樹(shù)有 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ù)中有、設(shè)一棵二叉樹(shù)中有3 3個(gè)葉子結(jié)點(diǎn)，有個(gè)葉子結(jié)點(diǎn)，有8 8個(gè)度為個(gè)度為1 1的結(jié)點(diǎn)，那么

30、該二叉樹(shù)中的結(jié)點(diǎn)，那么該二叉樹(shù)中總總 的結(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ù)、設(shè)樹(shù)T T的深度為的深度為4,4,其中度為其中度為1 1、2 2、3 3、4 4的結(jié)點(diǎn)個(gè)數(shù)分別為的結(jié)點(diǎn)個(gè)數(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全國(guó)計(jì)算機(jī)等級(jí)考試37全國(guó)計(jì)算機(jī)等級(jí)考試National Computer Rank Examination1010、設(shè)有左側(cè)二叉樹(shù)，對(duì)此二叉樹(shù)前序遍歷的結(jié)果為、設(shè)有左側(cè)二叉樹(shù)，對(duì)此二叉樹(shù)前序遍歷的結(jié)果為

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

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

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

34、變量安排有序化 對(duì)復(fù)雜數(shù)據(jù)結(jié)構(gòu)應(yīng)注釋說(shuō)明對(duì)復(fù)雜數(shù)據(jù)結(jié)構(gòu)應(yīng)注釋說(shuō)明3.3.語(yǔ)句的結(jié)構(gòu)語(yǔ)句的結(jié)構(gòu) 每條語(yǔ)句簡(jiǎn)單明了每條語(yǔ)句簡(jiǎn)單明了 盡量不用或少用盡量不用或少用GOTOGOTO語(yǔ)句語(yǔ)句 盡量只采用盡量只采用3 3種根本控制結(jié)構(gòu)編程種根本控制結(jié)構(gòu)編程4.4.輸入和輸出輸入和輸出 對(duì)輸入數(shù)據(jù)進(jìn)行校驗(yàn)和合理性檢查對(duì)輸入數(shù)據(jù)進(jìn)行校驗(yàn)和合理性檢查 輸入輸出格式保持一致輸入輸出格式保持一致 設(shè)計(jì)良好的輸出報(bào)表設(shè)計(jì)良好的輸出報(bào)表全國(guó)計(jì)算機(jī)等級(jí)考試42全國(guó)計(jì)算機(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語(yǔ)句。結(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)程序的易讀性。全國(guó)計(jì)算機(jī)等級(jí)考試43全國(guó)計(jì)算機(jī)等級(jí)考試National Computer Rank Examination利用圖示表示順序結(jié)構(gòu)ABAB程序流程圖N-S圖全國(guó)計(jì)算機(jī)等級(jí)考試44全國(guó)計(jì)算機(jī)等級(jí)考試National Computer Rank Examination利用圖示表示選擇結(jié)構(gòu)條件滿足不滿足AB程序流程圖N-S圖AB條件滿足不滿足全國(guó)計(jì)算機(jī)等級(jí)考試45全國(guó)計(jì)算機(jī)等級(jí)考試Na

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

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

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

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

40、人好人好人壞人壞人中國(guó)人中國(guó)人 外國(guó)人外國(guó)人張三張三全國(guó)計(jì)算機(jī)等級(jí)考試52全國(guó)計(jì)算機(jī)等級(jí)考試National Computer Rank Examination4 4、消息與多態(tài)性、消息與多態(tài)性1消息Message：進(jìn)行對(duì)象之間的信息傳遞。2多態(tài)性Polymorphism：同樣的消息傳遞給不同的對(duì)象，導(dǎo)致 完全不同的行動(dòng)。消息的組成：A.接收消息的對(duì)象名稱。B.消息標(biāo)識(shí)符，也叫做“消息名。C.零個(gè)或多個(gè)參數(shù)。全國(guó)計(jì)算機(jī)等級(jí)考試53全國(guó)計(jì)算機(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à)結(jié)構(gòu)、循環(huán)結(jié)構(gòu)分支結(jié)構(gòu)、等價(jià)結(jié)構(gòu)、循環(huán)結(jié)構(gòu) C)C)多分支結(jié)構(gòu)、賦值結(jié)構(gòu)、等價(jià)結(jié)構(gòu)多分支結(jié)構(gòu)、賦值結(jié)構(gòu)、等價(jià)結(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ì)程序時(shí)，應(yīng)采納的原那么之一是、在設(shè)計(jì)程序時(shí)，應(yīng)采納的原那么之一是 A)A)不限制不限制gotogoto語(yǔ)句的使用語(yǔ)句的使用 B)B)減少或取消注解行減少或取消注解行 C)C)程序越短越好程序越短越好 D)D)程序結(jié)構(gòu)應(yīng)有助于讀者理解程序結(jié)構(gòu)應(yīng)有助于讀者理解3 3、程序設(shè)計(jì)語(yǔ)言的根本成分是數(shù)據(jù)成分、運(yùn)算成分、控制成分和、程序設(shè)計(jì)語(yǔ)言的根

42、本成分是數(shù)據(jù)成分、運(yùn)算成分、控制成分和 A)A)對(duì)象成分對(duì)象成分 B)B)變量成分變量成分 C)C)語(yǔ)句成分語(yǔ)句成分 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ì)語(yǔ)言的先進(jìn)性程序設(shè)計(jì)語(yǔ)言的先進(jìn)性 D)D)程序易讀性程序易讀性全國(guó)計(jì)算機(jī)等級(jí)考試54全國(guó)計(jì)算機(jī)等級(jí)考試National Computer Rank Examination5 5、以下不屬于對(duì)象的根本特點(diǎn)的是、以下不屬于對(duì)象的根本特點(diǎn)的是 A)A)分類性分類性 B)B)多態(tài)性多態(tài)性 C)C)繼承性繼承性D)D)封裝性封

43、裝性 6 6、對(duì)建立良好的程序設(shè)計(jì)風(fēng)格，下面描述正確的選項(xiàng)是、對(duì)建立良好的程序設(shè)計(jì)風(fēng)格，下面描述正確的選項(xiàng)是 A)A)程序應(yīng)簡(jiǎn)單、清晰、可讀性好程序應(yīng)簡(jiǎn)單、清晰、可讀性好 B)B)符號(hào)名的命名只要符合語(yǔ)法符號(hào)名的命名只要符合語(yǔ)法 C)C)充分考慮程序的執(zhí)行效率充分考慮程序的執(zhí)行效率 D)D)程序的注釋可有可無(wú)程序的注釋可有可無(wú)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)過(guò)程、子過(guò)程和分程序過(guò)程、子過(guò)程和分程序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語(yǔ)句語(yǔ)句全國(guó)計(jì)算機(jī)等級(jí)考試55全國(guó)計(jì)算機(jī)等級(jí)考試National Computer Rank Examin

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

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

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

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

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

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

51、與需求分析、需求與需求分析需求：用戶對(duì)目標(biāo)軟件系統(tǒng)在功能、行為、性能、設(shè)計(jì) 約束等方面的期望。需求分析：發(fā)現(xiàn)用戶需求的過(guò)程需求分析階段的工作：1需求獲取 2需求分析 3編寫(xiě)需求規(guī)格說(shuō)明書(shū) 4需求評(píng)審 全國(guó)計(jì)算機(jī)等級(jí)考試64全國(guó)計(jì)算機(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)開(kāi)發(fā)方法 DSSD。D.面向?qū)ο蟮姆治龇椒?OOA。全國(guó)計(jì)算機(jī)等級(jí)考試65全國(guó)計(jì)算機(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ù)流存儲(chǔ)文件/數(shù)據(jù)源源/潭全國(guó)計(jì)算機(jī)等級(jí)考試66全國(guó)計(jì)算機(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ù)字典的作用：對(duì)數(shù)據(jù)流圖DFD中出現(xiàn)的被命名圖形元素進(jìn) 行確切的解釋。全國(guó)計(jì)算機(jī)等級(jí)考試67全國(guó)計(jì)算機(jī)等級(jí)考試National Computer Rank Examination結(jié)構(gòu)化分析方法：判定樹(shù)

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

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