二級公共基礎(chǔ)知識

1、二級公共根底知識一、數(shù)據(jù)結(jié)構(gòu)與算法 考點提示：1. 算法的根本概念；算法復雜度的概念和意義時間復雜度與空間復雜度。2. 數(shù)據(jù)結(jié)構(gòu)的定義；數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)的圖形表示；線性結(jié)構(gòu)與非線 性結(jié)構(gòu)的概念。3. 線性表的定義；線性表的順序存儲結(jié)構(gòu)及其插入與刪除運算。4. 棧和隊列的定義；棧和隊列的順序存儲結(jié)構(gòu)及其根本運算。5. 線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其根本運算。6. 樹的根本概念；二叉樹的定義及其存儲結(jié)構(gòu)；二叉樹的前序、中序和后序遍歷。 7順序查找與二分法查找算法；根本排序算法交換類排序，選擇類排序，插入類排序1.1 算法 算法：是指解題方案的準確而完整的描述。? 算法不

2、等于程序，也不等于計算方法；算法是解題思路，而程序是解題思路的在其 編譯環(huán)境中的具體描述。算法的特征：1可行性：在具體環(huán)境中可執(zhí)行和正確與否2確定性：每一步必須有明確的定義3有窮性：在有限步驟時間內(nèi)執(zhí)行完畢4擁有足夠的情報：初始數(shù)據(jù)或初始狀態(tài)必須要充足且正確。 算法的根本要素：一是對數(shù)據(jù)對象的運算和操作四類二是算法的控制結(jié)構(gòu)各操作之間的執(zhí)行順序。根本運算和操作包括：算術(shù)運算、邏輯運算、關(guān)系運算、數(shù)據(jù)傳輸。 算法的控制結(jié)構(gòu)：順序、選擇、循環(huán)。算法設(shè)計的根本方法：列舉法、歸納法、遞推、遞歸、減半遞推技術(shù)、回溯法。 算法復雜度：算法時間復雜度和算法空間復雜度。算法時間復雜度：是指執(zhí)行算法所需要的計算

3、工作量運算的執(zhí)行次數(shù)。? 衡量算法時間復雜度的主要因素： 一方面依賴于問題的規(guī)模，如N x N矩陣乘法運算，fn=0n3另一方面，某些情況下還和問題的輸入數(shù)據(jù)集有關(guān)如冒泡排序，此時用兩種方法分析：P(x)t(x)x Dn1 平均性態(tài)：用根本運算次數(shù)的加權(quán)平均值來衡量-An二2最壞情況復雜性：最大執(zhí)行次數(shù)-W n= maxtxx Dn算法空間復雜度：是指執(zhí)行算法所占用的空間，包括算法程序所占用的空間、 輸入的初始數(shù)據(jù)所占用的空間、算法執(zhí)行過程中所需要的額外空間。算法設(shè)計的要求：1正確性 2可讀性 3健壯性4效率與低存儲量需求1.2 數(shù)據(jù)結(jié)構(gòu)的根本概念數(shù)據(jù)結(jié)構(gòu)：反映數(shù)據(jù)元素之間關(guān)系的表示。數(shù)據(jù)結(jié)構(gòu)

4、研究的三個方面 ：1各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；2各數(shù)據(jù)元素在計算機中的存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)； 3 對各種數(shù)據(jù)結(jié)構(gòu)進行的運算。數(shù)據(jù)的邏輯結(jié)構(gòu)：1表示數(shù)據(jù)元素的信息;2表示各數(shù)據(jù)元素之間的前后件關(guān)系。? 數(shù)據(jù)的邏輯結(jié)構(gòu)是個數(shù)據(jù)元素之間固有的，是與計算機硬件沒有關(guān)系的結(jié)構(gòu)數(shù)據(jù)邏輯結(jié)構(gòu)的四種形式：集數(shù)據(jù)存儲結(jié)構(gòu)：是指數(shù)據(jù)的邏 也稱數(shù)據(jù)的物理結(jié)構(gòu)。? 數(shù)據(jù)的物理結(jié)構(gòu)反映的是數(shù)據(jù)的存儲方法，這受到具體的物理存儲介質(zhì)制約。數(shù)據(jù)存儲結(jié)構(gòu)的三種形式：順序、鏈接、索引。? 一個數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素，其邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)不一定相同。數(shù)據(jù)結(jié)構(gòu)的表示：二元關(guān)系：例L5 年四季的數(shù)據(jù)結(jié)構(gòu)可以

5、表示成&= D R*春，夏，秋，冬R=春.夏夏，秋人秋，冬例13家庭成員數(shù)據(jù)結(jié)構(gòu)可以表示成D, RD二父親，兒子，女兒R=父親,兒子父親女兒圖形表示：圖1.2 -年四季數(shù)辭構(gòu)肘圖形圾示圖L3藐成躺輩分朋數(shù)觀溝船就示例h8用圖形表示數(shù)據(jù)結(jié)構(gòu)B=D, Rh其中D=djllWiW7卜伽亦 亦 dP dP d7M (dP d7)t (% S % 妙仙,ds)按前后件邏輯關(guān)系的復雜程度，將數(shù)據(jù)結(jié)構(gòu)分為兩類： 線性結(jié)構(gòu)線性表：1有且只有一個根結(jié)點；2每一個結(jié)點最多有一個前件，也最多有一個后件。? 在一個線性結(jié)構(gòu)中插入或刪除任何一個節(jié)點后還應該是線性結(jié)構(gòu)。圖1.5線性結(jié)構(gòu)特列非線性結(jié)構(gòu)：不滿足線性結(jié)

