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

1.1算法的復(fù)雜度

1.算法的基本概念

1、算法是指解題方案的準(zhǔn)確而完整的描述。換句話說，算法是對特定問題求

解步驟的一種描述。

*算法不等于程序，也不等計(jì)算機(jī)方法,程序的編制丕可能優(yōu)壬算法的設(shè)計(jì)限

（1）算法的基本特征

算法一般具有4個(gè)基本特征：可行性、確定性、有窮性、擁有足夠的情報(bào)。

注:&確定性,算法中每一步驟都必須有明確定義,不充許有模棱兩可的解釋,

不允許有多義性;&有窮性,算法必須能在有限的時(shí)間內(nèi)做完,即能在執(zhí)行有

限個(gè)步驟后終止,包括合理的執(zhí)行時(shí)

間的含義;

*算法的基本要素：一是對數(shù)據(jù)對象的運(yùn)算和操作；二是算法的控制結(jié)構(gòu)。

（2）*算法的基本運(yùn)算和操作包括：算術(shù)運(yùn)算、邏輯運(yùn)算、關(guān)系運(yùn)算、數(shù)據(jù)

傳輸。

（3）本算法的3種基本控制結(jié)構(gòu)是：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)。

（4）算法基本設(shè)計(jì)方法：列舉法、歸納法、遞推、遞歸、減半遞推技術(shù)、回

溯法。

（5）指令系統(tǒng):指的是一個(gè)計(jì)算機(jī)系統(tǒng)能執(zhí)行的所有指令的集合。

2.算法復(fù)雜度

*算法復(fù)雜度包括時(shí)間復(fù)雜度和空間復(fù)雜度。注意兩者的區(qū)別，無混淆，見表

時(shí)間復(fù)雜執(zhí)行算法所需要的計(jì)算工

度作量

空間復(fù)雜執(zhí)行這個(gè)算法所需要的內(nèi)

度存空間

1.2數(shù)據(jù)結(jié)構(gòu)

1.2.1邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)

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

(1)*數(shù)據(jù)結(jié)構(gòu):指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合O

②數(shù)據(jù)結(jié)構(gòu)研究的正個(gè)方面；,I、數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)

系,…即數(shù)據(jù)的邏輯結(jié)構(gòu);」I、在對數(shù)據(jù)進(jìn)任處理時(shí),…各數(shù)據(jù)元素在計(jì)算機(jī)中的存

儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu);…in、對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。

2.邏輯結(jié)構(gòu)

數(shù)據(jù)的邏輯結(jié)構(gòu)是對數(shù)據(jù)元素之間的邏輯關(guān)系的描述。數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個(gè)

要素：一是數(shù)據(jù)元素的集合，通常記為D；二是D上的關(guān)系，它反映了數(shù)據(jù)元素

之間的前后件關(guān)系，通常記為R。一個(gè)數(shù)據(jù)結(jié)構(gòu)可以表示成：B=(D,R)

3.存儲結(jié)構(gòu)

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

注：順序存儲方式主要用于線性的數(shù)據(jù)結(jié)構(gòu)，它把邏輯上相鄰的數(shù)據(jù)元素存儲

在物理上相鄰的存儲單元里，結(jié)點(diǎn)之間的關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。

鏈?zhǔn)酱鎯Y(jié)構(gòu)就是在每個(gè)結(jié)點(diǎn)中至少包含一個(gè)指針域,用指針來體現(xiàn)數(shù)據(jù)元素

之間邏輯上的聯(lián)系。

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

的物理結(jié)構(gòu))是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲至間里的存放形式?同二種邏輯

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

1.2.2線性結(jié)構(gòu)和非線性結(jié)構(gòu)

根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分

為兩大類型：線性結(jié)構(gòu)及非線性結(jié)構(gòu)。

（1）如果一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個(gè)條件：

②每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。

則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)。線性結(jié)構(gòu)又稱線性表。在一個(gè)線性結(jié)構(gòu)中插入

或刪除任何一個(gè)結(jié)點(diǎn)后還應(yīng)是線性結(jié)構(gòu)。棧，、隊(duì)列、串*線性鏈表等都為線性結(jié)

構(gòu)。

如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱之為非線性結(jié)構(gòu)。數(shù)組、廣義表、樹和

圖等數(shù)據(jù)結(jié)構(gòu)都是非線性結(jié)構(gòu)。

1.2.3線性表及其順序存儲結(jié)構(gòu)

線性表的存儲結(jié)構(gòu)主要分為順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)

線性表是由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的序號，元素之

間的相對位置是線性的。在復(fù)雜線性表中,由若干項(xiàng)數(shù)據(jù)元素組成的數(shù)據(jù)元素

