全國計算機等級考試二級教程——公共基礎(chǔ)知識大綱

1、全國計算機等級考試二級教程一一公共基礎(chǔ)知識考試大綱基本要求1. 掌握算法的基本概念。2. 掌握基本數(shù)據(jù)結(jié)構(gòu)及其操作。3. 掌握基本排序和查找算法。4. 掌握逐步求精的結(jié)構(gòu)化程序設(shè)計方法。5. 掌握軟件工程的基本方法，具有初步應(yīng)用相關(guān)技術(shù)進(jìn)行軟件開發(fā)的能力。6. 掌握數(shù)據(jù)庫的基本知識，了解關(guān)系數(shù)據(jù)庫的設(shè)計?？荚噧?nèi)容一、基本數(shù)據(jù)結(jié)構(gòu)與算法1. 算法的基本概念；算法復(fù)雜度的概念和意義（時間復(fù)雜度與空間復(fù)雜度）。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. 棧和隊列的定義；棧和隊列的順

2、序存儲結(jié)構(gòu)及其基本運算。5. 線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運算。6. 樹的基本概念；二叉樹的定義及其存儲結(jié)構(gòu)；二叉樹的前序、中序和后序遍歷。7. 順序查找與二分法查找算法；基本排序算法（交換類排序，選擇類排序，插入類排序）。二、程序設(shè)計基礎(chǔ)1. 程序設(shè)計方法與風(fēng)格。2. 結(jié)構(gòu)化程序設(shè)計。3. 面向?qū)ο蟮某绦蛟O(shè)計方法，對象，方法，屬性及繼承與多態(tài)性。三、軟件工程基礎(chǔ)1. 軟件工程基本概念，軟件生命周期概念，軟件工具與軟件開發(fā)環(huán)境。2. 結(jié)構(gòu)化分析方法，數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說明書。3. 結(jié)構(gòu)化設(shè)計方法，總體設(shè)計與詳細(xì)設(shè)計。4. 軟件測試的方法，白盒測試與黑盒測試，測試用

3、例設(shè)計，軟件測試的實施，單元測試、集成測試和 系統(tǒng)測試。5. 程序的調(diào)試，靜態(tài)調(diào)試與動態(tài)調(diào)試。四、數(shù)據(jù)庫設(shè)計基礎(chǔ)1. 數(shù)據(jù)庫的基本概念：數(shù)據(jù)庫，數(shù)據(jù)庫管理系統(tǒng)，數(shù)據(jù)庫系統(tǒng)。2. 數(shù)據(jù)模型，實體聯(lián)系模型及 E-R圖，從E-R圖導(dǎo)出關(guān)系數(shù)據(jù)模型。3. 關(guān)系代數(shù)運算，包括集合運算及選擇、投影、連接運算，數(shù)據(jù)庫規(guī)范化理論。4. 數(shù)據(jù)庫設(shè)計方法和步驟：需求分析、概念設(shè)計、邏輯設(shè)計和物理設(shè)計的相關(guān)策略?？荚嚪绞焦不A(chǔ)知識有10道選擇題和5道填空題共三十分第一章數(shù)據(jù)結(jié)構(gòu)與算法1.1算法1、算法是指解題方案的準(zhǔn)確而完整的描述。換句話說，算法是對特定問題求解步驟的一種描述。* :算法不等于程序，也不等于計算方

4、法。程序的編制不可能優(yōu)于算法的設(shè)計（注釋1 ）。2、算法的基本特征（1）可行性。針對實際問題而設(shè)計的算法，執(zhí)行后能夠得到滿意的結(jié)果。（2） 確定性。每一條指令的含義明確， 無二義性。并且在任何條件下，算法只有唯一的一條執(zhí)行路徑, 即相同的輸入只能得出相同的輸出。（3）有窮性。算法必須在有限的時間內(nèi)完成。有兩重含義，一是算法中的操作步驟為有限個，二是每 個步驟都能在有限時間內(nèi)完成。（4）擁有足夠的情報。算法中各種運算總是要施加到各個運算對象上，而這些運算對象又可能具有某種初始狀態(tài)，這就是算法執(zhí)行的起點或依據(jù)。因此，一個算法執(zhí)行的結(jié)果總是與輸入的初始數(shù)據(jù)有關(guān)，不 同的輸入將會有不同的結(jié)果輸岀。當(dāng)輸

5、入不夠或輸入錯誤時，算法將無法執(zhí)行或執(zhí)行有錯。一般說來，當(dāng) 算法擁有足夠的情報時，此算法才是有效的；而當(dāng)提供的情報不夠時，算法可能無效。* :綜上所述，所謂算法，是一組嚴(yán)謹(jǐn)?shù)囟x運算順序的規(guī)則，并且每一個規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。3、算法復(fù)雜度主要包括時間復(fù)雜度和空間復(fù)雜度。（1）算法時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量，可以用執(zhí)行算法的過程中所需基本運算的執(zhí)行次數(shù)來度量。（2）算法空間復(fù)雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。（注釋1）這是因為：在編寫程序時要受到計算機系統(tǒng)運行環(huán)境的限制，程序通常還要考慮很多與方法 和分析無關(guān)的細(xì)節(jié)問題。1.2數(shù)據(jù)結(jié)構(gòu)的基本概

6、念1、數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。2、數(shù)據(jù)結(jié)構(gòu)主要研究和討論以下三個方面的問題：（1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)包含：1）表示數(shù)據(jù)元素的信息；2）表示各數(shù)據(jù)元素之間的前后件關(guān)系（ 注釋1）（2）在對數(shù)據(jù)進(jìn)行處理時，各數(shù)據(jù)元素在計算機中的存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)。數(shù)據(jù)的存儲結(jié)構(gòu)有順序、鏈接、索引等。1）順序存儲。它是把邏輯上相鄰的結(jié)點存儲在物理位置相鄰的存儲單元里，結(jié)點間的邏輯關(guān)系由存儲 單元的鄰接關(guān)系來體現(xiàn)。由此得到的存儲表示稱為順序存儲結(jié)構(gòu)。2）鏈接存儲。它不要求邏輯上相鄰的結(jié)點在物理位置上亦相鄰，結(jié)點間的邏輯關(guān)系是由附加的指針字

7、 段表示的。由此得到的存儲表示稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)。3）索引存儲：除建立存儲結(jié)點信息外，還建立附加的索引表來標(biāo)識結(jié)點的地址。* :數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系，數(shù)據(jù)的存儲結(jié)構(gòu)（也稱數(shù)據(jù)的物理結(jié)構(gòu)）是數(shù)據(jù)的 邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式。同一種邏輯結(jié)構(gòu)的數(shù)據(jù)可以采用不同的存儲結(jié)構(gòu)，但影響數(shù)據(jù) 處理效率。（3 ）對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運算。3、數(shù)據(jù)結(jié)構(gòu)的圖形表示一個數(shù)據(jù)結(jié)構(gòu)除了用二元關(guān)系表示外，還可以直觀地用圖形表示。在數(shù)據(jù)結(jié)構(gòu)的圖形表示中，對于數(shù) 據(jù)集合D中的每一個數(shù)據(jù)元素用中間標(biāo)有元素值的方框表示，一般稱之為數(shù)據(jù)結(jié)點，并簡稱為結(jié)點；為了 進(jìn)一步表示各數(shù)據(jù)元素之間的前后件關(guān)系，對于