6、構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。? 線性結(jié)構(gòu)和非線性結(jié)構(gòu)都可以是空數(shù)據(jù)結(jié)構(gòu)，對于空數(shù)據(jù)結(jié)構(gòu)的運算是按線性結(jié)構(gòu)的規(guī)那么來處理的，那么屬于線性結(jié)構(gòu)；否那么屬于非線性結(jié)構(gòu)。1.3線性表及順序存儲結(jié)構(gòu)線性表：線性表是最常用且最簡單的一種線性數(shù)據(jù)結(jié)構(gòu)。簡言之，一個線性表是n個數(shù)據(jù)元素的有限序列。線性表有兩種存儲結(jié)構(gòu)(順序存儲和鏈式存儲)如26個英文字母的字母表(A,B,C,D,Z)是一個線性表，表中的數(shù)據(jù)元素是單個字母字符。數(shù)據(jù)元素的定義在不同情況下各不相同在復雜線性表中，一個數(shù)據(jù)元素可以由假設(shè)干個數(shù)據(jù)項(item)組成。在這種情況下，常把數(shù)據(jù)元素稱為記錄(record)，含有大量記錄的線性表又稱文件( file)

7、非空線性表的結(jié)構(gòu)特征：(1)有且只有一個根結(jié)點a1，它無前件；(2 )有且只有一個終端結(jié)點an，它無后件；(3 )除根結(jié)點與終端結(jié)點外，其他所有結(jié)點有且只有一個前件，也有且只有一個后件。結(jié)點個數(shù)n稱為線性表的長度，當 n=0時，稱為空表。 線性表的順序存儲結(jié)構(gòu)：指用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。 線性表的順序存儲結(jié)構(gòu)具有以下兩個根本特點：(1) 線性表中所有元素的所占的存儲空間是連續(xù)的；(2) 線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。ai 的存儲地址為： ADR(ai)=ADR(a1)+(i-1)k,，ADR(a1)為第一個元素的地址，k代表每個元素占的字節(jié)數(shù)。