稱為記錄，而由多個(gè)記錄構(gòu)成的線性表又稱為文件。

非空線性表的結(jié)構(gòu)特征：（1）且只有一個(gè)根結(jié)點(diǎn)al,它無前件；（2）有且只

有一個(gè)終端結(jié)點(diǎn)an,它無后件；（3）除根結(jié)點(diǎn)及終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)有

且只有一個(gè)前件，也有且只有一個(gè)后件。結(jié)點(diǎn)個(gè)數(shù)n稱為線性表的長度，當(dāng)n=0

時(shí)，稱為空表。*線性表的順序存儲結(jié)構(gòu)具有以下兩個(gè)基本特點(diǎn)：（1）線性表

中所有元素的所占的存儲空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲空間

中是按邏輯順序依次存放的。

ai的存儲地址為：ADR（ai）=ADR（al）+（i-l）k,,ADR（al）為第一個(gè)元素的地址，k

代表每個(gè)元素占的字節(jié)數(shù)。順序表的運(yùn)算：查找、插入、刪除3種。

1.3棧（重點(diǎn)）

＞L棧的基本概念（棧（stack）是一種特殊的線性表）

＞棧星限定在T進(jìn)行插入及刪除運(yùn)算的線性熱

＞在棧史,-允許插入及刪除的一端稱為棧頂,不允許插入及刪除的另一端稱

為棧底。棧頂元素總是最后被插入的元素,棧底元素總是最先被插入陋素」

即棧是按照“先進(jìn)后出”（FILO）或“后進(jìn)先出”（LIFO）的原則組織數(shù)據(jù)的。

＞棧具有記憶作用。

注:用top表示棧頂位置,用bottom表示棧底。當(dāng)表中沒有元素時(shí)稱為空棧

2.棧的基本運(yùn)算：（1）插入元素稱為入棧運(yùn)算；（2）刪除元素稱為退棧運(yùn)算；

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

計(jì)算棧的個(gè)數(shù)：棧底-棧頂+1

1.4隊(duì)列（重點(diǎn)）

1.隊(duì)列的基本概念

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

后就指針指向隊(duì)尾，復(fù)9成指針指向隊(duì)頭,隊(duì)列懸“先進(jìn)先出"（FIEQ）或“后

進(jìn)后出”（LILO）的線性表。

2.隊(duì)列運(yùn)算

入隊(duì)運(yùn)算是往隊(duì)列隊(duì)尾插入一個(gè)數(shù)據(jù)元素；退隊(duì)運(yùn)算是從隊(duì)列的隊(duì)頭刪除一個(gè)

數(shù)據(jù)元素。

隊(duì)列的順序存儲結(jié)構(gòu)一般采用隊(duì)列循環(huán)的形式。循環(huán)隊(duì)列s=0表示隊(duì)列空；s=l

且front二rear表示隊(duì)列滿。計(jì)算循環(huán)隊(duì)列的元素個(gè)數(shù)：“尾指針減頭指針”，若

為負(fù)數(shù)，再加其容量即可。

隊(duì)列是一種特殊的線性表九循環(huán)隊(duì)列是隊(duì)列的順序存儲結(jié)構(gòu)￡.

1.5鏈表

數(shù)據(jù)結(jié)構(gòu)中的每一個(gè)結(jié)點(diǎn)對應(yīng)于一個(gè)存儲單元，這種存儲單元稱為存儲結(jié)點(diǎn)，

簡稱結(jié)點(diǎn)￡結(jié)點(diǎn)由兩部分組成：（1）用于存儲數(shù)據(jù)元素值2稱為數(shù)據(jù)域;（2）

用王存放指針」稱為撤讖」用王指向前二個(gè)或后二個(gè)結(jié)尾在鏈?zhǔn)酱鎯Y(jié)構(gòu)

中，存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以不連續(xù),多數(shù)據(jù)結(jié)點(diǎn)的存儲順莊及數(shù)據(jù)元素

之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定

的。鏈?zhǔn)酱鎯Ψ绞郊纯捎糜诒硎揪€性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。

線性鏈表，HEAD稱為頭指針,HEAD=NIJLL（或0）稱為空表，如果是兩指針：左

指針（Llink）指向前件結(jié)點(diǎn)，右指針（Rlink）指向后件結(jié)點(diǎn)。線性鏈表的基

本運(yùn)算：查找、插入、刪除。

1.6樹及二叉樹★★★★★

1.樹的基本概念

樹是一種簡單的非線性結(jié)構(gòu)二所有元素之間具有明顯的層次特性j在樹結(jié)構(gòu)中,

每一個(gè)結(jié)點(diǎn)只有一個(gè)前件,稱為父結(jié)點(diǎn),沒有前件的結(jié)點(diǎn)只有二個(gè)人稱為樹的

