二級公共基礎(chǔ)知識輔導(dǎo)講義

全國計算機等級考試一一二級公共基礎(chǔ)學(xué)問教程

第一章數(shù)據(jù)結(jié)構(gòu)與算法

1.1算法

1、邈是指解題方案的精確而完整的描述。換句話說，算法是對特定問題求解步驟

的一種描述。

批注［WX1］：這是因為：在編寫程序時要受到計算機系

*:算法不等于程序，也不等于計算方法。程序的編制不行能優(yōu)于算法的設(shè)計」

統(tǒng)運行環(huán)境的限制，程序通常還要考慮很多與方法和分

析無關(guān)的細(xì)微環(huán)節(jié)問題。

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)輸入

不夠或輸入錯誤時，算法將無法執(zhí)行或執(zhí)行有錯。一般說來，當(dāng)算法擁有足夠的情

報時，此算法才是有效的；而當(dāng)供應(yīng)的情報不夠時，算法可能無效。

*：綜上所述，所謂算法，是一組嚴(yán)謹(jǐn)?shù)囟x運算依次的規(guī)則，并且每一個規(guī)則都是

有效的，且是明確的，此依次將在有限的次數(shù)下終止。

3、算法困難度主要包括時間困難度和空間困難度。

(1)算法|時間困難度|是指執(zhí)行算法所須要的計算工作量,可以用執(zhí)行算法的過程中

所需基本運算的執(zhí)行次數(shù)來度量=

(2)算法臣面麻闔是指執(zhí)行這個算法所須要的內(nèi)存空間。

1.2數(shù)據(jù)結(jié)構(gòu)的基本概念

1、幽蜓樹是指相互有關(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)系一批注[wx2]:前后件關(guān)系：一般狀況下，在具有相同特

征的數(shù)據(jù)元素集合中，各個數(shù)據(jù)元素之間存在某種關(guān)系

（即聯(lián)系），這種關(guān)系反映了該集合中的數(shù)據(jù)元素所固

（2）在對數(shù)據(jù)進(jìn)行處理時，各數(shù)據(jù)元素在計算機中的存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)。

有的一種結(jié)構(gòu)。在數(shù)據(jù)處理領(lǐng)域中，通常把數(shù)據(jù)元素之

數(shù)據(jù)的存儲結(jié)構(gòu)有依次、鏈接、索引等。間這種固有的關(guān)系簡潔地用前后件關(guān)系（即干脆前驅(qū)與

干脆后繼關(guān)系）來描述。

1）依次存儲。它是把邏輯上相鄰的結(jié)點存儲在物理位置相鄰的存儲單元里，結(jié)點間

的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。由此得到的存儲表示稱為依次存儲結(jié)構(gòu)。

2）鏈接存儲。它不要求邏輯上相鄰的結(jié)點在物理位置上亦相鄰，結(jié)點間的邏輯關(guān)系

是由附加的指針字段表示的。由此得到的存儲表示稱為鏈?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)系，

對于關(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)每一個結(jié)批注[wx3]:在數(shù)據(jù)結(jié)構(gòu)中，沒有前件的結(jié)點稱為根結(jié)

點。

點最多有一個前件，也最多有一個后件。

*：常見的線性結(jié)構(gòu)有線性表、棧、隊列和線性鏈表等。

(2)|非線性結(jié)構(gòu)不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。

*：常見的非線性結(jié)構(gòu)有樹、二叉樹和圖等。

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)健?/p>

2、線性表的依次存儲結(jié)構(gòu)具有兩個基本特點：(1)線性表中全部元素所占的存儲

空間是連續(xù)的；(2)線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯依次依次存放的。

*：由此可以看出，在線性表的依次存儲結(jié)構(gòu)中，其前后件兩個元素在存儲空間中是

緊鄰的，且前件元素確定存儲在后件元素的前面，可以通過計算機干脆確定第i個結(jié)

點的存儲地址。

3、依次表的插入、刪除運算

(1)依次表的插入運算：在一般狀況下，要在第i(l<i<n)個元素之前插入一個

新元素時，首先要從最終一個(即第n個)元素起先，直到第i個元素之間共n-i+1

個元素依次向后移動一個位置，移動結(jié)束后，第i個位置就被空出，然后將新元素插

入到第i項。插入結(jié)束后，線性表的長度就增加了1。

：順性表的插入運算時須要移動元素，在等概率狀況下，平均須要移動n/2個元素。

（2）依次表的刪除運算：在一般狀況下，要刪除第i（iViVn）個元素時，則要從

第i+1個元素起先，直到第n個元素之間共n-i個元素依次向前移動一個位置。刪

除結(jié)束后，線性表的長度就減小了1。

*：進(jìn)行順性表的刪除運算時也須要移動元素，在等概率狀況下，平均須要移動（n-1）

/2個元素。插入、刪除運算不便利。

1.4棧和隊列

1、棧與其基本運算

周是限定在一端進(jìn)行插入與刪除運算的線性表。

在棧中，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。

棧頂元素總是最終被插入的元素，棧底元素總是最先被插入的元素。即棧是依據(jù)“先

進(jìn)后出”或“后進(jìn)先出”的原則組織數(shù)據(jù)的。

棧具有記憶作用。

棧的基本運算：1）插入元素稱為入棧運算；2）刪除元素稱為退棧運算；3）讀棧

頂元素是將棧頂元素賦給一個指定的變量，此時指針無變更。

棧的存儲方式和線性表類似，也有兩種，即依次棧和鏈?zhǔn)綏！?/p>

2、隊列與其基本運算

瓦列是指允許在一端（隊尾）進(jìn)入插入，而在另一端（隊頭）進(jìn)行刪除的線性表。

尾指針（Rear）指向隊尾元素，頭指針（front）指向排頭元素的前一個位置（隊頭）。

隊列是“先進(jìn)先出”或“后進(jìn)后出”的線性表。

隊列運算包括：1）入隊運算：從隊尾插入一個元素；2）退隊運算：從隊頭刪除一

個元素。

循環(huán)隊列與其運算：所謂循環(huán)隊列，就是將隊列存儲空間的最終一個位置繞到第一

個位置，形成邏輯上的環(huán)狀空間，供隊列循環(huán)運用。在循環(huán)隊列中，用隊尾指針rear

指向隊列中的隊尾元素，用排頭指針front指向排頭元素的前一個位置，因此，從

頭指針front指向的后一個位置直到隊尾指針rear指向的位置之間，全部的元素均

為隊列中的元素。

*：循環(huán)隊列中元素的個數(shù)=3@＞紅0出。

1.5線性鏈表

1、線性表依次存儲的缺點：（1）插入或刪除的運算效率很低。在依次存儲的線性

表中，插入或刪除數(shù)據(jù)元素時須要移動大量的數(shù)據(jù)元素；（2）線性表的依次存儲結(jié)

構(gòu)下，線性表的存儲空間不便于擴充；（3）線性表的依次存儲結(jié)構(gòu)不便于對存儲空