8、可以看出，順序存儲是一種隨機存取的存儲結(jié)構(gòu)。只要知道某元素地址，其他任何元素地址都可以計算出來占k個字節(jié)占1c個字節(jié)占k個字節(jié)占k個字節(jié)存儲地址ADR(a|> ADR(a|>+kTADRCa.J+G-Dk*V圖仁& 絨性表的順序存儲結(jié)構(gòu)順序表的運算(時間復雜度)插入：在平均情況下，要插入一個兀素，需要移動表中一半的兀素。刪除：在平均情況下，要刪除一個元素，需要移動表中一半的元素。?線性表的順序存儲結(jié)構(gòu)對于小線性表或者其中元素不常變動的線性表來說是適宜的，而對于經(jīng)常需要變動的大線性表就不太適宜了，效率比擬低。線性表的順序存儲結(jié)構(gòu)，插入和刪除元素時需大量移動元素，故不便于插入和

9、刪除操作1.4棧：棧和隊列線性結(jié)構(gòu)是限定在一端進行插入與刪除的線性表，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧按照 先進后出FILO 或后進先出LIFO 組織數(shù)據(jù)，棧具有記憶作用。用top表示棧頂位置，用 bottom表示棧底。棧的根本運算：1插入元素稱為入棧運算；2刪除元素稱為退棧運算；3讀棧頂元素 是將棧頂元素還有初始化、置空、判斷棧是否為空或滿入棧 退棧桟頂cop 圖K9棧樂意團隊列：是指允許在一端隊尾進入插入，而在另一端隊頭進行刪除的線性表。Rear指針指向隊尾最后一個元素，front指針指向隊頭第一個元素的前面 。隊列是先進先出FIFO 或后進后出LILO

10、的線性表。隊列運算：1入隊運算：從隊尾插入一個元素；2退隊運算：從隊頭刪除一個元素。退仏亠ABC D E | F _入隊t1frontrear圖I.M具有勺個元素的隊列示意圖1.5線性鏈表由于順序存儲有一些缺點，某些情況我們需采用鏈式存儲結(jié)構(gòu)。鏈式結(jié)構(gòu)中的每一個數(shù)據(jù)結(jié)點對應于一個存儲單元，這種存儲單元稱為存儲結(jié)點，簡稱結(jié)點。結(jié)點由兩局部組成：1用于存儲數(shù)據(jù)元素值，稱為數(shù)據(jù)域；2用于存放指針，稱為指針域，指向前一個或后一個結(jié)點。線性鏈表：在定義的鏈表中，假設(shè)只含有一個指針域來存放下一個元素的地址，稱單鏈表或線性鏈表。HEADf 嫡HEAD查找：在線性鏈表中，即使知道被訪問結(jié)點的序號i，也不能像順

11、序存儲那樣直接按序號i訪問結(jié)點，而只能從鏈表的head出發(fā)，順指針域next逐個往下搜索，直到找到第i個結(jié)點為止。因此，鏈表不是隨機存取結(jié)構(gòu)，而是順序存取結(jié)構(gòu)。q->iwxt - p->next. p->next = q.插入:刪除:p->-next = p->next->next; p-next-> prior = p;上述線性鏈表雖然插入和刪除比擬方便，但對于空表和非空表的運算不統(tǒng)一，因此,引入另一種鏈接方式：循環(huán)鏈表。循環(huán)鏈表的兩個特點：i增加一個表頭結(jié)點，其數(shù)據(jù)域任意，指針域指向線性表的第一個 元素的結(jié)點，循環(huán)鏈表的頭指針指向表頭結(jié)點。2循環(huán)鏈

12、表最后一個結(jié)點的指針域不是NULL，而是指向表頭結(jié)點。這樣所有結(jié)點指針構(gòu)成 了 一個環(huán)狀鏈。? 這樣，只要給出表中任何一個結(jié)點的位置，就可以從他出發(fā)訪問到表中的其他結(jié)點,這是單鏈表做不到的；由于在循環(huán)鏈表中設(shè)置了一個表頭結(jié)點，因此，在任何情況 下，循環(huán)鏈表中至少有一個結(jié)點存在，從而使空表與非空表的運算統(tǒng)一。1.6 樹與二叉樹樹是一種簡單的非線性結(jié)構(gòu)，元素之間具有明顯的層次特性。在樹結(jié)構(gòu)中，每一個結(jié)點只有一個前件，稱為父結(jié)點，沒有前件的結(jié)點只有一個，稱為 樹的根結(jié)點，簡稱樹的根。每一個結(jié)點可以有多個后件，稱為該結(jié)點的子結(jié)點。沒有后 件的結(jié)點稱為葉子結(jié)點。在樹結(jié)構(gòu)中，一個結(jié)點所擁有的后件的個數(shù)稱為

13、該結(jié)點的度，所有結(jié)點中最大的度稱為 樹的度。樹的最大層次稱為樹的深度。(1) 樹所有結(jié)點的度之和比結(jié)點總數(shù)小1(2) 樹所有結(jié)點的度之和與邊的條數(shù)之和相等二叉樹的特點：1非空二叉樹只有一個根結(jié)點；2每一個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹與右子樹。e糜應天h的二又擁圖V31 二叉樽例二叉樹的五種形態(tài)：空樹只有根節(jié)點只有左子樹只有右子樹二叉樹的根本性質(zhì)：1在二叉樹的第 k層上，最多有2k-1k > 1個結(jié)點；求單層最多節(jié)點數(shù)2深度為m的二叉樹最多有2m-1個結(jié)點；求樹的最多結(jié)點總數(shù)3 度為0的結(jié)點即葉子結(jié)點總是比度為2的結(jié)點多一個；n0=n2+1常用于求某個度 的結(jié)點數(shù)4 具有n

14、個結(jié)點的二叉樹，其深度至少為intlog2n+1 二叉樹的最小深度滿二叉樹：一顆深度為k且有2k-1個結(jié)點的二叉樹稱為滿二叉樹可見，滿二叉樹結(jié)點總數(shù)一定是奇數(shù)完全二叉樹：深度為k的，有n個結(jié)點的二叉樹，當且僅當其每一個結(jié)點都與深度為k的滿二叉樹中編號從1至n的結(jié)點對應5具有n個結(jié)點的完全二叉樹的深度為Iog2n+1或Iog2 n+1;求完全二叉樹的深度6設(shè)完全二叉樹共有 n個結(jié)點。如果從根結(jié)點開始，按層序每一層從左到右用自然 數(shù)1, 2,.n給結(jié)點進行編號k=1,2.n，有以下結(jié)論：用于確定某個點的位置 假設(shè)k=1 ,那么該結(jié)點為根結(jié)點，它沒有父結(jié)點；假設(shè)k>1，那么該結(jié)點的父結(jié)點編號為

15、INTk/2;常用于確定父節(jié)點總數(shù) 假設(shè)2k< n,那么編號為k的結(jié)點的左子結(jié)點編號為 2k;否那么該結(jié)點無左子結(jié)點 也無右子結(jié) 點； 假設(shè)2k+1 <n,那么編號為k的結(jié)點的右子結(jié)點編號為2k+1 ;否那么該結(jié)點無右子結(jié)點。中:IDJBKEAFCG二叉樹存儲結(jié)構(gòu)常采用鏈式存儲結(jié)構(gòu)，對于滿二叉樹與完全二叉樹可以按層序進行順序存儲。 二叉樹的遍歷按某種次序，訪問二叉樹中的所有結(jié)點，使得每個結(jié)點僅被訪問一次1前序根遍歷DLR ,首先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹；2中序根遍歷LDR ,首先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹；3后序根遍歷LRD ,首先遍歷左子樹，然后

16、訪問遍歷右子樹，最后訪問根結(jié)點。 ? 注意，遍歷時子樹也要遵循遍歷規(guī)那么。刖：ABDIJEKCFG后:IJDKEBFGCA? 規(guī)律：前序遍歷第一個節(jié)點是樹的根， 后續(xù)遍歷最后一個節(jié)點是樹的根。1.7查找技術(shù)順序查找：從表的一端開始，順序掃描線性表只能使用順序查找的情況：1 線性表為無序表不管是順序存儲還是鏈式存儲 2表采用鏈式存儲結(jié)構(gòu)即使是有序存儲。最壞情況需要比擬 n次 二分查找：把表不斷折半，和中值比擬*只適用于順序存儲的有序表對于長度為 n 的有序線性表，最壞情況只需比擬 log2n 次1.8 排序技術(shù)交換類排序法： 1冒泡排序法，最壞需要比擬的次數(shù)為 nn-1/2 。2快速排序法 ,最

17、壞需要比擬的次數(shù)為 n2 插入類排序法： 1簡單插入排序法，最壞需要比擬的次數(shù)為nn-1/2 。2希爾排序法 ,最壞需要比擬的次數(shù)為 n1.5 選擇類排序法： 1簡單項選擇擇排序法，最壞需要比擬的次數(shù)為nn-1/2 。2堆排序法，最壞情況需要 nlog2n 次比擬 。二、程序設(shè)計根底1. 形成良好的程序設(shè)計風格應注意的因素2. 結(jié)構(gòu)化程序設(shè)計的主要原那么3. 結(jié)構(gòu)化程序的根本結(jié)構(gòu)與特點4. 結(jié)構(gòu)化程序設(shè)計的原那么和方法的應用5. 面向?qū)ο蟪绦蛟O(shè)計的主要優(yōu)點6. 面向?qū)ο蠓椒ǖ母靖拍顚ο?、類和實例、消息、繼承和多態(tài)性 注意區(qū)分：結(jié)構(gòu)化程序設(shè)計和面向?qū)ο蟪绦蛟O(shè)計本章學習方法 ：這兩章以概述的形式