8、關(guān)系R中的每一個二元組，用一條有向線段從前件結(jié)點指向后件結(jié)點。4、數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。（1 ）線性結(jié)構(gòu)（非空的數(shù)據(jù)結(jié)構(gòu)）條件：1）有且只有一個根結(jié)點（注釋2）； 2）每一個結(jié)點最多有一個前驅(qū)，也最多有一個后繼。* :常見的線性結(jié)構(gòu)有線性表、棧、隊列和線性鏈表等。（2）非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。* :常見的非線性結(jié)構(gòu)有樹、二叉樹和圖等。（注釋1）前后件關(guān)系：一般情況下，在具有相同特征的數(shù)據(jù)元素集合中，各個數(shù)據(jù)元素之間存在某種 關(guān)系（即聯(lián)系），這種關(guān)系反映了該集合中的數(shù)據(jù)元素所固有的一種結(jié)構(gòu)。在數(shù)據(jù)處理領(lǐng)域中，通常把數(shù)據(jù) 元素之間這種固有的關(guān)系簡單地用前后件

9、關(guān)系（即直接前驅(qū)與直接后繼關(guān)系）來描述。（注釋2）在數(shù)據(jù)結(jié)構(gòu)中，沒有前去的結(jié)點稱為根結(jié)點。1.3線性表及其順序存儲結(jié)構(gòu)1、 線性表由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的序號，元素之間的相對位置是線性的。 線性表是由n（n>0）個數(shù)據(jù)元素組成的一個有限序列，表中的每一個數(shù)據(jù)元素，除了第一個外，有且只有一個前件，除了最后一個外，有且只有一個后件。線性表中數(shù)據(jù)元素的個數(shù)稱為線性表的長度。線性表可 以為空表。*:線性表是一種存儲結(jié)構(gòu)，它的存儲方式：順序和鏈?zhǔn)健?、 線性表的順序存儲結(jié)構(gòu)具有兩個基本特點：（1）線性表中所有元素所占的存儲空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲空間中是

10、按邏輯順序依次存放的。* :由此可以看岀，在線性表的順序存儲結(jié)構(gòu)中，其前后件兩個元素在存儲空間中是緊鄰的，且前件元素一定存儲在后件元素的前面，可以通過計算機直接確定第i個結(jié)點的存儲地址。3、順序表的插入、刪除運算（學(xué)吧學(xué)吧獨家稿件）（1） 順序表的插入運算：在一般情況下，要在第i （1<i wn）個元素之前插入一個新元素時，首先要從最后一個（即第n個）元素開始，直到第i個元素之間共n-i+1個元素依次向后移動一個位置，移動 結(jié)束后，第i個位置就被空岀，然后將新元素插入到第i項。插入結(jié)束后，線性表的長度就增加了1。*:順性表的插入運算時需要移動元素，在等概率情況下，平均需要移動n/2個元素

11、。（2） 順序表的刪除運算：在一般情況下，要刪除第i （1<i wn）個元素時，則要從第i+1個元素開始， 直到第n個元素之間共n-i個元素依次向前移動一個位置。刪除結(jié)束后，線性表的長度就減小了1。*：進(jìn)行順性表的刪除運算時也需要移動元素，在等概率情況下，平均需要移動（n-1 ） /2個元素。插入、刪除運算不方便。1.4棧和隊列1、棧及其基本運算棧是限定在一端進(jìn)行插入與刪除運算的線性表。在棧中，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧頂元素總是最后被插入的元素，棧底元素總是最先被插入的元素。即棧是按照“先進(jìn)后岀”或“后進(jìn)先岀”的原則組織數(shù)據(jù)的。棧具有記憶作用。棧

12、的基本運算：1）插入元素稱為入棧運算；2）刪除元素稱為退棧運算；3）讀棧頂元素是將棧頂元素 賦給一個指定的變量，此時指針無變化。棧的存儲方式和線性表類似，也有兩種，即順序棧和鏈?zhǔn)綏！?、隊列及其基本運算隊列是指允許在一端（隊尾）進(jìn)入插入，而在另一端（隊頭）進(jìn)行刪除的線性表。尾指針（Rear ）指向隊尾元素，頭指針（front ）指向排頭元素的前一個位置（隊頭）。隊列是“先進(jìn)先岀”或“后進(jìn)后岀”的線性表。隊列運算包括：1）入隊運算：從隊尾插入一個元素；2）退隊運算：從隊頭刪除一個元素。循環(huán)隊列及其運算：所謂循環(huán)隊列，就是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯 上的環(huán)狀空間，供隊列循

13、環(huán)使用。在循環(huán)隊列中，用隊尾指針rear指向隊列中的隊尾元素，用排頭指針front指向排頭元素的前一個位置，因此，從頭指針front指向的后一個位置直到隊尾指針rear指向的位置之間，所有的元素均為隊列中的元素。* :循環(huán)隊列中元素的個數(shù) =rear-front 。1.5線性鏈表1、 線性表順序存儲的缺點：（1）插入或刪除的運算效率很低。在順序存儲的線性表中，插入或刪除數(shù) 據(jù)元素時需要移動大量的數(shù)據(jù)元素 ；（2）線性表的順序存儲結(jié)構(gòu)下，線性表的存儲空間不便于擴(kuò)充；（3）線性 表的順序存儲結(jié)構(gòu)不便于對存儲空間的動態(tài)分配。2、線性鏈表：線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表，是一種物理存儲單元上非連續(xù)、

14、非順序的存儲結(jié) 構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接來實現(xiàn)的。因此，在鏈?zhǔn)酱鎯Ψ绞街?，每個結(jié)點由兩部分組成：一部分用于存放數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分用于存放指針，稱為指針域，用于指向該結(jié)點的前一個或后一個結(jié)點（即前件或后件），如下圖所示：數(shù)據(jù)域 wadak0aA（）錯點結(jié)構(gòu)空狠m俶示意圖線性鏈表分為單鏈表、雙向鏈表和循環(huán)鏈表三種類型。在單鏈表中，每一個結(jié)點只有一個指針域，由這個指針只能找到其后件結(jié)點，而不能找到其前件結(jié)點。因此，在某些應(yīng)用中，對于線性鏈表中的每個結(jié)點設(shè)置兩個指針，一個稱為左指針，指向其前件結(jié)點；另一個稱為右指針，指向其后件結(jié)點，這種鏈表稱為雙向鏈表，如下圖所示：

15、左指針鱷域右謝I丨II H£AD T “ 丨勺丨 L 1 丨 q I L'"11。査結(jié)構(gòu)一個非空的舉向糖表示意國3、線性鏈表的基本運算（1）在線性鏈表中包含指定元素的結(jié)點之前插入一個新元素。* :在線性鏈表中插入元素時，不需要移動數(shù)據(jù)元素，只需要修改相關(guān)結(jié)點指針即可，也不會岀現(xiàn)“上溢（注釋1）”現(xiàn)象。（2）在線性鏈表中刪除包含指定元素的結(jié)點。* :在線性鏈表中刪除元素時，也不需要移動數(shù)據(jù)元素，只需要修改相關(guān)結(jié)點指針即可。(3) 將兩個線性鏈表按要求合并成一個線性鏈表。(4) 將一個線性鏈表按要求進(jìn)行分解。(5) 逆轉(zhuǎn)線性鏈表。(6) 復(fù)制線性鏈表。(7) 線性鏈表的