間的動態(tài)安排。

2、線性鏈表：線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表，是一種物理存儲單元上非連續(xù)、

非依次的存儲結(jié)構(gòu),數(shù)據(jù)元素的邏輯依次是通過鏈表中的指針鏈接來實現(xiàn)的。因此，

在鏈?zhǔn)酱鎯Ψ绞街校總€結(jié)點由兩部分組成：一部分用于存放數(shù)據(jù)元素的值，稱為

數(shù)據(jù)域；另一部分用于存放指針，稱為指針域，用于指向該結(jié)點的前一個或后一個

結(jié)點（即前件或后件）

線性鏈表分為單鏈表、雙向鏈表和循環(huán)鏈表三種類型。

在單鏈表中，每一個結(jié)點只有一個指針域，由這個指針只能找到其后件結(jié)點，而不

能找到其前件結(jié)點。因此，在某些應(yīng)用中，對于線性鏈表中的每個結(jié)點設(shè)置兩個指

針，一個稱為左指針，指向其前件結(jié)點；另一個稱為右指針，指向其后件結(jié)點，這

種鏈表稱為雙向鏈表

3、線性鏈表的基本運算

（1）在線性鏈表中包含指定元素的結(jié)點之前插入一個新元素。

*：在線性鏈表中插入元素時，不須要移動數(shù)據(jù)元素，只須要修改相關(guān)結(jié)點指針即可，

也不會出現(xiàn)上溢］'現(xiàn)象.批注［wx4］:當(dāng)為一個線性表安排依次存儲結(jié)構(gòu)后，假

如出現(xiàn)線性表的存儲空間已滿，但還須要插入新的元素

時，就會發(fā)生“上溢”現(xiàn)象。

（2）在線性鏈表中刪除包含指定元素的結(jié)點。

*:在線性鏈表中刪除元素時，也不須要移動數(shù)據(jù)元素，只須要修改相關(guān)結(jié)點指針即

可。

(3)將兩個線性鏈表按要求合并成一個線性鏈表。

(4)將一個線性鏈表按要求進(jìn)行分解。

(5)逆轉(zhuǎn)線性鏈表。

(6)復(fù)制線性鏈表。

(7)線性鏈表的排序。

(8)線性鏈表的查找。

*：線性鏈表不能隨機存取:批注[wx5]:在鏈表中，即使知道被訪問結(jié)點的序號i,

也不能像依次表中那樣干脆按序號i訪問結(jié)點，而只能

從鏈表的頭指針動身，順著鏈域逐個結(jié)點往下搜尋，直

4、循環(huán)鏈表與其基本運算

至搜尋到第i個結(jié)點為止。因此，鏈表不是隨機存儲結(jié)

構(gòu)。

在線性鏈表中，其插入與刪除的運算雖然比較便利，但還存在一個問題，在運算過

程中對于空表和對第一個結(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)成了一個環(huán)狀

鏈。

循環(huán)鏈表的優(yōu)點主要體現(xiàn)在兩個方面：一是在循環(huán)鏈表中，只要指出表中任何一個

結(jié)點的位置，就可以從它動身訪問到表中其他全部的結(jié)點，而線性單鏈表做不到這

一點；二是由于在循環(huán)鏈表中設(shè)置了一個表頭結(jié)點，在任何狀況下，循環(huán)鏈表中至

少有一個結(jié)點存在，從而使空表與非空表的運算統(tǒng)一。

*:循環(huán)鏈表是在單鏈表的基礎(chǔ)上增加了一個表頭結(jié)點，其插入和刪除運算與單鏈表

相同。但它可以從任一結(jié)點動身來訪問表中其他全部結(jié)點，并實現(xiàn)空表與非空表的

運算的統(tǒng)一。

1.6樹與二叉樹

1、樹的基本概念

網(wǎng)是一種簡潔的非線性結(jié)構(gòu)。在樹這種數(shù)據(jù)結(jié)構(gòu)中，全部數(shù)據(jù)元素之間的關(guān)系具有

明顯的層次特性。

在樹結(jié)構(gòu)中，每一個結(jié)點只有一個前件，稱為|父結(jié)點沒有前件的結(jié)點只有一個，

稱為樹的根結(jié)點，簡稱樹的根。每一個結(jié)點可以有多個后件，稱為該結(jié)點的另邈。

沒有后件的結(jié)點稱為|葉子結(jié)點

在樹結(jié)構(gòu)中，一個結(jié)點所擁有的后件的個數(shù)稱為該|結(jié)點的周,全部結(jié)點中最大的度

稱為|樹的度樹的最大層次稱為|樹的深度。

2、二叉樹與其基本性質(zhì)

（1）什么是二叉樹

|二叉樹|是一種很有用的非線性結(jié)構(gòu),它具有以下兩個特點：1）非空二叉樹只有一個

根結(jié)點；2）每一個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹與右子樹。

*:依據(jù)二叉樹的概念可知，二叉樹的度可以為0（葉結(jié)點）、1（只有一棵子樹）

或2（有2棵子樹）。?日?

（2）二叉樹的基本性質(zhì)

性質(zhì)1在二叉樹的第k層上，最多有個結(jié)點。

性質(zhì)2深度為m的二叉樹葬個個結(jié)點。

性質(zhì)3在隨意一棵二叉樹中匚莒了的丘土千葉子軍君總、比度為2的結(jié)點

多一個。性質(zhì)4具有n個結(jié)點的二叉樹,其深度至少為，其中表

示取的整數(shù)部分。

3、滿二叉樹與完全二叉樹

滿二叉樹：除最終一層外，每一層上的全部結(jié)點都有兩個子結(jié)點。

完全二叉樹：除最終一層外，每一層上的結(jié)點數(shù)均達(dá)到最大值；在最終一層上只缺

少右邊的若干結(jié)點。

*：依據(jù)完全二叉樹的定義可得出：度為1的結(jié)點的個數(shù)為。或1。

完全二叉樹還具有如下兩個特性：

性質(zhì)5具有n個結(jié)點的完全二叉匚。

性質(zhì)6設(shè)完全二叉樹共有n個結(jié)點，假如從根結(jié)點起先，按層序（每一層從左到

右）用自然數(shù)1,2,n給結(jié)點進(jìn)行編號，則對于編號為k（k=l,2,…，n）

的結(jié)點有以下結(jié)論：

①若k=l,則該結(jié)點為根結(jié)點，它沒有父結(jié)點；若k>l,則該結(jié)點的父結(jié)點的編號

為INT（k/2）o

②若2kVn,則編號為k的左子結(jié)點編號為2k;否則該結(jié)點無左子結(jié)點（明顯也沒

有右子結(jié)點）。

③若2k+l<n,則編號為k的右子結(jié)點編號為2k+l;否則該結(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)行依次存儲仁批注[wx6]:這樣，不僅節(jié)約了存儲空間，又能便利地

確定每一個結(jié)點的父結(jié)點與左右子結(jié)點的位置，但依次

存儲結(jié)構(gòu)對于一般的二叉樹不適用。