18、簡介了標準化開發(fā)軟件的方法。與數(shù)據(jù)結(jié)構(gòu)不同，這 兩章內(nèi)容主要是記憶性的知識點。程序設(shè)計根底的內(nèi)容與大綱改革前添加了面向?qū)ο蟪绦?設(shè)計的內(nèi)容，大家可以對本章進行幾次細讀后了解即可；軟件工程根底這章主要考核內(nèi)容 為結(jié)構(gòu)化分析及結(jié)構(gòu)化設(shè)計方法即SA及SD,約占50% ,信息量較大，其次是軟件測試約占 20% ，考生需要將相關(guān)的概念及規(guī)那么背誦，在以后有時機進行程序開發(fā)時這些知 識可以得到深刻理解。2.1 程序設(shè)計方法與風格 當今主導程序設(shè)計風格： “清晰第一，效率第二 良好的程序設(shè)計風格應注意的因素：1、源程序文檔化；? 符號命名要有規(guī)那么? 正確的注釋：注釋分序言性注釋和功能性注釋? 視覺組織2、

19、數(shù)據(jù)說明的方法；3、語句的結(jié)構(gòu)；4、輸入和輸出。I料-趕序說明；系藥英單設(shè)置*-程序功能：動憩顯茅一半棗統(tǒng)動態(tài)菓用*扁寫日期:原創(chuàng)作看：ldtf自由表結(jié)構(gòu)說明：停段寬度沒有嚴格要求"可以隨實際盾況吏動席 Key n 日* Pat ent n B寬 Ms 電c. 30羋 Command c 00水 i.ec 七 1* QuitkE呼 =10* btn_Naine :10J決宦是隱議不可用功能，還是DHAELED=*=-亢.吋j隱栽j為一 F.吋 > 不ttf用define HisHiddeilFiinc . FLOCAL lnMennKey, lcMeiiuNanift lcDe

20、EineMertu, lcSubliarMenulIajne, IcShortCntKey lcCoi料-創(chuàng)逹秤臨時表-諧函數(shù)在本過程文件中2.2結(jié)構(gòu)化程序設(shè)計結(jié)構(gòu)化程序設(shè)計方法的四條原那么是：1.自頂向下；2.逐步求精；3模塊化；4限制使用goto語句。結(jié)構(gòu)化程序的根本結(jié)構(gòu)和特點：1順序結(jié)構(gòu)：按照語句的自然順序，一條一條的執(zhí)行；2選擇結(jié)構(gòu)：又稱分支結(jié)構(gòu)，包括簡單項選擇擇和多分支選擇結(jié)構(gòu)，可根據(jù)條件，判斷應該 選擇哪一條分支來執(zhí)行相應的語句序列；3 重復結(jié)構(gòu)：又稱循環(huán)結(jié)構(gòu)，可根據(jù)給定條件，判斷是否需要重復執(zhí)行某一相同程序段。 包括直到型循環(huán)和當型循環(huán)。結(jié)構(gòu)化程序設(shè)計原那么和方法的應用L使用程序

21、設(shè)計語言中的順序、選擇.循環(huán)等冇限的控制給構(gòu)表示甘序的控制邏輯;2.選用的控制結(jié)構(gòu)只準許有一個入口和一個出口；M程庫i吾句址臉容易識別的塊.毎塊只仃 個入口和一個出口：4-區(qū)雜結(jié)構(gòu)應該用嵌龔的基木控制結(jié)構(gòu)進行組合嵌全來買現(xiàn)：久語宕中斯徨有的輕制結(jié)構(gòu).應該釆用前后一致的方法來棋擬； 氐嚴格控制GOTO語句的使用。藥意思是擠1用個非緒構(gòu)化的觀序設(shè)計語育去實現(xiàn)一牛結(jié)構(gòu)化的構(gòu)造】2假設(shè)不便用GOTO語旬會使功能模勵；3在某種可以改善而不是損害理洋可讀性的情況下.雖然結(jié)構(gòu)化程序設(shè)計方法有很多優(yōu)點，但它仍是一種面向過程的設(shè)計方法。缺點：:它把數(shù)據(jù)和處理數(shù)據(jù)的過程別離為相互獨立的實體，當數(shù)據(jù)結(jié)構(gòu)改變時，所有

22、相關(guān)的處理過程的都要進行相應的修改，程序的可重用性差。2.3面向?qū)ο蟮某绦蛟O(shè)計傳統(tǒng)的程序設(shè)計方法是面向過程的也就是面向過程的程序設(shè)計，其核心方法是以算法為核心。面向?qū)ο蠓椒ê图夹g(shù)以對象為核心。對象是由數(shù)據(jù)和容許的操作組成的封裝體，與客觀實體有直接的對應關(guān)系。對象之間通過傳遞消息互相聯(lián)系， 以模擬現(xiàn)實世界中不同事物 彼此之間的聯(lián)系。面向?qū)ο蠓椒ǖ膬?yōu)點：1 與人類習慣的思維方法一致；2穩(wěn)定性好；3可重用性好；4易于開發(fā)大型軟件產(chǎn)品；5可維護性好。* 面向?qū)ο蟮哪Ｐ椭?，最根本的概念是對象和類。對象是面向?qū)ο蠓椒ㄖ凶罡镜母拍?，可以用來表示客觀世界中的任何實體，對象是現(xiàn)實世界實體的抽象。面向?qū)ο蟮某绦?/p>

