全國計(jì)算機(jī)等級(jí)考試二級(jí)輔導(dǎo)公共基礎(chǔ)講義

全國計(jì)算機(jī)等級(jí)考試一二級(jí)公共基礎(chǔ)知識(shí)輔導(dǎo)講義

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

1.1算法

國

1

*:算法不等于程序,也不等于計(jì)算方法。程序的編制不可能優(yōu)于算法的設(shè)計(jì)。

2、算法的基本特征

(1可行性。針對(duì)實(shí)際問題而設(shè)計(jì)的算法，執(zhí)行后能夠得到滿意的結(jié)果。

(2確定性。每一條指令的含義明確，無二義性。并且在任何條件下，算法只有唯

一的一條執(zhí)行路徑，即相同的輸入只能得出相同的輸出。

(3有窮性。算法必須在有限的時(shí)間內(nèi)完成。有兩重含義,一是算法中的操作步

驟為有限個(gè)，二是每個(gè)步驟都能在有限時(shí)間內(nèi)完成。

(4擁有足夠的情報(bào)。算法中各種運(yùn)算總是要施加到各個(gè)運(yùn)算對(duì)象上，而這些運(yùn)

算對(duì)象又可能具有某種初始狀態(tài)，這就是算法執(zhí)行的起點(diǎn)或依據(jù)。因此，一個(gè)算法執(zhí)

行的結(jié)果總是與輸入的初始數(shù)據(jù)有關(guān)，不同的輸入將會(huì)有不同的結(jié)果輸出。當(dāng)輸入

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

時(shí),此算法才是有效的;而當(dāng)提供的情報(bào)不夠時(shí)，算法可能無效。

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

有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。

3、算法復(fù)雜度主要包括時(shí)間復(fù)雜度和空間復(fù)雜度。

(1算法時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量，可以用執(zhí)行算法的過程

中所需基本運(yùn)算的執(zhí)行次數(shù)來度量。(2

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

1

2、數(shù)據(jù)結(jié)構(gòu)主要研究和討論以下三個(gè)方面的問題：

(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)

系。

(2在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)

構(gòu)。

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引等。

1順序存儲(chǔ)。它是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)

間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來體現(xiàn)。由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)

構(gòu)。

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

系是由附加的指針字段表示的。由此得到的存儲(chǔ)表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

3索引存儲(chǔ):除建立存儲(chǔ)結(jié)點(diǎn)信息外，還建立附加的索引表來標(biāo)識(shí)結(jié)點(diǎn)的地址。

*:數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)(也稱數(shù)據(jù)的

物理結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式。同一種邏輯結(jié)構(gòu)的數(shù)

據(jù)可以采用不同的存儲(chǔ)結(jié)構(gòu)，但影響數(shù)據(jù)處理效率。

(3對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。

3、數(shù)據(jù)結(jié)構(gòu)的圖形表示

一個(gè)數(shù)據(jù)結(jié)構(gòu)除了用二元關(guān)系表示外,還可以直觀地用圖形表示。在數(shù)據(jù)結(jié)構(gòu)

的圖形表示中，對(duì)于數(shù)據(jù)集合D中的每一個(gè)數(shù)據(jù)元素用中間標(biāo)有元素值的方框表示,

一般稱之為數(shù)據(jù)結(jié)點(diǎn)，并簡(jiǎn)稱為結(jié)點(diǎn);為了進(jìn)一步表示各數(shù)據(jù)元素之間的前后件關(guān)系,

對(duì)于關(guān)系R中的每一個(gè)二元組，用一條有向線段從前件結(jié)點(diǎn)指向后件結(jié)點(diǎn)。

4、數(shù)據(jù)結(jié)構(gòu)分為兩大類型:線性結(jié)構(gòu)和非線性結(jié)構(gòu)。

(11有且只有一個(gè)根結(jié)點(diǎn);2每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。

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

回

1

n(n加個(gè)數(shù)據(jù)元素組成的一個(gè)有限序列，表中的每一個(gè)數(shù)據(jù)元素，除了第一個(gè)外,

有且只有一個(gè)前件，除了最后一個(gè)外,有且只有一個(gè)后件。線性表中數(shù)據(jù)元素的個(gè)數(shù)

稱為線性表的長(zhǎng)度。線性表可以為空表。

*:線性表是一種存儲(chǔ)結(jié)構(gòu)，它的存儲(chǔ)方式:順序和鏈?zhǔn)健?/p>

2、線性表的順序存儲(chǔ)結(jié)構(gòu)具有兩個(gè)基本特點(diǎn):(1線性表中所有元素所占的存儲(chǔ)

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

*：由此可以看出，在線性表的順序存儲(chǔ)結(jié)構(gòu)中淇前后件兩個(gè)元素在存儲(chǔ)空間中

是緊鄰的，且前件元素一定存儲(chǔ)在后件元素的前面，可以通過計(jì)算機(jī)直接確定第i個(gè)

結(jié)點(diǎn)的存儲(chǔ)地址。

3、順序表的插入、刪除運(yùn)算

（I順序表的插入運(yùn)算:在一般情況下，要在第i（閆＜n個(gè)元素之前插入一個(gè)新元

素時(shí)，首先要從最后一個(gè)（即第n個(gè)元素開始,直到第i個(gè)元素之間共n-i+l個(gè)元素依

次向后移動(dòng)一個(gè)位置，移動(dòng)結(jié)束后，第i個(gè)位置就被空出，然后將新元素插入到第i

項(xiàng)。插入結(jié)束后，線性表的長(zhǎng)度就增加了1。

*：順性表的插入運(yùn)算時(shí)需要移動(dòng)元素，在等概率情況下,平均需要移動(dòng)n/2個(gè)元

素U

（2順序表的刪除運(yùn)算:在一般情況下，要?jiǎng)h除第i（臼＜n個(gè)元素時(shí)，則要從第i+1

個(gè)元素開始,直到第n個(gè)元素之間共n-i個(gè)元素依次向前移動(dòng)一個(gè)位置。刪除結(jié)束后,

線性表的長(zhǎng)度就減小了L

*：進(jìn)行順性表的刪除運(yùn)算時(shí)也需要移動(dòng)元素，在等概率情況下,平均需要移動(dòng)（n-

1/2個(gè)元素。插入、刪除運(yùn)算不方便。

1.4棧和隊(duì)列

1、棧及其基本運(yùn)算

叵

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

底。棧頂元素總是最后被插入的元素,棧底元素總是最先被插入的元素。即棧是按

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

棧具有記憶作用。

棧的基本運(yùn)算:1插入元素稱為入棧運(yùn)算:2刪除元素稱為退棧運(yùn)算;3讀棧頂元素

是將棧頂元素賦給一個(gè)考定的變量，此時(shí)指針無變化。

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

2、隊(duì)列及其基本運(yùn)算

Rear指向隊(duì)尾元素，頭指針（front指向排頭元素的前一個(gè)位置（隊(duì)頭。

麗

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

隊(duì)列運(yùn)算包括:I入隊(duì)運(yùn)算:從隊(duì)尾插入一個(gè)元素;2退隊(duì)運(yùn)算:從隊(duì)頭刪除一個(gè)元

素。

循環(huán)隊(duì)列及其運(yùn)算:所謂循環(huán)隊(duì)列，就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第

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

指向隊(duì)列中的隊(duì)尾元素用排頭指針front指向排頭元素的前一個(gè)位置，因此，從頭指

針front指向的后一個(gè)位置直到隊(duì)尾指針rear指向的位置之間,所有的元素均為隊(duì)列

中的元素。*:循環(huán)隊(duì)列中元素的個(gè)數(shù)=rear-front。

1.5線性鏈表

1、線性表順序存儲(chǔ)的缺點(diǎn)：（1插入或刪除的運(yùn)算效率很低。在順序存儲(chǔ)的線

性表中，插入或刪除數(shù)據(jù)元素時(shí)需要移動(dòng)大量的數(shù)據(jù)元素;（2線性表的順序存儲(chǔ)結(jié)構(gòu)

下，線性表的存儲(chǔ)空間不便于擴(kuò)充;（3線性表的順序存儲(chǔ)結(jié)構(gòu)不便于對(duì)存儲(chǔ)空間的動(dòng)

態(tài)分配。

2

、線性鏈表:線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表，是一種物理存儲(chǔ)單元上非連

續(xù)、非順序的存儲(chǔ)結(jié)構(gòu),數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接來實(shí)現(xiàn)的。

因此，在鏈?zhǔn)酱鎯?chǔ)方式中，每個(gè)結(jié)點(diǎn)由兩部分組成:一部分用于存放數(shù)據(jù)元素的值,稱

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

點(diǎn)（即前件或后件,如下圖所示：

線性鏈表分為單鏈表、雙向鏈表和循環(huán)鏈表三種類型。數(shù)據(jù)域指針域

HEAD…（a結(jié)點(diǎn)結(jié)構(gòu)（b一個(gè)非空的線性鏈表示意圖

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

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

一個(gè)稱為左指針，指向其前件結(jié)點(diǎn);另一個(gè)稱為右指針，指向其后件結(jié)點(diǎn)，這種鏈表稱

為雙向鏈表,如下圖所示：

網(wǎng)網(wǎng)網(wǎng)

3、線性鏈表的基本運(yùn)算

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

*:在線性鏈表中插入元素時(shí)，不需要移動(dòng)數(shù)據(jù)元素,只需要修改相關(guān)結(jié)點(diǎn)指針即

可，也不會(huì)出現(xiàn)“上溢”現(xiàn)象。

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

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

即可。

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

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

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

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

(7線性鏈表的排序。

(8線性鏈表的查找。

近線性鏈表不能隨機(jī)存取。

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

在線性鏈表中，其插入與刪除的運(yùn)算雖然比較方便，但還存在一個(gè)問題，在運(yùn)算過

程中對(duì)于空表和對(duì)第一個(gè)結(jié)點(diǎn)的處理必須單獨(dú)考慮,使空表與非空表的運(yùn)算不統(tǒng)

-o為了克服線性鏈表的這個(gè)缺點(diǎn)，可以采用另一種鏈接方式，即循環(huán)鏈表。

與前面所討論的線性鏈表相比,循環(huán)鏈表具有以下兩個(gè)特點(diǎn)：1在鏈表中增加了

一個(gè)表頭結(jié)點(diǎn)，其數(shù)據(jù)域?yàn)槿我饣蛘吒鶕?jù)需要來設(shè)置，指針域指向線性表的第一個(gè)元

素的結(jié)點(diǎn)，而循環(huán)鏈表的頭指針指向表頭結(jié)點(diǎn);2循環(huán)鏈表中最后一個(gè)結(jié)點(diǎn)的指針域

不是空，而是指向表頭結(jié)點(diǎn)。即在循環(huán)鏈表中，所有結(jié)點(diǎn)的指針構(gòu)成了一個(gè)環(huán)狀鏈。

□

II

下圖a是一個(gè)非空的循環(huán)鏈表，圖b是一個(gè)空的循環(huán)鏈表：

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

個(gè)結(jié)點(diǎn)的位置，就可以從它出發(fā)訪問到表中其他所有的結(jié)點(diǎn)，而線性單鏈表做不到這

一點(diǎn);二是由于在循環(huán)鏈表中設(shè)置了一個(gè)表頭結(jié)點(diǎn),在任何情況下，循環(huán)鏈表中至少有

一個(gè)結(jié)點(diǎn)存在，從而使空表與非空表的運(yùn)算統(tǒng)一。

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

鏈表相同。但它可以從任一結(jié)點(diǎn)出發(fā)來訪問表中其他所有結(jié)點(diǎn)，并實(shí)現(xiàn)空表與非空

表的運(yùn)算的統(tǒng)一。

1.6樹與二叉樹

1、樹的基本概念

回

忖子、闔

封畫稱為國導(dǎo)沒仃網(wǎng)網(wǎng)

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

㈣

（1什么是二叉樹

1非空二叉樹只有一個(gè)根結(jié)點(diǎn);2每一個(gè)結(jié)點(diǎn)最多有兩棵子樹，且分別稱為該結(jié)點(diǎn)

的左子樹與右子樹。

網(wǎng)

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

2（有2棵子樹。

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

性質(zhì)1在二叉樹的第k層上,最多有個(gè)結(jié)點(diǎn)。

右指針

左指針數(shù)據(jù)域（a結(jié)點(diǎn)結(jié)構(gòu)

...HEAD（b一個(gè)非空的雙向鏈表示意圖

性質(zhì)2深度為m的二叉樹最多有個(gè)個(gè)結(jié)點(diǎn)。性質(zhì)3在任意一棵二叉樹中,度

數(shù)為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)總比度為2的結(jié)點(diǎn)多一個(gè)。性質(zhì)4具有n個(gè)結(jié)點(diǎn)的二叉

樹,其深度至少為，其中表示取的整數(shù)部分。3、滿二叉樹與完全二叉樹

滿二叉樹:除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。

完全二叉樹:除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值;在最后一層上只缺

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

*:根據(jù)完全二叉樹的定義可得出:度為1的結(jié)點(diǎn)的個(gè)數(shù)為?；騦o

下圖a表示的是滿二叉樹，下圖b表示的是完全二叉樹:

完全二叉樹還具有如下兩個(gè)特性：

性質(zhì)5具有n個(gè)結(jié)點(diǎn)的完全二叉樹深度為。

性質(zhì)6設(shè)完全二叉樹共有n個(gè)結(jié)點(diǎn)，如果從根結(jié)點(diǎn)開始，按層序(每一層從左到右

用自然數(shù)1,2，…,n給結(jié)點(diǎn)進(jìn)行編號(hào),則對(duì)于編號(hào)為k(k=l,2,…,n的結(jié)點(diǎn)有以下結(jié)論：

①若k=l,則該結(jié)點(diǎn)為根結(jié)點(diǎn)，它沒有父結(jié)點(diǎn);若kA,則該結(jié)點(diǎn)的父結(jié)點(diǎn)的編號(hào)為

INT(k/2o

②若2k<n，則編號(hào)為k的左子結(jié)點(diǎn)編號(hào)為2k;否則該結(jié)點(diǎn)無左子結(jié)點(diǎn)(顯然也

沒有右子結(jié)點(diǎn)。

③若2k+l<n，則編號(hào)為k的右子結(jié)點(diǎn)編號(hào)為2k+l;否則該結(jié)點(diǎn)無右子結(jié)點(diǎn)。

4、二叉樹的存儲(chǔ)結(jié)構(gòu)

在計(jì)算機(jī)中，二叉樹通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

與線性鏈表類似,用于存儲(chǔ)二叉樹中各元素的存儲(chǔ)結(jié)點(diǎn)也由兩部分組成:數(shù)據(jù)域

和指針域。但在二叉樹中，由于每一個(gè)元素可以有兩個(gè)后件（即兩個(gè)子結(jié)點(diǎn)，因此，用

于存儲(chǔ)二叉樹的存儲(chǔ)結(jié)點(diǎn)的指針域有兩個(gè):一個(gè)用于指向該結(jié)點(diǎn)的左子結(jié)點(diǎn)的存儲(chǔ)

地址，稱為左指針域;另一個(gè)用于指向該結(jié)點(diǎn)的右子結(jié)點(diǎn)的存儲(chǔ)地址，稱為右指針域。

*:一般二叉樹通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，對(duì)于滿二叉樹與完全二叉樹來說，可以按

層序進(jìn)行順序存儲(chǔ)。

5、二叉樹的遍歷

二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有結(jié)點(diǎn)。二叉樹的遍歷可以分為

以下三種：

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

左子樹，最后遍歷右子樹;并且，在遍歷左右子樹時(shí)，仍然先訪問根結(jié)點(diǎn)，然后遍歷左子

樹，最后遍歷右子樹。

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

根結(jié)點(diǎn)，最后遍歷右子樹;并且，在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后訪問根

結(jié)點(diǎn)，最后遍歷右子樹。

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

右子樹，最后訪問根結(jié)點(diǎn)，并且，在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后遍歷右

子樹，最后訪問根結(jié)點(diǎn)。

1.7查找技術(shù)

查找:根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元

素。

查找結(jié)果：（查找成功:找到:查找不成功:沒找到。

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

1、順序查找

基本思想:從表中的第一個(gè)元素開始,將給定的值與表中逐個(gè)元素的關(guān)鍵字進(jìn)行

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

成功。

在平均情況下，利用順序查找法在線性表中查找一個(gè)元素，大約要與線性表中一

半的元素進(jìn)行比較,最壞情況下需要比較n次。

1

2-m1]

[log2+n][log2nn21og(a滿二叉樹(b完全二叉樹

1川。g2+n

順序查找一個(gè)具有n個(gè)元素的線性表，其平均復(fù)雜度為O(no

下列兩種情況下只能采用順序查找：

1如果線性表是無序表(即表中的元素是無序的，則不管是順序存儲(chǔ)結(jié)構(gòu)還是鏈

式存儲(chǔ)結(jié)構(gòu),都只能用順序查找。

2即使是有序線性表，如果采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),也只能用順序查找。

2、二分法查找

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

該記錄為止。

前提:必須在具有順序存儲(chǔ)結(jié)構(gòu)的有序表中進(jìn)行。

查找過程:

1若中間項(xiàng)（中間項(xiàng)mid=（n-l/2,mid的值四舍五入取整的值等于x,則說明已查至上

2若x小于中間項(xiàng)的值，則在線性表的前半部分查找；

3若x大于中間項(xiàng)的值，則在線性表的后半部分查找。

特點(diǎn):比順序查找方法效率高。最壞的情況下，需要比較log2n次。

*:二分法查找只適用于順序存儲(chǔ)的線性表，且表中元素必須按關(guān)鍵字有序（升序

排列。對(duì)于無序線性表和線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)只能用順序查找。在長(zhǎng)度為n的有

序線性表中進(jìn)行二分法查找，其時(shí)間復(fù)雜度為O（log2n。

1.8排序技術(shù)

排序是指將一個(gè)無序序列整理成按值非遞減順序排列的有序序列，即是將無序

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

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

2、插入類排序法（方法:簡(jiǎn)單插入排序，希爾排序。

3、選擇類排序法（方法:簡(jiǎn)單選擇排序，堆排序。

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

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

冒泡排序相鄰元素比較，不滿足條件時(shí)交換n(n-l)/2

交換類

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

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

簡(jiǎn)單插入排序n(n-l)/2

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

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

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

簡(jiǎn)單選擇排序n(n-l)/2

換到表的最前面

選擇類

陸建堆.缺￡坨誰而三支什也B1仁一個(gè)彳安辦

本章應(yīng)考點(diǎn)撥:本章內(nèi)容在筆試中會(huì)出現(xiàn)5-6個(gè)題目，是公共基礎(chǔ)知識(shí)部分出題

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

N(n-l/2nlog2n

第二章程序設(shè)計(jì)基礎(chǔ)

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

程序設(shè)計(jì)的風(fēng)格主要強(qiáng)調(diào):“清晰第一，效率第二:主要應(yīng)注重和考慮下述一些

因素：

(1源程序文檔化。

1符號(hào)名的命名。符號(hào)名能反映它所代表的實(shí)際東西，應(yīng)有一定的實(shí)際含義。

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

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

口說明、程序位置、開發(fā)簡(jiǎn)歷、程序設(shè)計(jì)者、復(fù)審者、復(fù)審日期及修改日期等。

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

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

(2數(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避免

使用臨時(shí)變量而使程序的可讀性下降;6避免不必要的轉(zhuǎn)移;7盡量使用庫函數(shù):8避免

采用復(fù)雜的條件語句;9盡量減少使用“否定”條件語句;10數(shù)據(jù)結(jié)構(gòu)要有利于程序的

簡(jiǎn)化;11要模塊化,使模塊功能盡可能單一化;12利用信息隱蔽，確保每一個(gè)模塊的獨(dú)

立性;13從數(shù)據(jù)出發(fā)去構(gòu)造程序;14不要修補(bǔ)不好的程序，要重新編寫。

(4輸入和輸出。1對(duì)輸入數(shù)據(jù)檢驗(yàn)數(shù)據(jù)的合法性;2檢查輸入項(xiàng)的各種重要組合

的合法性;3輸入格式要簡(jiǎn)單，使得輸入的步驟和操作盡可能簡(jiǎn)單;4輸入數(shù)據(jù)時(shí)，應(yīng)允

許使用自由格式;5應(yīng)允許缺省值;6輸入一批數(shù)據(jù)時(shí)，最好使用輸入結(jié)束標(biāo)志;7在以

交互式輸入/輸出方式進(jìn)行輸入時(shí)，要在屏幕上使用提示符明確提示輸入的請(qǐng)求洞時(shí)

在數(shù)據(jù)輸入過程中和輸入結(jié)束時(shí),應(yīng)在屏幕上給出狀態(tài)信息;8當(dāng)程序設(shè)計(jì)語言對(duì)輸

入格式有嚴(yán)格要求時(shí)，應(yīng)保持輸入格式與輸入語句的一致性;給所有的輸出加注釋，并

設(shè)計(jì)輸出報(bào)表格式。

2.2結(jié)構(gòu)化程序設(shè)計(jì)(面向過程的程序設(shè)計(jì)方法

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

制使用goto語句。

2、結(jié)構(gòu)化程序的基本結(jié)構(gòu):順序結(jié)構(gòu)，選擇結(jié)構(gòu)，重復(fù)結(jié)構(gòu)。

1順序結(jié)構(gòu)。一種簡(jiǎn)單的程序設(shè)計(jì)，即按照程序語句行的自然順序，一條語句一

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

2選擇結(jié)構(gòu)。又稱分支結(jié)構(gòu)，包括簡(jiǎn)單選擇和多分支選擇結(jié)構(gòu)，可根據(jù)條件，判斷

應(yī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)，

從而實(shí)現(xiàn)任何單入口/單出口的程序。2.3面向?qū)ο蟮某绦蛟O(shè)計(jì)

客觀世界中任何一個(gè)事物都可以被看成是一個(gè)對(duì)象，面向?qū)ο蠓椒ǖ谋举|(zhì)就是

主張從客觀世界固有的事物出發(fā)來構(gòu)造系統(tǒng)，提倡人們?cè)诂F(xiàn)實(shí)生活中常用的思維來

認(rèn)識(shí)、理解和描述客觀事物，強(qiáng)調(diào)最終建立的系統(tǒng)能夠映射問題域。也就是說，系統(tǒng)

中的對(duì)象及對(duì)象之間的關(guān)系能夠如實(shí)地反映問題域中固有的事物及其關(guān)系。

面向?qū)ο蠓椒ǖ闹饕獌?yōu)點(diǎn)：(1與人類習(xí)慣的思維方法一致;(2穩(wěn)定性好;(3可重用

性好;(4易于開發(fā)大型軟件產(chǎn)品;(5可維護(hù)性好。

木:面向?qū)ο蟮某绦蛟O(shè)計(jì)主要考慮的是提高軟件的可重用性。

幽

計(jì)方法中的對(duì)象是系統(tǒng)中用來描述客觀事物的一個(gè)實(shí)體，是構(gòu)成系統(tǒng)的一個(gè)基

本單位，由一組表示其靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成。對(duì)象是屬性和

方法的封裝體。

操作描述了對(duì)象執(zhí)行的功能，操作也稱為方法或服務(wù)。操作是對(duì)象的動(dòng)態(tài)屬

性。

近一個(gè)對(duì)象由對(duì)象名、屬性和操作三部分組成。

對(duì)象的基本特點(diǎn):標(biāo)識(shí)惟一性,分類性，多態(tài)性,封裝性，模塊獨(dú)立性好。

(1標(biāo)識(shí)惟一性。指對(duì)象是可區(qū)分的，并且由對(duì)象的內(nèi)在本質(zhì)來區(qū)分，而不是通過

描述來區(qū)分。

(2分類性。指可以將具有相同屬性的操作的對(duì)象抽象成類。

(3多態(tài)性。指同一個(gè)操作可以是不同對(duì)象的行為。

(4封裝性。從外面看只能看到對(duì)象的外部特性即只需知道數(shù)據(jù)的取值范圍和

可以對(duì)該數(shù)據(jù)施加的操作，根本無需知道數(shù)據(jù)的具體結(jié)構(gòu)以及實(shí)現(xiàn)操作的算法。對(duì)

象的內(nèi)部，即處理能力的實(shí)行和內(nèi)部狀態(tài)，對(duì)外是不可見的。從外面不能直接使用對(duì)

象的處理能力，也不能直接修改其內(nèi)部狀態(tài)，對(duì)象的內(nèi)部狀態(tài)只能由其自身改變。

什信息隱蔽是通過對(duì)象的封裝性來實(shí)現(xiàn)的。

(5模塊獨(dú)立性好。對(duì)象是面向?qū)ο蟮能浖幕灸K，它是由數(shù)據(jù)及可以對(duì)這

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

所需做的處理來設(shè)置，沒有無關(guān)的操作。從模塊的獨(dú)立性考慮，對(duì)象

內(nèi)部各種元素彼此結(jié)合得很緊密.內(nèi)聚性強(qiáng)。

類是指具有共同屬性、共同方法的對(duì)象的集合。所以類是對(duì)象的抽象，對(duì)象是

對(duì)應(yīng)類的一個(gè)實(shí)例。

(1接收消息的對(duì)象的名稱;(2消息標(biāo)識(shí)符，也稱消息名:(3零個(gè)或多個(gè)參數(shù)0

*:在面向?qū)ο蠓椒ㄖ?，一個(gè)對(duì)象請(qǐng)求另一個(gè)對(duì)象為其服務(wù)的方式是通過發(fā)送消

息。

麗

有一個(gè)父類，多重繼承指一個(gè)類允許有多個(gè)父類。

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

明乃

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

較小的一章。本章內(nèi)容比較少，也很簡(jiǎn)單，掌握住基本的概念就可以輕松應(yīng)對(duì)考試了,

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

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

3.1軟件工程基本概念

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

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

軟件的特點(diǎn)包括:I軟件是一種邏輯實(shí)體，而不是物理實(shí)體,具有抽象性;2軟件的

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

化問題;4軟件的開發(fā)、運(yùn)行對(duì)計(jì)算機(jī)系統(tǒng)具有依賴性，受計(jì)算機(jī)系統(tǒng)的限制,這導(dǎo)致

了軟件移植的問題;5軟件復(fù)雜性高，成本昂貴;6軟件開發(fā)涉及諸多的社會(huì)因素。

2、軟件危機(jī)與軟件工程

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

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

現(xiàn)在：

1軟件需求的增長(zhǎng)得不到滿足。用戶對(duì)系統(tǒng)不滿意的情況經(jīng)常發(fā)生。

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

期的情況經(jīng)常發(fā)生。

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

4軟件不可維護(hù)或維護(hù)程度非常低。

5軟件的成本不斷提高。

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

總之,可以將軟件危機(jī)可以歸結(jié)為成本、質(zhì)量、生產(chǎn)率等問題。

是要建造一個(gè)優(yōu)良的軟件系統(tǒng),它所包含的內(nèi)容概括為以下兩點(diǎn)：

1軟件開發(fā)技術(shù)，主要有軟件開發(fā)方法學(xué)、軟件工具、軟件工程環(huán)境。

2軟件工程管理，主要有軟件管理、軟件工程經(jīng)濟(jì)學(xué)。

軟件工程的主要思想是將工程化原則運(yùn)用到軟件開發(fā)過程,它包括3個(gè)要素:方

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

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

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

3、軟件生命周期

iw

軟件生命周期分為軟件定義、軟件開發(fā)及軟件運(yùn)行維護(hù)三個(gè)階段：

1軟件定義階段:包括制定計(jì)劃和需求分析。

制定計(jì)劃:確定總目標(biāo);可行性研究;探討解決方案;制定開發(fā)計(jì)劃。

需求分析:對(duì)待開發(fā)軟件提出的需求進(jìn)行分析并給出詳細(xì)的定義。

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

軟件設(shè)計(jì):分為概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)兩個(gè)部分。

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

軟件測(cè)試:在設(shè)計(jì)測(cè)試用例的基礎(chǔ)上檢驗(yàn)軟件的各個(gè)組成部分。

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

刪改。

*:軟件生命周期中所花費(fèi)最多的階段是軟件運(yù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èi)用;能按時(shí)完成開

發(fā)，及時(shí)交付使用。

(3軟件工程原則:抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備

性和可驗(yàn)證性。

幽

開發(fā)過程的復(fù)雜性。

蟀

|儲(chǔ)息除閾

2

3

大會(huì)使模塊內(nèi)部的復(fù)雜性增加，不利于模塊的理解和修改也不利于模塊的調(diào)試

和重用:模塊太小會(huì)導(dǎo)致整個(gè)系統(tǒng)表示過于復(fù)雜，不利于控制系統(tǒng)的復(fù)雜性。

緒,市:型I

模塊也

確定性I：

4

5

6

7

8

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

(1軟件開發(fā)工具

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

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

的，軟件開發(fā)工具為軟件工程方法提供了自動(dòng)的或半自動(dòng)的軟件支撐環(huán)境口同時(shí)，軟

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

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

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

合。

眄

CASE,ComputerAidedSoftwareEngineering將各種軟件工具、開發(fā)機(jī)器和一個(gè)

存放開發(fā)過程信息的中心數(shù)據(jù)庫組合起來，形成軟件工程環(huán)境。它將極大降低軟件

開發(fā)的技術(shù)難度并保證軟件開發(fā)的質(zhì)量。

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

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

1、需求分析

需求分析方法有：1結(jié)構(gòu)化需求分析方法;2面向?qū)ο蟮姆治龇椒ā?/p>

跡

*

*:需求分析一般分為需求獲取、需求分析、編寫需求規(guī)格說明書和需求評(píng)審四

個(gè)步驟進(jìn)行。

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

結(jié)構(gòu)化分析方法是結(jié)構(gòu)化程序設(shè)計(jì)理論在軟件需求分析階段的應(yīng)用。

結(jié)構(gòu)化分析方法的實(shí)質(zhì):著眼于數(shù)據(jù)流，自頂向下，逐層分解，建立系統(tǒng)的處理流

程,以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具，建立系統(tǒng)的邏輯模型。

結(jié)構(gòu)化分析的常用工具：1數(shù)據(jù)流圖（DFD;2數(shù)據(jù)字典（DD;3判定樹;4判定表。

麗

中用于表示系統(tǒng)邏輯模型的一種工具。

加工數(shù)據(jù)流存儲(chǔ)文件源、潭

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

:輸入數(shù)據(jù)經(jīng)加工變換產(chǎn)生輸出。

:表示處理過程中存放各種數(shù)據(jù)的文件。

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

下圖是一個(gè)數(shù)據(jù)流圖的示例:

于輸入、輸出、存儲(chǔ)成分和中間計(jì)算結(jié)果有共同的理解。

近數(shù)據(jù)字典的作用是對(duì)數(shù)據(jù)流圖中出現(xiàn)的被命名的圖形元素的確切解釋。

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

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

回（

計(jì)約束的說明、合適的驗(yàn)收標(biāo)準(zhǔn)，給出對(duì)目標(biāo)軟件的各種需求。

3.3結(jié)構(gòu)化設(shè)計(jì)方法

1、軟件設(shè)計(jì)的基礎(chǔ)

*:需求分析主要解決“做什么”的問題而軟件設(shè)計(jì)主要解決‘怎么做”的問題。

從技術(shù)觀點(diǎn)來看，軟件設(shè)計(jì)包括軟件結(jié)構(gòu)設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、接口設(shè)計(jì)、過程設(shè)

計(jì)。

麗］（付

存儲(chǔ)W件I

源，河:

從工程角度來看,軟件設(shè)計(jì)分兩步完成，即概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)。

呵|（W

I數(shù)據(jù)流

軟件設(shè)計(jì)的基本原理包括:抽象、模塊化、信息隱蔽和模塊獨(dú)立性。

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

他細(xì)節(jié)。

2模塊化。解決一個(gè)復(fù)雜問題時(shí)自頂向下逐步把軟件系統(tǒng)劃分成一個(gè)個(gè)較小

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

3信息隱蔽。每個(gè)模塊的實(shí)施細(xì)節(jié)對(duì)于其他模塊來說是隱蔽的。

4模塊獨(dú)立性。

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

叵

陋

一個(gè)設(shè)計(jì)良好的軟件系統(tǒng)應(yīng)具有高內(nèi)聚、低耦合的特征。

在結(jié)構(gòu)化程序設(shè)計(jì)中，模塊劃分的原則是:模塊內(nèi)具有高內(nèi)聚度，模塊間具有低耦

合度。

2、總體設(shè)計(jì)（概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)

（1總體設(shè)計(jì)（概要設(shè)計(jì)

軟件概要設(shè)計(jì)的基本任務(wù)是：1設(shè)計(jì)軟件系統(tǒng)結(jié)構(gòu);2數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫設(shè)計(jì);3編

寫概要設(shè)計(jì)文檔;4概要設(shè)計(jì)文檔評(píng)審。

常用的軟件結(jié)構(gòu)設(shè)計(jì)工具是結(jié)構(gòu)圖，也稱程序結(jié)構(gòu)圖。程序結(jié)構(gòu)圖的基本圖符：

模塊用一個(gè)矩形表示，箭頭表示模塊間的調(diào)用關(guān)系。在結(jié)構(gòu)圖中還可以用帶注

釋的箭頭表示模塊調(diào)用過程中來回傳遞的信息。還可用帶實(shí)心圓的箭頭表示傳遞的

是控制信息，空心圓箭心表示傳遞的是數(shù)據(jù)信息。

經(jīng)常使用的結(jié)構(gòu)圖有四種模塊類型:傳入模塊、傳出模塊、變換模塊和協(xié)調(diào)模

塊。其表示形式如下圖：

日

它們的含義分別是:

傳入模塊

傳出模塊

變換模塊

協(xié)調(diào)模塊

程序結(jié)構(gòu)圖的例圖及有關(guān)術(shù)語列舉如下:

n1

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

是從屬模塊。

傳入

==

原子模塊:樹中位于葉子結(jié)點(diǎn)的模塊。

面向數(shù)據(jù)流的設(shè)計(jì)方法定義了一些不同的映射方法，利用這些方法可以把數(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ù)處理問題的工作機(jī)理是接受一項(xiàng)事務(wù)，根據(jù)事務(wù)處理的

特點(diǎn)和性質(zhì)，選擇分派一個(gè)適當(dāng)?shù)奶幚韱卧?，然后給出結(jié)果。

（2詳細(xì)設(shè)計(jì)

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

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

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

常用的過程設(shè)計(jì)（即詳細(xì)設(shè)計(jì)工具有以下幾種：

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

/處理/輸出圖。

表格工具:判定表。

語言工具:PDL（偽碼

3.4軟件測(cè)試

1、軟件測(cè)試定義:使用人工或自動(dòng)手段來運(yùn)行或測(cè)定某個(gè)系統(tǒng)的過程,其目的

在于檢驗(yàn)它是否滿足規(guī)定的需求或是弄

一般模塊數(shù)據(jù)信息密制信息

清預(yù)期結(jié)果與實(shí)際結(jié)果之間的差別。

*:軟件測(cè)試的目的:盡可能地多發(fā)現(xiàn)程序中的錯(cuò)誤。

軟件測(cè)試準(zhǔn)則

1、追溯到需求

2、嚴(yán)格執(zhí)行測(cè)試計(jì)劃，排除隨意性

3、注意群集現(xiàn)象

4、避免自己檢查自己的程序

5、窮舉測(cè)試不可能

6、妥善保存測(cè)試計(jì)劃、用例、分析報(bào)告

2、軟件測(cè)試方法:靜態(tài)測(cè)試和動(dòng)態(tài)測(cè)試。

靜態(tài)測(cè)試

主要包括白盒測(cè)試方法和黑盒測(cè)試方法。

(1白盒測(cè)試

白盒測(cè)試方法也稱為結(jié)構(gòu)測(cè)試或邏輯驅(qū)動(dòng)測(cè)試。它是根據(jù)軟件產(chǎn)品的內(nèi)部工作

過程，檢查內(nèi)部成分,以確認(rèn)每種內(nèi)部操作符合設(shè)計(jì)規(guī)格要求。

白盒測(cè)試的基本原則:保證所測(cè)模塊中每一獨(dú)立路徑至少執(zhí)行一次;保證所測(cè)模

塊所有判斷的每一分支至少執(zhí)行一次;保證所測(cè)模塊每一循環(huán)都在邊界條件和一般

條件下至少各執(zhí)行一次;驗(yàn)證所有內(nèi)部數(shù)據(jù)結(jié)構(gòu)的有效性。

*：白盒測(cè)試法的測(cè)試用例是根據(jù)程序的內(nèi)部邏輯來設(shè)計(jì)的，主要用軟件的單元

測(cè)試，主要方法有邏輯覆蓋、基本路徑測(cè)試等。

A、邏輯覆蓋。邏輯覆蓋泛指一系列以程序內(nèi)部的邏輯結(jié)構(gòu)為基礎(chǔ)的測(cè)試用例

設(shè)計(jì)技術(shù)。通常程序中的邏輯表示有判斷、分支、條件等幾種表示方法。

語句覆蓋:選擇足夠的測(cè)試用例，使得程序中每一個(gè)語句至少都能被執(zhí)行一次。

路徑覆蓋:執(zhí)行足夠的測(cè)試用例，使程序中所有的可能的路徑都至少經(jīng)歷一次。

判定覆蓋:使設(shè)計(jì)的測(cè)試用例保證程序中每個(gè)判斷的每個(gè)取值分支（T或F至少

經(jīng)歷一次。

條件覆蓋:設(shè)計(jì)的測(cè)試用例保證程序中每個(gè)判斷的每個(gè)條件的可能取值至少執(zhí)

行一次。

判斷-條件覆蓋:設(shè)計(jì)足夠的測(cè)試用例,使判斷中每個(gè)條件的所有可能取值至少執(zhí)

行一次，同時(shí)每個(gè)判斷的所有可能取值分支至少執(zhí)行一次。

*：邏輯覆蓋的強(qiáng)度依次是:語句覆蓋〈路徑覆蓋〈判定覆蓋〈條件覆蓋〈判斷-條件

覆蓋。

B、基本路徑測(cè)試。其思想和步驟是,根據(jù)軟件過程性描述中的控制流程確定程

序的環(huán)路復(fù)雜性度量，用此度量定義基本路徑集合，并由此導(dǎo)出一組測(cè)試用例，對(duì)每一

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

（2黑盒測(cè)試

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

功能是否滿足需求進(jìn)行測(cè)試和驗(yàn)證。

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

誤、性能錯(cuò)誤、初始化和終止條件錯(cuò)誤。黑盒測(cè)試不關(guān)心程序內(nèi)部的邏輯,只是根

據(jù)程序的功能說明來設(shè)計(jì)測(cè)試用例，主要方法有等價(jià)類劃分法、邊界值分析法、錯(cuò)

誤推測(cè)法和因果圖等，主要用軟件的確認(rèn)測(cè)試。

它是將程序的所有可能的輸入數(shù)據(jù)劃分成若干部分（及若干等價(jià)類，然后從每個(gè)

等價(jià)類中選取數(shù)據(jù)作為測(cè)試用例。

撞態(tài)瀏試

用】本義：1狀

B

c

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

測(cè)試。

(1單元測(cè)試

曲未測(cè)同

各種錯(cuò)誤。

單元測(cè)試根據(jù)程序的內(nèi)部結(jié)構(gòu)來設(shè)計(jì)測(cè)試用例，其依據(jù)是詳細(xì)設(shè)計(jì)說明書和源

程序。單元測(cè)試的技術(shù)可以采用靜態(tài)分析和動(dòng)態(tài)測(cè)試。對(duì)動(dòng)態(tài)測(cè)試通常以白盒測(cè)試

為主，輔之以黑盒測(cè)試。

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

界測(cè)試。

*：在進(jìn)行單元測(cè)試時(shí)要用一些輔助模塊去模擬與被測(cè)模塊相聯(lián)系的其他模塊，

即為被測(cè)模塊設(shè)計(jì)和搭建驅(qū)動(dòng)模塊和

業(yè)動(dòng)模塊|甌石

樁模塊

困

(2集成測(cè)試

集成測(cè)試是測(cè)試和組裝軟件的過程，它是把模塊在按照設(shè)計(jì)要求組裝起來的同

時(shí)進(jìn)行測(cè)試，主要目的是發(fā)現(xiàn)與接口有關(guān)的錯(cuò)誤。

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

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

條件和非法輸入的測(cè)試等。

集成測(cè)試通常采用兩種方式:非增量方式組裝與增量方式組裝。

業(yè)動(dòng)模塊

試,最終得到要求的軟件系統(tǒng)。

以動(dòng)模塊I

組裝的過程中邊連接邊測(cè)試，以發(fā)現(xiàn)連接過程中產(chǎn)生的問題。最后通過增殖逐

步組裝成要求的軟件系統(tǒng)。增量方式組裝又包括自頂向下、自底向上、自頂向下與

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

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

確認(rèn)測(cè)試的任務(wù)是驗(yàn)證軟件的有效性，即驗(yàn)證軟件的功能和性能及其他特性是

否與用戶的要求一致。

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

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

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

日動(dòng)模塊|

系統(tǒng)測(cè)試的測(cè)試用例應(yīng)根據(jù)需求分析規(guī)格說明來設(shè)計(jì)，并在實(shí)際使用環(huán)境下來

運(yùn)行。

系統(tǒng)測(cè)試的具體實(shí)施一般包括:功能測(cè)試、性能測(cè)試、操作測(cè)試、配置測(cè)試、

外部接口測(cè)試、安全性測(cè)試等。

3.5程序的調(diào)試

程序調(diào)試的任務(wù)是診斷和改正程序中的錯(cuò)誤,主要在開發(fā)階段進(jìn)行，調(diào)試程序應(yīng)

該由編制源程序的程序員來完成。

程序調(diào)試的基本步驟：(1錯(cuò)誤定位;(2糾正錯(cuò)誤;(3回歸測(cè)試。

*:軟件的調(diào)試后要進(jìn)行回歸測(cè)試,防止引進(jìn)新的錯(cuò)誤。

軟件調(diào)試可分為靜態(tài)調(diào)試和動(dòng)態(tài)調(diào)試。靜態(tài)調(diào)試主要是指通過人的思維來分析

源程序代碼和排錯(cuò)，是主要的調(diào)試手段，而動(dòng)態(tài)調(diào)試是輔助靜態(tài)調(diào)試。

對(duì)軟件主要的調(diào)試方法可以采用：

(1強(qiáng)行排錯(cuò)法。主要方法有:通過內(nèi)存全部打印來排錯(cuò);在程序特定部位設(shè)置打

印語句;自動(dòng)調(diào)試工具。

(2回溯法。發(fā)現(xiàn)了錯(cuò)誤,分析錯(cuò)誤征兆，確定發(fā)現(xiàn)“癥狀”的位置。一般用于小程

序。

(3原因排除法。是通過演繹、歸納和二分法來實(shí)現(xiàn)的。

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

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

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

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

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

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

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

(1數(shù)據(jù):實(shí)際上就是描述事物的符號(hào)記錄。

數(shù)據(jù)的特點(diǎn):有一定的結(jié)構(gòu)，有型與值之分0數(shù)據(jù)的型給出了數(shù)據(jù)表示的類型，如

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

(2

數(shù)據(jù)庫(DB)

被各個(gè)應(yīng)用程序所共享。

數(shù)據(jù)庫存放數(shù)據(jù)是按數(shù)據(jù)所提供的數(shù)據(jù)模式存放的，具有集成與共享的特點(diǎn)，亦

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

程序所使用。

數(shù)據(jù)庫(DB)

3

服務(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)建提

供有效的存取方法與手段。

3數(shù)據(jù)操縱。數(shù)據(jù)庫管理系統(tǒng)為用戶使用數(shù)據(jù)庠中的數(shù)據(jù)提供方便，它一般提供

如查詢、插入、修改以及刪除數(shù)據(jù)的功能。此外，它自身還具有做簡(jiǎn)單的算術(shù)運(yùn)算

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

力。

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

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

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

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

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

本功能。

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

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

作中如果不加控制和管理，多個(gè)應(yīng)用程序間就會(huì)相互干擾，從而對(duì)數(shù)據(jù)庫中的數(shù)據(jù)造

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

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

管理系統(tǒng)必須有能力及時(shí)進(jìn)行恢復(fù).這就是數(shù)據(jù)庫的故障恢復(fù)。

6數(shù)據(jù)的服務(wù)。數(shù)據(jù)庫管理系統(tǒng)提供對(duì)數(shù)據(jù)庫中數(shù)據(jù)的多種服務(wù)功能，如數(shù)據(jù)拷

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

（5:由數(shù)據(jù)庫（數(shù)據(jù)、數(shù)據(jù)庫管理系統(tǒng)（軟件、數(shù)據(jù)庫管理員（人員、硬件平臺(tái)（硬

件、軟件平臺(tái)（軟件五個(gè)部分構(gòu)成的運(yùn)行實(shí)體。

（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)歷了三個(gè)階段:人工管理階段、文件系統(tǒng)階段和數(shù)據(jù)

庫系統(tǒng)階段。

下表是數(shù)據(jù)管理三個(gè)階段的比較:

［，（DB）

數(shù)據(jù)原管理系統(tǒng)（DB野）

數(shù)據(jù)庫管理員（DB《）一

數(shù)據(jù)庫系統(tǒng)（DBS）1I

人工管理階段文件系統(tǒng)階段數(shù)據(jù)庫系統(tǒng)階段

應(yīng)用背景科學(xué)計(jì)算科學(xué)計(jì)算、管理大規(guī)模管理

硬件背景無直接存取存儲(chǔ)設(shè)磁盤、俄鼓大容量他備盤

背

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

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

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

*:數(shù)據(jù)庫系統(tǒng)可以減少數(shù)據(jù)冗余，但無法避免一切冗余。

（3數(shù)據(jù)獨(dú)立性:?即數(shù)據(jù)庫中數(shù)據(jù)獨(dú)立于應(yīng)用程序而不依賴于應(yīng)用程序。也就是

說，數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)與存取方式的改變不會(huì)影響應(yīng)用程序。

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

阿臚獨(dú)、立件

1

儲(chǔ)的更換、存取方式改變等都不影響數(shù)據(jù)庫的邏輯結(jié)構(gòu)，從而不致弓I起應(yīng)用程

序的變化。

'故扣獨(dú):0■件

2

修改應(yīng)用程序，這就是數(shù)據(jù)的邏輯獨(dú)立性。

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

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

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

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

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

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

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

|次據(jù)獨(dú)

物理獨(dú)立

涉處熱工?

1

2

3

件級(jí)上，它還未深入到設(shè)備級(jí)上(如磁盤及磁盤操作。內(nèi)模式對(duì)一般用戶是透明

的，但它的設(shè)計(jì)直接影響數(shù)據(jù)庫的性能。

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

數(shù)如:獨(dú)。:件

1

相應(yīng)的概念模式/內(nèi)模式的映射,使得數(shù)據(jù)庫的邏輯模式不變,其外模式不變、應(yīng)

用程序不用修改，從而保證數(shù)據(jù)具有

數(shù)擔(dān)獨(dú)、工性

2

模式/邏輯模式映射，使得用戶所使用的那部分外模式不變,從而應(yīng)用程序不必修

改,保證數(shù)據(jù)具有較高的邏輯獨(dú)立性。

4.2數(shù)據(jù)模型

1、數(shù)據(jù)模型

（1數(shù)據(jù)模型的概念:是數(shù)據(jù)特征的抽象，它從抽象層次上描述了系統(tǒng)的靜態(tài)特

征、動(dòng)態(tài)行為和約束條件，為數(shù)據(jù)庫系統(tǒng)的信息表示與操作提供一個(gè)抽象的框架。

（2數(shù)據(jù)模型所描述的內(nèi)容有三個(gè)部分，它們是數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操作與數(shù)據(jù)約

束。

1數(shù)據(jù)結(jié)構(gòu):數(shù)據(jù)結(jié)啕是所研究的對(duì)象類型的集合，包括與數(shù)據(jù)類型、內(nèi)容、性

質(zhì)有關(guān)的對(duì)象，以及與數(shù)據(jù)之間聯(lián)系有關(guān)的對(duì)象。它用于描述系統(tǒng)的靜態(tài)特性。

2數(shù)據(jù)操作:數(shù)據(jù)操作是對(duì)數(shù)據(jù)庫中各種對(duì)象（型的實(shí)例（值允許執(zhí)行的操作的集

合，包括操作的含義、符號(hào)、操作規(guī)則及實(shí)現(xiàn)操作的語句等。它用于描述系統(tǒng)的動(dòng)

態(tài)特性。

3數(shù)據(jù)的約束條件:數(shù)據(jù)的約束條件是一組完整性規(guī)則的集合。完整性規(guī)則是給

定的數(shù)據(jù)模型中數(shù)據(jù)及其聯(lián)系所具有的制約和依存規(guī)則，用以限定符號(hào)數(shù)據(jù)模型的

數(shù)據(jù)庫狀態(tài)及狀態(tài)的變化,以保證數(shù)據(jù)的正確、有效和相容。（3數(shù)據(jù)模型分為概念

模型、邏輯數(shù)據(jù)模型和物理模型三類：

1概念數(shù)據(jù)模型:簡(jiǎn)稱概念模型，是對(duì)客觀世界復(fù)雜事物的結(jié)構(gòu)描述及它們之間

的內(nèi)在聯(lián)系的刻畫。概念模型主要有:E-R模型（實(shí)體聯(lián)系模型、擴(kuò)充的E-R模型、

面向?qū)ο竽Ｐ图爸^詞模型等。

2邏輯數(shù)據(jù)模型:又稱數(shù)據(jù)模型，是一種面向數(shù)據(jù)庫系統(tǒng)的模型，該模型著重于在

數(shù)據(jù)庫系統(tǒng)一級(jí)的實(shí)現(xiàn)。邏輯數(shù)據(jù)模型主要有:層次模型、網(wǎng)狀模型、關(guān)系模型、

面向?qū)ο竽Ｐ偷取?/p>

3物理數(shù)據(jù)模型:又稱物理模型，它是一種面向計(jì)算機(jī)物理表示的模型，此模型給

出了數(shù)據(jù)模型在計(jì)算機(jī)上物理結(jié)構(gòu)的表示。

2、實(shí)體聯(lián)系模型及E-R圖（1E-R模型的基本概念：1實(shí)體:現(xiàn)實(shí)世界中的事

物。2屬性:事物的特性。

3聯(lián)系:現(xiàn)實(shí)世界中事物間的關(guān)系。實(shí)體集的關(guān)系有一對(duì)一、一對(duì)多、多對(duì)多的

聯(lián)系。

E-R模型三個(gè)基本概念之間的聯(lián)接關(guān)系：1實(shí)體集（聯(lián)系與屬性間的聯(lián)接關(guān)系;2

實(shí)體（集與聯(lián)系。*：E-R模型的基本成分是實(shí)體和聯(lián)系。（2E-R模型的圖示法：I實(shí)

體集:用矩形表示。2屬性:用橢圓形表示。3聯(lián)系:用菱形表示。

4實(shí)體集與屬性間的聯(lián)接關(guān)系:用無向線段表示。5實(shí)體集與聯(lián)系間的聯(lián)接關(guān)系:

用尢向線段表示。

（3數(shù)據(jù)庫管理系統(tǒng)常見的數(shù)據(jù)模型有層次模型、網(wǎng)狀模型和關(guān)系模型三種。

1層次模型的基本結(jié)構(gòu)是樹形結(jié)構(gòu)，具有以下特點(diǎn):A、每棵樹有且僅有一個(gè)無

雙親結(jié)點(diǎn)，稱為根;B、樹中除根外所有結(jié)點(diǎn)有且僅有一個(gè)雙親。

2網(wǎng)狀模型是層次模型的一個(gè)特例，從圖論上看,網(wǎng)狀模型是一個(gè)不加任何條件

限制的無向圖。

3)關(guān)系模型采用二維表來表示，簡(jiǎn)稱表，由表框架及表的元組組成。一個(gè)二

維表就是一個(gè)關(guān)系。二維表的表框架由n個(gè)命名的屬性組成，n稱為屬性元數(shù)。每

個(gè)屬性有一個(gè)取值范圍稱為值域。表框架對(duì)應(yīng)了關(guān)系的模式，即類型的概念。在

表框架中按行可以存放數(shù)據(jù)，每行數(shù)據(jù)稱為元組，實(shí)際上，一個(gè)元組是由n個(gè)元組

分量所組成，每個(gè)元組分量是表框架中每個(gè)屬性的投影值。學(xué)號(hào)2(X)7102

200720320073052007406姓名張潔然李一明王劉麗宏性別男男女男出生年

月07-07-8805-01-8704-09-8810-11-88班級(jí)籍貫07動(dòng)畫1班天津07播音5班廣

西南寧07管理4班遼寧沈陽07新聞3班江蘇南京*：同一個(gè)關(guān)系模型的任兩個(gè)

元組值不能完全相同。主碼：或稱為關(guān)鍵字、主鍵，簡(jiǎn)稱碼、鍵，表中的一個(gè)屬

性或幾個(gè)屬性的組合、其值能唯一地標(biāo)識(shí)表中一個(gè)元組的，稱為關(guān)系的主碼或關(guān)

鍵字。例如，學(xué)生的學(xué)號(hào)。主碼屬性不能取空值。外部關(guān)鍵字：或稱為外鍵，在

一個(gè)關(guān)系中含有與另一個(gè)關(guān)系的關(guān)鍵字相對(duì)應(yīng)的屬性組稱為該關(guān)系的外部關(guān)鍵字。

外部關(guān)鍵字取空值或?yàn)橥獠勘碇袑?duì)應(yīng)的關(guān)鍵字值。例如，在學(xué)生表中含有的所屬

班級(jí)名字，是班級(jí)表中的關(guān)鍵字屬性，它是學(xué)生表中的外部關(guān)鍵字。