16、排序。(8) 線性鏈表的查找。* :線性鏈表不能隨機存取( 注釋2 )。4、循環(huán)鏈表及其基本運算在線性鏈表中，其插入與刪除的運算雖然比較方便，但還存在一個問題，在運算過程中對于空表和對 第一個結(jié)點的處理必須單獨考慮，使空表與非空表的運算不統(tǒng)一。為了克服線性鏈表的這個缺點，可以采 用另一種鏈接方式，即循環(huán)鏈表。與前面所討論的線性鏈表相比，循環(huán)鏈表具有以下兩個特點：1)在鏈表中增加了一個表頭結(jié)點，其數(shù)據(jù)域為任意或者根據(jù)需要來設(shè)置，指針域指向線性表的第一個元素的結(jié)點，而循環(huán)鏈表的頭指針指向表頭 結(jié)點;2)循環(huán)鏈表中最后一個結(jié)點的指針域不是空，而是指向表頭結(jié)點。即在循環(huán)鏈表中，所有結(jié)點的指針構(gòu)成了一個

17、環(huán)狀鏈。下圖a是一個非空的循環(huán)鏈表，圖 b是一個空的循環(huán)鏈表：循環(huán)鏈表的優(yōu)點主要體現(xiàn)在兩個方面：一是在循環(huán)鏈表中，只要指岀表中任何一個結(jié)點的位置，就可以從它岀發(fā)訪問到表中其他所有的結(jié)點，而線性單鏈表做不到這一點；二是由于在循環(huán)鏈表中設(shè)置了一個表頭結(jié)點，在任何情況下，循環(huán)鏈表中至少有一個結(jié)點存在，從而使空表與非空表的運算統(tǒng)一。* :循環(huán)鏈表是在單鏈表的基礎(chǔ)上增加了一個表頭結(jié)點，其插入和刪除運算與單鏈表相同。但它可以從任一結(jié)點岀發(fā)來訪問表中其他所有結(jié)點，并實現(xiàn)空表與非空表的運算的統(tǒng)一。注釋1 :當(dāng)為一個線性表分配順序存儲結(jié)構(gòu)后，如果岀現(xiàn)線性表的存儲空間已滿，但還需要插入新的元素時，就會發(fā)生“上溢”

18、現(xiàn)象。注釋2 :在鏈表中，即使知道被訪問結(jié)點的序號i，也不能像順序表中那樣直接按序號i訪問結(jié)點，而只能從鏈表的頭指針岀發(fā)，順著鏈域逐個結(jié)點往下搜索，直至搜索到第i個結(jié)點為止。因此，鏈表不是隨機存儲結(jié)構(gòu)。1.6樹與二叉樹1、樹的基本概念樹是一種簡單的非線性結(jié)構(gòu)。在樹這種數(shù)據(jù)結(jié)構(gòu)中，所有數(shù)據(jù)元素之間的關(guān)系具有明顯的層次特性。在樹結(jié)構(gòu)中，每一個結(jié)點只有一個前件，稱為父結(jié)點。沒有前件的結(jié)點只有一個，稱為樹的根結(jié)點，簡稱樹的根。每一個結(jié)點可以有多個后件，稱為該結(jié)點的子結(jié)點。沒有后件的結(jié)點稱為 葉子結(jié)點。在樹結(jié)構(gòu)中，一個結(jié)點所擁有的后件的個數(shù)稱為該結(jié)點的度，所有結(jié)點中最大的度稱為 樹的度。樹的最大層次稱為

19、樹的深度。2、二叉樹及其基本性質(zhì)(1) 什么是二叉樹二叉樹是一種很有用的非線性結(jié)構(gòu)，它具有以下兩個特點：1）非空二叉樹只有一個根結(jié)*:根據(jù)二叉樹的概念可知，二叉樹的度可以為0（葉結(jié)點）、1（只有一棵子樹）或2（有2棵子樹）。（2）二叉樹的基本性質(zhì)（學(xué)吧學(xué)吧獨家稿件）性質(zhì)1在二叉樹的第k層上，最多有2k-1（k >1）個結(jié)點。性質(zhì)2深度為m的二叉樹最多有個2m-1個結(jié)點。性質(zhì)3在任意一棵二叉樹中，度數(shù)為 0的結(jié)點（即葉子結(jié)點）總比度為2的結(jié)點多一個。性質(zhì)4具有n個結(jié)點的二叉樹，其深度至少為 log 2n+1，其中l(wèi)og 2n表示取log 2n的整數(shù)部分。3、滿二叉樹與完全二叉樹滿二叉樹：除

20、最后一層外，每一層上的所有結(jié)點都有兩個子結(jié)點。完全二叉樹：除最后一層外，每一層上的結(jié)點數(shù)均達(dá)到最大值 ;在最后一層上只缺少右邊的若干結(jié)點。* :根據(jù)完全二叉樹的定義可得出：度為1的結(jié)點的個數(shù)為0或1。完全二叉樹還具有如下兩個特性：性質(zhì)5具有n個結(jié)點的完全二叉樹深度為log 2n+1。性質(zhì)6設(shè)完全二叉樹共有n個結(jié)點，如果從根結(jié)點開始，按層序 （每一層從左到右）用自然數(shù)1，2,， n給結(jié)點進(jìn)行編號，則對于編號為k（k=1，2，,， n）的結(jié)點有以下結(jié)論： 若k=1，則該結(jié)點為根結(jié)點，它沒有父結(jié)點；若k>1，則該結(jié)點的父結(jié)點的編號為INT（k/2）。 若2k<n，則編號為 k的左子結(jié)點編

21、號為2k;否則該結(jié)點無左子結(jié)點（顯然也沒有右子結(jié)點）。 若2k+1<n，則編號為 k的右子結(jié)點編號為2k+1;否則該結(jié)點無右子結(jié)點。4、二叉樹的存儲結(jié)構(gòu)在計算機中，二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。與線性鏈表類似，用于存儲二叉樹中各元素的存儲結(jié)點也由兩部分組成：數(shù)據(jù)域和指針域。但在二叉 樹中，由于每一個元素可以有兩個后件（即兩個子結(jié)點），因此，用于存儲二叉樹的存儲結(jié)點的指針域有兩個:一個用于指向該結(jié)點的左子結(jié)點的存儲地址，稱為左指針域；另一個用于指向該結(jié)點的右子結(jié)點的存儲地址，稱為右指針域。* : 一般二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，對于滿二叉樹與完全二叉樹來說，可以按層序進(jìn)行順序存儲 （注釋1）

22、。5、二叉樹的遍歷二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有結(jié)點。二叉樹的遍歷可以分為以下三種：（1）前序遍歷（DLR）:若二叉樹為空，則結(jié)束返回。否則：首先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹；并且，在遍歷左右子樹時，仍然先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹。（2）中序遍歷（LDR）:若二叉樹為空，則結(jié)束返回。否則：首先遍歷左子樹，然后訪問根結(jié)點，最后遍 歷右子樹；并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹。（3）后序遍歷（LRD）:若二叉樹為空，則結(jié)束返回。否則：首先遍歷左子樹，然后遍歷右子樹，最后訪 問根結(jié)點，并且，在遍歷左、右子樹時，仍然先