23、設(shè)計方法中的對象是系統(tǒng)中用來描述客觀事物的一個實體， 是構(gòu)成系統(tǒng)的一個根本單位，由一組表示其靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成。屬性即對象所包含的特征信息，描述對象的狀態(tài) 操作描述了對象執(zhí)行的功能，操作也稱為方法或效勞。對象的根本特點：1標識惟一性：對象是可以互相區(qū)分的2分類性：將具有相同屬性和操作的對象抽象成類3 多態(tài)性：同一個操作可以是不同對象的行為4 封裝性：從外面看只能看到對象的外部特征，而不知道也無需知道數(shù)據(jù)的具體結(jié)構(gòu)以 及實現(xiàn)操作的算法。封裝性實現(xiàn)了信息的隱蔽，保證對象不受外部的破壞和干擾。5模塊獨立性：對象是一個封裝體。信息的隱蔽使模塊通過有限的接口傳遞消息，降低 了模塊的耦

24、合。類是指具有共同屬性、 共同方法的對象的集合。 所以類是對象的抽象， 對象是對應類的一個 實例。消息是一個實例與另一個實例之間傳遞的信息。消息的組成包括：1接收消息的對象的名稱誰；2消息標識符，也稱消息名做；3 零個或多個參數(shù)什么。対錄 0： 口Commandl過程電：ClickThisform. text 1. value= "ok" Thisform. backcolor=rgb 255255, 0 繼承是指能夠直接獲得已有的性質(zhì)和特征，而不必重復定義他們。是類之間共享屬性和操作的機制提高可重用性，減少冗余繼承分單繼承改進和多重繼承嫁接 。單繼承指一個類只允許有一個父

25、類，多重繼承 指一個類允許有多個父類。三、軟件工程根底1. 軟件工程根本概念，軟件生命周期概念，軟件工具與軟件開發(fā)環(huán)境。2. 結(jié)構(gòu)化分析方法，數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說明書。3. 結(jié)構(gòu)化設(shè)計方法，總體設(shè)計與詳細設(shè)計。4. 軟件測試的方法，白盒測試與黑盒測試，測試用例設(shè)計，軟件測試的實施，單元測試、 集成測試和系統(tǒng)測試。5. 程序的調(diào)試，靜態(tài)調(diào)試與動態(tài)調(diào)試。3.1軟件工程的根本概念計算機軟件是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。軟件的特點包括：1軟件是一種邏輯實體;2 軟件的生產(chǎn)與硬件不同，它沒有明顯的制作過程；3軟件在運行、使用期間不存在磨損、老化問題；4軟件的開發(fā)、運行對計算機系統(tǒng)具

26、有依賴性，受計算機系統(tǒng)的限制，這導致了軟件移 植的問題；5軟件復雜性高，本錢昂貴；6軟件開發(fā)涉及諸多的社會因素。軟件按功能分為應用軟件、系統(tǒng)軟件、支撐軟件或工具軟件。軟件生產(chǎn)的開展：1程序設(shè)計時代2程序系統(tǒng)時代3軟件工程時代 軟件危機： 軟件需求的增長得不到滿足 軟件開發(fā)本錢和進度無法控制 軟件質(zhì)量難以保證 軟件不可維護或維護程度非常低 軟件本錢不斷提高 軟件開發(fā)生產(chǎn)效率的提高趕不上硬件的開展和應用需求的增長總之，軟件危機可以歸結(jié)為本錢、質(zhì)量和生產(chǎn)率等問題軟件工程是應用于計算機軟件的定義、開發(fā)和維護的一整套方法、工具、文檔、實踐標準和工序。軟件工程包括3個要素：方法、工具和過程。軟件工程過程是

27、把軟件轉(zhuǎn)化為輸出的一組彼此相關(guān)的資源和活動，包含4種根本活動：1 P軟件規(guī)格說明；2 D 軟件開發(fā)；3 C軟件確認；4 A 軟件演進。軟件生命周期：軟件產(chǎn)品從提出、實現(xiàn)、使用維護到停止使用退役的過程。軟件生命周期三個階段：軟件定義、軟件開發(fā)、運行維護時間最長，主要活動階段包括：可行性研究和方案制定，需求分析，軟件設(shè)計，軟件實現(xiàn)，軟件測試，運行和維護軟件生命周期的主要活動階段為：1可行性研究和方案制定。 確定待開發(fā)軟件系統(tǒng)的開發(fā)目標和總的要求，給出它在功能、性能、可靠性以及接口等方面的可能方案，制定完成開發(fā)任務(wù)的實施方案。2需求分析。對待開發(fā)軟件提出的需求進行分析并給出詳細定義，即準確地確定軟件

28、 系統(tǒng)的功能。編寫軟件規(guī)格說明書及初步的用戶手冊，提交評審。3軟件設(shè)計。系統(tǒng)設(shè)計人員和程序設(shè)計人員應該在反復理解軟件需求的根底上，給出 軟件的結(jié)構(gòu)、模塊的劃分、功能的分配以及處理流程。4軟件實現(xiàn)。把軟件設(shè)計轉(zhuǎn)換成計算機可以接受的程序代碼。即完成源程序的編碼， 編寫用戶手冊、操作手冊等面向用戶的文檔，編寫單元測試方案。5軟件測試。在設(shè)計測試用例的根底上，檢驗軟件的各個組成局部。編寫測試分析報 告。6運行和維護。將已交付的軟件投入運行，并在運行使用中不斷地維護，根據(jù)新提出 的需求進行必要而且可能的擴充和刪改?？尚行猿x亢 胡步硒甘勅L義111-1T詳牢® tl開程女3E!開V-測試|11|