根結(jié)點(diǎn)，簡稱樹的根。每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒

有后件的結(jié)點(diǎn)稱為歸結(jié)點(diǎn)八套樹結(jié)構(gòu).扎…=±M點(diǎn)所擁直的后性的個(gè)數(shù)稱為

該結(jié)點(diǎn)的度，所有結(jié)點(diǎn)中最大的度稱為樹的度。樹的最大層次稱為樹的深度?！?/p>

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

二叉樹是一種很有用的非線性結(jié)構(gòu)，具有以下兩個(gè)特點(diǎn)：（1）非空二叉樹只有

一個(gè)根結(jié)點(diǎn)；（2）每一個(gè)結(jié)點(diǎn)最多有兩棵子樹，且分別稱為該結(jié)點(diǎn)的左子樹及

右子樹。

＞基本性質(zhì)：性質(zhì)1在二叉樹的第k層上，最多有個(gè)結(jié)點(diǎn)。性質(zhì)2深度為m

的二叉樹最多有個(gè)個(gè)結(jié)點(diǎn)。性質(zhì)3卷任意一探二又樹中，度數(shù)為o的結(jié)

點(diǎn)（即葉子結(jié)點(diǎn)）總比度為2的結(jié)點(diǎn)多一個(gè)?他質(zhì)4具有旦個(gè)結(jié)點(diǎn)的二叉

樹,其深度至少為…，其史…表示取…的整數(shù)部分

>3.滿二叉樹及完全二叉樹

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

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

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

注意:深度為m的滿二叉樹最多有個(gè)個(gè)結(jié)點(diǎn)

完全二叉樹具有以下兩個(gè)性質(zhì)：

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

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

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

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

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

為INT(k/2)；

②若2kWn,則編號為k的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號為2k；否則該結(jié)點(diǎn)無左子結(jié)點(diǎn)(顯

然也沒有右子結(jié)點(diǎn))；

③若2k+lWn,則編號為k的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號為2k+l；否則該結(jié)點(diǎn)無右子結(jié)

點(diǎn)o

二叉樹存儲結(jié)構(gòu)采用鏈?zhǔn)酱鎯Y(jié)構(gòu)-對于滿二叉樹及完全二叉樹可以按層序進(jìn)

行順序存儲

4.二叉樹的遍歷★★★★

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

以下三種

⑴前序遍歷(DLR):若二叉樹為空,則結(jié)束返回。杳則；首先訪問根結(jié)點(diǎn).然

后遍歷左子樹，最后遍歷右子樹;“并且,在遍歷左右子樹時(shí)，仍然先訪問根

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

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

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

然后訪問根結(jié)點(diǎn),最后遍歷右子樹。

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

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

然后遍歷右子樹"最后訪問根結(jié)點(diǎn).

1.7查找技術(shù)

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

素。

查找成功/查找失敗

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

①如果線性表為無序表，則不管是順序存儲結(jié)構(gòu)還是鏈?zhǔn)酱鎯Y(jié)構(gòu)，只能用順

序查找；

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

查找分為：順序查找二分法查找

二分法查找只適用于順序存儲的有序表（能使用二分法查找的線性表必須滿足

用順序存儲結(jié)構(gòu)和線性表尾有序表兩個(gè)條件。）對壬長度為n的有序線性表，最

壞情況區(qū)需比較次,而順序查找需要比較n次。

注:“有序”是特指元素按非遞減排列,即從小到大排列,但允許相鄰元素相

等。下一節(jié)排序中,有序的含義也是如此

1.8排序技術(shù)

排序是指將一個(gè)無序序列整理成按值非遞減順序排列的有序序列。1.交換類排

序法（冒泡排序，快速排序）2.插入類排序法（簡單插入排序，希爾排序）3.

選擇類排序法（簡單選擇排序，堆排序）

冒泡排序法,快速排序法，簡單插入排序法,簡單選擇排序法,最壞需要比較的

次數(shù)為n(n-l)/2