5、二叉樹的遍歷

二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的全部結(jié)點。二叉樹的遍歷可以分為以下

三種：

(1)前序遍歷(DLR):若二叉樹為空，則結(jié)束返回。否則：首先訪問根結(jié)點，然

后遍歷左子樹，最終遍歷右子樹；并且，在遍歷左右子樹時，仍舊先訪問根結(jié)點，

然后遍歷左子樹，最終遍歷右子樹。

(2)中序遍歷(LDR):若二叉樹為空，則結(jié)束返回。否則：首先遍歷左子樹，然

后訪問根結(jié)點，最終遍歷右子樹；并且，在遍歷左、右子樹時，仍舊先遍歷左子樹，

然后訪問根結(jié)點，最終遍歷右子樹。

(3)后序遍歷(LRD):若二叉樹為空，則結(jié)束返回。否則：首先遍歷左子樹，然

后遍歷右子樹，最終訪問根結(jié)點，并且，在遍歷左、右子樹時，仍舊先遍歷左子樹，

然后遍歷右子樹，最終訪問根結(jié)點。

1.7查找技術(shù)

查找：依據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素。

查找結(jié)果：(查找勝利：找到；查找不勝利：沒找到。)

平均查找長度：查找過程中關(guān)鍵字和給定值比較的平均次數(shù)。

1、依次查找

基本思想：從表中的第一個元素起先，將給定的值與表中逐個元素的關(guān)鍵字進(jìn)行比

較，直到兩者相符，查到所要找的元素為止。否則就是表中沒有要找的元素，查找

不勝利。

在平均狀況下，利用依次查找法在線性表中查找一個元素，大約要與線性表中一半

的元素進(jìn)行比較，最壞狀況下須要比較n次。

依次查找一個具有n個元素的線性表，其平均困難度為O（n）。

下列兩種狀況下只能接受依次查找：

1）假如線性表是無序表（即表中的元素是無序的），則不管是依次存儲結(jié)構(gòu)還是鏈

式存儲結(jié)構(gòu)，都只能用依次查找。

2）即使是有序線性表，假如接受鏈?zhǔn)酱鎯Y(jié)構(gòu)，也只能用依次查找。

2、二分法查找

思想：先確定待查找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認(rèn)找不到

該記錄為止。

前提：必需在具有依次存儲結(jié)構(gòu)的有序表中進(jìn)行。

查找過程：

1）若中間項（中間項mid=（n-l）/2,mid的值四舍五入取整）的值等于x,則說明

已查到；

2）若x小于中間項的值，則在線性表的前半部分查找；

3）若x大于中間項的值，則在線性表的后半部分查找。

特點：比依次查找方法效率高。最壞的狀況下，須要比較log2n次。

*：二分法查找只適用于依次存儲的線性表,且表中元素必需按關(guān)鍵字有序（升序）

排列。對于無序線性表和線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)只能用依次查找。在長度為n的有〔批注「X7”允許相鄰元素值相等

序線性表中進(jìn)行二分法查找，其時間困難度為O（1。82找。

1.8排序技術(shù)

排序是指將一個無序序列整理成按值非遞減依次排列的有序序列，即是將無序的記

錄序列調(diào)整為有序記錄序列的一種操作。

1、交換類排序法（方法：冒泡排序，快速排序）。

2、插入類排序法（方法：簡潔插入排序，希爾排序）。

3、選擇類排序法（方法：簡潔選擇排序，堆排序）。

總結(jié)：各種排序法比較:

類別排序方法基本思想時間復(fù)雜度

冒泡排序相鄰元素比較，不滿足條件時交換心-1）般

交換類

快速排序選擇基準(zhǔn)元素，通過交換，劃分成兩個子序列O(nlo&n)

待排序的元素看成為一個有序表和一個無序表，

簡單插入排序心-1）般

插入類將無序表中元素插入到有序表中

希爾排序分割成若干個子序列分別進(jìn)行直接插入排序O(n1J)

掃描整個線性表，從中選出最小的元素，將它交

簡單選擇排序心-1）總

換到表的最前面

選擇類

選建堆，然后將堆頂元素與堆中最后一個元素交

堆排序O(n]ogjn)

換，再調(diào)整為堆

本章應(yīng)考點撥：本章內(nèi)容在筆試中會出現(xiàn)5-6個題目，是公共基礎(chǔ)學(xué)問部分出題量

比較多的一章，所占分值也比較大，約10分。

其次章程序設(shè)計基礎(chǔ)

2.1程序設(shè)計風(fēng)格0

程序設(shè)計的風(fēng)格主要強調(diào)：“清楚第一，效率其次上要應(yīng)留意和考慮下述一些因批注[wx8]:“清楚第一，效率其次”是當(dāng)今主導(dǎo)的程

序設(shè)計風(fēng)格。

素：

（1）源程序文檔化。

1）符號名的命名。符號名能反映它所代表的實際東西，應(yīng)有確定的實際含義。

2）程序的注釋。分為序言性注釋和功能性注釋。

序言性注釋：位于程序開頭部分，包括程序標(biāo)題、程序功能說明、主要算法、接口

說明、程序位置、開發(fā)簡歷、程序設(shè)計者、復(fù)審者、復(fù)審日期與修改日期等。

功能性注釋：嵌在源程序體之中，用于描述其后的語句或程序的主要功能。

3）視覺組織。利用空格、空行、縮進(jìn)等技巧使程序?qū)哟吻宄?/p>

（2）數(shù)據(jù)說明。1）數(shù)據(jù)說明的次序規(guī)范化；2）說明語句中變量支配有序化；3）

運用注釋來說明困難數(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）避開接受困難的條件語句；9）盡量削減運用“否定”條件語句；10）

數(shù)據(jù)結(jié)構(gòu)要有利于程序的簡化；11）要模塊化，使模塊功能盡可能單一化；12）利

用情息隱藏確保健二個模塊的獨實性匚13）從數(shù)據(jù)動身去構(gòu)造程曲_14）不要修批注[wx9]:信息隱藏是指接受封裝技術(shù)，將程序模塊

的實施細(xì)微環(huán)節(jié)隱藏起來，使模塊接口盡量簡潔.即指

在設(shè)計和確定模塊時，使得一個模塊內(nèi)包含的信息（過

補不好的程序，要重新編寫。

程或數(shù)據(jù)），對于不須要這些信息的其它模塊來說，是

不能訪問的。

（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è)計輸出報表格式。

2.2結(jié)構(gòu)化程序設(shè)計（面對過程的程序設(shè)計方法）

1、結(jié)構(gòu)化程序設(shè)計方法的主要原則可以概括為：自頂向下,逐步求精,模塊化,?

制運用goto語句。

（1）自頂向下。程序設(shè)計時，應(yīng)先考慮總體，后考慮細(xì)微環(huán)節(jié)；先考慮全局目標(biāo)，

后考慮局部目標(biāo)。不要一起先就過多追求眾多的細(xì)微環(huán)節(jié)，先從最上層總目標(biāo)起先