29、注闈|1 14|Ht護+Itats1関3軟件生命周期? 其中，可行性研究的目的就是用最小的代價確定在問題定義階段確定的目標是否實 現(xiàn)。可行性內(nèi)容包括經(jīng)濟可行性研究、技術(shù)可行性研究、法律可行性研究、開發(fā)方 案的選擇性研究。? 軟件設(shè)計階段根據(jù)復雜程度可分為概要設(shè)計和詳細設(shè)計兩個階段。? 整個軟件生命周期中，最長的階段就是使用維護階段 軟件工程的目標和與原那么：目標：在給定本錢、進度的前提下，開發(fā)出具有有效性、可靠性、可理解性、可維護性、可 重用性、可適應性、可移植性、可追蹤性和可互操作性且滿足用戶需求的產(chǎn)品。原那么：抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗證性。 軟件開發(fā)工具

30、：協(xié)助開發(fā)人員進行開發(fā)所使用的軟件。軟件開發(fā)環(huán)境：全面支持軟件開發(fā)全過程的軟件工具集合，由軟件工具機制和環(huán)境集成機制構(gòu)成。3.2結(jié)構(gòu)化分析方法? 需求分析是指用戶對目標軟件系統(tǒng)在功能、行為、性能、設(shè)計約束等方面的期望， 需求分析的任務(wù)是發(fā)現(xiàn)需求、求精、建模和定義需求的過程。需求分析將建立所需 的數(shù)據(jù)模型、功能模型和控制模型? 需求分析階段的4個方面工作：需求獲取、需求分析、編寫需求規(guī)格說明書、需求評審? 常見的需求分析方法有：1結(jié)構(gòu)化需求分析方法：主要有面向數(shù)據(jù)流的結(jié)構(gòu)化分 析方法、面向數(shù)據(jù)結(jié)構(gòu)的jacks on方法和面向數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)化數(shù)據(jù)系統(tǒng)開發(fā)方法2面向?qū)ο蟮姆治龅姆椒ā＝Y(jié)構(gòu)化分析方法的

31、實質(zhì)：著眼于數(shù)據(jù)流，自頂向下，逐層分解，建立系統(tǒng)的處理流程，以數(shù) 據(jù)流圖和數(shù)據(jù)字典為主要工具，建立系統(tǒng)的邏輯模型。結(jié)構(gòu)化分析的常用工具1數(shù)據(jù)流圖；2數(shù)據(jù)字典；3 判定樹；4判定表。數(shù)據(jù)流圖DFD ：描述數(shù)據(jù)處理過程的工具，它以圖形的方式描繪數(shù)據(jù)在系統(tǒng)中流動和處 理的過程，它只反響系統(tǒng)必須完成的邏輯功能，所以是一種功能模型。0加工耕林縣帥工娥產(chǎn)錨航二 肄蟒贈沆表藏理詫中存骼柵馳丈他 I |亂此縣貯將實他存折棄護JSL金1 敗尸1 U 府、z年月R 圖5,4 很荷戦歐業(yè)務(wù)的數(shù)BE疏1料數(shù)據(jù)字典DD :對DD中所有與系統(tǒng)相關(guān)的數(shù)據(jù)元素的一個有組織的列表，以及精確的、 嚴格的定義，使得用戶和系統(tǒng)分析員

32、對于輸入、輸出、存儲成分和中間計算結(jié)果有共同的理解。數(shù)據(jù)字典是結(jié)構(gòu)化分析的核心。數(shù)據(jù)流圖和數(shù)據(jù)字典共同組成系統(tǒng)的邏輯模型。軟件需求規(guī)格說明書的作用：1、便于用戶、開發(fā)人員進行理解和交流。2、作為軟件開發(fā)工作的根底和依據(jù)。3、作為確認測試和驗收的依據(jù)。3.3結(jié)構(gòu)設(shè)計方法軟件設(shè)計是開發(fā)階段最重要的步驟，是將需求準確地轉(zhuǎn)化為完整的軟件產(chǎn)品或系統(tǒng)的唯一途徑。軟件設(shè)計是確定系統(tǒng)的物理模型。軟件設(shè)計的根本原理：抽象、模塊化、信息隱蔽和模塊獨立性模塊的獨立程度是評價設(shè)計好壞的最重要度量標準，衡量軟件模塊獨立性使用耦合性和內(nèi)聚性兩個定性的度量標準。在程序結(jié)構(gòu)中各模塊的內(nèi)聚性越強，那么耦合性越弱。優(yōu)秀軟件應高內(nèi)

33、聚，低耦合。結(jié)構(gòu)化設(shè)計方法的根本要求是，在詳細設(shè)計階段，為了確保模塊邏輯清晰， 就應該要求所有的模塊只使用單入口、單出口以及順序、選擇和循環(huán)3種根本控制結(jié)構(gòu)。? 從技術(shù)觀點來看，軟件設(shè)計包括軟件結(jié)構(gòu)設(shè)計、數(shù)據(jù)設(shè)計、接口設(shè)計、過程設(shè)計。結(jié)構(gòu)設(shè)計：定義軟件系統(tǒng)各主要部件之間的關(guān)系。數(shù)據(jù)設(shè)計：將分析時創(chuàng)立的模型轉(zhuǎn)化為數(shù)據(jù)結(jié)構(gòu)的定義。接口設(shè)計：描述軟件內(nèi)部、軟件和協(xié)作系統(tǒng)之間以及軟件與人之間如何通信。過程設(shè)計：把系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過程描述。? 從工程管理角度來看：概要總體設(shè)計和詳細設(shè)計。概要設(shè)計：又稱結(jié)構(gòu)設(shè)計，將軟件需求轉(zhuǎn)化為軟件體系結(jié)構(gòu)，確定系統(tǒng)級接口、全局數(shù)據(jù)結(jié)構(gòu)或數(shù)據(jù)庫模式。詳細設(shè)計：也稱

