C語(yǔ)言二級(jí)公共基礎(chǔ)知識(shí)講義

全國(guó)計(jì)算機(jī)等級(jí)考試NationalComputerRankExamination二級(jí)·公共基礎(chǔ)知識(shí)全國(guó)計(jì)算機(jī)等級(jí)考試1二級(jí)公共基礎(chǔ)知識(shí)二級(jí)公共基礎(chǔ)知識(shí)考試內(nèi)容數(shù)據(jù)結(jié)構(gòu)和算法程序設(shè)計(jì)基礎(chǔ)軟件工程數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)全國(guó)計(jì)算機(jī)等級(jí)考試2二級(jí)公共基礎(chǔ)知識(shí)1、二級(jí)公共基礎(chǔ)的考試方式為筆試，與各科語(yǔ)言的筆試部分合為一張?jiān)嚲怼９不A(chǔ)部分占全卷的30分。2、公共基礎(chǔ)知識(shí)有10道選擇題和5道填空題。二級(jí)公共基礎(chǔ)知識(shí)考試方式全國(guó)計(jì)算機(jī)等級(jí)考試3二級(jí)公共基礎(chǔ)知識(shí)理解基本概念多做練習(xí)適當(dāng)記憶一些名詞與所學(xué)程序設(shè)計(jì)語(yǔ)言結(jié)合起來(lái)理解二級(jí)公共基礎(chǔ)知識(shí)學(xué)習(xí)方法全國(guó)計(jì)算機(jī)等級(jí)考試4二級(jí)公共基礎(chǔ)知識(shí)第一章數(shù)據(jù)結(jié)構(gòu)和算法全國(guó)計(jì)算機(jī)等級(jí)考試5二級(jí)公共基礎(chǔ)知識(shí)本章知識(shí)要點(diǎn)算法算法的定義算法的特征算法復(fù)雜度數(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二級(jí)公共基礎(chǔ)知識(shí)算法是對(duì)特定問(wèn)題求解步驟的一種描述。一、算法算法的特性：

（1）有窮性：算法必須在有限的次數(shù)內(nèi)完成。（2）確定性：算法的每一步必須是明確的。（3）可行性：算法的每一步必須是可以實(shí)現(xiàn)的。

（4）擁有足夠的情報(bào)：算法必須有一定的輸入和輸出。全國(guó)計(jì)算機(jī)等級(jí)考試7二級(jí)公共基礎(chǔ)知識(shí)算法的基本要素：（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二級(jí)公共基礎(chǔ)知識(shí)算法的復(fù)雜度：衡量算法優(yōu)劣的量。（1）時(shí)間復(fù)雜度：算法的時(shí)間耗費(fèi)。A.算法中基本操作重復(fù)執(zhí)行次數(shù)和算法執(zhí)行時(shí)間同步增長(zhǎng)，稱作算法的時(shí)間復(fù)雜度。B.算法中基本操作重復(fù)執(zhí)行次數(shù)和問(wèn)題規(guī)模有關(guān)，是問(wèn)題規(guī)模的函數(shù)。C.算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量。（2）空間復(fù)雜度：執(zhí)行算法所需要的內(nèi)存空間。全國(guó)計(jì)算機(jī)等級(jí)考試9二級(jí)公共基礎(chǔ)知識(shí)二、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)主要研究?jī)煞矫娴膯?wèn)題：（1）數(shù)據(jù)本身。（2）數(shù)據(jù)之間的前后件關(guān)系。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)本身數(shù)據(jù)之間的前后件關(guān)系數(shù)據(jù)結(jié)構(gòu)表示為：DS={D，S}例：D={春，夏，秋，冬}S={(春,夏)，(夏,秋)，(秋,冬)，(冬,春)}全國(guó)計(jì)算機(jī)等級(jí)考試10二級(jí)公共基礎(chǔ)知識(shí)數(shù)據(jù)的結(jié)構(gòu)分為：（1）物理結(jié)構(gòu)：數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)介質(zhì)中真正存儲(chǔ)的結(jié)構(gòu)，也被稱為“存儲(chǔ)結(jié)構(gòu)”（2）邏輯結(jié)構(gòu)：人們所理解的數(shù)據(jù)之間的結(jié)構(gòu)，可以用圖示的方法繪畫(huà)出來(lái)的數(shù)據(jù)之間的結(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)系，也不一定是一一對(duì)應(yīng)的。全國(guó)計(jì)算機(jī)等級(jí)考試11二級(jí)公共基礎(chǔ)知識(shí)數(shù)據(jù)的結(jié)構(gòu)分為：（1）線性結(jié)構(gòu)：非空數(shù)據(jù)結(jié)構(gòu)同時(shí)滿足以下兩個(gè)條件就是線性結(jié)構(gòu)：A.有且僅有一個(gè)根結(jié)點(diǎn)；B.除頭結(jié)點(diǎn)和尾結(jié)點(diǎn)外，任何結(jié)點(diǎn)有且僅有一個(gè)前件和一個(gè)后件。（2）非線性結(jié)構(gòu)：除了線性結(jié)構(gòu)都是非線性結(jié)構(gòu)。全國(guó)計(jì)算機(jī)等級(jí)考試12二級(jí)公共基礎(chǔ)知識(shí)全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(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ī)等級(jí)考試13二級(jí)公共基礎(chǔ)知識(shí)1020304050607080三、順序表：順序表就是數(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í)考試14二級(jí)公共基礎(chǔ)知識(shí)四、堆棧棧頂top棧底入棧/壓入出棧/彈出1、定義：只允許在棧頂位置插入數(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)后出表（FILO）5、堆棧具備存儲(chǔ)功能：函數(shù)的遞歸調(diào)用和表達(dá)式求解都用到了堆棧。全國(guó)計(jì)算機(jī)等級(jí)考試15二級(jí)公共基礎(chǔ)知識(shí)入棧順序：a、b、c、d、e、f?？誥bacbabadba…………..入a入b入c出c入d模擬堆棧的數(shù)據(jù)出入過(guò)程：全國(guó)計(jì)算機(jī)等級(jí)考試16二級(jí)公共基礎(chǔ)知識(shí)【典型題型】假設(shè)一個(gè)堆棧，入棧順序?yàn)閍bcde，認(rèn)為在任何時(shí)刻均允許出棧，下列選項(xiàng)中不可能的出棧順序?yàn)椋篈）abcde（可能）B）edcba（可能）C）cdeba（可能）D）cdeab（不可能）如果進(jìn)棧序列為e1,e2,e3,e4，則可能的出棧序列是（）A)e3,e1,e4,e2 B)e2,e4,e3,e1C)e3,e4,e1,e2 D)任意順序棧底至棧頂依次存放元素A、B、C、D，在第五個(gè)元素E入棧前，棧中元素可以出棧，則出棧序列可能是（）A)ABCED B)DCBEAC)DBCEA D)CDABE全國(guó)計(jì)算機(jī)等級(jí)考試17二級(jí)公共基礎(chǔ)知識(shí)五、隊(duì)列隊(duì)頭front隊(duì)尾rear入隊(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í)考試18二級(jí)公共基礎(chǔ)知識(shí)六、循環(huán)隊(duì)列rearfront全國(guó)計(jì)算機(jī)等級(jí)考試19二級(jí)公共基礎(chǔ)知識(shí)入隊(duì)順序：a、b、c、d、e、f模擬循環(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í)考試20二級(jí)公共基礎(chǔ)知識(shí)七、線性鏈表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ù)域，用來(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)數(shù)據(jù)域指針域12345^單鏈表全國(guó)計(jì)算機(jī)等級(jí)考試21二級(jí)公共基礎(chǔ)知識(shí)鏈表的種類：?jiǎn)捂湵?、循環(huán)鏈表、雙向鏈表。1234512345循環(huán)鏈表雙向鏈表^12345^全國(guó)計(jì)算機(jī)等級(jí)考試22二級(jí)公共基礎(chǔ)知識(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í)考試23二級(jí)公共基礎(chǔ)知識(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í)考試24二級(jí)公共基礎(chǔ)知識(shí)1、二叉樹(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í)考試25二級(jí)公共基礎(chǔ)知識(shí)2、有序樹(shù)與無(wú)序樹(shù)：eABeBA二叉樹(shù)和度為二的樹(shù)的區(qū)別：A.二叉樹(shù)是有序樹(shù)，度為二的樹(shù)是普通樹(shù)，屬于無(wú)序樹(shù)。B.二叉樹(shù)允許為空，度為二的數(shù)至少有三個(gè)結(jié)點(diǎn)?！酒胀?shù)不允許為空，至少有一個(gè)結(jié)點(diǎn)】全國(guó)計(jì)算機(jī)等級(jí)考試26二級(jí)公共基礎(chǔ)知識(shí)3、二叉樹(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í)考試27二級(jí)公共基礎(chǔ)知識(shí)4、滿二叉樹(shù)和完全二叉樹(shù)：A.滿二叉樹(shù)：二叉樹(shù)的每一層均具備該層最大結(jié)點(diǎn)個(gè)數(shù)。（即：不具備度為1的結(jié)點(diǎn)）B.完全二叉樹(shù)：滿二叉樹(shù)是一個(gè)特殊的完全二叉樹(shù)。將所有結(jié)點(diǎn)自上向下、自左向右編號(hào)，結(jié)點(diǎn)編號(hào)連續(xù)而不缺失。xeoqkbgxeoqkb滿二叉樹(shù)完全二叉樹(shù)123456全國(guó)計(jì)算機(jī)等級(jí)考試28二級(jí)公共基礎(chǔ)知識(shí)5、二叉樹(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，其左孩子為2n，其右孩子為2n+1。xeoqkbg1234567全國(guó)計(jì)算機(jī)等級(jí)考試29二級(jí)公共基礎(chǔ)知識(shí)填空題：設(shè)一棵完全二叉樹(shù)共有700個(gè)結(jié)點(diǎn)，則在該二叉樹(shù)中有

個(gè)葉子結(jié)點(diǎn)二叉樹(shù)的結(jié)點(diǎn)共有三種：度為0的葉子結(jié)點(diǎn)、度為1的結(jié)點(diǎn)和度為2的結(jié)點(diǎn)。設(shè)度為0的葉子結(jié)點(diǎn)個(gè)數(shù)為n0，度為1的結(jié)點(diǎn)個(gè)數(shù)為n1，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2，則：

n0+n1+n2=700 （1）根據(jù)二叉樹(shù)性質(zhì)：葉子結(jié)點(diǎn)個(gè)數(shù)比度為2的結(jié)點(diǎn)個(gè)數(shù)多1，即：

n0=n2+1 （2）將（2）式帶入（1）式，所以：

n0+n1+n0-1=7002n0=701-n1完全二叉樹(shù)總結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)，則度為1的結(jié)點(diǎn)個(gè)數(shù)為1；完全二叉樹(shù)的總結(jié)點(diǎn)個(gè)數(shù)為奇數(shù)，則度為1的結(jié)點(diǎn)個(gè)數(shù)為0。所以：2n0=701-1，即n0=350。全國(guó)計(jì)算機(jī)等級(jí)考試30二級(jí)公共基礎(chǔ)知識(shí)6、二叉樹(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í)考試31二級(jí)公共基礎(chǔ)知識(shí)第二章程序設(shè)計(jì)基礎(chǔ)全國(guó)計(jì)算機(jī)等級(jí)考試32二級(jí)公共基礎(chǔ)知識(shí)本章知識(shí)要點(diǎn)面向過(guò)程的程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)模塊化程序設(shè)計(jì)面向?qū)ο蟮某绦蛟O(shè)計(jì)對(duì)象的定義對(duì)象的屬性和方法類和實(shí)例的派生與繼承消息與多態(tài)性全國(guó)計(jì)算機(jī)等級(jí)考試33二級(jí)公共基礎(chǔ)知識(shí)一、程序設(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ǔ)言：模塊就是模塊、子例程、子程序。VFP數(shù)據(jù)庫(kù)：模塊就是子程序。Access數(shù)據(jù)庫(kù)：模塊就是宏、事件代碼。2、面向?qū)ο蟮某绦蛟O(shè)計(jì)：VB、VFP、Java、Delphi等。全國(guó)計(jì)算機(jī)等級(jí)考試34二級(jí)公共基礎(chǔ)知識(shí)二、程序設(shè)計(jì)風(fēng)格1.源程序文檔化選擇標(biāo)示符的名字注釋（序言性和功能性注釋）程序的視覺(jué)組織2.數(shù)據(jù)說(shuō)明的方法顯式地說(shuō)明一切變量數(shù)據(jù)說(shuō)明的次序應(yīng)該規(guī)范化說(shuō)明語(yǔ)句中變量安排有序化對(duì)復(fù)雜數(shù)據(jù)結(jié)構(gòu)應(yīng)注釋說(shuō)明3.語(yǔ)句的結(jié)構(gòu)每條語(yǔ)句簡(jiǎn)單明了盡量不用或少用GOTO語(yǔ)句盡量只采用3種基本控制結(jié)構(gòu)編程4.輸入和輸出對(duì)輸入數(shù)據(jù)進(jìn)行校驗(yàn)和合理性檢查輸入輸出格式保持一致設(shè)計(jì)良好的輸出報(bào)表全國(guó)計(jì)算機(jī)等級(jí)考試35二級(jí)公共基礎(chǔ)知識(shí)三、結(jié)構(gòu)化程序設(shè)計(jì)20世紀(jì)70年代提出了結(jié)構(gòu)化程序設(shè)計(jì)