希爾排序，最壞需要比較的次數(shù)為°(”")雄排序，最壞需要比較的次數(shù)為

O(nlog2n)

相比以上幾種(除希爾排序法外)，堆排序法的時(shí)間復(fù)雜度最小。

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

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

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

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

〃清晰第一、效率第二〃已成為當(dāng)今主導(dǎo)的程序設(shè)計(jì)風(fēng)格。

形成良好的程序設(shè)計(jì)風(fēng)格需注意：

1.源程序文檔化；

2.數(shù)據(jù)說明的方法；

3.語句的結(jié)構(gòu)；

4.輸入和輸出。

注釋分序言性注釋和功能性注釋。語句結(jié)構(gòu)清晰第一、效率第二。

2.2結(jié)構(gòu)化程序設(shè)計(jì)

1.結(jié)構(gòu)化程序設(shè)計(jì)方法的四條原則是:L自頂向下逐步求精;/.模塊化“

4.限制使用goW語句…

2、結(jié)構(gòu)化程序的基本結(jié)構(gòu)及特點(diǎn)：

(1)順序結(jié)構(gòu)：一種簡單的程序設(shè)計(jì)，最基本、最常用的結(jié)構(gòu)；

(2)選擇結(jié)構(gòu)：又稱分支結(jié)構(gòu)，包括簡單選擇和多分支選擇結(jié)構(gòu)，可根據(jù)

條件，判斷應(yīng)該選擇哪一條分支來執(zhí)行相應(yīng)的語句序列；

（3）循環(huán)結(jié)構(gòu)：又稱重復(fù)結(jié)構(gòu)，可根據(jù)給定條件，判斷是否需要重復(fù)執(zhí)行

某一相同或類似的程序段。

結(jié)構(gòu)化程序設(shè)計(jì)的特點(diǎn)：只有一個(gè)入口和出口

2.3面向?qū)ο蠓椒?/p>

面向?qū)ο蟮某绦蛟O(shè)計(jì)：以60年代末挪威奧斯陸大學(xué)和挪威計(jì)算機(jī)中心研制的

SIMULA語言為標(biāo)志。

面向?qū)ο蠓椒ǖ膬?yōu)點(diǎn)：（1）及人類習(xí)慣的思維方法一致；（2）穩(wěn)定性好；（3）

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

球面向?qū)ο蟮某绦蛟O(shè)it主要考慮的是提高軟件的可重用性泰對象是屬性和左

法的封裝體2…

”二仝對象由對象名、屬性和操作三部分組虹

面向?qū)ο蟮幕咎攸c(diǎn)：繼承性，多態(tài)性，封裝性

*:信息隱蔽是通過對象的封裝性來實(shí)現(xiàn)的?

對象是面向?qū)ο蠓椒ㄖ凶罨镜母拍?，可以用來表示客觀世界中的任何實(shí)體，

對象是實(shí)體的抽象。

面向?qū)ο蟮某绦蛟O(shè)計(jì)方法中的對象是系統(tǒng)中用來描述客觀事物的?個(gè)實(shí)體，

是構(gòu)成系統(tǒng)的一個(gè)基本單位

由一組表示其靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成。

屬性即對象所包含的信息，操作描述了對象執(zhí)行的功能，是對象的動態(tài)屬性，

操作也稱為方法或服務(wù)。

性；（5）模塊獨(dú)立性好?！?/p>

類是指具有共同屬性黑共同方法的對象的集合。所以類是對象的抽象，對象是

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

消息是一個(gè)實(shí)例及另一個(gè)實(shí)例之間傳遞的信息。對象間的通信靠消息傳遞。它

請求對象執(zhí)行某一處理

回答某一要求的信息，它統(tǒng)一了數(shù)據(jù)流和控制流

消息是一個(gè)實(shí)例及另一個(gè)實(shí)例之間傳遞的信息。

消息的組成包括（1）接收消息的對象的名稱；（2）消息標(biāo)識符，也稱消息名；

（3）零個(gè)或多個(gè)參數(shù)。

繼承是指能夠直接獲得已有的性質(zhì)和特征,而不必重復(fù)定義他們。

繼承分單繼承和多重繼承。單繼承指一個(gè)類只允許有一個(gè)父類,多重繼承指一

個(gè)類允許有多個(gè)父類。

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

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

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

出題量較小的一章。本章內(nèi)容比較少，也很

單，掌握住基本的概念就可以輕松應(yīng)對考試了，所以在這部分丟分，比較可

惜。）

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

3.1軟件工程基本概念

1.軟件定義及軟件特點(diǎn)

軟件指的是計(jì)算機(jī)系統(tǒng)中及硬件相互依存的另一部分，包括程序、數(shù)據(jù)和相關(guān)

文檔的完整集合。

根據(jù)應(yīng)用目標(biāo)的不同，軟件可分應(yīng)用軟件、系統(tǒng)軟件和支撐軟件（或工具軟件）

軟件的特點(diǎn)包括：（1）軟件是一種邏輯實(shí)體；（2）軟件的生產(chǎn)及硬件不同，它

沒有明顯的制作過程

（3）軟件在運(yùn)行、使用期間不存在磨損、老化問題；（4）軟件的開發(fā)、運(yùn)行

對計(jì)算機(jī)系統(tǒng)具有依賴

性，受計(jì)算機(jī)系統(tǒng)的限制，這導(dǎo)致了軟件移植的問題；（5）軟件復(fù)雜性高，成