34、過程設(shè)計，確定每個模塊的實現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用適當方法表示算法和數(shù)據(jù)結(jié)構(gòu)的細節(jié)。概要設(shè)計的根本任務(wù)是：1設(shè)計軟件系統(tǒng)結(jié)構(gòu)；2數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫設(shè)計；3編寫概要設(shè)計文檔；4概要設(shè)計文檔評審。軟件結(jié)構(gòu)設(shè)計常用工具：結(jié)構(gòu)圖 SC模塊用一個矩形表示箭頭表示模塊間的調(diào)用關(guān)系帶注釋的箭頭表示模塊調(diào)用過程中來回傳遞的信息用帶實心圓的箭頭表示傳遞的是控制信息空心圓箭心表示傳遞的是數(shù)據(jù)。結(jié)構(gòu)圖的根本形式：根本形式、順序形式、重復形式、選擇形式。一股摸塊數(shù)拯信息控制信息圈3思結(jié)構(gòu)圖根本圖符面向數(shù)據(jù)流的設(shè)計方法，主要是分析信息在系統(tǒng)中加工和流動的情況。典型的數(shù)據(jù)流類型有兩種：變換型和事務(wù)型。詳細設(shè)計：主要確定每個

35、模塊具體執(zhí)行過程，也稱過程設(shè)計。詳細設(shè)計的結(jié)果根本上決定了最終的程序代碼的質(zhì)量。常見的詳細設(shè)計工具有：圖形工具程序流程圖PFD、N-S、問題分析圖PAD和HIPO 表格工具判定表語言工具過程設(shè)計語言 PDL偽碼。B13多分女選禪型IS3.18 F?序流我圖枸成的5種控制給構(gòu)COXITlI <5! SjAx：輸入*if O«iSlS 罪忡 1 公武 I 計算call sub, else if C x>15> 公式 2 計算：call sub:»ub < : for 1= 3 i+ do 記!IK:輸出:J用PDL表示的根本控制結(jié)枸的常用詞匯如下；順序：

36、條件：IF/THEN/ELSENDIF循環(huán)】DOWHH同EMDDO循環(huán)：REPEAT UNT1UENDREPEAT分丸 CASE_OFWHEN/SELnCT/WHEN/SELECT/ENDCASE3.4 軟件測試軟件測試：使用人工或自動手段來運行或測定某個系統(tǒng)的過程，用以檢驗它是否滿足規(guī)定的需求或是弄清預期結(jié)果與實際結(jié)果之間的差異。軟件測試的目的：為發(fā)現(xiàn)錯誤而執(zhí)行程序的過程。軟件測試靜態(tài)測試：主要通過人工測試。不用測試實例動態(tài)測試：利用計算機進行測試。黑盒測試 白盒測試白盒測試結(jié)構(gòu)測試：在程序內(nèi)部進行，主要用于完成軟件內(nèi)部操作的驗證，如果想用白盒測試出所有錯誤，那么至少要把所有可能的路徑都執(zhí)行

37、一次。主要方法有邏輯覆蓋、根本路徑測試。黑盒測試：主要診斷功能錯誤或遺漏、界面錯誤、數(shù)據(jù)結(jié)構(gòu)或外部數(shù)據(jù)庫訪問錯誤、性能錯誤、初始化和終止條件錯，用于軟件確認。主要方法有等價類劃分法、邊界值分析法、錯 誤推測法等。軟件測試過程一般按 4個步驟進行：單元測試：發(fā)現(xiàn)各個模塊內(nèi)可能存在的錯誤，主要依據(jù)詳細設(shè)計說明書和源程序集成測試：發(fā)現(xiàn)和接口有關(guān)的錯誤，主要依據(jù)概要設(shè)計說明書驗收測試確認測試：運用黑盒測試法驗證軟件的功能是否滿足需求規(guī)格說明書的需求， 軟件配置是否正確、完整。系統(tǒng)測試：在真實的工作環(huán)境下檢驗軟件是否正常工作3.5 程序的調(diào)試軟件測試主要為了發(fā)現(xiàn)錯誤，它的執(zhí)行貫穿軟件生命周期，而程序調(diào)試

38、的任務(wù)是診斷和改正 程序中的錯誤，主要在開發(fā)階段進行；程序調(diào)試的根本步驟：1錯誤定位；2 修改設(shè)計和代碼，以排除錯誤；3進行回歸測試，防止引進新的錯誤。軟件調(diào)試可分表靜態(tài)調(diào)試和動態(tài)調(diào)試。靜態(tài)調(diào)試主要是指通過人的思維來分析源程序代碼和排錯，是主要的設(shè)計手段，而動態(tài)調(diào)試是輔助靜態(tài)調(diào)試。主要調(diào)試方法有：1強行排錯法；2回溯法；3原因排除法。四、數(shù)據(jù)庫設(shè)計根底? 數(shù)據(jù)庫、數(shù)據(jù)庫管理系統(tǒng)、數(shù)據(jù)庫系統(tǒng)? 數(shù)據(jù)庫系統(tǒng)的開展，數(shù)據(jù)庫系統(tǒng)的根本特點，數(shù)據(jù)庫系統(tǒng)的結(jié)構(gòu)體系? 實體聯(lián)系模型及 E-R 圖，從 E-R 圖導出關(guān)系數(shù)據(jù)模型? 集合運算及選擇、投影、連接運算，數(shù)據(jù)標準化理論? 數(shù)據(jù)庫設(shè)計方法和步驟：需求分

