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

全國計(jì)算機(jī)等級(jí)考試NationalComputerRankExamination二級(jí)·公共根底知識(shí)全國計(jì)算機(jī)等級(jí)考試1二級(jí)公共根底知識(shí)考試內(nèi)容數(shù)據(jù)結(jié)構(gòu)和算法程序設(shè)計(jì)根底軟件工程數(shù)據(jù)庫設(shè)計(jì)根底全國計(jì)算機(jī)等級(jí)考試21、二級(jí)公共根底的考試方式為筆試，與各科語言的筆試局部合為一張?jiān)嚲怼９哺拙植空既淼?0分。2、公共根底知識(shí)有10道選擇題和5道填空題。二級(jí)公共根底知識(shí)考試方式全國計(jì)算機(jī)等級(jí)考試3理解根本概念多做練習(xí)適當(dāng)記憶一些名詞與所學(xué)程序設(shè)計(jì)語言結(jié)合起來理解二級(jí)公共根底知識(shí)學(xué)習(xí)方法全國計(jì)算機(jī)等級(jí)考試4第一章數(shù)據(jù)結(jié)構(gòu)和算法全國計(jì)算機(jī)等級(jí)考試5本章知識(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ì)列、樹算法的根本要素全國計(jì)算機(jī)等級(jí)考試6算法是對(duì)特定問題求解步驟的一種描述。一、算法算法的特性：〔1〕有窮性：算法必須在有限的次數(shù)內(nèi)完成。〔2〕確定性：算法的每一步必須是明確的。〔3〕可行性：算法的每一步必須是可以實(shí)現(xiàn)的?！?〕擁有足夠的情報(bào)：算法必須有一定的輸入和輸出。全國計(jì)算機(jī)等級(jí)考試7算法的根本要素：〔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)全國計(jì)算機(jī)等級(jí)考試8算法的復(fù)雜度：衡量算法優(yōu)劣的量?！?〕時(shí)間復(fù)雜度：算法的時(shí)間消耗。A.算法中根本操作重復(fù)執(zhí)行次數(shù)和算法執(zhí)行時(shí)間同步增長，稱作算法的時(shí)間復(fù)雜度。B.算法中根本操作重復(fù)執(zhí)行次數(shù)和問題規(guī)模有關(guān)，是問題規(guī)模的函數(shù)。C.算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量?！?〕空間復(fù)雜度：執(zhí)行算法所需要的內(nèi)存空間。全國計(jì)算機(jī)等級(jí)考試9二、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)主要研究兩方面的問題：〔1〕數(shù)據(jù)本身?！?〕數(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={(春,夏)，(夏,秋)，(秋,冬)，(冬,春)}全國計(jì)算機(jī)等級(jí)考試10數(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)，可以用圖示的方法繪畫出來的數(shù)據(jù)之間的結(jié)構(gòu)。例：一個(gè)班由35名同學(xué)，他們的座位牌號(hào)就是物理結(jié)構(gòu)，一次考試的排名是邏輯結(jié)構(gòu)。1注意：邏輯結(jié)構(gòu)和物理結(jié)構(gòu)沒有必然的聯(lián)系，也不一定是一一對(duì)應(yīng)的。全國計(jì)算機(jī)等級(jí)考試11數(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è)后件?！?〕非線性結(jié)構(gòu)：除了線性結(jié)構(gòu)都是非線性結(jié)構(gòu)。全國計(jì)算機(jī)等級(jí)考試12全國計(jì)算機(jī)等級(jí)考試二級(jí)公共根底知識(shí)要求掌握的數(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ī)等級(jí)考試131020304050607080三、順序表：順序表就是數(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)?！?〕任意其他結(jié)點(diǎn)至多有一個(gè)前件，一個(gè)后件?！?〕頭結(jié)點(diǎn)沒有前件，尾結(jié)點(diǎn)沒有后件。全國計(jì)算機(jī)等級(jí)考試14四、堆棧棧頂top棧底入棧/壓入出棧/彈出1、定義：只允許在棧頂位置插入數(shù)據(jù)和刪除數(shù)據(jù)的線性結(jié)構(gòu)是堆棧，簡稱為“?！薄?、堆棧屬于線性結(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á)式求解都用到了堆棧。全國計(jì)算機(jī)等級(jí)考試15入棧順序：a、b、c、d、e、f棧空abacbabadba…………..入a入b入c出c入d模擬堆棧的數(shù)據(jù)出入過程：全國計(jì)算機(jī)等級(jí)考試16【典型題型】假設(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全國計(jì)算機(jī)等級(jí)考試17五、隊(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〕。全國計(jì)算機(jī)等級(jí)考試18六、循環(huán)隊(duì)列rearfront全國計(jì)算機(jī)等級(jí)考試19入隊(duì)順序：a、b、c、d、e、f模擬循環(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ī)等級(jí)考試20七、線性鏈表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ù)域，用來存儲(chǔ)數(shù)據(jù)。B.指針域，用來指向下一個(gè)結(jié)點(diǎn)的位置。3、繪畫一個(gè)由5個(gè)節(jié)點(diǎn)組成的線性鏈表，數(shù)據(jù)為1、2、3、4、5。鏈表的結(jié)點(diǎn)數(shù)據(jù)域指針域12345^單鏈表全國計(jì)算機(jī)等級(jí)考試21鏈表的種類：單鏈表、循環(huán)鏈表、雙向鏈表。1234512345循環(huán)鏈表雙向鏈表^12345^全國計(jì)算機(jī)等級(jí)考試22八、樹與二叉樹1、樹屬于非線性結(jié)構(gòu)。2、樹的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)不相同。3、樹有且僅有一個(gè)根節(jié)點(diǎn)。根節(jié)點(diǎn)xeoqkbg全國計(jì)算機(jī)等級(jí)考試23二叉樹：每個(gè)結(jié)點(diǎn)最多分兩叉的有序樹。二叉樹二叉樹的術(shù)語有序樹與無序樹二叉樹的五種根本結(jié)構(gòu)滿二叉樹和完全二叉樹二叉樹的計(jì)算二叉樹的遍歷全國計(jì)算機(jī)等級(jí)考試241、二叉樹的術(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)的個(gè)數(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ī)等級(jí)考試252、有序樹與無序樹：eABeBA二叉樹和度為二的樹的區(qū)別：A.二叉樹是有序樹，度為二的樹是普通樹，屬于無序樹。B.二叉樹允許為空，度為二的數(shù)至少有三個(gè)結(jié)點(diǎn)?！酒胀洳辉试S為空，至少有一個(gè)結(jié)點(diǎn)】全國計(jì)算機(jī)等級(jí)考試263、二叉樹的五種根本結(jié)構(gòu)：aaabcbab空二叉樹只有一個(gè)結(jié)點(diǎn)的二叉樹有兩個(gè)結(jié)點(diǎn)的二叉樹有三個(gè)結(jié)點(diǎn)的二叉樹全國計(jì)算機(jī)等級(jí)考試274、滿二叉樹和完全二叉樹：A.滿二叉樹：二叉樹的每一層均具備該層最大結(jié)點(diǎn)個(gè)數(shù)?！布矗翰痪邆涠葹?的結(jié)點(diǎn)〕B.完全二叉樹：滿二叉樹是一個(gè)特殊的完全二叉樹。將所有結(jié)點(diǎn)自上向下、自左向右編號(hào)，結(jié)點(diǎn)編號(hào)連續(xù)而不缺失。xeoqkbgxeoqkb滿二叉樹完全二叉樹123456全國計(jì)算機(jī)等級(jí)考試285、二叉樹的計(jì)算：A.二叉樹第n層的最大結(jié)點(diǎn)個(gè)數(shù)：2n-1。B.n層滿二叉樹的結(jié)點(diǎn)個(gè)數(shù)：2n-1。C.n層完全二叉樹的最小結(jié)點(diǎn)個(gè)數(shù)：2n-1。n層完全二叉樹的最大結(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ì)于任意二叉樹都有：n0=n2+1。E.結(jié)點(diǎn)編號(hào)：任意結(jié)點(diǎn)編號(hào)n，其左孩子為2n，其右孩子為2n+1。xeoqkbg1234567全國計(jì)算機(jī)等級(jí)考試29填空題：設(shè)一棵完全二叉樹共有700個(gè)結(jié)點(diǎn)，那么在該二叉樹中有個(gè)葉子結(jié)點(diǎn)二叉樹的結(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ù)二叉樹性質(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完全二叉樹總結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)，那么度為1的結(jié)點(diǎn)個(gè)數(shù)為1；完全二叉樹的總結(jié)點(diǎn)個(gè)數(shù)為奇數(shù)，那么度為1的結(jié)點(diǎn)個(gè)數(shù)為0。所以：2n0=701-1，即n0=350。全國計(jì)算機(jī)等級(jí)考試306、二叉樹的遍歷：A.前/先〔根〕序遍歷，GLR?！靖?jié)點(diǎn)為序列開頭】B.中〔根〕序遍歷，LGR。【沒有左子樹，根節(jié)點(diǎn)為開頭；沒有右子樹，根節(jié)點(diǎn)為結(jié)尾】【左右子樹均有，根節(jié)點(diǎn)的位置位于左子樹結(jié)點(diǎn)個(gè)數(shù)之和+1】C.后〔根〕序遍歷，LRG?！靖?jié)點(diǎn)為序列結(jié)尾】xeoqbg先序序列：xeqbog中序序列：qebxog后序序列：qbegox全國計(jì)算機(jī)等級(jí)考試31第二章程序設(shè)計(jì)根底全國計(jì)算機(jī)等級(jí)考試32本章知識(shí)要點(diǎn)面向過程的程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)模塊化程序設(shè)計(jì)面向?qū)ο蟮某绦蛟O(shè)計(jì)對(duì)象的定義對(duì)象的屬性和方法類和實(shí)例的派生與繼承消息與多態(tài)性全國計(jì)算機(jī)等級(jí)考試33一、程序設(shè)計(jì)方法1、面向過程的程序設(shè)計(jì)：C語言、BASIC語言等?！?〕結(jié)構(gòu)化程序設(shè)計(jì)：順序、選擇、循環(huán)。三大結(jié)構(gòu)〔順序、選擇、循環(huán)〕可以解決所有的問題，和問題的規(guī)模沒有關(guān)系?！?〕模塊化程序設(shè)計(jì)：利用將程序分解的方法，將復(fù)雜的問題簡單化，將單一的問題分成多個(gè)模塊獨(dú)立解決。C語言：模塊就是函數(shù)。VB語言：模塊就是模塊、子例程、子程序。VFP數(shù)據(jù)庫：模塊就是子程序。Access數(shù)據(jù)庫：模塊就是宏、事件代碼。2、面向?qū)ο蟮某绦蛟O(shè)計(jì)：VB、VFP、Java、Delphi等。全國計(jì)算機(jī)等級(jí)考試34二、程序設(shè)計(jì)風(fēng)格1.源程序文檔化選擇標(biāo)示符的名字注釋〔序言性和功能性注釋〕程序的視覺組織2.數(shù)據(jù)說明的方法顯式地說明一切變量數(shù)據(jù)說明的次序應(yīng)該標(biāo)準(zhǔn)化說明語句中變量安排有序化對(duì)復(fù)雜數(shù)據(jù)結(jié)構(gòu)應(yīng)注釋說明3.語句的結(jié)構(gòu)每條語句簡單明了盡量不用或少用GOTO語句盡量只采用3種根本控制結(jié)構(gòu)編程4.輸入和輸出對(duì)輸入數(shù)據(jù)進(jìn)行校驗(yàn)和合理性檢查輸入輸出格式保持一致設(shè)計(jì)良好的輸出報(bào)表全國計(jì)算機(jī)等級(jí)考試35三、結(jié)構(gòu)化程序設(shè)計(jì)20世紀(jì)70年代提出了結(jié)構(gòu)化程序設(shè)計(jì)