本昂貴；（6）軟件開發(fā)

涉及諸多的社會因素。

2.軟件工程

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

中所遇到的一系列嚴(yán)重問題

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

方法、工具和過程。方法

完成軟件工程項(xiàng)目的技術(shù)手段；工具是支持軟件的開發(fā)、管理、文檔生成；過

程支持軟件開發(fā)的各個(gè)環(huán)

的控制、管理。

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

本活動：（1）P——軟件

規(guī)格說明；（2）D——軟件開發(fā)；（3）C——軟件確認(rèn)；（4）A——軟件演進(jìn)。

3.2軟件生命周期

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

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

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

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

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

格說明書

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

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

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

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

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

充和刪改。

*:軟件生命周期中所花費(fèi)最多的階段是軟件運(yùn)行維護(hù)階段

3、（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)證性。

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

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

析建立的模型的特性來分：靜態(tài)分析和動態(tài)分析。2.結(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）判

定表。

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

加工數(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í)體。

（1）數(shù)據(jù)流圖（DFD）是分析員及用戶之間極好的通信工具。

⑵數(shù)據(jù)字典（DD）是對數(shù)據(jù)流圖中所有元素的定義的集合，是結(jié)構(gòu)化分析的核

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

數(shù)據(jù)字典中有4種類型的條目：數(shù)據(jù)流、數(shù)據(jù)項(xiàng)、數(shù)據(jù)存儲和加工。

3、軟件需求規(guī)格說明書是需求分析階段的最后成果，是軟件開發(fā)的重要文檔之

一。它的特點(diǎn)是具有正確性、無歧義性、完整性、可驗(yàn)證性、一致性、可理解性、

可修改性和可追蹤性。

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

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

軟件設(shè)計(jì)的基本目標(biāo)是用比較抽象概括的方式確定目標(biāo)系統(tǒng)如何完成預(yù)定的任

務(wù)，軟件設(shè)計(jì)是確定系統(tǒng)的物理模型。軟件設(shè)計(jì)是開發(fā)階段最重要的步驟，是將

需求準(zhǔn)確地轉(zhuǎn)化為完整的軟件產(chǎn)品或系統(tǒng)的唯一途徑。

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

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

結(jié)構(gòu)設(shè)計(jì)，，將軟件需求轉(zhuǎn)化為軟件體系結(jié)構(gòu)，確定系統(tǒng)級接口、全局?jǐn)?shù)據(jù)結(jié)構(gòu)或

數(shù)據(jù)庫模式。

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

數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)。

軟件設(shè)計(jì)的一般過程：軟件設(shè)計(jì)是一個(gè)迭代的過程；先進(jìn)行高層次的結(jié)構(gòu)設(shè)計(jì)；

后進(jìn)行低層次的過程設(shè)計(jì)；穿插進(jìn)行數(shù)據(jù)設(shè)計(jì)和接口設(shè)計(jì)。

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

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

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

內(nèi)聚性：是一個(gè)模塊內(nèi)部各個(gè)元素間彼此結(jié)合的緊密程度的度量。

*:按內(nèi)聚性由弱到強(qiáng)排列，內(nèi)聚可以分為以下幾種：偶然內(nèi)聚、邏輯內(nèi)聚、時(shí)

間內(nèi)聚、過程內(nèi)聚、通信內(nèi)聚、順序內(nèi)聚及功能內(nèi)聚。

耦合性：是模塊間互相連接的緊密程度的度量。

*:按耦合性由高到低排列，耦合可以分為以下幾種：內(nèi)容耦合、公共耦合、外

部耦合、控制耦合、標(biāo)記耦合、數(shù)據(jù)耦合以及非直接耦合。

一個(gè)設(shè)計(jì)良好的軟件系統(tǒng)應(yīng)具有高內(nèi)聚、低耦合的特征。在結(jié)構(gòu)化程序設(shè)計(jì)中,

模塊劃分的原則是:模塊內(nèi)具有高內(nèi)聚度，模塊間具有低耦合度。

區(qū)總體設(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ì)文檔評審。

常用的軟件結(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ù)信息一

結(jié)構(gòu)圖的基本形式:基本形式、順序形式、重復(fù)形式、選擇形式。…結(jié)構(gòu)圖有四種

模塊類型“傳入模塊、傳出模塊二變換模塊和協(xié)調(diào)模塊2典型的數(shù)據(jù)流類型有兩

種“…變換型和事務(wù)型。變換型系統(tǒng)結(jié)構(gòu)圖由輸入「中心變捶、輸出三部分組成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é)。―

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

1.圖形工具:程序流程圖、N-S（方盒圖）、PAD（問題分析圖）和町以）（層次圖+輸