39、析、概念設(shè)計、邏輯設(shè)計和物理設(shè)計的相關(guān)策略? 數(shù)據(jù)庫管理本章學習方法 數(shù)據(jù)庫是當前軟件處理的信息核心，目前大局部軟件都是基于數(shù)據(jù)庫的，因此學習一下數(shù) 據(jù)庫知識對程序開發(fā)也是很有幫助的。 本章主要的考核點是關(guān)系模型、 關(guān)系代數(shù)及數(shù)據(jù)庫系統(tǒng)的根本概念， 其余的知識點了解即可，其中數(shù)據(jù)庫的設(shè)計和管理可以結(jié)合著軟件工程來看，考生會發(fā)現(xiàn)這兩者有很多相 似之處。除了關(guān)系代數(shù)會考一些簡單的計算問題外，其余的都是以概念題的形式考核，大家需要仔細的閱 讀。4.1 數(shù)據(jù)庫系統(tǒng)的根本概念? 數(shù)據(jù)：實際上就是描述事物的符號記錄。? 數(shù)據(jù)的特點：有一定的結(jié)構(gòu)，有型與值之分，如整型、實型、字符型等。而數(shù)據(jù)的 值給出了符合

40、定型的值。? 數(shù)據(jù)庫 DB ：是數(shù)據(jù)的集合，具有統(tǒng)一的結(jié)構(gòu)形式并存放于統(tǒng)一的存儲介質(zhì)內(nèi)，是 多種應用數(shù)據(jù)的集成，并可被各個應用程序共享。? 數(shù)據(jù)庫存放數(shù)據(jù)是按數(shù)據(jù)所提供的數(shù)據(jù)模式存放的，具有集成與共享的特點。? 數(shù)據(jù)庫管理系統(tǒng) DBMS ：一種系統(tǒng)軟件，負責數(shù)據(jù)庫中的數(shù)據(jù)組織、數(shù)據(jù)操縱、數(shù) 據(jù)維護、控制及保護和數(shù)據(jù)效勞等，是數(shù)據(jù)庫的核心。數(shù)據(jù)庫管理系統(tǒng)功能： 1數(shù)據(jù)模式定義：即為數(shù)據(jù)庫構(gòu)建其數(shù)據(jù)框架； 2數(shù)據(jù)存取的物理構(gòu)建：為數(shù)據(jù)模式的物理存取與構(gòu)建提供有效的存取方法與手段； 3數(shù)據(jù)操縱：為用戶使用數(shù)據(jù)庫的數(shù)據(jù)提供方便，如查詢、插入、修改、刪除等以及簡 單的算術(shù)運算及統(tǒng)計；4數(shù)據(jù)的完整性、平安

41、性定義與檢查；5數(shù)據(jù)庫的并發(fā)控制與故障恢復；6數(shù)據(jù)的效勞：如拷貝、轉(zhuǎn)存、重組、性能監(jiān)測、分析等。 為完成以上六個功能，數(shù)據(jù)庫管理系統(tǒng)提供以下的數(shù)據(jù)語言：1數(shù)據(jù)定義語言 DDL ：負責數(shù)據(jù)的模式定義與數(shù)據(jù)的物理存取構(gòu)建； 2數(shù)據(jù)操縱語言 DML ：負責數(shù)據(jù)的操縱，如查詢與增、刪、改等；3數(shù)據(jù)控制語言 DCL ：負責數(shù)據(jù)完整性、平安性的定義與檢查以及并發(fā)控制、故障恢 復等。數(shù)據(jù)語言按其使用方式具有兩種形式：交互式命令又稱自含型或自主型語言 、嵌入式命令宿主型語言 。數(shù)據(jù)庫管理員 DBA ：對數(shù)據(jù)庫進行規(guī)劃、設(shè)計、維護、監(jiān)視等的專業(yè)管理人員。數(shù)據(jù)庫系統(tǒng) DBS ：由數(shù)據(jù)庫數(shù)據(jù) 、數(shù)據(jù)庫管理系統(tǒng)軟件

42、、數(shù)據(jù)庫管理員人員 、 硬件平臺硬件 、軟件平臺軟件五個局部構(gòu)成的運行實體。數(shù)據(jù)庫應用系統(tǒng) DBAS ：由數(shù)據(jù)庫系統(tǒng)、應用軟件及應用界面三者組成。 數(shù)據(jù)庫開展階段：人工管理階段數(shù)據(jù)庫應用系統(tǒng)DBAS 數(shù)據(jù)庫系統(tǒng)DBS 數(shù)據(jù)庫管理系統(tǒng)DBMS關(guān)系數(shù)據(jù)庫系統(tǒng)階段數(shù)據(jù)庫DB文件系統(tǒng)階段層次與網(wǎng)狀數(shù)據(jù)庫系統(tǒng)階段? 數(shù)據(jù)庫系統(tǒng)的三級模式：1外模式：也稱子模式與用戶模式。是用戶的數(shù)據(jù)視圖，也就是用戶所見到的數(shù)據(jù)模式；一個數(shù)據(jù)庫可以有多個外模式視圖2 概念模式邏輯模式或模式：數(shù)據(jù)庫系統(tǒng)中全局數(shù)據(jù)邏輯結(jié)構(gòu)的描述，全體用戶公共 數(shù)據(jù)視圖，不涉及具體的硬件和軟件環(huán)境，一個數(shù)據(jù)庫只有一個概念模式；3 內(nèi)模式：又稱物理模式，它給出了數(shù)據(jù)庫物理存儲結(jié)構(gòu)與物理存取方法。索引存取一個數(shù)據(jù)庫只有一個內(nèi)模式? 數(shù)據(jù)庫系統(tǒng)的兩級映射:1外模式到概念模式的映射。2概念模式到內(nèi)模式的映射;4.2數(shù)據(jù)模型? 數(shù)據(jù)模型的概念：是數(shù)據(jù)特征的抽象，從抽象層次上描述了系統(tǒng)的靜態(tài)特征、動態(tài) 行