23、遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點。注釋1 :這樣，不僅節(jié)省了存儲空間，又能方便地確定每一個結(jié)點的父結(jié)點與左右子結(jié)點的位置，但順 序存儲結(jié)構(gòu)對于一般的二叉樹不適用。1.7查找技術(shù)查找：根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素。查找結(jié)果：（查找成功：找到；查找不成功：沒找到。）平均查找長度：查找過程中關(guān)鍵字和給定值比較的平均次數(shù)。1、順序查找基本思想：從表中的第一個元素開始，將給定的值與表中逐個元素的關(guān)鍵字進(jìn)行比較，直到兩者相符，查到所要找的元素為止。否則就是表中沒有要找的元素，查找不成功。在平均情況下，利用順序查找法在線性表中查找一個元素，大約要與線性表中一半的

24、元素進(jìn)行比較， 最壞情況下需要比較n次。順序查找一個具有n個元素的線性表，其平均復(fù)雜度為0（n）。下列兩種情況下只能采用順序查找：1） 如果線性表是無序表（即表中的元素是無序的），則不管是順序存儲結(jié)構(gòu)還是鏈?zhǔn)酱鎯Y(jié)構(gòu)，都只 能用順序查找。2）即使是有序線性表，如果采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，也只能用順序查找。2、二分法查找思想：先確定待查找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認(rèn)找不到該記錄為止。前提：必須在具有順序存儲結(jié)構(gòu)的有序表中進(jìn)行。查找過程：1） 若中間項（中間項 mid=（n-1）/2 ，mid的值四舍五入取整）的值等于 X，則說明已查到；2）若x小于中間項的值，則在線性表的前半部分查

25、找；3）若x大于中間項的值，則在線性表的后半部分查找。特點：比順序查找方法效率高。最壞的情況下，需要比較Iog2n次。* :二分法查找只適用于順序存儲的線性表，且表中元素必須按關(guān)鍵字有序（升序）排列（注釋1）。對于無序線性表和線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)只能用順序查找。在長度為n的有序線性表中進(jìn)行二分法查找，其時間復(fù)雜度為 O（log2n ）。注釋1:允許相鄰元素值相等。1.8排序技術(shù)排序是指將一個無序序列整理成按值非遞減順序排列的有序序列，即是將無序的記錄序列調(diào)整為有序 記錄序列的一種操作。1、 交換類排序法（方法：冒泡排序，快速排序）。2、 插入類排序法（方法：簡單插入排序，希爾排序）。3、 選擇

26、類排序法（方法：簡單選擇排序，堆排序）?？偨Y(jié)：各種排序法比較：所占本章應(yīng)考點撥：本章內(nèi)容在筆試中會岀現(xiàn) 5-6個題目，是公共基礎(chǔ)知識部分岀題量比較多的一章， 分值也比較大，約10分。第二章考點2.1程序設(shè)計風(fēng)格程序設(shè)計的風(fēng)格主要強調(diào)：“清晰第一，效率第二”（ 注釋1）。主要應(yīng)注重和考慮下述一些因素: （1 ）源程序文檔化。1）符號名的命名。符號名能反映它所代表的實際東西，應(yīng)有一定的實際含義。2）程序的注釋。分為序言性注釋和功能性注釋。序言性注釋：位于程序開頭部分，包括程序標(biāo)題、程序功能說明、主要算法、接口說明、程序位置、 開發(fā)簡歷、程序設(shè)計者、復(fù)審者、復(fù)審日期及修改日期等。功能性注釋：嵌在源程

27、序體之中，用于描述其后的語句或程序的主要功能。3）視覺組織。利用空格、空行、縮進(jìn)等技巧使程序?qū)哟吻逦?。?）數(shù)據(jù)說明。1）數(shù)據(jù)說明的次序規(guī)范化；2）說明語句中變量安排有序化；3）使用注釋來說明復(fù)雜數(shù)據(jù)的結(jié)構(gòu)。（3）語句的結(jié)構(gòu)。1）在一行內(nèi)只寫一條語句；2）程序編寫應(yīng)優(yōu)先考慮清晰性；3）程序編寫要做到清晰第一，效率第二；4）在保證程序正確的基礎(chǔ)上再要求提高效率；5）避免使用臨時變量而使程序的可讀性下降；6）避免不必要的轉(zhuǎn)移；7）盡量使用庫函數(shù)；8）避免采用復(fù)雜的條件語句；9）盡量減少使用“否定”條件語句；10）數(shù)據(jù)結(jié)構(gòu)要有利于程序的簡化；11）要模塊化，使模塊功能盡可能單一化；12）利用信息隱蔽

28、（注釋2 ），確保每一個模塊的獨立性；13）從數(shù)據(jù)岀發(fā)去構(gòu)造程序；14）不要修補不好的程序，要重新編寫。（4）輸入和輸出。1）對輸入數(shù)據(jù)檢驗數(shù)據(jù)的合法性；2）檢查輸入項的各種重要組合的合法性；3）輸入格式要簡單，使得輸入的步驟和操作盡可能簡單；4）輸入數(shù)據(jù)時，應(yīng)允許使用自由格式；5) 應(yīng)允許缺省值；6) 輸入一批數(shù)據(jù)時，最好使用輸入結(jié)束標(biāo)志；7) 在以交互式輸入/輸岀方式進(jìn)行輸入時，要在屏幕上使用提示符明確提示輸入的請求，同時在數(shù)據(jù) 輸入過程中和輸入結(jié)束時，應(yīng)在屏幕上給岀狀態(tài)信息；8) 當(dāng)程序設(shè)計語言對輸入格式有嚴(yán)格要求時，應(yīng)保持輸入格式與輸入語句的一致性；給所有的輸岀加注釋，并設(shè)計輸岀報表格

29、式。注釋1 : “清晰第一，效率第二”是當(dāng)今主導(dǎo)的程序設(shè)計風(fēng)格。注釋2 :信息隱蔽是指采用封裝技術(shù)，將程序模塊的實施細(xì)節(jié)隱藏起來，使模塊接口盡量簡單。即指在 設(shè)計和確定模塊時，使得一個模塊內(nèi)包含的信息(過程或數(shù)據(jù))，對于不需要這些信息的其它模塊來說，是不能訪問的。2.2結(jié)構(gòu)化程序設(shè)計(面向過程的程序設(shè)計方法)1、 結(jié)構(gòu)化程序設(shè)計方法的主要原則可以概括為：自頂向下，逐步求精，模塊化，限制使用goto語句 (1 )自頂向下。程序設(shè)計時，應(yīng)先考慮總體，后考慮細(xì)節(jié)；先考慮全局目標(biāo)，后考慮局部目標(biāo)。不要一開始就過多追求眾多的細(xì)節(jié)，先從最上層總目標(biāo)開始設(shè)計，逐步使問題具體化。(2 )逐步求精。對復(fù)雜問題，