（StructuredProgramming）結(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í)考試36二級(jí)公共基礎(chǔ)知識(shí)利用圖示表示順序結(jié)構(gòu)ABAB程序流程圖N-S圖全國(guó)計(jì)算機(jī)等級(jí)考試37二級(jí)公共基礎(chǔ)知識(shí)利用圖示表示選擇結(jié)構(gòu)條件滿足不滿足AB程序流程圖N-S圖AB條件滿足不滿足全國(guó)計(jì)算機(jī)等級(jí)考試38二級(jí)公共基礎(chǔ)知識(shí)利用圖示表示重復(fù)結(jié)構(gòu)(1)條件滿足不滿足S條件滿足不滿足S程序流程圖當(dāng)型循環(huán)程序流程圖直到型循環(huán)全國(guó)計(jì)算機(jī)等級(jí)考試39二級(jí)公共基礎(chǔ)知識(shí)利用圖示表示重復(fù)結(jié)構(gòu)(2)WHILE條件SSUNTIL條件N-S圖當(dāng)型循環(huán)N-S圖直到型循環(huán)全國(guó)計(jì)算機(jī)等級(jí)考試40二級(jí)公共基礎(chǔ)知識(shí)三、面向?qū)ο蟮某绦蛟O(shè)計(jì)面向?qū)ο?ObjectOriented)的程序設(shè)計(jì)方法已經(jīng)發(fā)展成為主流的軟件開(kāi)發(fā)方法，起源于對(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í)考試41二級(jí)公共基礎(chǔ)知識(shí)面向?qū)ο蠓椒ǖ闹饕獌?yōu)點(diǎn)：（1）與人類習(xí)慣的思維方法一致。（2）穩(wěn)定性好。（3）可重用性好。（4）易于開(kāi)發(fā)大型軟件產(chǎn)品。（5）可維護(hù)性好。全國(guó)計(jì)算機(jī)等級(jí)考試42二級(jí)公共基礎(chǔ)知識(shí)1、對(duì)象的定義對(duì)象：現(xiàn)實(shí)生活中存在的可以相互區(qū)分的物體。是屬性和方法的封裝。對(duì)象的基本特點(diǎn)：（1）標(biāo)識(shí)唯一性。（2）分類型。（3）多態(tài)性。（4）封裝性。（5）模塊獨(dú)立型好。全國(guó)計(jì)算機(jī)等級(jí)考試43二級(jí)公共基礎(chǔ)知識(shí)2、對(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)激活。屬性名屬性值方法名事件封裝性：(Encapsulation)對(duì)象依靠對(duì)象名將自身的屬性和方法封裝。全國(guó)計(jì)算機(jī)等級(jí)考試44二級(jí)公共基礎(chǔ)知識(shí)3、類和實(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í)子類。人好人壞人中國(guó)人外國(guó)人張三全國(guó)計(jì)算機(jī)等級(jí)考試45二級(jí)公共基礎(chǔ)知識(shí)4、消息與多態(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í)考試46二級(jí)公共基礎(chǔ)知識(shí)第三章軟件工程基礎(chǔ)軟件（Software）=程序+文檔全國(guó)計(jì)算機(jī)等級(jí)考試47二級(jí)公共基礎(chǔ)知識(shí)本章知識(shí)要點(diǎn)軟件危機(jī)軟件生命周期需求分析概要設(shè)計(jì)詳細(xì)設(shè)計(jì)測(cè)試調(diào)試軟件工程全國(guó)計(jì)算機(jī)等級(jí)考試48二級(jí)公共基礎(chǔ)知識(shí)一、軟件危機(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)率的提高趕不上硬件的發(fā)展和應(yīng)用需求的增長(zhǎng)?？傊?，可以將軟件危機(jī)歸結(jié)為成本、質(zhì)量、生產(chǎn)率問(wèn)題全國(guó)計(jì)算機(jī)等級(jí)考試49二級(jí)公共基礎(chǔ)知識(shí)二、軟件工程軟件工程是為了擺脫軟件危機(jī)而誕生的，主要思想是在軟件開(kāi)發(fā)過(guò)程中應(yīng)用工程化原則。軟件工程的三要素：方法、工具、工程。軟件工程的主要內(nèi)容：軟件開(kāi)發(fā)技術(shù)、軟件工程管理。軟件工程的原則：（1）抽象。（2）信息隱蔽。（3）模塊化。（4）局部化。（5）確定性。（6）一致性。（7）完備性。（8）可驗(yàn)證性。全國(guó)計(jì)算機(jī)等級(jí)考試50二級(jí)公共基礎(chǔ)知識(shí)二、軟件生命周期軟件生命周期（SoftwareLifeCycle，SLC）：將軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過(guò)程稱為“軟件生命周期”。可行性研究需求分析概要設(shè)計(jì)詳細(xì)設(shè)計(jì)實(shí)現(xiàn)測(cè)試使用退役維護(hù)定義階段開(kāi)發(fā)階段維護(hù)階段全國(guó)計(jì)算機(jī)等級(jí)考試51二級(jí)公共基礎(chǔ)知識(shí)軟件工程步驟用到的方法用到的工具生成的文檔需求分析結(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í)考試52二級(jí)公共基礎(chǔ)知識(shí)三、需求分析需求與需求分析需求分析的方法結(jié)構(gòu)化分析方法數(shù)據(jù)流圖與數(shù)據(jù)字典判定樹(shù)與判定表軟件需求規(guī)格說(shuō)明書(shū)全國(guó)計(jì)算機(jī)等級(jí)考試53二級(jí)公共基礎(chǔ)知識(shí)1、需求與需求分析需求：用戶對(duì)目標(biāo)軟件系統(tǒng)在功能、行為、性能、設(shè)計(jì)約束等方面的期望。需求分析：發(fā)現(xiàn)用戶需求的過(guò)程需求分析階段的工作：（1）需求獲?。?）需求分析（3）編寫(xiě)需求規(guī)格說(shuō)明書(shū)（4）需求評(píng)審全國(guó)計(jì)算機(jī)等級(jí)考試54二級(jí)公共基礎(chǔ)知識(shí)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ū)ο蟮姆治龇椒∣OA。全國(guó)計(jì)算機(jī)等級(jí)考試55二級(jí)公共基礎(chǔ)知識(shí)3、結(jié)構(gòu)化分析方法：數(shù)據(jù)流圖DFD數(shù)據(jù)流圖DFD中的主要圖形元素：加工/轉(zhuǎn)換數(shù)據(jù)流存儲(chǔ)文件/數(shù)據(jù)源源/潭全國(guó)計(jì)算機(jī)等級(jí)考試56二級(jí)公共基礎(chǔ)知識(shí)結(jié)構(gòu)化分析方法：數(shù)據(jù)字典DD數(shù)據(jù)字典DD是結(jié)構(gòu)化分析方法的核心。數(shù)據(jù)字典的作用：對(duì)數(shù)據(jù)流圖DFD中出現(xiàn)的被命名圖形元素進(jìn)行確切的解釋。全國(guó)計(jì)算機(jī)等級(jí)考試57二級(jí)公共基礎(chǔ)知識(shí)結(jié)構(gòu)化分析方法：判定樹(shù)與判定表判定樹(shù)