人/處理/輸出圖）-

程序流程圖中主要元素：1）方框：表示一個(gè)處理步驟2）菱形框：表示一個(gè)邏

輯條件3）箭頭：表示控制流向2、表格工具：判定表。

3、語言工具：PDL（偽碼）

3.5軟件測試

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

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

軟件測試的目的：盡可能地多發(fā)現(xiàn)程序中的錯(cuò)誤，不能也不可能證明程序沒

有錯(cuò)誤。軟件測試的關(guān)鍵是設(shè)計(jì)測試用例，一個(gè)好的測試用例能找到迄今為止

尚未發(fā)現(xiàn)的錯(cuò)誤。

2.軟件測試方法：靜態(tài)測試和動態(tài)測試。

靜態(tài)測試：包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量。不實(shí)際運(yùn)行軟件，主

要通過人工進(jìn)行。

動態(tài)測試：是基于計(jì)算機(jī)的測試，主要包括白盒測試方法和黑盒測試方法。

（1）白盒測試

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

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

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

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

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

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

元測試，主要方法有邏輯覆蓋、基本路徑測試等。

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

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

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

次。

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

次。

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

少經(jīng)歷一次。

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

執(zhí)行一次。

判斷-條件覆蓋：設(shè)計(jì)足夠的測試用例，使判斷中每個(gè)條件的所有可能取值至

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

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

條件覆蓋。

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

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

例，對每一條獨(dú)立執(zhí)行路徑進(jìn)行測試。

(2)黑盒測試

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

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

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

誤、性能錯(cuò)誤、初始化和終止條件錯(cuò)誤。

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

主要方法有等價(jià)類劃分法、邊界值分析法、錯(cuò)誤推測法等，主要用軟件的確認(rèn)

測試。

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

測試

3.6程序的調(diào)試

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

應(yīng)該由編制源程序的程序員

來完成。

程序調(diào)試的基本步驟：（1）錯(cuò)誤定位；（2）修改設(shè)計(jì)和代碼，以排除錯(cuò)誤；（3）

進(jìn)行回歸測試，防止引進(jìn)

新的錯(cuò)誤。

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

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

建序化附挑錯(cuò),建主

要的調(diào)試手段，而動態(tài)調(diào)試是輔助靜態(tài)調(diào)試。

對軟件主要的調(diào)試方法可以采用：（1）強(qiáng)行排錯(cuò)法。（2）回溯法。（3）原因排除法。

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

是公共基礎(chǔ)部分比較重要的一章。從出題的

深度來看,主要考察對基本概念的識記，有少量對基本原理的理解，沒有

實(shí)際運(yùn)用，因此考生在復(fù)習(xí)本章時(shí).，重點(diǎn)應(yīng)

放在基木概念的記憶和基木原理的理解上“）

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

4.1數(shù)據(jù)庫的基本概念

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

（1）數(shù)據(jù)：實(shí)際上就是描述事物的符號記錄。數(shù)據(jù)的特點(diǎn)：有一定的結(jié)構(gòu)，有

型及值之分，如整型、實(shí)型、字符型等。

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

介質(zhì)內(nèi)，是多種應(yīng)用數(shù)據(jù)的集成，并可被各個(gè)應(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ù)庫構(gòu)建其數(shù)據(jù)框架；（2）

數(shù)據(jù)存取的物理構(gòu)建：為數(shù)據(jù)模式的物理存取及構(gòu)建提供有效的存取方法及手

段；（3）數(shù)據(jù)操縱：為月戶使用數(shù)據(jù)庫的數(shù)據(jù)提供方便，如查詢、插入、修改、

刪除等以及簡單的算術(shù)運(yùn)算及統(tǒng)計(jì)；（4）數(shù)據(jù)的完整性、安生性定義及檢查；

（5）數(shù)據(jù)庫的并發(fā)控制及故障恢復(fù)；（6）數(shù)據(jù)的服務(wù)：如拷貝、轉(zhuǎn)存、重組、

性能監(jiān)測、分析等。

為完成數(shù)據(jù)庫管理系統(tǒng)的功能，數(shù)據(jù)庫管理系統(tǒng)提供相應(yīng)的數(shù)據(jù)語言：數(shù)據(jù)定

義語言、數(shù)據(jù)操縱語言、數(shù)據(jù)控制語言。數(shù)據(jù)語言按其使用方式具有兩種結(jié)構(gòu)

形式：交互式命令（又稱自含型或自主型語言）宿主型語言（一般可嵌入某些宿

主語言中）。

數(shù)據(jù)定義語言：負(fù)責(zé)數(shù)據(jù)的模式定義及數(shù)據(jù)的物理存取構(gòu)建；