30、應(yīng)設(shè)計一些子目標(biāo)作過渡，逐步細(xì)化。(3) 模塊化。一個復(fù)雜問題，肯定是由若干稍簡單的問題構(gòu)成。模塊化是把程序要解決的總目標(biāo)分解 為分目標(biāo)，再進(jìn)一步分解為具體的小目標(biāo)，把每個小目標(biāo)稱為一個模塊。(4 )限制使用goto語句。2、結(jié)構(gòu)化程序的基本結(jié)構(gòu)：順序結(jié)構(gòu)，選擇結(jié)構(gòu)，重復(fù)結(jié)構(gòu)。1) 順序結(jié)構(gòu)。一種簡單的程序設(shè)計，即按照程序語句行的自然順序，一條語句一條語句地執(zhí)行程序， 它是最基本、最常用的結(jié)構(gòu)。2) 選擇結(jié)構(gòu)。又稱分支結(jié)構(gòu)，包括簡單選擇和多分支選擇結(jié)構(gòu)，可根據(jù)條件，判斷應(yīng)該選擇哪一條分 支來執(zhí)行相應(yīng)的語句序列。3) 重復(fù)結(jié)構(gòu)。又稱循環(huán)結(jié)構(gòu)，可根據(jù)給定的條件，判斷是否需要重復(fù)執(zhí)行某一相同的或類似

31、的程序段。僅僅使用順序、選擇和循環(huán)三種基本控制結(jié)構(gòu)就足以表達(dá)各種其他形式結(jié)構(gòu)，從而實現(xiàn)任何單入口/單岀口的程序。2.3面向?qū)ο蟮某绦蛟O(shè)計客觀世界中任何一個事物都可以被看成是一個對象，面向?qū)ο蠓椒ǖ谋举|(zhì)就是主張從客觀世界固有的 事物岀發(fā)來構(gòu)造系統(tǒng)，提倡人們在現(xiàn)實生活中常用的思維來認(rèn)識、理解和描述客觀事物，強調(diào)最終建立的 系統(tǒng)能夠映射問題域。也就是說，系統(tǒng)中的對象及對象之間的關(guān)系能夠如實地反映問題域中固有的事物及 其關(guān)系。面向?qū)ο蠓椒ǖ闹饕獌?yōu)點：(1 )與人類習(xí)慣的思維方法一致；(2) 穩(wěn)定性好；(3) 可重用(注釋1)性好；(4) 易于開發(fā)大型軟件產(chǎn)品；(5) 可維護(hù)性好。*:面向?qū)ο蟮某绦蛟O(shè)計

32、主要考慮的是提高軟件的可重用性。對象是面向?qū)ο蠓椒ㄖ凶罨镜母拍?，可以用來表示客觀世界中的任何實體，對象是實體的抽象。面向?qū)ο蟮某绦蛟O(shè)計方法中的對象是系統(tǒng)中用來描述客觀事物的一個實體，是構(gòu)成系統(tǒng)的一個基本單位，由 一組表示其靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成。對象是屬性和方法的封裝體。屬性即對象所包含的信息，它在設(shè)計對象時確定，一般只能通過執(zhí)行對象的操作來改變。操作描述了對象執(zhí)行的功能，操作也稱為方法或服務(wù)。操作是對象的動態(tài)屬性。* :一個對象由對象名、屬性和操作三部分組成。對象的基本特點：標(biāo)識惟一性，分類性，多態(tài)性，封裝性，模塊獨立性好。（1）標(biāo)識惟一性。指對象是可區(qū)分的，并且由對象的內(nèi)

33、在本質(zhì)來區(qū)分，而不是通過描述來區(qū)分。（2）分類性。指可以將具有相同屬性的操作的對象抽象成類。（3）多態(tài)性。指同一個操作可以是不同對象的行為。（4）封裝性。從外面看只能看到對象的外部特性，即只需知道數(shù)據(jù)的取值范圍和可以對該數(shù)據(jù)施加的 操作，根本無需知道數(shù)據(jù)的具體結(jié)構(gòu)以及實現(xiàn)操作的算法。對象的內(nèi)部，即處理能力的實行和內(nèi)部狀態(tài)，對外是不可見的。從外面不能直接使用對象的處理能力，也不能直接修改其內(nèi)部狀態(tài)，對象的內(nèi)部狀態(tài)只 能由其自身改變。* :信息隱蔽是通過對象的封裝性來實現(xiàn)的。（5）模塊獨立性好。對象是面向?qū)ο蟮能浖幕灸K，它是由數(shù)據(jù)及可以對這些數(shù)據(jù)施加的操作所 組成的統(tǒng)一體，而且對象是以數(shù)據(jù)為

34、中心的，操作圍繞對其數(shù)據(jù)所需做的處理來設(shè)置，沒有無關(guān)的操作。 從模塊的獨立性考慮，對象內(nèi)部各種元素彼此結(jié)合得很緊密，內(nèi)聚性強。類是指具有共同屬性、共同方法的對象的集合。所以類是對象的抽象，對象是對應(yīng)類的一個實例。消息是一個實例與另一個實例之間傳遞的信息。消息的組成包括：（1）接收消息的對象的名稱；（2）消息標(biāo)識符，也稱消息名；（3）零個或多個參數(shù)。* :在面向?qū)ο蠓椒ㄖ?，一個對象請求另一個對象為其服務(wù)的方式是通過發(fā)送消息。繼承是指能夠直接獲得已有的性質(zhì)和特征，而不必重復(fù)定義他們。繼承分單繼承和多重繼承。單繼承 指一個類只允許有一個父類，多重繼承指一個類允許有多個父類。* :類的繼承性是類之間共

35、享屬性和操作的機制，它提高了軟件的可重用性。多態(tài)性是指同樣的消息被不同的對象接受時可導(dǎo)致完全不同的行動的現(xiàn)象。本章應(yīng)考點撥：本章在考試中會岀現(xiàn)約1個題目，所占分值大約占2分，是岀題量較小的一章。本章內(nèi) 容比較少，也很簡單，掌握住基本的概念就可以輕松應(yīng)對考試了，所以在這部分丟分，比較可惜。注釋1 :軟件的重用是指在不同的軟件開發(fā)過程中重復(fù)使用相同或相似軟件的過程。3.1軟件工程基本概念1、軟件的相關(guān)概念計算機軟件是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。軟件的特點包括：1）軟件是一種邏輯實體，而不是物理實體，具有抽象性（注釋 1） ; 2）軟件的生 產(chǎn)與硬件不同，它沒有明顯的制作過程； 3）軟件在運

36、行、使用期間不存在磨損、老化問題；4 ）軟件的開發(fā)、運行對計算機系統(tǒng)具有依賴性，受計算機系統(tǒng)的限制，這導(dǎo)致了軟件移植的問題；5）軟件復(fù)雜性高，成本昂貴；6 ）軟件開發(fā)涉及諸多的社會因素（注釋 2 ）。2、軟件危機與軟件工程軟件工程源自軟件危機。所謂軟件危機是泛指在計算機軟件的開發(fā)和維護(hù)過程中所遇到的一系列嚴(yán)重 問題。具體的說，在軟件開發(fā)和維護(hù)過程中，軟件危機主要表現(xiàn)在：1）軟件需求的增長得不到滿足。用戶對系統(tǒng)不滿意的情況經(jīng)常發(fā)生。2）軟件開發(fā)成本和進(jìn)度無法控制。開發(fā)成本超岀預(yù)算，開發(fā)周期大大超過規(guī)定日期的情況經(jīng)常發(fā)生。3）軟件質(zhì)量難以保證。4）軟件不可維護(hù)或維護(hù)程度非常低。5）軟件的成本不斷提