設(shè)計，逐步使問題具體化。

（2）逐步求精。對困難問題，應(yīng)設(shè)計一些子目標(biāo)作過渡，逐步細(xì)化。

（3）模塊化。一個困難問題，確定是由若干稍簡潔的問題構(gòu)成。模塊化是把程序要

解決的總目標(biāo)分解為分目標(biāo)，再進(jìn)一步分解為具體的小目標(biāo)，把每個小目標(biāo)稱為一

個模塊。

（4）限制運用got。語句。

2、結(jié)構(gòu)化程序的基本結(jié)構(gòu)：依次結(jié)構(gòu),選擇結(jié)構(gòu),重復(fù)結(jié)構(gòu)。

1）依次結(jié)構(gòu)。一種簡潔的程序設(shè)計，即依據(jù)程序語句行的自然依次，一條語句一條

語句地執(zhí)行程序，它是最基本、最常用的結(jié)構(gòu)。

2）選擇結(jié)構(gòu)。又稱分支結(jié)構(gòu)，包括簡潔選擇和多分支選擇結(jié)構(gòu)，可依據(jù)條件，推斷

應(yīng)當(dāng)選擇哪一條分支來執(zhí)行相應(yīng)的語句序列。

3）重復(fù)結(jié)構(gòu)。又稱循環(huán)結(jié)構(gòu),可依據(jù)給定的條件，推斷是否須要重復(fù)執(zhí)行某一相同

的或類似的程序段。

僅僅運用依次、選擇和循環(huán)三種基本限制結(jié)構(gòu)就足以表達(dá)各種其他形式結(jié)構(gòu)，從而

實現(xiàn)任何單入口/單出口的程序。

2.3面對對象的程序設(shè)計

客觀世界中任何一個事物都可以被看成是一個對象，面對對象方法的本質(zhì)就是主見

從客觀世界固有的事物動身來構(gòu)造系統(tǒng)，提倡人們在現(xiàn)實生活中常用的思維來相識、

理解和描述客觀事物,強調(diào)最終建立的系統(tǒng)能夠映射問題域。也就是說，系統(tǒng)中的

對象與對象之間的關(guān)系能夠照實地反映問題域中固有的事物與其關(guān)系。

面對對象方法的主要優(yōu)點：（1）與人類習(xí)慣的思維方法一樣;（2）穩(wěn)定性好;（3）

可重用性好；（4）易于開發(fā)大型軟件產(chǎn)品；（5）可維護(hù)性好。批注［wxis：軟件的：用非旨在不同的軟件開發(fā)過程

*:面對對象的程序設(shè)計主要考慮的是提高軟件的可重用性。

四是面對對象方法中最基本的概念，可以用來表示客觀世界中的任何實體，對象

是實體的抽象。面對對象的程序設(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)在本質(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)模塊獨立性好。對象是面對對象的軟件的基本模塊，它是由數(shù)據(jù)與可以對這些

數(shù)據(jù)施加的操作所組成的統(tǒng)一體，而且對象是以數(shù)據(jù)為中心的，操作圍繞對其數(shù)據(jù)

所需做的處理來設(shè)置，沒有無關(guān)的操作。從模塊的獨立性考慮，對象內(nèi)部各種元素

彼此結(jié)合得很緊密，內(nèi)聚性強。

國是指具有共同屬性、共同方法的對象的集合。所以類是對象的抽象，對象是對應(yīng)

類的一個實例。

逋是一個實例與另一個實例之間傳遞的信息。消息的組成包括：(1)接收消息的

對象的名稱；(2)消息標(biāo)識符，也稱消息名；(3)零個或多個參數(shù)。

*:在面對對象方法中，一個對象懇求另一個對象為其服務(wù)的方式是通過發(fā)送消息。

邈是指能夠干脆獲得已有的性質(zhì)和特征，而不必重復(fù)定義他們。繼承分單繼承和

多重繼承。單繼承指一個類只允許有一個父類，多重繼承指一個類允許有多個父類。

*:類的繼承性是類之間共享屬性和操作的機制，它提高了軟件的可重用性。

多態(tài)樹是指同樣的消息被不同的對象接受時可導(dǎo)致完全不同的行動的現(xiàn)象。

本章應(yīng)考點撥：本章在考試中會出現(xiàn)約1個題目，所占分值大約占2分，是出題量

較小的一章。本章內(nèi)容比較少，也很簡潔，駕馭住基本的概念就可以輕松應(yīng)對考試

了，所以在這部分丟分，比較惋惜。

第三章軟件工程基礎(chǔ)

3.1軟件工程基本概念

1、軟件的相關(guān)概念

計算機軟件是包括程序、數(shù)據(jù)與相關(guān)文檔的完整集合。

軟件的特點包括：1）版件是一種邏輯實體，而不是物理實體，具有抽象榭；2）軟批注［WX11］：軟件的這個特點使它與其它工程對象有

著明顯的差異。人們可以把它記錄在存儲介質(zhì)上，但卻

無法看到軟件本身的形態(tài)，必需通過視察、分析、思索、

件的生產(chǎn)與硬件不同，它沒有明顯的制作過程；3）軟件在運行、運用期間不存在磨

推斷，才能了解它的功能、性能等特性。

損、老化問題；4）軟件的開發(fā)、運行對計算機系統(tǒng)具有依靠性，受計算機系統(tǒng)的限

制，這導(dǎo)致了軟件移植的問題；5）軟件困難性高，成本昂貴；6）歌件開發(fā)涉與諸

多的社會因素|。批注［WX12］:很多軟件的開發(fā)和運行涉及軟件用戶的

機構(gòu)設(shè)置，體制問題以及管理方式等，甚至涉及到人們

的觀念和心理，軟件學(xué)問產(chǎn)權(quán)及法律等問題。（學(xué)吧學(xué)

2、軟件危機與軟件工程

吧獨家稿件）

軟件工程源自軟件危機。所謂軟件危機是泛指在計算機軟件的開發(fā)和維護(hù)過程中所

遇到的一系列嚴(yán)峻問題。具體的說，在軟件開發(fā)和維護(hù)過程中，軟件危機主要表現(xiàn)

在：

1）軟件需求的增長得不到滿足。用戶對系統(tǒng)不滿足的狀況常常發(fā)生。

2）軟件開發(fā)成本和進(jìn)度無法限制。開發(fā)成本超出預(yù)算，開發(fā)周期大大超過規(guī)定日期

的狀況常常發(fā)生。

3）軟件質(zhì)量難以保證。

4）軟件不行維護(hù)或維護(hù)程度特別低。

5）軟件的成本不斷提高。

6）軟件開發(fā)生產(chǎn)率的提高跟不上硬件的發(fā)展和應(yīng)用需求的增長。

總之，可以將軟件危機可以歸結(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)濟學(xué)。

軟件工程的主要思想是將工程化原則運用到軟件開發(fā)過程,它包括3個要素：方法、