數(shù)據(jù)操縱語言：負(fù)責(zé)數(shù)據(jù)的操縱，如查詢及增、冊k改等；

數(shù)據(jù)控制語言：負(fù)責(zé)數(shù)據(jù)完整性、安全性的定義及檢查以及并發(fā)控制、故障恢

復(fù)等。

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

4.2數(shù)據(jù)庫系統(tǒng)的發(fā)展和基本特點(diǎn)

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

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

庫系統(tǒng)階段。

2、數(shù)據(jù)庫系統(tǒng)的基本特點(diǎn)（1）數(shù)據(jù)的高集成性。（2）數(shù)據(jù)的高共享性及低冗余性。

（3）數(shù)據(jù)獨(dú)立性：（4）數(shù)據(jù)統(tǒng)一管理及控制

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

物理獨(dú)立性：物理獨(dú)立性即是數(shù)據(jù)的物理結(jié)構(gòu)（包括存儲結(jié)構(gòu)，存取方式等）

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

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

邏輯獨(dú)立性：數(shù)據(jù)庫總體邏輯結(jié)構(gòu)的改變，如修改數(shù)據(jù)模式、增加新的數(shù)

據(jù)類型、改變數(shù)據(jù)間聯(lián)系等，不需要相應(yīng)修改應(yīng)用程序，這就是數(shù)據(jù)的邏輯獨(dú)

立性。

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

據(jù)庫系統(tǒng)：由數(shù)據(jù)庫（數(shù)據(jù)）、數(shù)據(jù)庫管理系統(tǒng)（軟件）、數(shù)據(jù)庫管理員（人員）、

硬件平臺＜硬件％軟件平臺逐件）五個(gè)部分構(gòu)成的運(yùn)行實(shí)體。一數(shù)據(jù)庫應(yīng)用系

統(tǒng)數(shù)據(jù)庫系紙應(yīng)用軟件及應(yīng)用界面三道組成一

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

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

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

數(shù)據(jù)視圖。

2）外模式：也稱子模式或用戶模式，它是用戶的數(shù)據(jù)視圖，也就是用戶所見到

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

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

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

盤及磁盤操作）。內(nèi)模式對一般用戶是透明的，但它的設(shè)計(jì)直接影響數(shù)據(jù)庫的性

能。

內(nèi)模式處于最底層，它反映了數(shù)據(jù)在計(jì)算機(jī)物理結(jié)構(gòu)中的實(shí)際存儲形式，概念

模式處于中間層，它反映了設(shè)計(jì)者的數(shù)據(jù)全局邏輯要求，而外模式處于最外層,

它反映了用戶對數(shù)據(jù)的要求。

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

D概念模式/內(nèi)模式的映射：實(shí)現(xiàn)了概念模式到內(nèi)模式之間的相互轉(zhuǎn)換。當(dāng)數(shù)據(jù)

庫的存儲結(jié)構(gòu)發(fā)生變化時(shí)，通過修改相應(yīng)的概念模式/內(nèi)模式的映射，使得數(shù)

據(jù)庫的邏輯模式不變，其外模式不變，應(yīng)用程序不用修改，從而保證數(shù)據(jù)具有

很高的物理獨(dú)立性。

2）外模式/概念模式的映射：實(shí)現(xiàn)了外模式到概念模式之間的相互轉(zhuǎn)換。當(dāng)邏輯

模式發(fā)生變化時(shí)，通過修改相應(yīng)的外模式/邏輯模式映射，使得用戶所使用的

那部分外模式不變，從而應(yīng)用程序不必修改，保證數(shù)據(jù)具有較高的邏輯獨(dú)立

性。

4.4數(shù)據(jù)模型的基本概念

數(shù)據(jù)模型從抽象層次上描述了數(shù)據(jù)庫系統(tǒng)的靜態(tài)特征、動態(tài)行為和約束條件，因

此數(shù)據(jù)模型通常由數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操作及數(shù)據(jù)約束三部分組成。

數(shù)據(jù)庫管理系統(tǒng)所支持的數(shù)據(jù)模型分為3種：層次模型、網(wǎng)狀模型和關(guān)系模型。

1）層次模型的基本結(jié)構(gòu)是樹形結(jié)構(gòu)。，具有以下特點(diǎn)：（1）每棵樹有且僅有一

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

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

件限制的無向圖。

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

表就是一個(gè)關(guān)系。二維表中的每一個(gè)分量都是不可再分的。在二維表中凡能唯

一標(biāo)識元組的最小屬性稱為鍵或碼。從所有侯選健中選取一個(gè)作為用戶使用的

鍵稱主鍵。表A中的某屬性是某表B的鍵，則稱該屬性集為A的外鍵或外碼。