37、高。6）軟件開發(fā)生產(chǎn)率的提高跟不上硬件的發(fā)展和應(yīng)用需求的增長?？傊梢詫④浖C可以歸結(jié)為成本、質(zhì)量、生產(chǎn)率等問題。軟件工程是應(yīng)用于計算機軟件的定義、開發(fā)和維護(hù)的一整套方法、工具、文檔、實踐標(biāo)準(zhǔn)和工序。軟 件工程的目的就是要建造一個優(yōu)良的軟件系統(tǒng)，它所包含的內(nèi)容概括為以下兩點：1）軟件開發(fā)技術(shù)，主要有軟件開發(fā)方法學(xué)、軟件工具、軟件工程環(huán)境。2）軟件工程管理，主要有軟件管理、軟件工程經(jīng)濟(jì)學(xué)。軟件工程的主要思想是將工程化原則運用到軟件開發(fā)過程，它包括3個要素：方法、工具和過程。方法是完成軟件工程項目的技術(shù)手段；工具是支持軟件的開發(fā)、管理、文檔生成；過程支持軟件開發(fā)的各個環(huán) 節(jié)的控制、管理。軟件工

38、程過程是把輸入轉(zhuǎn)化為輸岀的一組彼此相關(guān)的資源和活動。3、軟件生命周期軟件生命周期：軟件產(chǎn)品從提岀、實現(xiàn)、使用維護(hù)到停止使用退役的過程。軟件生命周期分為軟件定義、軟件開發(fā)及軟件運行維護(hù)三個階段：1）軟件定義階段：包括制定計劃和需求分析。制定計劃：確定總目標(biāo)；可行性研究；探討解決方案；制定開發(fā)計劃。需求分析：對待開發(fā)軟件提岀的需求進(jìn)行分析并給岀詳細(xì)的定義。2）軟件開發(fā)階段：軟件設(shè)計：分為概要設(shè)計和詳細(xì)設(shè)計兩個部分。軟件實現(xiàn)：把軟件設(shè)計轉(zhuǎn)換成計算機可以接受的程序代碼。軟件測試：在設(shè)計測試用例的基礎(chǔ)上檢驗軟件的各個組成部分。3）軟件運行維護(hù)階段：軟件投入運行，并在使用中不斷地維護(hù)，進(jìn)行必要的擴(kuò)充和刪改

39、。*:軟件生命周期中所花費最多的階段是軟件運行維護(hù)階段。4、軟件工程的目標(biāo)和與原則（1）軟件工程目標(biāo)：在給定成本、進(jìn)度的前提下，開發(fā)岀具有有效性、可靠性、可理解性、可維護(hù)性、可重用性、可適應(yīng)性、可移植性、可追蹤性和可互操作性且滿足用戶需求的產(chǎn)品。（2）軟件工程需要達(dá)到的基本目標(biāo)應(yīng)是：付岀較低的開發(fā)成本；達(dá)到要求的軟件功能；取得較好的軟 件性能；開發(fā)的軟件易于移植；需要較低的維護(hù)費用；能按時完成開發(fā)，及時交付使用。（3）軟件工程原則：抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗證性。1）抽象：抽象是事物最基本的特性和行為，忽略非本質(zhì)細(xì)節(jié)，采用分層次抽象，自頂向下，逐層細(xì)化 的辦法

40、控制軟件開發(fā)過程的復(fù)雜性。2）信息隱蔽：采用封裝技術(shù)，將程序模塊的實現(xiàn)細(xì)節(jié)隱蔽起來，使模塊接口盡量簡單。3）模塊化：模塊是程序中相對獨立的成分，一個獨立的編程單位，應(yīng)有良好的接口定義。模塊的大小 要適中，模塊過大會使模塊內(nèi)部的復(fù)雜性增加，不利于模塊的理解和修改，也不利于模塊的調(diào)試和重用；模塊太小會導(dǎo)致整個系統(tǒng)表示過于復(fù)雜，不利于控制系統(tǒng)的復(fù)雜性。4）局部化：保證模塊間具有松散的耦合關(guān)系，模塊內(nèi)部有較強的內(nèi)聚性。5）確定性：軟件開發(fā)過程中所有概念的表達(dá)應(yīng)是確定、無歧義且規(guī)范的。6）致性：程序內(nèi)外部接口應(yīng)保持一致，系統(tǒng)規(guī)格說明與系統(tǒng)行為應(yīng)保持一致。7）完備性：軟件系統(tǒng)不丟失任何重要成分，完全實現(xiàn)系

41、統(tǒng)所需的功能。8）可驗證性：應(yīng)遵循容易檢查、測評、評審的原則，以確保系統(tǒng)的正確性。5、軟件開發(fā)工具與軟件開發(fā)環(huán)境（1）軟件開發(fā)工具軟件開發(fā)工具的完善和發(fā)展將促使軟件開發(fā)方法的進(jìn)步和完善，促進(jìn)軟件開發(fā)的高速度和高質(zhì)量。軟 件開發(fā)工具的發(fā)展是從單項工具的開發(fā)逐步向集成工具發(fā)展的，軟件開發(fā)工具為軟件工程方法提供了自動 的或半自動的軟件支撐環(huán)境。同時，軟件開發(fā)方法的有效應(yīng)用也必須得到相應(yīng)工具的支持，否則方法將難 以有效的實施。（2）軟件開發(fā)環(huán)境軟件開發(fā)環(huán)境（或稱軟件工程環(huán)境）是全面支持軟件開發(fā)全過程的軟件工具集合。計算機輔助軟件工程（CASE Computer Aided Software Engin

42、eering ）將各種軟件工具、開發(fā)機器和 一個存放開發(fā)過程信息的中心數(shù)據(jù)庫組合起來，形成軟件工程環(huán)境。它將極大降低軟件開發(fā)的技術(shù)難度并 保證軟件開發(fā)的質(zhì)量。注釋1:軟件的這個特點使它與其它工程對象有著明顯的差異。人們可以把它記錄在存儲介質(zhì)上，但卻無法看到軟件本身的形態(tài)，必須通過觀察、分析、思考、判斷，才能了解它的功能、性能等特性。注釋2:許多軟件的開發(fā)和運行涉及軟件用戶的機構(gòu)設(shè)置，體制問題以及管理方式等，甚至涉及到人們的觀念和心理，軟件知識產(chǎn)權(quán)及法律等問題。3.2結(jié)構(gòu)化分析方法結(jié)構(gòu)化方法的核心和基礎(chǔ)是結(jié)構(gòu)化程序設(shè)計理論。1、需求分析需求分析方法有：1）結(jié)構(gòu)化需求分析方法；2 ）面向?qū)ο蟮姆治?/p>

43、方法。*:需求分析的任務(wù)就是導(dǎo)岀目標(biāo)系統(tǒng)的邏輯模型，解決“做什么”的問題。* :需求分析一般分為需求獲取、需求分析、編寫需求規(guī)格說明書和需求評審四個步驟進(jìn)行。2、結(jié)構(gòu)化分析方法結(jié)構(gòu)化分析方法是結(jié)構(gòu)化程序設(shè)計理論在軟件需求分析階段的應(yīng)用。結(jié)構(gòu)化分析方法的實質(zhì)：著眼于數(shù)據(jù)流，自頂向下，逐層分解，建立系統(tǒng)的處理流程，以數(shù)據(jù)流圖和 數(shù)據(jù)字典為主要工具，建立系統(tǒng)的邏輯模型。結(jié)構(gòu)化分析的常用工具：1）數(shù)據(jù)流圖（DFD; 2）數(shù)據(jù)字典（DD）; 3）判定樹；4）判定表。數(shù)據(jù)流圖以圖形的方式描繪數(shù)據(jù)在系統(tǒng)中流動和處理的過程，它反映了系統(tǒng)必須完成的邏輯功能，是 結(jié)構(gòu)化分析方法中用于表示系統(tǒng)邏輯模型的一種工具。加