工具和過程。方法是完成軟件工程項目的技術(shù)手段；工具是支持軟件的開發(fā)、管理、

文檔生成；過程支持軟件開發(fā)的各個環(huán)節(jié)的限制、管理。

軟件工程過程是把揄A轉(zhuǎn)化為輸出的一組彼此相關(guān)的資源和活動。

3、軟件生命周期

軟件生命周期卜軟件產(chǎn)品從提出、實現(xiàn)、運用維護(hù)到停止運用退役的過程。

軟件生命周期分為軟件定義、軟件開發(fā)與軟件運行維護(hù)三個階段:

1）軟件定義階段：包括制定支配和需求分析。

制定支配：確定總目標(biāo)；可行性探討；探討解決方案；制定開發(fā)支配。

需求分析：對待開發(fā)軟件提出的需求進(jìn)行分析并給出具體的定義。

2）軟件開發(fā)階段：

軟件設(shè)計：分為概要設(shè)計和具體設(shè)計兩個部分。

軟件實現(xiàn)：把軟件設(shè)計轉(zhuǎn)換成計算機可以接受的程序代碼。

軟件測試：在設(shè)計測試用例的基礎(chǔ)上檢驗軟件的各個組成部分。

3）軟件運行維護(hù)階段：軟件投入運行，并在運用中不斷地維護(hù)，進(jìn)行必要的擴充和

刪改。

:軟件生命周期中所花費最多的階段是軟件運行維護(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ì)微環(huán)節(jié)，接受分層次抽象,

自頂向下，逐層細(xì)化的方法限制軟件開發(fā)過程的困難性。

2)|信息隱藏|：接受封裝技術(shù)，將程序模塊的實現(xiàn)細(xì)微環(huán)節(jié)隱藏起來，使模塊接口盡

量簡潔。

3)|模塊批模塊是程序中相對獨立的成分，一個獨立的編程單位，應(yīng)有良好的接口

定義。模塊的大小要適中，模塊過大會使模塊內(nèi)部的困難性增加，不利于模塊的理

解和修改，也不利于模塊的調(diào)試和重用；模塊太小會導(dǎo)致整個系統(tǒng)表示過于困難，

不利于限制系統(tǒng)的困難性。

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)系統(tǒng)所需的功能。

8)|可驗證樹:應(yīng)遵循簡潔檢查、測評、評審的原則，以確保系統(tǒng)的正確性。

5、軟件開發(fā)工具與軟件開發(fā)環(huán)境

⑴軟件開發(fā)工具

軟件開發(fā)工具的完善和發(fā)展將促使軟件開發(fā)方法的進(jìn)步和完善，促進(jìn)軟件開發(fā)的高

速度和高質(zhì)量。軟件開發(fā)工具的發(fā)展是從單項工具的開發(fā)逐步向集成工具發(fā)展的，

軟件開發(fā)工具為軟件工程方法供應(yīng)了自動的或半自動的軟件支撐環(huán)境。同時，軟件

開發(fā)方法的有效應(yīng)用也必需得到相應(yīng)工具的支持，否則方法將難以有效的實施。

(2)軟件開發(fā)環(huán)境

軟件開發(fā)環(huán)境(或稱軟件工程環(huán)境)是全面支持軟件開發(fā)全過程的軟件工具集合。

計算機協(xié)助軟件工程(CASE,ComputerAidedSoftwareEngineering)將各種

軟件工具、開發(fā)機器和一個存放開發(fā)過程信息的中心數(shù)據(jù)庫組合起來，形成軟件工

程環(huán)境。它將極大降低軟件開發(fā)的技術(shù)難度并保證軟件開發(fā)的質(zhì)量。

3.2結(jié)構(gòu)化分析方法

結(jié)構(gòu)化方法的核心和基礎(chǔ)是結(jié)構(gòu)化程序設(shè)計理論。

1、需求分析

需求分析方法有：1)結(jié)構(gòu)化需求分析方法；2)面對對象的分析方法。

*：|需求分析|的任務(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ù)在系統(tǒng)中流淌和處理的過程，它反映了系統(tǒng)必需完

成的邏輯功能，是結(jié)構(gòu)化分析方法中用于表示系統(tǒng)邏輯模型的一種工具。

上圖是數(shù)據(jù)流圖的基本圖形元素：

甌（轉(zhuǎn)換）：輸入數(shù)據(jù)經(jīng)加工變換產(chǎn)生輸出。

數(shù)據(jù)流沿箭頭方向傳送數(shù)據(jù)的通道，一般在旁邊標(biāo)注數(shù)據(jù)流名。

存儲文件I（數(shù)據(jù)源）：表示處理過程中存放各種數(shù)據(jù)的文件。

源，潭表示系統(tǒng)和環(huán)境的接口，屬系統(tǒng)之外的實體。

畫數(shù)據(jù)流圖的基本步驟：自外向內(nèi)，自頂向下，逐層細(xì)化，完善求精。

數(shù)據(jù)字典對全部與系統(tǒng)相關(guān)的數(shù)據(jù)元素的一個有組織的列表，以與精確的、嚴(yán)格

的定義，使得用戶和系統(tǒng)分析員對于輸入、輸出、存儲成分和中間計算結(jié)果有共同

的理解。

*:數(shù)據(jù)字典的作用是對數(shù)據(jù)流圖中出現(xiàn)的被命名的圖形元素的準(zhǔn)確說明。

*:數(shù)據(jù)字典是結(jié)構(gòu)化分析方法的核心。

3、軟件需求規(guī)格說明書（SRS）

軟件需求規(guī)格說麻闈是需求分析階段的最終成果,通過建立完整的信息描述、具體

的功能和行為描述、性能需求和設(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)換成軟件的過程性描述。

從工程角度來看，軟件設(shè)計分兩步完成，即概要設(shè)計和具體設(shè)計。

概要設(shè)計又稱結(jié)構(gòu)設(shè)計，將軟件需求轉(zhuǎn)化為軟件體系結(jié)構(gòu)，確定系統(tǒng)級接口、全

局?jǐn)?shù)據(jù)結(jié)構(gòu)或數(shù)據(jù)庫模式。

具體設(shè)計確定每個模塊的實現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用適當(dāng)方法表示算法和數(shù)據(jù)

結(jié)構(gòu)的細(xì)微環(huán)節(jié)。

軟件設(shè)計的基本原理包括：抽象、模塊化、信息隱藏和模塊獨立性。

1）抽象。抽象是一種思維工具，就是把事物本質(zhì)的共同特性提取出來而不考慮其他

細(xì)微環(huán)節(jié)。

2）模塊化。解決一個困難問題時自頂向下逐步把軟件系統(tǒng)劃分成一個個較小的、相

對獨立但又不相互關(guān)聯(lián)的模塊的過程。

3）信息隱藏。每個模塊的實施細(xì)微環(huán)節(jié)對于其他模塊來說是隱藏的。

4）模塊獨立性。軟件系統(tǒng)中每個模塊只涉與軟件要求的具體的子功能，而和軟件系