〔StructuredProgramming〕結(jié)構(gòu)化程序設(shè)計(jì)的原那么：〔1〕自頂向下。〔2〕逐步求精?！?〕模塊化。〔4〕限制使用goto語句。結(jié)構(gòu)化程序設(shè)計(jì)的根本結(jié)構(gòu)：〔1〕順序結(jié)構(gòu)。〔2〕選擇結(jié)構(gòu)?！?〕重復(fù)結(jié)構(gòu)。結(jié)構(gòu)化程序設(shè)計(jì)主要強(qiáng)調(diào)程序的易讀性。全國計(jì)算機(jī)等級(jí)考試36利用圖示表示順序結(jié)構(gòu)ABAB程序流程圖N-S圖全國計(jì)算機(jī)等級(jí)考試37利用圖示表示選擇結(jié)構(gòu)條件滿足不滿足AB程序流程圖N-S圖AB條件滿足不滿足全國計(jì)算機(jī)等級(jí)考試38利用圖示表示重復(fù)結(jié)構(gòu)(1)條件滿足不滿足S條件滿足不滿足S程序流程圖當(dāng)型循環(huán)程序流程圖直到型循環(huán)全國計(jì)算機(jī)等級(jí)考試39利用圖示表示重復(fù)結(jié)構(gòu)(2)WHILE條件SSUNTIL條件N-S圖當(dāng)型循環(huán)N-S圖直到型循環(huán)全國計(jì)算機(jī)等級(jí)考試40三、面向?qū)ο蟮某绦蛟O(shè)計(jì)面向?qū)ο?ObjectOriented)的程序設(shè)計(jì)方法已經(jīng)開展成為主流的軟件開發(fā)方法，起源于對(duì)面向?qū)ο笳Z言的研究。20世紀(jì)60年代后期首次被提出，80年代開始走向?qū)嵱?。面向?qū)ο蟮某绦蛟O(shè)計(jì)的術(shù)語：對(duì)象、屬性、方法、封裝性、事件、類、父類、子類、實(shí)例、派生、繼承、消息、多態(tài)性。全國計(jì)算機(jī)等級(jí)考試41面向?qū)ο蠓椒ǖ闹饕獌?yōu)點(diǎn)：〔1〕與人類習(xí)慣的思維方法一致?！?〕穩(wěn)定性好?！?〕可重用性好?！?〕易于開發(fā)大型軟件產(chǎn)品。〔5〕可維護(hù)性好。全國計(jì)算機(jī)等級(jí)考試421、對(duì)象的定義對(duì)象：現(xiàn)實(shí)生活中存在的可以相互區(qū)分的物體。是屬性和方法的封裝。對(duì)象的根本特點(diǎn)：〔1〕標(biāo)識(shí)唯一性?！?〕分類型?！?〕多態(tài)性?！?〕封裝性。〔5〕模塊獨(dú)立型好。全國計(jì)算機(jī)等級(jí)考試432、對(duì)象的屬性和方法屬性〔Property〕：用來描述對(duì)象的狀態(tài)，是對(duì)象的靜態(tài)特性。包括屬性名和屬性值兩方面。例如：“顯示器”作為對(duì)象，具備“顏色”屬性，取值為“銀白色”。方法〔Method〕：用來描述對(duì)象的行為，是對(duì)象的動(dòng)態(tài)特性。方法具備方法名。方法必須利用事件來激活。例如:“顯示器”作為對(duì)象，具備“關(guān)閉”的方法，必須用“斷電”事件來激活。屬性名屬性值方法名事件封裝性：(Encapsulation)對(duì)象依靠對(duì)象名將自身的屬性和方法封裝。全國計(jì)算機(jī)等級(jí)考試443、類和實(shí)例的派生與繼承〔1〕類〔Class〕：具有相同屬性和方法的對(duì)象的集合，是對(duì)對(duì)象屬性和方法的抽象?！?〕實(shí)例〔Instances〕：類的子類派生出的對(duì)象就是該類的一個(gè)實(shí)例。類展現(xiàn)對(duì)象的共性；實(shí)例展現(xiàn)對(duì)象的個(gè)性?！?〕派生過程中將發(fā)生屬性和方法的繼承〔Inheritance〕父類將自身的所有屬性和方法傳遞給子類，子類繼承父類傳遞的所有屬性和方法，并產(chǎn)生自身特有的屬性和方法，再將這些屬性和方法的總和傳遞給下一級(jí)子類。人好人壞人中國人外國人張三全國計(jì)算機(jī)等級(jí)考試454、消息與多態(tài)性〔1〕消息〔Message〕：進(jìn)行對(duì)象之間的信息傳遞?！?〕多態(tài)性〔Polymorphism〕：同樣的消息傳遞給不同的對(duì)象，導(dǎo)致完全不同的行動(dòng)。消息的組成：A.接收消息的對(duì)象名稱。B.消息標(biāo)識(shí)符，也叫做“消息名”。C.零個(gè)或多個(gè)參數(shù)。全國計(jì)算機(jī)等級(jí)考試46第三章軟件工程基礎(chǔ)軟件（Software）=程序+文檔全國計(jì)算機(jī)等級(jí)考試47本章知識(shí)要點(diǎn)軟件危機(jī)軟件生命周期需求分析概要設(shè)計(jì)詳細(xì)設(shè)計(jì)測試調(diào)試軟件工程全國計(jì)算機(jī)等級(jí)考試48一、軟件危機(jī)軟件危機(jī)主要表現(xiàn)在：〔1〕軟件需求的增長得不到滿足?！?〕軟件開發(fā)本錢和進(jìn)度無法控制。〔3〕軟件質(zhì)量難以保證。〔4〕軟件不可維護(hù)或可維護(hù)度非常低?！?〕軟件的本錢不斷提高?！?〕軟件開發(fā)生產(chǎn)率的提高趕不上硬件的開展和應(yīng)用需求的增長?？傊?，可以將軟件危機(jī)歸結(jié)為本錢、質(zhì)量、生產(chǎn)率問題全國計(jì)算機(jī)等級(jí)考試49二、軟件工程軟件工程是為了擺脫軟件危機(jī)而誕生的，主要思想是在軟件開發(fā)過程中應(yīng)用工程化原那么。軟件工程的三要素：方法、工具、工程。軟件工程的主要內(nèi)容：軟件開發(fā)技術(shù)、軟件工程管理。軟件工程的原那么：〔1〕抽象?！?〕信息隱蔽?！?〕模塊化?！?〕局部化。〔5〕確定性?！?〕一致性?！?〕完備性?！?〕可驗(yàn)證性。全國計(jì)算機(jī)等級(jí)考試50二、軟件生命周期軟件生命周期〔SoftwareLifeCycle，SLC〕：將軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過程稱為“軟件生命周期”?？尚行匝芯啃枨蠓治龈乓O(shè)計(jì)詳細(xì)設(shè)計(jì)實(shí)現(xiàn)測試使用退役維護(hù)定義階段開發(fā)階段維護(hù)階段全國計(jì)算機(jī)等級(jí)考試51軟件工程步驟用到的方法用到的工具生成的文檔需求分析結(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ī)等級(jí)考試52三、需求分析需求與需求分析需求分析的方法結(jié)構(gòu)化分析方法數(shù)據(jù)流圖與數(shù)據(jù)字典判定樹與判定表軟件需求規(guī)格說明書全國計(jì)算機(jī)等級(jí)考試531、需求與需求分析需求：用戶對(duì)目標(biāo)軟件系統(tǒng)在功能、行為、性能、設(shè)計(jì)約束等方面的期望。需求分析：發(fā)現(xiàn)用戶需求的過程需求分析階段的工作：〔1〕需求獲取〔2〕需求分析〔3〕編寫需求規(guī)格說明書〔4〕需求評(píng)審全國計(jì)算機(jī)等級(jí)考試542、需求分析的方法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ū)ο蟮姆治龇椒∣OA。全國計(jì)算機(jī)等級(jí)考試553、結(jié)構(gòu)化分析方法：數(shù)據(jù)流圖DFD數(shù)據(jù)流圖DFD中的主要圖形元素：加工/轉(zhuǎn)換數(shù)據(jù)流存儲(chǔ)文件/數(shù)據(jù)源源/潭全國計(jì)算機(jī)等級(jí)考試56結(jié)構(gòu)化分析方法：數(shù)據(jù)字典DD數(shù)據(jù)字典DD是結(jié)構(gòu)化分析方法的核心。數(shù)據(jù)字典的作用：對(duì)數(shù)據(jù)流圖DFD中出現(xiàn)的被命名圖形元素進(jìn)行確切的解釋。全國計(jì)算機(jī)等級(jí)考試57結(jié)構(gòu)化分析方法：判定樹與判定表判定樹