44、工數(shù)據(jù)藹存?zhèn)蛭募蠄D是數(shù)據(jù)流圖的基本圖形元素:加工（轉(zhuǎn)換）：輸入數(shù)據(jù)經(jīng)加工變換產(chǎn)生輸岀。數(shù)據(jù)流：沿箭頭方向傳送數(shù)據(jù)的通道，一般在旁邊標(biāo)注數(shù)據(jù)流名存儲文件（數(shù)據(jù)源）：表示處理過程中存放各種數(shù)據(jù)的文件。源，潭：表示系統(tǒng)和環(huán)境的接口，屬系統(tǒng)之外的實體。畫數(shù)據(jù)流圖的基本步驟：自外向內(nèi)，自頂向下，逐層細(xì)化，完善求精。下圖是一個數(shù)據(jù)流圖的示例:II數(shù)據(jù)字典：對所有與系統(tǒng)相關(guān)的數(shù)據(jù)元素的一個有組織的列表，以及精確的、嚴(yán)格的定義，使得用戶 和系統(tǒng)分析員對于輸入、輸岀、存儲成分和中間計算結(jié)果有共同的理解。*:數(shù)據(jù)字典的作用是對數(shù)據(jù)流圖中出現(xiàn)的被命名的圖形元素的確切解釋。* :數(shù)據(jù)字典是結(jié)構(gòu)化分析方法的核心。3、

45、軟件需求規(guī)格說明書（SRS軟件需求規(guī)格說明書是需求分析階段的最后成果，通過建立完整的信息描述、詳細(xì)的功能和行為描述、性能需求和設(shè)計約束的說明、合適的驗收標(biāo)準(zhǔn)，給岀對目標(biāo)軟件的各種需求。3.3結(jié)構(gòu)化設(shè)計方法1、軟件設(shè)計的基礎(chǔ)* :需求分析主要解決“做什么”的問題，而軟件設(shè)計主要解決“怎么做”的問題 從技術(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)換成軟件的過程性描述。從工程角度來看，軟件

46、設(shè)計分兩步完成，即概要設(shè)計和詳細(xì)設(shè)計。概要設(shè)計：又稱結(jié)構(gòu)設(shè)計，將軟件需求轉(zhuǎn)化為軟件體系結(jié)構(gòu)，確定系統(tǒng)級接口、全局?jǐn)?shù)據(jù)結(jié)構(gòu)或數(shù)據(jù)庫模式詳細(xì)設(shè)計：確定每個模塊的實現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用適當(dāng)方法表示算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)。軟件設(shè)計的基本原理包括：抽象、模塊化、信息隱蔽和模塊獨立性。1）抽象。抽象是一種思維工具，就是把事物本質(zhì)的共同特性提取岀來而不考慮其他細(xì)節(jié)。2）模塊化。解決一個復(fù)雜問題時自頂向下逐步把軟件系統(tǒng)劃分成一個個較小的、相對獨立但又不相互 關(guān)聯(lián)的模塊的過程。3）信息隱蔽。每個模塊的實施細(xì)節(jié)對于其他模塊來說是隱蔽的。4）模塊獨立性。軟件系統(tǒng)中每個模塊只涉及軟件要求的具體的子功能，而和軟件系統(tǒng)

47、中其他的模塊的接口是簡單的*:模塊分解的主要指導(dǎo)思想是信息隱蔽和模塊獨立性。模塊的耦合性和內(nèi)聚性是衡量軟件的模塊獨立性的兩個定性指標(biāo)。內(nèi)聚性：是一個模塊內(nèi)部各個元素間彼此結(jié)合的緊密程度的度量。* :按內(nèi)聚性由弱到強排列，內(nèi)聚可以分為以下幾種：偶然內(nèi)聚、邏輯內(nèi)聚、時間內(nèi)聚、過程內(nèi)聚、通 信內(nèi)聚、順序內(nèi)聚及功能內(nèi)聚。耦合性：是模塊間互相連接的緊密程度的度量。* :按耦合性由高到低排列，耦合可以分為以下幾種：內(nèi)容耦合、公共耦合、外部耦合、控制耦合、標(biāo) 記耦合、數(shù)據(jù)耦合以及非直接耦合。一個設(shè)計良好的軟件系統(tǒng)應(yīng)具有高內(nèi)聚、低耦合的特征。在結(jié)構(gòu)化程序設(shè)計中，模塊劃分的原則是：模塊內(nèi)具有高內(nèi)聚度，模塊間具有

48、低耦合度。2、總體設(shè)計（概要設(shè)計）和詳細(xì)設(shè)計（1 ）總體設(shè)計（概要設(shè)計）軟件概要設(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)圖，也稱程序結(jié)構(gòu)圖。程序結(jié)構(gòu)圖的基本圖符：模塊用一個矩形表示，箭頭表示模塊間的調(diào)用關(guān)系。在結(jié)構(gòu)圖中還可以用帶注釋的箭頭表示模塊調(diào)用 過程中來回傳遞的信息。還可用帶實心圓的箭頭表示傳遞的是控制信息，空心圓箭心表示傳遞的是數(shù)據(jù)信 息。o-9一般履塊數(shù)據(jù)信息揑制信慝經(jīng)常使用的結(jié)構(gòu)圖有四種模塊類型：傳入模塊、傳岀模塊、變換模塊和協(xié)調(diào)模塊。其表示形式如下圖:它們的含義分別是：傳入模塊：

49、從下屬模塊取得數(shù)據(jù)，經(jīng)處理再將其傳送給上級模塊。傳岀模塊：從上級模塊取得數(shù)據(jù)，經(jīng)處理再將其傳送給下屬模塊。變換模塊：從上級模塊取得數(shù)據(jù)，進(jìn)行特定的處理，轉(zhuǎn)換成其他形式，再傳送給上級模塊。協(xié)調(diào)模塊：對所有下屬模塊進(jìn)行協(xié)調(diào)和管理的模塊。程序結(jié)構(gòu)圖的例圖及有關(guān)術(shù)語列舉如下：«E1I/ MEO課4* Cl V±L / / 也由?祕pWt|深度：表示控制的層數(shù)。上級模塊、從屬模塊：上、下兩層模塊a和b,且有a調(diào)用b,則a是上級模塊，b是從屬模塊。寬度：整體控制跨度（最大模塊數(shù)的層）的表示。扇入：調(diào)用一個給定模塊的模塊個數(shù)。扇岀：一個模塊直接調(diào)用的其他模塊數(shù)。原子模塊：樹中位于葉子結(jié)點