統(tǒng)中其他的模塊的接口是簡潔的。

*：模塊分解的主要指導(dǎo)思想是信息隱藏和模塊獨立性。

模塊的耦合性和內(nèi)聚性是衡量軟件的模塊獨立性的兩個定性指標(biāo)。

隨性：是一個模塊內(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)聚度，模塊間具有低耦

合度。

2、總體設(shè)計（概要設(shè)計）和具體設(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ù)信息。

麗表示限制的層數(shù)。

上級模塊、從屬模塊：上、下兩層模塊a和b,且有a調(diào)用b,則a是上級模塊，b

是從屬模塊。

蔽:整體限制跨度（最大模塊數(shù)的層）的表示。

畫：調(diào)用一個給定模塊的模塊個數(shù)。

麗：一個模塊干脆調(diào)用的其他模塊數(shù)。

原子模塊：樹中位于葉子結(jié)點的模塊。

面對數(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ù)奶幚韡單元［,然后給g整批注［wxl3］:單元是程序中最小的部分，由可以隱含的

三部分組成：數(shù)據(jù)輸入、加工和數(shù)據(jù)輸出。

（2）具體設(shè)計

具體設(shè)計是為軟件結(jié)構(gòu)圖中的每一個模塊確定實現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用某種選

定的表達(dá)工具表示算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)微環(huán)節(jié)。

*：具體設(shè)計的任務(wù)是確定實現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，不同于編碼或編程。

常用的過程設(shè)計（即具體設(shè)計）工具有以下幾種：

圖形工具：程序流程圖、N-S（方盒圖）、PAD（問題分析圖）和HIPO（層次圖+

輸入/處理/輸出圖）。

表格工具：判定表。

批注［wxl4］:PDL（偽碼）：過程設(shè)計語言，它是用正文

語言工具：PDL（偽碼）

形式表示數(shù)據(jù)和處理過程的設(shè)計工具.

3.4軟件測試

1、軟件測試定義：運用人工或自動手段來運行或測定某個系統(tǒng)的過程，其目的在于

檢驗它是否滿足規(guī)定的需求或是弄清預(yù)期結(jié)果與實際結(jié)果之間的差別。

*：軟件測試的目的：盡可能地多發(fā)覺程序中的錯誤，不能也不行能證明程序沒有錯

誤。軟件測試的關(guān)鍵是設(shè)計櫥試用例L一個好的測試用例能找到迄今為止尚未發(fā)覺..批注震用譬鬟特定

的錯誤。

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)都在邊界條件和一般條

件下至少各執(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è)計的測試用例保證程序中每個推斷的每個條件的可能取值至少執(zhí)行一

次。

推斷-條件覆蓋：設(shè)計足夠的測試用例，使推斷中每個條件的全部可能取值至少執(zhí)行

一次，同時每個推斷的全部可能取值分支至少執(zhí)行一次。

*：邏輯覆蓋的強度依次是：語句覆蓋〈路徑覆蓋〈判定覆蓋〈條件覆蓋〈推斷-條件覆

蓋。

B、基本路徑測試。其思想和步驟是，依據(jù)軟件過程性描述中的限制流程確定程序的

環(huán)路困難性度量，用此度量定義基本路徑集合，并由此導(dǎo)出一組測試用例，對每一

條獨立執(zhí)行路徑進(jìn)行測試。

(2)黑盒測試

黑盒測試方法也稱為功能測試或數(shù)據(jù)驅(qū)動測試。黑盒測試是對軟件已經(jīng)實現(xiàn)的功能

是否滿足需求進(jìn)行測試和驗證。

黑盒測試主要診斷功能不對或遺漏、接口錯誤、數(shù)據(jù)結(jié)構(gòu)或外部數(shù)據(jù)庫訪問錯誤、

性能錯誤、初始化和終止條件錯誤。

黑盒測試不關(guān)切程序內(nèi)部的邏輯，只是依據(jù)程序的功能說明來設(shè)計測試用例,主要

方法有等價類劃分法、邊界值分析法、錯誤推想法等,主要用軟件的確認(rèn)測試。

A、|等價類劃分源這是一種典型的黑盒測試方法，它是將程序的全部可能的輸入數(shù)

據(jù)劃分成若干部分(與若干等價類)，然后從每個等價類中選取數(shù)據(jù)作為測試用例。

B、|邊界值分析法它是對各種輸入、輸出范圍的邊界狀況設(shè)計測試用例的方法。

C、|錯誤推想法人們可以靠閱歷和直覺推想程序中可能存在的各種錯誤，從而有針

對性地編寫檢查這些錯誤的用例。

3、軟件測試過程一般按4個步驟進(jìn)行：單元測試、集成測試、確認(rèn)測試和系統(tǒng)測試。

(1)單元測試

單元測試|是對軟件設(shè)計的最小單位——模塊(程序單元)進(jìn)行正確性檢測的測試，

目的是發(fā)覺各模塊內(nèi)部可能存在的各種錯誤。

單元測試依據(jù)程序的內(nèi)部結(jié)構(gòu)來設(shè)計測試用例,其依據(jù)是具體設(shè)計說明書和源程序。

單元測試的技術(shù)可以接受靜態(tài)分析和動態(tài)測試。對動態(tài)測試通常以白盒測試為主,

輔之以黑盒測試。

單元測試的內(nèi)容包括：模塊接口測試、局部數(shù)據(jù)結(jié)構(gòu)測試、錯誤處理測試和邊界測

試。

*：在進(jìn)行單元測試時，要用一些協(xié)助模塊去模擬與被測模塊相聯(lián)系的其他模塊，即

為被測模塊設(shè)計和搭建驅(qū)動模塊和樁模塊。其中，|驅(qū)動模塊|相當(dāng)于被測模塊的主程

序，它接收測試數(shù)據(jù)，并傳給被測模塊，輸出實際測試結(jié)果；而|樁模塊|是模擬其他

被調(diào)用模塊，不必將子模塊的全部功能帶入。

(2)集成測試

藏麗是測試和組裝軟件的過程，它是把模塊在依據(jù)設(shè)計要求組裝起來的同時進(jìn)

行測試，主要目的是發(fā)覺與接口有關(guān)的錯誤。

集成測試的依據(jù)是概要設(shè)計說明書。

集成測試所涉與的內(nèi)容包括：軟件單元的接口測試、全局?jǐn)?shù)據(jù)結(jié)構(gòu)測試、邊界條件

和非法輸入的測試等。

集成測試通常接受兩種方式：非增量方式組裝與增量方式組裝。

非增量方式組裝也稱為一次性組裝方式。首先對每個模塊分別進(jìn)行模塊測試，然

后再把全部模塊組裝在一起進(jìn)行測試，最終得到要求的軟件系統(tǒng)。

增量方式組裝又稱漸增式集成方式。首先對一個個模塊進(jìn)行模塊測試，然后將這

些模塊逐步組裝成較大的系統(tǒng)，在組裝的過程中邊連接邊測試，以發(fā)覺連接過程中