主碼：或稱為關(guān)鍵字）表中的一個(gè)屬性或幾個(gè)屬性的組合、其值能唯一地標(biāo)識

表中一個(gè)元組的。主碼屬性不能取空值關(guān)系中的數(shù)據(jù)約束:（1）實(shí)體完整性約

束:約束關(guān)系的主鍵中屬性值不能為空值；（2）參照完全性約束:是關(guān)系之間

的基本約束;（3）用戶定義的完整性約束:它反映了具體應(yīng)用中數(shù)據(jù)的語義要

求。

4.5E-R模型

LE-R模型的基本概念：

1）實(shí)體：現(xiàn)實(shí)世界中的事物。

2）屬性：事物的特性。

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

的聯(lián)系。

E哼…模型三個(gè)基本概念之間的聯(lián)接關(guān)私實(shí)體是概念世朋的基本單位,…屬性

有屬性域，每個(gè)實(shí)體可取屬性域內(nèi)的值工二±實(shí)體的歷有屬.性值叫元組。~

*：E-R模型的基本成分是實(shí)體和聯(lián)系。

2.E-R模型的圖示法：

1）實(shí)體集：用矩形表示。

2）屬性：用橢圓形表示。

3）聯(lián)系：用菱形表示。

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

5）實(shí)體集及聯(lián)系間的聯(lián)接關(guān)系：用無向線段表示。

4.6關(guān)系模型

關(guān)系模式采用二維表來表示，一個(gè)關(guān)系對應(yīng)一張二維表?？梢赃@么說，一個(gè)關(guān)系

就是一個(gè)二維表，但是一個(gè)二維表不一定是一個(gè)關(guān)系。

?元組：在一個(gè)二維表（一個(gè)具體關(guān)系）中，水平方向的行稱為元組。元組對應(yīng)

存儲文件中的一個(gè)具體記錄；

?屬性：一維表中垂直方向的列稱為屬性，每一列有一個(gè)屬性名；

?域：屬性的取值范圍，也就是不同元組對同一屬性的取值所限定的范圍。

關(guān)系模型采用二維表來表示，二維表一般滿足下面7個(gè)性質(zhì)：

①二維表中元組個(gè)數(shù)是有限的一一元組個(gè)數(shù)有限性；

②二維表中元組均不相同一一元組的唯一性；

③二維表中元組的次序可以任意交換一一元組的次序無關(guān)性；

④二維表中元組的分量是不可分割的基本數(shù)據(jù)項(xiàng)一一元組分量的原子性；

⑤二維表中屬性名各不相同一一屬性名唯一性；

⑥二維表中屬性及次序無關(guān)，可任意交換一一屬性的次序無關(guān)性；

⑦二維表屬性的分量具有及該屬性相同的值域一一分量值域的統(tǒng)一性。

*：同一個(gè)關(guān)系模型的任兩個(gè)元組值不能完全相同。?.

4.7關(guān)系代數(shù)

關(guān)系數(shù)據(jù)庫系統(tǒng)的特點(diǎn)之一是它建立在數(shù)據(jù)理論的基礎(chǔ)之上,有很多數(shù)據(jù)理論

可以表示關(guān)系模型的數(shù)據(jù)操作，其中最為著名的是關(guān)系代數(shù)及關(guān)系演算。

1、關(guān)系的數(shù)據(jù)結(jié)構(gòu)

關(guān)系是由若干個(gè)不同的元組所組成，因此關(guān)系可視為元組的集合。n元關(guān)系是一

個(gè)n元有序組的集合。

關(guān)系模型的基本運(yùn)算：1）插入；2）刪除；3）修改；4）查詢（包括投影、選擇、笛

卡爾積運(yùn)算）。

2、關(guān)系操縱

關(guān)系模型的數(shù)據(jù)操縱即是建立在關(guān)系上的數(shù)據(jù)操縱，一般有查詢、增加、刪除和

修改四種操作。

3、集合運(yùn)算及選擇、投影、連接運(yùn)算

（1）并（U）：關(guān)系R和S具有相同的關(guān)系模式，R和S的并是由屬于R或?qū)儆赟

的元組構(gòu)成的集合。

⑵差（一）：關(guān)系R和S具有相同的關(guān)系模式，R和S的差是由屬于R但不屬于S

的元組構(gòu)成的集合。

（3）交（A）：關(guān)系R和S具有相同的關(guān)系模式，R和S的交是由屬于R且屬于S

的元組構(gòu)成的集合。

（4）廣義笛卡爾積（X）：設(shè)關(guān)系R和S的屬性個(gè)數(shù)分別為n、m,則R和S的廣義

笛卡爾積是一個(gè)有（n+m）列的元