50、的模塊。面向數(shù)據(jù)流的設(shè)計方法定義了一些不同的映射方法，利用這些方法可以把數(shù)據(jù)流圖變換成結(jié)構(gòu)圖表示 軟件的結(jié)構(gòu)。數(shù)據(jù)流的類型：大體可以分為兩種類型，變換型和事務(wù)型。A、變換型：變換型數(shù)據(jù)處理問題的工作過程大致分為三步，即取得數(shù)據(jù)、變換數(shù)據(jù)和輸出數(shù)據(jù)。變換 型系統(tǒng)結(jié)構(gòu)圖由輸入、中心變換、輸岀三部分組成。B、事務(wù)型：事務(wù)型數(shù)據(jù)處理問題的工作機理是接受一項事務(wù)，根據(jù)事務(wù)處理的特點和性質(zhì)，選擇分派 一個適當(dāng)?shù)奶幚韱卧ㄗ⑨?），然后給岀結(jié)果。（2 ）詳細(xì)設(shè)計詳細(xì)設(shè)計是為軟件結(jié)構(gòu)圖中的每一個模塊確定實現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用某種選定的表達(dá)工具表示 算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)。* :詳細(xì)設(shè)計的任務(wù)是確定實現(xiàn)算法和

51、局部數(shù)據(jù)結(jié)構(gòu)，不同于編碼或編程。常用的過程設(shè)計（即詳細(xì)設(shè)計）工具有以下幾種：圖形工具：程序流程圖、 N-S （方盒圖）、PAD（問題分析圖）和 HIPO （層次圖+輸入/處理/輸出圖） 表格工具：判定表。語言工具：PDL （偽碼）（注釋2）注釋1 :單元是程序中最小的部分，由可以隱含的三部分組成：數(shù)據(jù)輸入、加工和數(shù)據(jù)輸岀。注釋2 : PDL（偽碼）：過程設(shè)計語言，它是用正文形式表示數(shù)據(jù)和處理過程的設(shè)計工具。3.4軟件測試1、 軟件測試定義：使用人工或自動手段來運行或測定某個系統(tǒng)的過程，其目的在于檢驗它是否滿足規(guī) 定的需求或是弄清預(yù)期結(jié)果與實際結(jié)果之間的差別。* :軟件測試的目的：盡可能地多發(fā)現(xiàn)

52、程序中的錯誤，不能也不可能證明程序沒有錯誤。軟件測試的關(guān) 鍵是設(shè)計測試用例（注釋1 ），一個好的測試用例能找到迄今為止尚未發(fā)現(xiàn)的錯誤。2、軟件測試方法：靜態(tài)測試和動態(tài)測試。靜態(tài)測試：包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量。不實際運行軟件，主要通過人工進(jìn)行。 動態(tài)測試：是基于計算機的測試，主要包括白盒測試方法和黑盒測試方法。（1 ）白盒測試白盒測試方法也稱為結(jié)構(gòu)測試或邏輯驅(qū)動測試。它是根據(jù)軟件產(chǎn)品的內(nèi)部工作過程，檢查內(nèi)部成分， 以確認(rèn)每種內(nèi)部操作符合設(shè)計規(guī)格要求。白盒測試的基本原則：保證所測模塊中每一獨立路徑至少執(zhí)行一次；保證所測模塊所有判斷的每一分 支至少執(zhí)行一次；保證所測模塊每一循環(huán)都在邊

53、界條件和一般條件下至少各執(zhí)行一次；驗證所有內(nèi)部數(shù)據(jù) 結(jié)構(gòu)的有效性。*:白盒測試法的測試用例是根據(jù)程序的內(nèi)部邏輯來設(shè)計的，主要用軟件的單元測試， 主要方法有邏輯覆蓋、基本路徑測試等。A、邏輯覆蓋。邏輯覆蓋泛指一系列以程序內(nèi)部的邏輯結(jié)構(gòu)為基礎(chǔ)的測試用例設(shè)計技術(shù)。通常程序中的 邏輯表示有判斷、分支、條件等幾種表示方法。語句覆蓋：選擇足夠的測試用例，使得程序中每一個語句至少都能被執(zhí)行一次。路徑覆蓋：執(zhí)行足夠的測試用例，使程序中所有的可能的路徑都至少經(jīng)歷一次。判定覆蓋：使設(shè)計的測試用例保證程序中每個判斷的每個取值分支（T或F）至少經(jīng)歷一次。條件覆蓋：設(shè)計的測試用例保證程序中每個判斷的每個條件的可能取值至

54、少執(zhí)行一次。判斷-條件覆蓋：設(shè)計足夠的測試用例， 使判斷中每個條件的所有可能取值至少執(zhí)行一次，同時每個判斷的所有可能取值分支至少執(zhí)行一次。* :邏輯覆蓋的強度依次是：語句覆蓋 路徑覆蓋 判定覆蓋 條件覆蓋 判斷-條件覆蓋。B、基本路徑測試。其思想和步驟是，根據(jù)軟件過程性描述中的控制流程確定程序的環(huán)路復(fù)雜性度量， 用此度量定義基本路徑集合，并由此導(dǎo)岀一組測試用例，對每一條獨立執(zhí)行路徑進(jìn)行測試。（2 ）黑盒測試黑盒測試方法也稱為功能測試或數(shù)據(jù)驅(qū)動測試。黑盒測試是對軟件已經(jīng)實現(xiàn)的功能是否滿足需求進(jìn)行 測試和驗證。黑盒測試主要診斷功能不對或遺漏、接口錯誤、數(shù)據(jù)結(jié)構(gòu)或外部數(shù)據(jù)庫訪問錯誤、性能錯誤、初始化

55、 和終止條件錯誤。黑盒測試不關(guān)心程序內(nèi)部的邏輯，只是根據(jù)程序的功能說明來設(shè)計測試用例，主要方法有等價類劃分 法、邊界值分析法、錯誤推測法等，主要用軟件的確認(rèn)測試。A、等價類劃分法。這是一種典型的黑盒測試方法，它是將程序的所有可能的輸入數(shù)據(jù)劃分成若干部分 （及若干等價類），然后從每個等價類中選取數(shù)據(jù)作為測試用例。B、邊界值分析法。它是對各種輸入、輸岀范圍的邊界情況設(shè)計測試用例的方法。C錯誤推測法。人們可以靠經(jīng)驗和直覺推測程序中可能存在的各種錯誤，從而有針對性地編寫檢查這 些錯誤的用例。3、軟件測試過程一般按 4個步驟進(jìn)行：單元測試、集成測試、確認(rèn)測試和系統(tǒng)測試。（1 ）單元測試單元測試是對軟件設(shè)計的最小單位一一模塊（程序單元）進(jìn)行正確性檢測的測試，目的是發(fā)現(xiàn)各模塊 內(nèi)部可能存在的各種錯誤。單元測試根據(jù)程序的內(nèi)部結(jié)構(gòu)來設(shè)計測試用例，其依據(jù)是詳細(xì)設(shè)計說明書和源程序。單元測試的技術(shù) 可以采用靜態(tài)分析和動態(tài)測試。對動態(tài)測試通常以白盒測試為主，輔之以黑盒測試。單元測試的內(nèi)容包括：模塊接口測試、局部數(shù)據(jù)結(jié)構(gòu)測試、錯誤處理測試和邊界測試。*:在進(jìn)行單元測試時，要用一些輔助模塊去模擬與被測模塊相聯(lián)系的其他模塊，即為被測模塊設(shè)計和 搭建驅(qū)動模塊和樁模塊