條件1

條件2

結(jié)果計(jì)7月－9月

訂票量>20:

15%算12月

訂票量<=20:5%折扣1月－6月

訂票量>20:30%量10月11月

訂票量<=20:5%全國(guó)計(jì)算機(jī)等級(jí)考試58二級(jí)公共基礎(chǔ)知識(shí)判定表旅游時(shí)間7月—9月，12月1月—6月，10月，11月訂票量>20%<=20%>20%<=20%折扣率15%5%30%20%全國(guó)計(jì)算機(jī)等級(jí)考試59二級(jí)公共基礎(chǔ)知識(shí)結(jié)構(gòu)化分析方法：需求規(guī)格說(shuō)明書(shū)軟件需求規(guī)格說(shuō)明書(shū)（SRS）是需求分析階段的最后成果，將在軟件工程的最后轉(zhuǎn)換為用戶手冊(cè)。軟件需求規(guī)格說(shuō)明書(shū)的作用：（1）便于用戶、開(kāi)發(fā)人員進(jìn)行理解和交流。（2）反映出用戶問(wèn)題的結(jié)構(gòu)，可作為軟件開(kāi)發(fā)工作的基礎(chǔ)和依據(jù)。（3）作為確認(rèn)測(cè)試和驗(yàn)收的依據(jù)。全國(guó)計(jì)算機(jī)等級(jí)考試60二級(jí)公共基礎(chǔ)知識(shí)四、概要設(shè)計(jì)軟件設(shè)計(jì)的基本原理：（1）抽象：把事物本質(zhì)的共同特性提取出來(lái)而不考慮細(xì)節(jié)。（2）模塊化：把待開(kāi)發(fā)軟件分解成若干個(gè)小的簡(jiǎn)單部分。（3）信息隱蔽：在一個(gè)模塊內(nèi)包含的信息，對(duì)于不需要這些信息的其他模塊來(lái)說(shuō)是不能訪問(wèn)的。（4）模塊獨(dú)立性：評(píng)價(jià)設(shè)計(jì)好壞的重要度量指標(biāo)。內(nèi)聚性和耦合性是模塊獨(dú)立性的兩個(gè)定性標(biāo)準(zhǔn)：A.內(nèi)聚性：一個(gè)模塊內(nèi)部各個(gè)元素間彼此結(jié)合的緊密程度。B.耦合性：模塊間互相連接的緊密程度。一款優(yōu)秀的軟件設(shè)計(jì)，應(yīng)做到高內(nèi)聚，低耦合。全國(guó)計(jì)算機(jī)等級(jí)考試61二級(jí)公共基礎(chǔ)知識(shí)概要設(shè)計(jì)的任務(wù)：（1）設(shè)計(jì)軟件系統(tǒng)結(jié)構(gòu)。（2）確定軟件的每一個(gè)模塊（3）確定模塊之間的調(diào)用關(guān)系（4）評(píng)價(jià)模塊結(jié)構(gòu)質(zhì)量。采用的方法：結(jié)構(gòu)化設(shè)計(jì)方法【SD】