條件1

條件2

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

訂票量>20:

15%算12月

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

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

訂票量<=20:5%全國計(jì)算機(jī)等級(jí)考試58判定表旅游時(shí)間7月—9月，12月1月—6月，10月，11月訂票量>20%<=20%>20%<=20%折扣率15%5%30%20%全國計(jì)算機(jī)等級(jí)考試59結(jié)構(gòu)化分析方法：需求規(guī)格說明書軟件需求規(guī)格說明書〔SRS〕是需求分析階段的最后成果，將在軟件工程的最后轉(zhuǎn)換為用戶手冊。軟件需求規(guī)格說明書的作用：〔1〕便于用戶、開發(fā)人員進(jìn)行理解和交流?！?〕反映出用戶問題的結(jié)構(gòu)，可作為軟件開發(fā)工作的根底和依據(jù)?！?〕作為確認(rèn)測試和驗(yàn)收的依據(jù)。全國計(jì)算機(jī)等級(jí)考試60四、概要設(shè)計(jì)軟件設(shè)計(jì)的根本原理：〔1〕抽象：把事物本質(zhì)的共同特性提取出來而不考慮細(xì)節(jié)?！?〕模塊化：把待開發(fā)軟件分解成假設(shè)干個(gè)小的簡單局部?！?〕信息隱蔽：在一個(gè)模塊內(nèi)包含的信息，對(duì)于不需要這些信息的其他模塊來說是不能訪問的?！?〕模塊獨(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)聚，低耦合。全國計(jì)算機(jī)等級(jí)考試61概要設(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)系全國計(jì)算機(jī)等級(jí)考試62認(rèn)識(shí)軟件結(jié)構(gòu)圖SC深度=3寬度=3上級(jí)模塊從屬模塊原子模塊扇入扇出全國計(jì)算機(jī)等級(jí)考試63五、詳細(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圖、問題分析圖PAD

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