產(chǎn)生的問題。最終通過增殖逐步組裝成要求的軟件系統(tǒng)。增量方式組裝又包括自頂

向下、自底向上、自頂向下與自底向上相結(jié)合等三種方式。

(3)確認(rèn)測試

確認(rèn)測試|的任務(wù)是驗證軟件的有效性,即驗證軟件的功能和性能與其他特性是否與

用戶的要求一樣。

確認(rèn)測試的主要依據(jù)是軟件需求規(guī)格說明書。

確認(rèn)測試主要運用黑盒測試法。

(4)系統(tǒng)測試

系統(tǒng)測試|的目的在于通過與系統(tǒng)的需求定義進(jìn)行比較，發(fā)覺軟件與系統(tǒng)定義不符合

或與之沖突的地方。

系統(tǒng)測試的測試用例應(yīng)依據(jù)需求分析規(guī)格說明來設(shè)計,并在實際運用環(huán)境下來運行。

系統(tǒng)測試的具體實施一般包括：功能測試、性能測試、操作測試、配置測試、外部

接口測試、平安性測試等。

3.5程序的調(diào)試

槨序調(diào)試I的任務(wù)是診斷和改正程序中的錯誤,主要在開發(fā)階段進(jìn)行，調(diào)試程序應(yīng)當(dāng)〔批注[WX16]:留意與軟件測試區(qū)分.

由編制源程序的程序員來完成O

程序調(diào)試的基本步驟：(1)錯誤定位;(2)訂正錯誤;(3)回來測試。

批注[WX17]:這是因為修改程序可能帶來新的錯誤，重

*：軟件的調(diào)試后要進(jìn)行回來測試,防止引進(jìn)新的錯誤。

復(fù)進(jìn)行暴露這個錯誤的原始測試或某些有關(guān)測試，以確

軟件調(diào)試可分為靜態(tài)調(diào)試和動態(tài)調(diào)試。靜態(tài)調(diào)試主要是指通過人的思維來分析源程認(rèn)該錯誤是否被解除、是否引進(jìn)了新的錯誤。

序代碼和排錯，是主要的調(diào)試手段，而動態(tài)調(diào)試是協(xié)助靜態(tài)調(diào)試。

對軟件主要的調(diào)試方法可以接受：

(1)強行排錯法。主要方法有：通過內(nèi)存全部打印來排錯；在程序特定部位設(shè)置打

印語句；自動調(diào)試工具。

(2)回溯法。發(fā)覺了錯誤，分析錯誤征兆，確定發(fā)覺“癥狀”的位置。一般用于小

程序。

(3)緣由解除法。是通過演繹、歸納和二分法來實現(xiàn)的。

1)演繹法。依據(jù)已有的測試用例，設(shè)想與枚舉出全部可能出錯的緣由作為假設(shè)；然

后再用原始測試數(shù)據(jù)或新的測試，從中逐個解除不行能正確的假設(shè)；最終，再用測

試數(shù)據(jù)驗證余下的假設(shè)確定出錯的緣由。

2)歸納法。從錯誤征兆著手，通過分析它們之間的關(guān)系來找出錯誤。大致分四步：

收集有關(guān)的數(shù)據(jù)；組織數(shù)據(jù)；提出假設(shè)；證明假設(shè)。

3)二分法。在程序的關(guān)鍵點給變量賦正確值，然后運行程序并檢查程序的輸出。假

如輸出結(jié)果正確，則錯誤緣由在程序的前半部分；反之，錯誤緣由在程序的后半部

分。

本章應(yīng)考點撥：本章在筆試中一般占8分左右，約3道選擇題，1道填空題，是公

共基礎(chǔ)部分比較重要的一章。從出題的深度來看，本章主要考察對基本概念的識記,

有少量對基本原理的理解，沒有實際運用，因此考生在復(fù)習(xí)本章時，重點應(yīng)放在基

本概念的記憶和基本原理的理解上。

第四章數(shù)據(jù)庫設(shè)計基礎(chǔ)

4.1數(shù)據(jù)庫系統(tǒng)的基本概念

1、數(shù)據(jù)、數(shù)據(jù)庫、數(shù)據(jù)管理系統(tǒng)

（1）數(shù)據(jù)：事實上就是描述事物的符號記錄。

數(shù)據(jù)的特點：有確定的結(jié)構(gòu)，有型與值之分。數(shù)據(jù)的型給出了數(shù)據(jù)表示的類型，如

整型、實型、字符型等。而數(shù)據(jù)的值給出了符合給定型的值，如整型（INT）值15。

（2）|數(shù)據(jù)庫（DB）］：是數(shù)據(jù)的集合，具有統(tǒng)一的結(jié)構(gòu)形式并存放于統(tǒng)一的存儲介

質(zhì)內(nèi)，是多種應(yīng)用數(shù)據(jù)的集成，并可被各個應(yīng)用程序所共享。

數(shù)據(jù)庫存放數(shù)據(jù)是按數(shù)據(jù)所供應(yīng)的數(shù)據(jù)模式存放的，具有集成與共享的特點，亦即

是數(shù)據(jù)庫集中了各種應(yīng)用的數(shù)據(jù)，進(jìn)行統(tǒng)一的構(gòu)造和存儲，而使它們可被不同應(yīng)用

程序所運用。

（3）|數(shù)據(jù)庫管理系統(tǒng)（DBMS）一種系統(tǒng)軟件，負(fù)責(zé)數(shù)據(jù)庫中的數(shù)據(jù)組織、數(shù)據(jù)

操縱、數(shù)據(jù)維護(hù)、限制與愛護(hù)和數(shù)據(jù)服務(wù)等，是數(shù)據(jù)庫的核心。

數(shù)據(jù)庫管理系統(tǒng)功能：

1）數(shù)據(jù)模式定義。數(shù)據(jù)庫管理系統(tǒng)負(fù)責(zé)為數(shù)據(jù)庫構(gòu)建模式，也就是為數(shù)據(jù)庫構(gòu)建其

數(shù)據(jù)框架。

2）數(shù)據(jù)存取的物理構(gòu)建。數(shù)據(jù)庫管理系統(tǒng)負(fù)責(zé)為數(shù)據(jù)模式的物理存取與構(gòu)建供應(yīng)有

效的存取方法與手段。

3）數(shù)據(jù)操縱。數(shù)據(jù)庫管理系統(tǒng)為用戶運用數(shù)據(jù)庫中的數(shù)據(jù)供應(yīng)便利，它一般供應(yīng)如

查詢、插入、修改以與刪除數(shù)據(jù)的功能。此外，它自身還具有做簡潔的算術(shù)運算與

統(tǒng)計的實力，而且還可以與某些過程性語言結(jié)合，使其具有強大的過程性操作實力。

4）數(shù)據(jù)的完整性、安生性定義與檢查。數(shù)據(jù)庫中的數(shù)據(jù)具有內(nèi)在語義上的關(guān)聯(lián)性與