使用的工具：軟件結(jié)構(gòu)圖SC。軟件結(jié)構(gòu)圖SC中的主要圖形元素模塊模塊間的調(diào)用關(guān)系全國(guó)計(jì)算機(jī)等級(jí)考試62二級(jí)公共基礎(chǔ)知識(shí)認(rèn)識(shí)軟件結(jié)構(gòu)圖SC深度=3寬度=3上級(jí)模塊從屬模塊原子模塊扇入扇出全國(guó)計(jì)算機(jī)等級(jí)考試63二級(jí)公共基礎(chǔ)知識(shí)五、詳細(xì)設(shè)計(jì)詳細(xì)設(shè)計(jì)的任務(wù)：為軟件結(jié)構(gòu)圖中每一個(gè)模塊確定實(shí)現(xiàn)的算法和數(shù)據(jù)結(jié)構(gòu)。表示算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)。采用的方法：結(jié)構(gòu)化編程方法【SP】

使用的工具：程序流程圖、N-S圖、問(wèn)題分析圖PAD

判定表過(guò)程設(shè)計(jì)語(yǔ)言/偽碼PDL全國(guó)計(jì)算機(jī)等級(jí)考試64二級(jí)公共基礎(chǔ)知識(shí)程序流程圖中的主要圖形元素：加工步驟控制流邏輯條件全國(guó)計(jì)算機(jī)等級(jí)考試65二級(jí)公共基礎(chǔ)知識(shí)六、軟件測(cè)試軟件測(cè)試的目的：盡可能多的發(fā)現(xiàn)錯(cuò)誤。（1）×錯(cuò)誤理解：軟件測(cè)試為了發(fā)現(xiàn)錯(cuò)誤并改正。（2）×錯(cuò)誤理解：軟件測(cè)試為了證明軟件正確性。軟件測(cè)試的準(zhǔn)則：（1）所有測(cè)試追溯到需求。（2）嚴(yán)格執(zhí)行測(cè)試計(jì)劃，排除測(cè)試隨意性。（3）充分注意測(cè)試中的群集現(xiàn)象：程序中存在錯(cuò)誤的概率與該程序中已發(fā)現(xiàn)的錯(cuò)誤數(shù)量成正比。（4）程序員避免檢測(cè)自己的程序。（5）窮舉測(cè)試不可能。（6）妥善保存測(cè)試文檔，為維護(hù)提供方便。全國(guó)計(jì)算機(jī)等級(jí)考試66二級(jí)公共基礎(chǔ)知識(shí)軟件測(cè)試的方法：（1）靜態(tài)測(cè)試：由人工進(jìn)行，無(wú)需借助計(jì)算機(jī)。（2）動(dòng)態(tài)測(cè)試：基于計(jì)算機(jī)，實(shí)際運(yùn)行軟件進(jìn)行測(cè)試A.白盒測(cè)試：邏輯覆蓋、基本路徑測(cè)試。B.黑盒測(cè)試：等價(jià)類劃分、邊界值分析、錯(cuò)誤推測(cè)法、因果圖。軟件測(cè)試的實(shí)施：第1步：?jiǎn)卧獪y(cè)試（對(duì)每一個(gè)模塊進(jìn)行測(cè)試）第2步：集成測(cè)試（將模塊組裝起來(lái)的同時(shí)進(jìn)行測(cè)試）第3步：確認(rèn)測(cè)試（驗(yàn)證軟件的功能和性能是否滿足需求）第4步：系統(tǒng)測(cè)試（評(píng)估系統(tǒng)環(huán)境下軟件的功能）全國(guó)計(jì)算機(jī)等級(jí)考試67二級(jí)公共基礎(chǔ)知識(shí)七、軟件調(diào)試（Debug）軟件調(diào)試的目的：診斷和改正程序中的錯(cuò)誤。軟件調(diào)試的基本步驟：第1步：錯(cuò)誤定位?！菊紦?jù)了調(diào)試的絕大多數(shù)工作量】第2步：修改設(shè)計(jì)和代碼，以排除錯(cuò)誤。第3步：進(jìn)行回歸測(cè)試，防止引進(jìn)新的錯(cuò)誤。全國(guó)計(jì)算機(jī)等級(jí)考試68二級(jí)公共基礎(chǔ)知識(shí)第四章數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)全國(guó)計(jì)算機(jī)等級(jí)考試69二級(jí)公共基礎(chǔ)知識(shí)一、理解數(shù)據(jù)庫(kù)：1、數(shù)據(jù)（Data）是描述事物的符號(hào)記錄。2、為什么引入數(shù)據(jù)庫(kù)：（1）數(shù)據(jù)量大，數(shù)據(jù)多。（2）方便查找。全國(guó)計(jì)算機(jī)等級(jí)考試70二級(jí)公共基礎(chǔ)知識(shí)二、數(shù)據(jù)庫(kù)原理術(shù)語(yǔ)：1、數(shù)據(jù)（Data）是描述事物的符號(hào)記錄。2、數(shù)據(jù)庫(kù)（DataBase，DB）數(shù)據(jù)的集合，是存放數(shù)據(jù)的倉(cāng)庫(kù)。3、數(shù)據(jù)庫(kù)管理系統(tǒng)（DBMS）負(fù)責(zé)數(shù)據(jù)的管理。（1）DBMS屬于系統(tǒng)軟件。（2）DBMS是數(shù)據(jù)庫(kù)系統(tǒng)的核心。4、數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng)（DBAS）利用DBMS開(kāi)發(fā)的應(yīng)用軟件。5、數(shù)據(jù)庫(kù)系統(tǒng)（DBS）使用了數(shù)據(jù)庫(kù)技術(shù)的計(jì)算機(jī)，屬于硬件系統(tǒng)。6、數(shù)據(jù)庫(kù)管理員（DBA）是數(shù)據(jù)庫(kù)系統(tǒng)的人的因素。負(fù)責(zé)管理、維護(hù)、設(shè)計(jì)、監(jiān)視數(shù)據(jù)庫(kù)系統(tǒng)的運(yùn)行。全國(guó)計(jì)算機(jī)等級(jí)考試71二級(jí)公共基礎(chǔ)知識(shí)計(jì)算機(jī)硬件操作系統(tǒng)數(shù)據(jù)庫(kù)管理系統(tǒng)數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng)用戶WindowsXP/Vista/7/2003等。Access/VisualFoxPro/SQLServer等。全國(guó)計(jì)算機(jī)等級(jí)考試72二級(jí)公共基礎(chǔ)知識(shí)三、數(shù)據(jù)庫(kù)系統(tǒng)的三級(jí)模式和兩級(jí)映射：數(shù)據(jù)庫(kù)（DB）內(nèi)模式（物理模式）概念模式外模式/子模式用戶模式外模式應(yīng)用應(yīng)用應(yīng)用概念模式–內(nèi)模式映射外模式-概念模式映射全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu)的描述局部數(shù)據(jù)邏輯結(jié)構(gòu)的描述全國(guó)計(jì)算機(jī)等級(jí)考試73二級(jí)公共基礎(chǔ)知識(shí)四、數(shù)據(jù)模型：1、數(shù)據(jù)模型的三層分類：（1）概念數(shù)據(jù)模型/概念模型（2）邏輯數(shù)據(jù)模型/數(shù)據(jù)模型（3）物理數(shù)據(jù)模型/物理模型2、典型的概念數(shù)據(jù)模型：E–R模型（實(shí)體-聯(lián)系模型）（1）實(shí)體：現(xiàn)實(shí)生活中的事物。（2）屬性：表示實(shí)體的一些特征。（3）聯(lián)系：實(shí)體之間的關(guān)聯(lián)。全國(guó)計(jì)算機(jī)等級(jí)考試74二級(jí)公共基礎(chǔ)知識(shí)3、實(shí)體間聯(lián)系：（1）一對(duì)一（1:1）學(xué)校--校長(zhǎng)【計(jì)算機(jī)不予處理】（2）一對(duì)多（1:m）學(xué)生–班級(jí)【計(jì)算機(jī)可以直接處理】（3）多對(duì)多（m:n）學(xué)生–課程【轉(zhuǎn)換為兩個(gè)一對(duì)多聯(lián)系再處理】歷史上出現(xiàn)過(guò)的數(shù)據(jù)模型：網(wǎng)狀模型、層次模型、關(guān)系模型全國(guó)計(jì)算機(jī)等級(jí)考試75二級(jí)公共基礎(chǔ)知識(shí)4、E-R模型的圖示表示法：實(shí)體聯(lián)系實(shí)體的屬性全國(guó)計(jì)算機(jī)等級(jí)考試76二級(jí)公共基礎(chǔ)知識(shí)五、關(guān)系模型：關(guān)系的數(shù)據(jù)結(jié)構(gòu)學(xué)號(hào)姓名性別年齡籍貫01張三男21河北02李四女24山東03王武男28陜西例：學(xué)生關(guān)系屬性元組/記錄主鍵關(guān)系就是二維表。1、元組是有限的。2、元組不能重復(fù)。3、屬性不能重復(fù)。4、元素的順序是無(wú)關(guān)的。5、屬性的順序是無(wú)關(guān)的。全國(guó)計(jì)算機(jī)等級(jí)考試77二級(jí)公共基礎(chǔ)知識(shí)關(guān)系的數(shù)據(jù)約束A.實(shí)體完整性約束主鍵取值不能為空，不能取重復(fù)值。主鍵取值不同，就是兩個(gè)不同的元組。B.參照完整性約束不允許引用不存在的元組。約束了關(guān)系之間相關(guān)聯(lián)的情況。C.用戶自定義完整性約束全國(guó)計(jì)算機(jī)等級(jí)考試78二級(jí)公共基礎(chǔ)知識(shí)六、關(guān)系代數(shù)：參與運(yùn)算的數(shù)據(jù)都是關(guān)系（二維表）。1、基本關(guān)系代數(shù)（1）交：R∩S=｛t|t∈R且t∈S｝（2）并：R∪S=｛t|t∈R或t∈S｝（3）差：R-S=｛t|t∈R且t∈S｝全國(guó)計(jì)算機(jī)等級(jí)考試79二級(jí)公共基礎(chǔ)知識(shí)RABC125149284560924SABC125349264560333R∩SABC125560結(jié)論：并交差三個(gè)操作都不能更改關(guān)系的屬性個(gè)數(shù)。全國(guó)計(jì)算機(jī)等級(jí)考試80二級(jí)公共基礎(chǔ)知識(shí)RABC125149560SABC125349R×SR.AR.BR.CS.AS.BS.C1251251491251493495601255603491253492、關(guān)系積（笛卡爾積）全國(guó)計(jì)算機(jī)等級(jí)考試81二級(jí)公共基礎(chǔ)知識(shí)3、擴(kuò)展關(guān)系代數(shù)：（1）選擇：σA>C(R)【對(duì)關(guān)系的橫向分解】（