一樣性，它們構(gòu)成了數(shù)據(jù)的完整性，數(shù)據(jù)的完整性是保證數(shù)據(jù)庫中數(shù)據(jù)正確的必要

條件，因此必需常常檢查以維護(hù)數(shù)據(jù)正確。數(shù)據(jù)庫中的數(shù)據(jù)具有共享性，而數(shù)據(jù)共

享可能會引發(fā)數(shù)據(jù)的非法運用，因此必須要對數(shù)據(jù)正確運用做出必要的規(guī)定，并在

運用時做檢查，這就是數(shù)據(jù)的平安性。數(shù)據(jù)完整性與平安性的維護(hù)是數(shù)據(jù)庫系統(tǒng)的

基本功能。

5）數(shù)據(jù)庫的并發(fā)限制與故障復(fù)原。數(shù)據(jù)庫是一個集成、共享的數(shù)據(jù)集合體，它能為

多個應(yīng)用程序服務(wù)，所以就存在著多個應(yīng)用程序?qū)?shù)據(jù)庫的并發(fā)操作。在并發(fā)操作

中假如不加限制和管理，多個應(yīng)用程序間就會相互干擾，從而對數(shù)據(jù)庫中的數(shù)據(jù)造

成破壞。因此，數(shù)據(jù)庫管理系統(tǒng)必需對多個應(yīng)用程序的并發(fā)操作做必要的限制以保

證數(shù)據(jù)不受破壞，這就是數(shù)據(jù)庫的并發(fā)限制。數(shù)據(jù)庫中的數(shù)據(jù)一旦遭到破壞，數(shù)據(jù)

庫管理系統(tǒng)必需有實力與時進(jìn)行復(fù)原，這就是數(shù)據(jù)庫的故障復(fù)原。

6）數(shù)據(jù)的服務(wù)。數(shù)據(jù)庫管理系統(tǒng)供應(yīng)對數(shù)據(jù)庫中數(shù)據(jù)的多種服務(wù)功能，如數(shù)據(jù)拷貝、

轉(zhuǎn)存、重組、性能監(jiān)測、分析等。

（4）|數(shù)據(jù)庫管理員（DBA）上對數(shù)據(jù)庫進(jìn)行規(guī)劃、設(shè)計、維護(hù)、監(jiān)視等的專業(yè)管

理人員。

（5）|數(shù)據(jù)庫系統(tǒng)（D由并由數(shù)據(jù)庫（數(shù)據(jù)）、數(shù)據(jù)庫管理系統(tǒng)（軟件）、數(shù)據(jù)

庫管理員（人員）、硬件平臺（硬件）、軟件平臺（軟件）五個部分構(gòu)成的運行實

體。

（6）數(shù)據(jù)庫應(yīng)用系統(tǒng)：由數(shù)據(jù)庫系統(tǒng)、應(yīng)用軟件與應(yīng)用界面三者組成。

*：數(shù)據(jù)庫技術(shù)的根本目標(biāo)是解決數(shù)據(jù)的共享問題。

2、數(shù)據(jù)庫系統(tǒng)的發(fā)展

數(shù)據(jù)庫管理發(fā)展至今已經(jīng)驗了三個階段：人工管理階段、文件系統(tǒng)階段和數(shù)據(jù)庫系

統(tǒng)階段。

3、數(shù)據(jù)庫系統(tǒng)的基本特點

（1）數(shù)據(jù)的高集成性。

(2)數(shù)據(jù)的高共享性與低冗余性。

*：數(shù)據(jù)庫系統(tǒng)可以削減數(shù)據(jù)冗余但無法避開一切冗余。/［批注［wxl8］:在一個集合中的重復(fù)數(shù)據(jù)稱為數(shù)據(jù)冗余

(3)數(shù)據(jù)獨立性:|數(shù)據(jù)獨立樹是數(shù)據(jù)與程序間的互不依靠性,即數(shù)據(jù)庫中數(shù)據(jù)獨立

于應(yīng)用程序而不依靠于應(yīng)用程序。也就是說，數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)與存取方

式的變更不會影響應(yīng)用程序。

數(shù)據(jù)獨立性一般分為物理獨立性與邏輯獨立性兩級。

1)|物理獨立樹:物理獨立性即是數(shù)據(jù)的物理結(jié)構(gòu)(包括存儲結(jié)構(gòu)，存取方式等)的

變更，如存儲設(shè)備的更換、物理存儲的更換、存取方式變更等都不影響數(shù)據(jù)庫的邏

輯結(jié)構(gòu)，從而不致引起應(yīng)用程序的變更。

2)|邏輯獨立科:數(shù)據(jù)庫總體邏輯結(jié)構(gòu)的變更，如修改數(shù)據(jù)模式、增加新的數(shù)據(jù)類型、

變更數(shù)據(jù)間聯(lián)系等，不須要相應(yīng)修改應(yīng)用程序，這就是數(shù)據(jù)的邏輯獨立性。

(4)數(shù)據(jù)統(tǒng)一管理與限制。

數(shù)據(jù)統(tǒng)一管理與限制主要包含以下三個方面：

1)數(shù)據(jù)的完整性檢查：檢查數(shù)據(jù)庫中數(shù)據(jù)的正確性以保證數(shù)據(jù)的正確。

2)數(shù)據(jù)的平安性愛護(hù)：檢查數(shù)據(jù)庫訪問者以防止非法訪問。

3)并發(fā)限制：限制多個應(yīng)用的并發(fā)訪問所產(chǎn)生的相互干擾以保證其正確性。

4、數(shù)據(jù)庫系統(tǒng)的內(nèi)部結(jié)構(gòu)體系

(1)數(shù)據(jù)庫系統(tǒng)的三級模式：

1)|概念模式|：數(shù)據(jù)庫系統(tǒng)中全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu)的描述，是全體用戶(應(yīng)用)公共數(shù)

批注［wxl9］:視圖是從一個或幾個基本表(或視圖)導(dǎo)

據(jù)視圖。

出的表，它與基本表不同，是一個虛表。數(shù)據(jù)庫中只存

2)|外模式也稱子模式或用戶模式，它是用戶的數(shù)據(jù)視圖，也就是用戶所見到的數(shù)放視圖的定義，而不存放視圖對應(yīng)的數(shù)據(jù)，這些數(shù)據(jù)仍

舊存放在原來的基本表中。

據(jù)模式，它由概念模式推導(dǎo)而出。

3)|內(nèi)模式卜又稱物理模式，它給出了數(shù)據(jù)庫物理存儲結(jié)構(gòu)與物理存取方法。內(nèi)模式

的物理性主要體現(xiàn)在操作系統(tǒng)與文件級上，它還未深化到設(shè)備級上(如磁盤與磁盤

操作)。內(nèi)模式對一般用戶是透亮的，但它的設(shè)計干脆影響數(shù)據(jù)庫的性能。

(2)數(shù)據(jù)庫系統(tǒng)的兩級映射：

1)|概念模式/內(nèi)模式的映射|：實現(xiàn)了概念模式到內(nèi)模式