全國(guó)計(jì)算機(jī)二級(jí)公共基礎(chǔ)學(xué)問(wèn)

一，數(shù)據(jù)結(jié)構(gòu)及算法

為攵據(jù)名吉構(gòu)指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。

數(shù)據(jù)結(jié)構(gòu)用來(lái)反映一個(gè)數(shù)據(jù)的內(nèi)部構(gòu)成，即一個(gè)數(shù)據(jù)由哪些成分構(gòu)成，以

什么方式構(gòu)成，呈現(xiàn)什么樣的結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)有邏輯上的數(shù)據(jù)結(jié)

構(gòu)才口物理上的省攵據(jù)結(jié)構(gòu)之分。邏輯上的數(shù)據(jù)結(jié)構(gòu)反映數(shù)據(jù)之間的邏

輯關(guān)系，而物理上的數(shù)據(jù)結(jié)構(gòu)反映數(shù)據(jù)在計(jì)算機(jī)內(nèi)部的存儲(chǔ)支配。數(shù)據(jù)結(jié)構(gòu)是數(shù)

據(jù)存在的形式。

算:去是解題的步驟，是指令的有限序列。它們規(guī)定了解決某一特定類型

問(wèn)題的一系列運(yùn)算，是對(duì)解題方案的精確及完整的描述。一個(gè)問(wèn)題的解決方案要

以算法為基礎(chǔ)。

1.1概念介紹

?算法的時(shí)間困難度：

算法的時(shí)間困又隹度是指執(zhí)行算法所須要的計(jì)算工作量。

算法的工作量用算法所執(zhí)行的基本運(yùn)算次數(shù)來(lái)度量，而算法所執(zhí)行的基本運(yùn)

算次數(shù)是問(wèn)題規(guī)模的函數(shù)，即

算法的工作量二千(n)

其中n是問(wèn)題的規(guī)模。

伊］出口,兩個(gè)n階矩陣相乘所須要的基本運(yùn)算(即兩個(gè)實(shí)數(shù)的乘法)次數(shù)為",

即計(jì)算工作量為也就是時(shí)間困難度為

?算法的空間困難度:

算法的空間困難度一般是指執(zhí)行這個(gè)算法所須要的內(nèi)存空間。

?數(shù)據(jù)的邏輯結(jié)構(gòu)

數(shù)據(jù)元素相互之間的關(guān)系，稱為結(jié)構(gòu)。

數(shù)據(jù)的邏輯結(jié)構(gòu)：是指反映數(shù)據(jù)元索之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。

?數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

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

數(shù)據(jù)的物理結(jié)構(gòu)。

各數(shù)據(jù)元素在計(jì)算機(jī)存儲(chǔ)空間中的位置關(guān)系及它們的邏輯關(guān)系不愿定是相

同的。同一種數(shù)據(jù)的邏輯垢構(gòu)可以依據(jù)須要表示成隨意一種或幾種不同的存儲(chǔ)結(jié)

構(gòu)。

數(shù)據(jù)的依次存儲(chǔ)方式：是將邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置上亦

相鄰的存儲(chǔ)單元里。也就是將全部存儲(chǔ)結(jié)點(diǎn)相繼存入在i個(gè)連續(xù)相鄰的存儲(chǔ)區(qū)

里。

數(shù)據(jù)的鏈?zhǔn)酱鎯?chǔ)方式：是在存儲(chǔ)每個(gè)結(jié)點(diǎn)信息的同時(shí)，增加一個(gè)指

針來(lái)表示結(jié)點(diǎn)間的邏輯關(guān)系。該方式不要求邏輯上相鄰結(jié)點(diǎn)在物理位置上亦相

鄰，結(jié)點(diǎn)間的邏輯美系是由附加的指針字段表示的。因此，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中的每

個(gè)結(jié)點(diǎn)都由兩部分組成：一部分用于存儲(chǔ)結(jié)點(diǎn)本身的信息，稱為數(shù)據(jù)域；另一

部分用于存儲(chǔ)該結(jié)點(diǎn)的后繼結(jié)點(diǎn)（或前驅(qū)結(jié)點(diǎn)）的存儲(chǔ)單元地址，稱為指4十域。

指針域可以包含一個(gè)或多個(gè)指針，這由結(jié)點(diǎn)之間的關(guān)系所確定。

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

假如在一個(gè)線性結(jié)構(gòu)中，一個(gè)數(shù)據(jù)元素都沒(méi)有，則稱該數(shù)據(jù)結(jié)構(gòu)為空數(shù)據(jù)結(jié)

構(gòu)。

線性結(jié)構(gòu)的邏輯特征：在一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)中，除第一個(gè)數(shù)據(jù)元

素只有一個(gè)后繼沒(méi)有前驅(qū)，最終一個(gè)數(shù)據(jù)元素只有一個(gè)前驅(qū)沒(méi)有后繼外，其他

的每一個(gè)數(shù)據(jù)元素僅有一個(gè)前驅(qū)和一個(gè)后繼。線性結(jié)構(gòu)也稱為線，性表。

注：某個(gè)元素干脆相鄰的前一個(gè)元素稱為此元素的前馬區(qū)，干脆相鄰的后一

個(gè)元素稱為此元素的后繼。

非線性結(jié)構(gòu)的邏輯”寺征：在一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)中，某數(shù)據(jù)元素可

能有多于?個(gè)前驅(qū)或后繼＜如樹(shù)型結(jié)構(gòu)等。

習(xí)題：

(一)選擇題(單選)

1.算法的時(shí)間困難度是指C)

A)算法的執(zhí)行時(shí)間

B)算法所處理的數(shù)據(jù)量

0算法程序中的語(yǔ)句或指令條數(shù)

D)算法在執(zhí)行過(guò)程中所須要的基本運(yùn)算次數(shù)

1.2線性表

線性表是由同一類型的數(shù)據(jù)元素構(gòu)成的一種線性的數(shù)據(jù)結(jié)構(gòu)。是一種最基本,

最常用的數(shù)據(jù)結(jié)構(gòu)。線性表常用的存儲(chǔ)方式有兩種：依次存儲(chǔ)方式和鏈接存儲(chǔ)方

式C

線性表的數(shù)學(xué)定義：

L=(ai,a2,a3,...,&】)

說(shuō)明：

線性表是具有相同類型的n(n2O)個(gè)數(shù)據(jù)元素組成的有限序列。

L：為表的名稱。

ai(i=l,2,...,n)：為表的元素，也稱為線性表中的一個(gè)結(jié)點(diǎn)。它可以是一個(gè)數(shù),

一個(gè)字符，一個(gè)字符串，也可以是一條記錄，還可以是困難的數(shù)據(jù)對(duì)象。ai是

az的前驅(qū)，a2是ai的后繼，a2是a3的前驅(qū)，a3是a2的后繼，…，依次類推。

n：為線性表的長(zhǎng)度(元素個(gè)數(shù))，當(dāng)n=0時(shí)稱線性表為空表。

線性表的特點(diǎn)：

在非空的線性表中：存在唯一的一個(gè)“第一個(gè)元素”(根結(jié)點(diǎn))。存在唯一的

一個(gè)“最終一個(gè)元素”(終端結(jié)點(diǎn))。除第一個(gè)元素外，其他的元素均有唯一的前

驅(qū)。除最終一個(gè)元素外，其他的元素均有唯一的后繼。

1.3棧和隊(duì)列

棧和隊(duì)列本質(zhì)上也是線性表，只是它們的操作受到了限制。

1.3.1棧

棧是限定僅在表尾進(jìn)行插入和刪除操作的線性表.表尾稱為棧頂(top)，表

頭稱為棧底(bottom)。

棧這種數(shù)據(jù)結(jié)構(gòu)，類似于子彈夾，底端是封閉的，最終玉入的子彈總是最先被彈

出，最先壓入的子彈只能最終被彈出。

棧頂元素總是最終被插入的元素，從而也是最先能被刪除的元素；棧底元素

總是最先被插入的元素，從而也是最終能被刪除的元素。即棧是依據(jù)“先進(jìn)后出”

或“后進(jìn)先出”的原則組織數(shù)據(jù)的。因此，棧也被稱為“先進(jìn)后出”表

或“后進(jìn)先出”表。由此可以看出，棧具有記憶作用。

1.3.2隊(duì)列

隊(duì)列是指只允許在表的一端插入元素，在另一端刪除元素的線性表。允許插入

的一端稱為隊(duì)尾(rear),允許刪除的一端稱為隊(duì)頭(front)。

在隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)中，最先插入的元素將最先能夠被刪除，反之最終插入的元

素將最終才能被刪除。因此，隊(duì)列又稱為“先進(jìn)先出”或“后進(jìn)后

出”的線性表。

1.4樹(shù)和二叉樹(shù)

1.4.1樹(shù)

樹(shù)形結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)中一種很重要的非線性結(jié)構(gòu)。在樹(shù)形結(jié)構(gòu)中，全部數(shù)據(jù)

元素之間的關(guān)系具有明顯的層次特性。樹(shù)形結(jié)構(gòu)很像自然界中的樹(shù)，像一棵倒長(zhǎng)

的樹(shù)。在現(xiàn)實(shí)生活中，能用樹(shù)形結(jié)構(gòu)表示的例子很多。參見(jiàn)下面的圖形：

樹(shù)形結(jié)構(gòu)的基本特征及基本術(shù)語(yǔ):

以下圖為例：

樹(shù)的根：

在樹(shù)形結(jié)構(gòu)中，沒(méi)有前驅(qū)的結(jié)點(diǎn)只有?個(gè)，稱為樹(shù)的根結(jié)點(diǎn)，簡(jiǎn)稱為樹(shù)的根。

如:上圖中的“R”。

父結(jié)點(diǎn)：

在樹(shù)形結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)（除了樹(shù)的根結(jié)點(diǎn)）只有一個(gè)前驅(qū)，稱為父結(jié)點(diǎn)。

如：上圖中的“R”是K,P,Q,D的父結(jié)點(diǎn)；“N”是X,Y的父結(jié)點(diǎn)。

子結(jié)點(diǎn)：

在樹(shù)形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)可以有多個(gè)后繼，稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。

如：上圖中的K,P,Q,D是“R”的子結(jié)點(diǎn)；X,Y是“N”的子結(jié)點(diǎn)。

葉子結(jié)點(diǎn)：

在樹(shù)形結(jié)構(gòu)中，沒(méi)有后繼的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)，也稱終端結(jié)點(diǎn)。

如：上圖中的C,M,F,E,X,GS,L,Z,A均為葉子結(jié)點(diǎn)。

結(jié)點(diǎn)的度：

在樹(shù)形結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后繼個(gè)數(shù)稱為該結(jié)點(diǎn)的度。

如:上圖中根結(jié)點(diǎn)R的度是4；結(jié)點(diǎn)T的度是3；結(jié)點(diǎn)P,Q,D,O,Y,W

的度都為1。葉子結(jié)點(diǎn)的度為0。

樹(shù)的度：

在樹(shù)形結(jié)構(gòu)中，全部結(jié)點(diǎn)中的最大的度稱為樹(shù)的度。如：L圖中樹(shù)的度為4,

因?yàn)榻Y(jié)點(diǎn)R的度最大，是4。

樹(shù)的深度：

在樹(shù)形結(jié)構(gòu)中，樹(shù)的最大層數(shù)稱為樹(shù)的深度（或高度）。如：上圖中樹(shù)的深度

是5。說(shuō)明：樹(shù)形結(jié)構(gòu)具有明顯的層次關(guān)系，即樹(shù)是一種層次結(jié)構(gòu)。在樹(shù)形

結(jié)構(gòu)中一般按如下原則分層：

1）根結(jié)點(diǎn)在第1層。

2）其余結(jié)點(diǎn)的層數(shù)等于其父結(jié)點(diǎn)的層數(shù)加1。

子樹(shù)：

在樹(shù)形結(jié)中，以某結(jié)點(diǎn)的一個(gè)子結(jié)點(diǎn)為根構(gòu)成的樹(shù)稱為該結(jié)點(diǎn)的一棵子樹(shù)。

如：上圖中，結(jié)點(diǎn)R有4裸子樹(shù)，它們分別以K,P,Q,D為根結(jié)點(diǎn)；結(jié)點(diǎn)P

有1棵子樹(shù)，其根結(jié)點(diǎn)為N；結(jié)點(diǎn)T有3棵子樹(shù)，它們分別以W,Z,A為根

結(jié)點(diǎn)。

在樹(shù)形結(jié)構(gòu)中，子樹(shù)間互不相交，葉子結(jié)點(diǎn)沒(méi)有子樹(shù)。

森林：

森林是M(M20)棵互不相交的樹(shù)的集合。刪去一棵樹(shù)的根，就得到一個(gè)森

林；反之，加上一個(gè)結(jié)點(diǎn)作樹(shù)根，森林就變?yōu)橐豢脴?shù)。

1.4.2二叉樹(shù)

(1)二叉樹(shù)的特點(diǎn)

①非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)。

②二叉樹(shù)中的每個(gè)結(jié)點(diǎn)，最多有兩棵子樹(shù)，分另稱為該結(jié)點(diǎn)的左子樹(shù)及右子

樹(shù),當(dāng)一個(gè)結(jié)點(diǎn)即沒(méi)有左子樹(shù)也沒(méi)有右子樹(shù)時(shí)，該結(jié)點(diǎn)就是葉子結(jié)點(diǎn)。在下面的

圖中，左面是只有根結(jié)點(diǎn)的二叉樹(shù)，右面是深度為4的二叉樹(shù)：

□

(2)滿二叉樹(shù)及完全二叉樹(shù)

1)滿二叉樹(shù)：

滿二叉樹(shù)是指除最終一層外，每一層上的全部結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。

就是說(shuō)，在滿二叉樹(shù)中，每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值，即在滿二叉樹(shù)的

第k層上有2rk2i)個(gè)結(jié)點(diǎn)，且深度為k的滿二叉樹(shù)有2kT(k21)個(gè)結(jié)點(diǎn)。

在下圖中分別是深度為2,3,4的滿二叉樹(shù):

圖1.32滿二叉樹(shù)

滿二叉樹(shù)中不存在度數(shù)為1的結(jié)點(diǎn)，每個(gè)分支結(jié)點(diǎn)均有兩棵深度相同的子樹(shù)，且

葉子結(jié)點(diǎn)都在最下一層。

2)完全二叉樹(shù)：

若一棵二叉樹(shù)最多只有最下面的兩層上結(jié)點(diǎn)的度數(shù)可以小于2,并且最下一

層上的全部結(jié)點(diǎn)都集中在該層最左邊的若干位置上，則此二叉樹(shù)稱為完全二叉

樹(shù)。

在下圖的4棵二叉樹(shù)中，分別是深度為3和4的完全二叉樹(shù):

滿二叉樹(shù)是完全二叉樹(shù)，完全二叉樹(shù)不愿定是滿二叉樹(shù)。

在滿二叉樹(shù)的最下一層上，從最右邊起先連續(xù)刪去若干結(jié)點(diǎn)后得到的二叉樹(shù)照IH

是一棵完全二叉樹(shù)。

在完全二叉樹(shù)中，若某個(gè)結(jié)點(diǎn)沒(méi)有左子結(jié)點(diǎn)，則它確定沒(méi)有右子結(jié)點(diǎn)，即該

結(jié)點(diǎn)必是葉子結(jié)點(diǎn)。

(3)二叉樹(shù)的性質(zhì)

假設(shè)定義根結(jié)點(diǎn)的層數(shù)為1（留意：有些資料中規(guī)定根結(jié)點(diǎn)的層數(shù)為0）。

性質(zhì)1：在二叉樹(shù)的第i層上，最多有2i—1（i21）個(gè)結(jié)點(diǎn)。

性質(zhì)2：深度為k的二叉樹(shù)最多有2k—1（k21）個(gè)結(jié)點(diǎn)。

性質(zhì)3：在隨意二叉樹(shù)中，若度為（）的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）的個(gè)數(shù)為no,度為

2的結(jié)點(diǎn)的個(gè)數(shù)為n2,則：nO=n2+1

（對(duì)」?完全二義樹(shù)還有如卜屈性）

性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，其深度為[Iog2n]+1。>'主：[logzn]

表示取log2n的整數(shù)部分。性質(zhì)5：假如將一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)自頂

向下，同一層自左向右連續(xù)給結(jié)點(diǎn)編號(hào)1,2,3,…，n,則對(duì)于隨意結(jié)

點(diǎn)i（1WiWn）有如下結(jié)論：

1）假如i=l,此結(jié)點(diǎn)為根結(jié)點(diǎn)，無(wú)前驅(qū)（即無(wú)父結(jié)點(diǎn)）；

假如i>l,則該結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為Int（i/2）。也可表示成[i/2],都

表示取整數(shù)。

2）假如2i〉n,則結(jié)點(diǎn)i無(wú)左子結(jié)點(diǎn)，明顯也沒(méi)有右子結(jié)點(diǎn)，是葉子結(jié)點(diǎn)。

假如2iWn,則結(jié)點(diǎn)i的左子結(jié)點(diǎn)是編號(hào)為2i的結(jié)點(diǎn)。

3）假如2i+l>n,則結(jié)點(diǎn)i無(wú)右子結(jié)點(diǎn)。

假如2i+lWn,則結(jié)點(diǎn)i的右子結(jié)點(diǎn)的編號(hào)為2i+1o

⑷二叉樹(shù)的遍歷

二叉樹(shù)的遍歷就是遵從某種次序，訪問(wèn)二叉樹(shù)中的全部結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)

僅被訪問(wèn)一次。

一棵非空二又樹(shù)是由根結(jié)點(diǎn)，左子樹(shù)和右子樹(shù)三部分組成。因此遍歷一棵

非空一義樹(shù)的問(wèn)題就可以分解為三項(xiàng)“子任條”：

①訪問(wèn)根結(jié)點(diǎn)（假設(shè)用D表示）。

②遍歷左子樹(shù)（假設(shè)用L表示）。

③遍歷右子樹(shù)（假設(shè)用R表示）。

在遍歷二叉樹(shù)的過(guò)程中，一般先遍歷左子樹(shù)，然后再遍歷右子樹(shù)。在先左后

右的原則下，依據(jù)訪問(wèn)根結(jié)點(diǎn)的次序，二叉樹(shù)的遍歷可分為三種：前序遍歷(DLR),

中序遍歷(LDR),后序遍歷(LRD)。

以下圖中的二叉樹(shù)為例：

前序遍歷(DLR):

首先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹(shù)，最終遍歷右子樹(shù)。在遍歷左，右子樹(shù)

時(shí)，照舊先訪問(wèn)子樹(shù)的根結(jié)點(diǎn)，然后遍歷其左子樹(shù)，最終遍歷其右子樹(shù)。即，前

序遍歷是指訪問(wèn)全部的根結(jié)點(diǎn)(包括子樹(shù)的根結(jié)點(diǎn))都在遍歷其左，右子樹(shù)之前。

前序遍歷的操作：

若二叉樹(shù)為空，則結(jié)束反返回。否則：

①訪問(wèn)根結(jié)點(diǎn)

②前序遍歷左子樹(shù)

③前序遍歷右子樹(shù)

如，對(duì)上圖中的二叉樹(shù)進(jìn)行前序遍歷的結(jié)果是：FCADBEGHP

中序遍歷(LDR):

首先遍歷左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最終遍歷右子樹(shù)。在遍歷

左，右子樹(shù)時(shí),照舊先遍歷其左子樹(shù),然后訪問(wèn)子樹(shù)的根結(jié)點(diǎn),最終遍歷其右

子樹(shù)。即，中序遍歷是指訪問(wèn)全部的根結(jié)點(diǎn)(包括子樹(shù)的根結(jié)點(diǎn))都在遍歷其左子

樹(shù)之后，在遍歷其右子樹(shù)之前。

中序遍歷的操作：

若二叉樹(shù)為空，則結(jié)束反返回。否則：

①中序遍歷左子樹(shù)

②訪問(wèn)根結(jié)點(diǎn)

③中序遍歷右子樹(shù)

如，對(duì)上圖中的二叉樹(shù)進(jìn)行中序遍歷的結(jié)果是：ACBDFEHGP

后序遍歷(LRD)：

首先遍歷左子樹(shù)，然后遍歷右子樹(shù)，最終訪問(wèn)根結(jié)點(diǎn)。

在遍歷左，右子樹(shù)時(shí)，照舊先遍歷其左子樹(shù)，然后遍歷其右子樹(shù)，最終訪問(wèn)子

樹(shù)的根結(jié)點(diǎn)。即，后序遍歷是指訪問(wèn)全部的根結(jié)點(diǎn)(包括子樹(shù)的根結(jié)點(diǎn))都在遍歷

其左，右子樹(shù)之后。

后序遍歷的操作：

若二叉樹(shù)為空，則結(jié)束反返回。否則：

①后序遍歷左子樹(shù)

②后序遍歷右子樹(shù)

③訪問(wèn)根結(jié)點(diǎn)

如，對(duì)上圖中的二叉樹(shù)進(jìn)行后序遍歷的結(jié)果是：ABDCHPGEF

1.5查找

查找又稱檢索。查找是指在一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)中查找某個(gè)指定的元素。通

常'，依據(jù)不同的數(shù)據(jù)結(jié)構(gòu)，應(yīng)接受不同的查找方法。

1.5.1依次查找

依次查找又稱依次搜尋或線性查找。依次查找一般是指在線性表中查找指定

的元素。

依次查找的基本思想：

在n個(gè)結(jié)點(diǎn)組成的線性表中，從線性表的一端起先，依次將線性表中的元素

及被查元素進(jìn)行比較，若相等則表示找到，即查找成功；若線性表中全部的元素

都及被查元素進(jìn)行了比較但都不相等，則表示線性表中沒(méi)有要找的元素，即查找

失敗。

在依次查找中，查找成功時(shí)最多須要比較n次，最少

比較1次，平均比較次數(shù)約為表長(zhǎng)的一半。查找失敗時(shí)比

較n+1次。

依次查找的時(shí)間困難度為0(n)。

對(duì)于無(wú)序表(即表中的元素的排列是無(wú)序的)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表(有序

的和無(wú)序的)，只能用依次查找。

依次查找的優(yōu)點(diǎn)：

算法簡(jiǎn)潔而適用范圍廣。對(duì)表中元素的排列次序無(wú)要求，既可以是按關(guān)鍵字

排列的有序表，也可以是無(wú)序表；對(duì)表的存儲(chǔ)結(jié)構(gòu)也無(wú)任何要求，既適用于依次

存儲(chǔ)的依次表，也適用于儲(chǔ)接存儲(chǔ)的鏈表。

依次查找的缺點(diǎn)：

查找效率低，平均查找長(zhǎng)度較大。當(dāng)n很大時(shí)不宜接受依次查找。

1.5.2二分查找

二分查找又稱折半查找。它是一種查找效率較高的查找方法。該方法只適用

于依次存儲(chǔ)結(jié)構(gòu)的有序表。通常是指有序表中的元素按值升序排列(非遞減有序

排列)。二分查找不能用于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表。

二分查找的基本思想：參見(jiàn)“C語(yǔ)言程序設(shè)計(jì)”或“VB程序設(shè)計(jì)”課件的

相應(yīng)內(nèi)容動(dòng)畫(huà)。

對(duì)于長(zhǎng)度為n的有序線性表，查找成功時(shí)最多須要比

較Iog2(n+1)次，最少比較1次，平均查找長(zhǎng)度近

似log2no當(dāng)查找失敗時(shí),比較Iog2n或Iog2(n+1)

次。

不管二分查找成功及否，其時(shí)間困難度均為

0(Iog2n)o

二分查找的最壞性能和平均性能相當(dāng)接近。

1.6排序

排序就是將文件中的記錄進(jìn)行整理，使之依據(jù)關(guān)鍵字進(jìn)行遞增或遞減的依次

排列起來(lái)，成為一個(gè)有序序列的過(guò)程。在本節(jié)所介紹的排序方法中，其排序的對(duì)

象一般認(rèn)為是依次存儲(chǔ)的線性表，在程序設(shè)計(jì)語(yǔ)言中就是一維數(shù)組。

這里的排序算法，都是針對(duì)升序排序。

1.6.1交換排序

交換排序是兩兩比較待排序記錄的關(guān)鍵字，若發(fā)覺(jué)兩個(gè)記錄關(guān)鍵字的次序相

反時(shí)即進(jìn)行交換，直到?jīng)]芍反序的記錄為止。下面介紹兩種常用的交換排序。

(1)冒泡排序

冒泡排序的基本思想：參見(jiàn)“C語(yǔ)言程序設(shè)計(jì)”或“VB程序設(shè)計(jì)”課件的

相應(yīng)內(nèi)容動(dòng)畫(huà)。

對(duì)于長(zhǎng)度為n的線性表，在最壞狀況下，冒泡排序須

要經(jīng)過(guò)n/2遍的掃描，比較次數(shù)為n(n-1)/2。

冒泡排序算法的平均時(shí)間困難度為0(n2),空間

困難度為0(1)。

(2)快速排序

快速排序的基本思想：

參見(jiàn)下圖：

分割

無(wú)

序

線分割

性

表分割

快速排序示意圖

從線性表中選取一個(gè)元素，設(shè)為T(mén),將線性表后面小于T的元素移到前面，

將線性表前面大于T的元素移到后面，結(jié)果就把線性表分成了兩部分(稱為兩個(gè)

子表)，T插入到其分界線的位置處，這個(gè)過(guò)程稱為線性表的分割。通過(guò)對(duì)線性

表的一次分割，就以T為分界線，將線性表分成了前后兩個(gè)子表，且前面子表中

的全部元素均不大于T,后面子表中的全部元素均不小于T。

假如對(duì)分割后的各子表再按上述原則進(jìn)行分割，并且這種分割過(guò)程可以始終

做下去，隨著對(duì)各子表不斷地進(jìn)行分割，劃分出的子表會(huì)越來(lái)越多(一次只能對(duì)

一個(gè)子表進(jìn)行再分割處理)，直到全部子表中的元素都排好序?yàn)橹?，則此時(shí)的線

性表就變成了有序表。

對(duì)于長(zhǎng)度為n的線性表：

在最壞狀況下，快速排序比較次數(shù)為n(n7)/2。算法

的時(shí)間困難度為0(n2),空間困難度為0(n)。

在最好狀況下，快速排序算法的時(shí)間困難度為

0(nlog2n),空間困難度為0(log2n)0

快速排序算法的平均時(shí)間困難度是0(nlog2n),平均

比較次數(shù)不大于(n+1)Iog2n

1.6.2插入排序

插入排序是每次將一個(gè)待排序的記錄按其關(guān)鍵字大小，插入到前面已排好的

序列中的適當(dāng)位置,直到全部記錄插入為止。

(1)干脆插入排序

快速排序的基本思想：請(qǐng)查看相關(guān)資料。

對(duì)于長(zhǎng)度為n的線性表：

在最壞狀況下，干脆插入排序比較次數(shù)為n(n-1)/2o

算法的時(shí)間困難度為0(n2)o

(2)希爾排序

希爾排序的基本思想：請(qǐng)查看相關(guān)資料。

對(duì)于長(zhǎng)度為n的線性表：

在最壞狀況下希爾排序比較次數(shù)為0（n1.5）0

1.6.3選擇排序

選擇排序的基本思想是：每一遍在115+16=1,2「?,11-1）個(gè)待排序記錄中選取關(guān)

鍵字最小的記錄作為有序序列中第i個(gè)記錄，直到全部記錄排完為止。

（1）干脆選擇排序

選擇排序的基本思想：參見(jiàn)“C語(yǔ)言程序設(shè)計(jì)”或“VB程序設(shè)計(jì)”課件的

相應(yīng)內(nèi)容動(dòng)畫(huà)。

在最壞狀況下，干脆選擇排序比較次數(shù)為

n（n-1）/2o

（2）堆排序

希爾排序的基本思想；請(qǐng)查看相關(guān)資料。

在最壞狀況下，堆排序比較次數(shù)為0（nlog2n）。

習(xí)題：

（一）選擇題（單選）

1.下列敘述中正確的是（D）

A）棧是“先進(jìn)先出”的線性表

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

C）循環(huán)隊(duì)列是非線性結(jié)構(gòu)

D）有序線性表既可以接受依次存儲(chǔ)結(jié)構(gòu)，也可以接受鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

2.下列關(guān)于棧的敘述中正確的是（A）

A）棧頂元素最先被刪除B）棧頂元素最終才能被刪除

0棧底元素恒久不能被刪除D）以上三種說(shuō)法都不對(duì)

3.下列敘述中正確的是（B）

A）有一個(gè)以上根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)不愿定是非線性結(jié)構(gòu)

B）只有一個(gè)根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)不愿定是線性結(jié)構(gòu)

0循環(huán)鏈表是非線性結(jié)構(gòu)

D）雙向鏈表是非線性結(jié)構(gòu)

4.支持子程序調(diào)用的數(shù)據(jù)結(jié)構(gòu)是（A）

A）棧B）樹(shù)C）隊(duì)列D）二叉樹(shù)

5.某二叉樹(shù)有5個(gè)度為2的結(jié)點(diǎn)，則該二叉樹(shù)中的葉子結(jié)點(diǎn)數(shù)是（C）

A）10B）8C）6D）4

提示：在隨意二義樹(shù)中，若度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）的個(gè)數(shù)為nO,度為2的結(jié)點(diǎn)的個(gè)數(shù)為

n2.則:n0=n2+l即n0（葉子結(jié)點(diǎn)數(shù)）=5+1=6

6.某二叉樹(shù)共有7個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)只有I個(gè)，則該二叉樹(shù)的深度為（假設(shè)根結(jié)點(diǎn)在第

一層）（D）

A）3B）4C）6D）7

7.下列排序方法中，最壞狀況下比較次數(shù)最少的是（D）

A）冒泡排序B）簡(jiǎn)潔選擇排序C）干脆插入排序D）建排序

8.下列敘述中正確的是（A）

A）對(duì)長(zhǎng)度為n的有序鏈表進(jìn)行查找，最壞的狀況下須要的比較次數(shù)為n

B）對(duì)K度為n的有序鏈衣進(jìn)行對(duì)分查找，最壞的狀況下須要的比較次數(shù)為（n/2）

0對(duì)長(zhǎng)度為n的有序鏈表進(jìn)行對(duì)分查找，最壞的狀況下須要的比較次數(shù)為（logan）

D）對(duì)長(zhǎng)度為n的有序鏈表進(jìn)行對(duì)分查找，最壞的狀況卜.須要的比較次數(shù)為（nlogzn）

（二）填空題

1.假設(shè)用一個(gè)長(zhǎng)度為50的數(shù)綱（數(shù)組元素的下標(biāo)從。到49）作為棧的存儲(chǔ)空間，棧底指針

bottom指向棧底元素，棧頂指針top指向棧頂元素，假如bottom=49,top=30（數(shù)組卜標(biāo)），則

棧中具有個(gè)元素。

答案：20

2.一個(gè)隊(duì)列的初始狀態(tài)為空?，F(xiàn)將元素A,B,C,D,E,F,5,4,3,2,1—

次入隊(duì)，然后再一次退隊(duì)，則元素退隊(duì)的依次為。

答案：A,B,C,D,E,F,5,4,3,2,1

3.設(shè)某循環(huán)隊(duì)列的容量為50,假如頭指針front=45（指向隊(duì)頭元素的前一個(gè)位置），尾指針

rear=10（指向隊(duì)尾元素），則該循環(huán)隊(duì)列中共有個(gè)元素。

答案：15

4.設(shè)二義樹(shù)如卜:

對(duì)該二叉樹(shù)進(jìn)行后序遍歷的結(jié)果為.

答案：E,D,B,G,11,F,C,A

5.一棵二叉樹(shù)的中序遍歷結(jié)果為DBEAFC,前序遍歷結(jié)果為ABDECF,則后序

遍歷結(jié)果為。

答案：DEBFCA

6.有序線性表能進(jìn)行二分查找的前提是該線性表必需是_____存儲(chǔ)。

答案：依次

二，軟件工程基礎(chǔ)

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

據(jù)及相關(guān)文檔的完整集合。

軟件由兩部分組成：一是機(jī)器可執(zhí)行的程序和數(shù)據(jù)；二是機(jī)器不行執(zhí)行的，

及軟件開(kāi)發(fā)，運(yùn)行，維護(hù)，運(yùn)用等有關(guān)的文檔。

軟件的分類

軟件按功能可以分為：應(yīng)用軟件，系統(tǒng)軟件，支撐軟件（或工具軟件）。

應(yīng)用軟件：是為解決特定領(lǐng)域的應(yīng)用而開(kāi)發(fā)的軟件。

系統(tǒng)軟件：是計(jì)算機(jī)管理自身資源，提高計(jì)算機(jī)運(yùn)用效率并為計(jì)算機(jī)用戶供應(yīng)各

種服務(wù)的軟件。

支撐軟件：是介于系統(tǒng)軟件和應(yīng)用軟件之間，幫助，書(shū)戶開(kāi)發(fā)軟件的工具性軟

件。

軟件生命周期

通常將軟件產(chǎn)品從提出，實(shí)現(xiàn)，運(yùn)用維護(hù)到停止運(yùn)用退役的過(guò)程稱為軟件

生命周期。參見(jiàn)下圖：

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

結(jié)構(gòu)化分析的常用工具：

數(shù)據(jù)流圖（DFD）：是措述數(shù)據(jù)處理過(guò)程的工具，是需求理解的邏輯模型的圖

形表示，它干脆支持系統(tǒng)的功能建模。

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

判定樹(shù)

判定表

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

常見(jiàn)的過(guò)程設(shè)計(jì)工具：

圖形工具：程序流程圖，N-S圖，PAD圖（問(wèn)題分析圖），HIPO

表格工具：判定表。

語(yǔ)言工具：PDL（偽碼）

軟件設(shè)計(jì)的基本原理

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

其他微小環(huán)節(jié)。

2）模塊化：是指把一個(gè)待開(kāi)發(fā)的軟件分解成若干小的簡(jiǎn)潔的部分。如高級(jí)

語(yǔ)言中的過(guò)程，函數(shù)，子程序等。每個(gè)模塊可以完成一個(gè)特定的子功能，各個(gè)

模塊可以按確定的方法組裝起來(lái)成為一個(gè)整體，從而實(shí)現(xiàn)整個(gè)系統(tǒng)的功能。

3）信息隱藏：是指在一個(gè)模塊內(nèi)包含的信息（過(guò)程或數(shù)據(jù)），對(duì)于不須要這些

信息的其他模塊來(lái)說(shuō)是不能訪問(wèn)的。

4）模塊獨(dú)立性：是指每個(gè)模塊只完成系統(tǒng)要求的獨(dú)立的子功能，并且及其他模

塊的聯(lián)系最少且接口簡(jiǎn)潔。模塊的獨(dú)立程度是評(píng)價(jià)設(shè)計(jì)好壞的重要度量標(biāo)準(zhǔn)。

衡量軟件的模塊獨(dú)立性運(yùn)用耦合性和內(nèi)聚性兩個(gè)定性

的度量標(biāo)準(zhǔn)。

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

功能角度來(lái)度量模塊內(nèi)的聯(lián)系。

內(nèi)聚性是信息隱藏和局部化概念的自然擴(kuò)展。一個(gè)模塊的內(nèi)聚性越強(qiáng)則該模

塊的模塊獨(dú)立性越強(qiáng)。作為軟件結(jié)構(gòu)設(shè)計(jì)的設(shè)計(jì)原則，要求每一個(gè)模塊的內(nèi)部都

具有很強(qiáng)的內(nèi)聚性，它的各個(gè)組成部分彼此都密切相關(guān)。

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

一個(gè)模塊及其他模塊的耦合性越強(qiáng)則該模塊的模塊獨(dú)立性越弱。原則上講，

模塊化設(shè)計(jì)總是盼望模塊間的耦合表現(xiàn)為非干脆耦合方式。但是，由于問(wèn)題所固

有的困難性和結(jié)構(gòu)化設(shè)計(jì)的原則，非干脆耦合往往是不存在的。

耦合性及內(nèi)聚性是模塊獨(dú)立性的兩個(gè)定性標(biāo)準(zhǔn)，耦合性及內(nèi)聚性是相互聯(lián)系

的。在程序結(jié)構(gòu)中，各模塊的內(nèi)聚性越強(qiáng)，則耦合性越弱。一般優(yōu)秀的軟件設(shè)計(jì),

應(yīng)盡量做到高內(nèi)聚，低耦合，即減弱模塊之間的耦合性和提高模塊內(nèi)的的內(nèi)聚性,

有利于提高模塊的獨(dú)立性＜

軟件測(cè)試

軟件測(cè)試是在軟件投入運(yùn)行前對(duì)軟件需求，設(shè)計(jì)，編碼的最終審核。軟件

測(cè)試是為了發(fā)覺(jué)錯(cuò)誤而執(zhí)行程序的過(guò)程。軟件測(cè)試應(yīng)當(dāng)制定明確的測(cè)試支配并按

支配執(zhí)行。

軟件測(cè)試的目的：是發(fā)覺(jué)錯(cuò)誤。

軟件測(cè)試方法和技術(shù)：若從是否須要執(zhí)行被測(cè)軟件的角度，可以分為靜態(tài)測(cè)

試和動(dòng)態(tài)測(cè)試方法。若依據(jù)功能劃分可以分為白盒測(cè)試和黑盒測(cè)試方法。

靜態(tài)測(cè)試：包括代碼檢查，靜態(tài)結(jié)構(gòu)分析，代碼質(zhì)量度量等。靜態(tài)測(cè)試不

實(shí)際運(yùn)行軟件，主要通過(guò)人工進(jìn)行。

動(dòng)態(tài)測(cè)試：是基于計(jì)算機(jī)的測(cè)試，是為了發(fā)覺(jué)錯(cuò)誤而執(zhí)行程序的過(guò)程。須要

細(xì)心設(shè)計(jì)一批測(cè)試用例，并利用這些測(cè)試用例去運(yùn)行程序，以發(fā)覺(jué)程序錯(cuò)誤的過(guò)

程。測(cè)試用例的格式為：

［（輸入值集）,（輸出值集）］

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

程，檢查內(nèi)部成分，以確認(rèn)每種內(nèi)部操作符合設(shè)計(jì)規(guī)格要求。白盒測(cè)試把測(cè)試對(duì)

象看作一個(gè)打開(kāi)的盒子，允許測(cè)試人員利用程序內(nèi)部的型輯結(jié)構(gòu)及有關(guān)信息來(lái)設(shè)

計(jì)或選擇測(cè)試用例，對(duì)程序全部的邏輯路徑進(jìn)行測(cè)試。通過(guò)在不同點(diǎn)檢查程序的

狀態(tài)來(lái)了解實(shí)際的運(yùn)行狀態(tài)是否及預(yù)期的一樣。所以，白盒測(cè)試是在程序內(nèi)部進(jìn)

行，主要用于完成軟件內(nèi)部操作的驗(yàn)證。

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

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

能是否滿足需求進(jìn)行測(cè)試司驗(yàn)證。黑盒測(cè)試完全不考慮程序內(nèi)部的邏輯結(jié)構(gòu)和內(nèi)

部特征，只依據(jù)程序的需求和功能規(guī)格說(shuō)明，檢查程序的功能是否符合它的功能

說(shuō)明。所以，黑盒測(cè)試是在軟件接口處進(jìn)行，完成功能驗(yàn)證。黑盒測(cè)試只檢查程

序功能是否依據(jù)需求規(guī)格說(shuō)明書(shū)的規(guī)定正常運(yùn)用，程序是否能適當(dāng)?shù)亟邮蛰斎霐?shù)

據(jù)而產(chǎn)生正確的輸出信息，并且保持外部信息（如數(shù)據(jù)庫(kù)或文件）的完整性。

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

問(wèn)錯(cuò)誤，性能錯(cuò)誤，初始化和終止條件錯(cuò)誤。黑盒測(cè)試方法主要有等價(jià)類劃分

法，邊界值分析法，錯(cuò)誤推想法，因果圖等，主要用于軟件確認(rèn)測(cè)試。

程序調(diào)試

在對(duì)程序進(jìn)行了成功的測(cè)試之后，將進(jìn)入程序調(diào)試（通常稱Debug,即排錯(cuò)）。

程序調(diào)試的任務(wù)是診斷和改正程序中的錯(cuò)誤。

它及軟件測(cè)試不同，軟件測(cè)試是盡可能多地發(fā)覺(jué)軟件中的錯(cuò)

誤，并找出軟件錯(cuò)誤的詳細(xì)位置。軟件測(cè)試貫穿整個(gè)

軟件生命期，調(diào)試主要在開(kāi)發(fā)階段。

習(xí)題：

（一）選擇題（單選）

1.軟件按功能可以分為：應(yīng)用軟件，系統(tǒng)軟件和支撐軟件（或工具軟件）。下面屬于應(yīng)用

軟件的是（C）

A）編譯程序B）操作系統(tǒng)C）教務(wù)管理系統(tǒng)D）匯編程序

2.軟件按功能可分為：應(yīng)用軟件，系統(tǒng)軟件，和支撐軟件（或工具軟件）。下面屬于系統(tǒng)

軟件的是（B）

A）編輯軟件B）操作系統(tǒng)。教務(wù)管理系統(tǒng)D）閱讀器，

3.軟件（程序）調(diào)試的任務(wù)是（A）

A）診斷和改正程序中的錯(cuò)誤B）盡可能多的發(fā)覺(jué)程序中的錯(cuò)誤

0發(fā)覺(jué)并改正程序中的全部錯(cuò)誤D）確定程序中錯(cuò)誤的性質(zhì)

4.下面敘述中錯(cuò)誤的是（A）

A）軟件測(cè)試的目的是發(fā)覺(jué)錯(cuò)誤并改正錯(cuò)誤

B）對(duì)被調(diào)試的程序進(jìn)行“錯(cuò)誤定位”是程序調(diào)試的必要步驟

C）程序調(diào)試通常也稱為Debug

D）軟件測(cè)試應(yīng)嚴(yán)格執(zhí)行測(cè)試支配，解除測(cè)試的隨意性

5.耦合性和內(nèi)聚性是對(duì)模塊獨(dú)立性度量的兩個(gè)標(biāo)準(zhǔn)。下列敘述中正確的是（B）

A）提高耦合性，降低內(nèi)聚性有利于提高模塊的獨(dú)立性

B）降低耦合性，提高內(nèi)聚性有利于提高模塊的獨(dú)立性

C）耦合性是指一個(gè)模塊內(nèi)部各個(gè)元素間彼此結(jié)合的緊密程度

D）內(nèi)聚性是指模塊間相互連接的緊密程度

6.數(shù)據(jù)流圖（DFD圖）是（C）

A）軟件概要設(shè)計(jì)的工具B）軟件詳細(xì)設(shè)計(jì)的工具

0結(jié)構(gòu)化方法的需求分析工具D）面對(duì)對(duì)象方法的需求分析工具

7.軟件生命周期可分為定義階段，開(kāi)發(fā)階段和維護(hù)階段。詳細(xì)設(shè)計(jì)屬于（B）

A）定義階段B）開(kāi)發(fā)階段C）維護(hù)階段D）上述三個(gè)階段

8.在軟件開(kāi)發(fā)中，需求分析階段產(chǎn)生的主要文檔是（D）

A）軟件集成測(cè)試支配B）軟件詳細(xì)設(shè)計(jì)說(shuō)明書(shū)0用戶手冊(cè)D）軟件需求規(guī)格說(shuō)

明書(shū)

9.結(jié)構(gòu)化程序所要求的基本結(jié)構(gòu)不包括（B）

A）依次結(jié)構(gòu)B）GOTO跳轉(zhuǎn)C）選擇（分支）結(jié)構(gòu)D）直復(fù)（循環(huán)）結(jié)構(gòu)

10.下面描述中錯(cuò)誤的是（A）

A)系統(tǒng)總體結(jié)構(gòu)圖支持軟件系統(tǒng)的詳細(xì)設(shè)計(jì)

B)軟件設(shè)計(jì)是將軟件需求轉(zhuǎn)換為軟件表示的過(guò)程

C)數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫(kù)設(shè)計(jì)是軟件設(shè)計(jì)的任務(wù)之一

D)PAD圖是軟件詳細(xì)設(shè)計(jì)的表示工具

(二)填空題

1.軟件測(cè)試可分為白盒測(cè)試和黑盒測(cè)試?；韭窂綔y(cè)試屬于測(cè)試。

答案：白盒

2.符合結(jié)構(gòu)化原則的三種基本限制結(jié)構(gòu)是：選擇結(jié)構(gòu)，循環(huán)結(jié)構(gòu)和

答案：依次結(jié)構(gòu)

3.軟件是______,數(shù)據(jù)和文檔的集合。

答案：程序

4.對(duì)軟件設(shè)計(jì)的最小單位(模塊或程序單元)進(jìn)行的測(cè)試通常為測(cè)試。

答案：?jiǎn)卧蚰K

三，數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)

計(jì)算機(jī)應(yīng)用的三大領(lǐng)域：科學(xué)計(jì)算，數(shù)據(jù)處理，過(guò)程限制。

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

數(shù)據(jù)(Data)：就是描述事物的符號(hào)記錄。

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

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

有“集成”，“共享”的特點(diǎn)。

數(shù)據(jù)庫(kù)管理系統(tǒng)(DBMS)：是數(shù)據(jù)庫(kù)的機(jī)構(gòu)，是一種系統(tǒng)軟件，負(fù)貢數(shù)據(jù)庫(kù)

中的數(shù)據(jù)組織，數(shù)據(jù)操縱，數(shù)據(jù)維護(hù)，限制及愛(ài)惜和數(shù)據(jù)服務(wù)等。數(shù)據(jù)庫(kù)管理

系統(tǒng)是數(shù)據(jù)庫(kù)系統(tǒng)的核心,

數(shù)據(jù)庫(kù)管理系統(tǒng)一般供應(yīng)相應(yīng)的數(shù)據(jù)語(yǔ)言(DataLanguage)來(lái)完成相應(yīng)的功

能:

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

數(shù)據(jù)操縱語(yǔ)言(DML)：負(fù)責(zé)數(shù)據(jù)的操縱，包括查詢及增，刪，改等操作。

數(shù)據(jù)限制語(yǔ)言(DCL)：負(fù)責(zé)數(shù)據(jù)完整性，平安性的定義及檢查以及并發(fā)限制,

故障復(fù)原等功能，包括系統(tǒng)初啟程序，文件讀寫(xiě)及維護(hù)程序，存取路徑管理程

序，緩沖區(qū)管理程序，平安性限制程序，完整性檢查程序，并發(fā)限制程序，

事務(wù)管理程序，運(yùn)行FL志管理程序，數(shù)據(jù)庫(kù)復(fù)原程序等。

數(shù)據(jù)庫(kù)管理員(DBA)：由于數(shù)據(jù)庫(kù)的共享性，因此對(duì)數(shù)據(jù)庫(kù)的規(guī)劃，設(shè)計(jì)，

維護(hù)，監(jiān)視等須要有專人管理，稱他們?yōu)閿?shù)據(jù)庫(kù)管理員。

數(shù)據(jù)庫(kù)系統(tǒng)(DBS)：由數(shù)據(jù)庫(kù)(數(shù)據(jù))，數(shù)據(jù)庫(kù)管理系統(tǒng)(軟件)，數(shù)據(jù)庫(kù)管理

員(人員)，系統(tǒng)硬件平臺(tái)(硬件)，系統(tǒng)軟件平臺(tái)(軟件)這五部分組成，稱為數(shù)據(jù)

庫(kù)系統(tǒng)。

數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng)(DBAS)：是數(shù)據(jù)庫(kù)系統(tǒng)再加上應(yīng)用軟件及應(yīng)用界面這三者

所組成。

E?R模型

該模型將現(xiàn)實(shí)世界的要求轉(zhuǎn)化成實(shí)體，聯(lián)系，屬性等幾個(gè)基本概念，以及

它們間的兩種基本聯(lián)接關(guān)系，并且可以用一種圖特殊直觀地表示出來(lái)。下面是

E-R模型的基本概念。

目前較為出名的概念模型有E-R模型，擴(kuò)充的E-R模型，面對(duì)對(duì)象模型及

謂詞模型等。

實(shí)體:現(xiàn)實(shí)世界中的事物可以抽象成為實(shí)體。實(shí)體是概念世界中的基本單位,

它們是客觀存在的且又相互區(qū)分的事物。凡是有共性的實(shí)體可組成?個(gè)集合稱實(shí)

體集。如學(xué)生A和學(xué)生B,他們都是實(shí)體，他們又都是學(xué)生，從而組成一個(gè)學(xué)

生實(shí)體集。

屬性：現(xiàn)實(shí)世界中的事物均有一些特性，這些特性可以用屬性來(lái)表示。屬性刻畫(huà)

了實(shí)體的特征。一個(gè)實(shí)體往往可以有若干個(gè)屬性。

聯(lián)系：現(xiàn)實(shí)世界中事物間的關(guān)聯(lián)稱為聯(lián)系。在概念世界中聯(lián)系反映J'實(shí)體集間

的確定關(guān)系。如工人及設(shè)備間的操作關(guān)系，上，下級(jí)間的領(lǐng)導(dǎo)關(guān)系等。

實(shí)體集間的聯(lián)系有多種，就實(shí)體集的個(gè)數(shù)而言有：

1)兩個(gè)實(shí)體集間的聯(lián)系。

2)多個(gè)實(shí)體集間的聯(lián)系。

3)一個(gè)實(shí)體集內(nèi)部的聯(lián)系：是一個(gè)實(shí)體集內(nèi)的不同實(shí)體間的聯(lián)系。

實(shí)體集間聯(lián)系的個(gè)數(shù)可以是單個(gè)也可以是多個(gè)，包括：

一對(duì)一的聯(lián)系，簡(jiǎn)記為1:1

一對(duì)多或多對(duì)一的聯(lián)系，簡(jiǎn)記為1:M或M:1(其中M也可以小寫(xiě))

多對(duì)多的聯(lián)系，簡(jiǎn)記為M:N或m:n

E-R模型由上面三個(gè)基本概念組成。由實(shí)體，聯(lián)系，屬性三者結(jié)合起來(lái)才

能表示現(xiàn)實(shí)世界。

E?R圖：E-R模型可以用一種特殊直觀的圖的形式表示，這種圖稱為E-R圖。在

E-R圖中我們分別用下面不同的幾何圖形表示E-R模型中的三個(gè)概念及兩個(gè)聯(lián)接

關(guān)系。

I)實(shí)體集表示法

用矩形表示實(shí)體集，在矩形內(nèi)寫(xiě)上該實(shí)體集的名字。照實(shí)體集學(xué)生(studenl),

課程(course)可表示為：

studentcourse

實(shí)體集表示法

2)屬性表示法

用橢圓形表示屬性，在橢圓形內(nèi)寫(xiě)上該屬性的名稱。如學(xué)生有屬性：學(xué)號(hào)(S#),

姓名(Sn)及年齡(Sa),可表示為：

(^sT)(^sT)

屬性表示法

3)聯(lián)系表示法

用菱形表示聯(lián)系，在菱形內(nèi)寫(xiě)上聯(lián)系名。如學(xué)生及課程間的聯(lián)系SC,可表

示為：

上面是三個(gè)基本概念分別用三種幾何圖形表示。下面是它們之間的聯(lián)接關(guān)系的圖

形表示。

4)實(shí)體集或聯(lián)系及屬性間的聯(lián)接關(guān)系

屬性依附于實(shí)體集，屬性也依附于聯(lián)系，因此它們之間分別有聯(lián)接關(guān)系。參

見(jiàn)卜圖：

其中：C#(課程號(hào))，Cn(課程名)，P#(預(yù)修課號(hào))

5)實(shí)體集及聯(lián)系間的聯(lián)接關(guān)系

如下圖表示實(shí)體集及聯(lián)系間的聯(lián)接關(guān)系：

還可以在線段邊上注明其對(duì)應(yīng)的函數(shù)關(guān)系，如1:1,l:n,n:m等。下圖表示

student及course間有多對(duì)多聯(lián)系：

兩個(gè)實(shí)體集間聯(lián)系叫二元聯(lián)系，多個(gè)實(shí)體集間聯(lián)系叫多元聯(lián)系。下圖聯(lián)系

FPU是一種三元聯(lián)系(工廠，產(chǎn)品及用戶間的聯(lián)系)：

下面是實(shí)體間多種聯(lián)系圖：

(a)圖：公司職工(enpbyee)間上，下級(jí)管理(manage)的聯(lián)系。即一個(gè)實(shí)體集

內(nèi)部可以有多種聯(lián)系。

(b)圖：老師(T)及學(xué)生(S)之間可以有教學(xué)(E)聯(lián)系也可以有管理(M)聯(lián)系。即

實(shí)體集間可以有多種聯(lián)系,

E-R圖的一個(gè)實(shí)例

關(guān)系模型

關(guān)系模型接受二維表來(lái)表示，簡(jiǎn)稱表。

二維表由表框架(Frame)及表的元組(Tuple)組成。表框架由n個(gè)命名的屬性

(Attribute)組成，n稱為屬性元數(shù)(Arity)。每個(gè)屬性有一個(gè)取值范圍，稱為值域

(Domain)o表框架對(duì)應(yīng)了關(guān)系的模式，即類型的概念。

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

n個(gè)元組重量所組成，每個(gè)元組重量是表框架中每個(gè)屬性的投影值。一個(gè)表框架

可以存放m個(gè)元組，m稱為表的基數(shù)(Cardinality)。

一個(gè)n元表框架及框架內(nèi)m個(gè)元組構(gòu)成了一個(gè)完整的二維表。

關(guān)系框架及關(guān)系元組構(gòu)成了一個(gè)關(guān)系。一個(gè)語(yǔ)義相關(guān)的關(guān)系集合構(gòu)成一個(gè)

關(guān)系數(shù)據(jù)庫(kù)。關(guān)系的框架稱為關(guān)系模式，而語(yǔ)義相關(guān)的關(guān)系模式集合構(gòu)成了關(guān)系

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

滿足下面7特性質(zhì)的二維表稱為關(guān)系(Relation)：

I)元組個(gè)數(shù)有限性：二維表中元組個(gè)數(shù)是有限的。

2)元組的惟一性：二維表中元組均不相同。

3)元組的次序無(wú)關(guān)性：二維表中元組的次序可以隨意交換。

4)元組重量的原子性：二維表中元組的重量是不行分割的基本數(shù)據(jù)項(xiàng)。

5)屬性名惟一性：二維表中屬性名各不相同。

6)屬性的次序無(wú)關(guān)性：二維表中屬性及次序無(wú)關(guān)，可隨意交換。

7)重量值域的同一性：二維表屬性的重量具有及該屬性相同的值域。

以二維表(關(guān)系)為基本結(jié)構(gòu)所建立的模型稱為關(guān)系模型，

在關(guān)系模型中的一個(gè)重要概念是鍵(Key)或碼。鍵具有標(biāo)識(shí)元組，建立元組

間聯(lián)系等重要作用。

鍵或碼：在二維表中凡能惟一標(biāo)識(shí)元組的最小屬性集稱為該表的鍵或碼。

候選鍵或候選碼：二維表中可能有若干個(gè)鍵，它們稱為該表的候選鍵

(CandidalaKey)或候選碼。

主鍵或主碼：從二維表的全部候選鍵中選取一個(gè)作為用戶運(yùn)用的鍵，稱為主

鍵(PrimaryKey)或主碼。一般主鍵也簡(jiǎn)稱為鍵或碼。

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

(ForeignKey)或外碼。

表中確定要有鍵，因?yàn)榧偃绫碇腥繉傩缘淖蛹皇擎I，則表中屬性的全

集必為鍵(稱為全鍵)，因此也確定有主鍵。

在關(guān)系元組的重量中允許出現(xiàn)空值(NullValue)以表示信息空缺?？罩涤糜诒?/p>

示未知的值或不行能出現(xiàn)的值，一般用NULL表示。一般關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)都支

持空值，但是有兩個(gè)限制：關(guān)系的主鍵中不允許出現(xiàn)空值，因?yàn)槿缰麈I為空值則

失去了其元組標(biāo)識(shí)的作用；須要定義有關(guān)空值的運(yùn)算。

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

關(guān)第代數(shù)是關(guān)于關(guān)系數(shù)據(jù)庫(kù)的理論。

數(shù)據(jù)庫(kù)設(shè)計(jì)及管理

數(shù)據(jù)庫(kù)設(shè)計(jì)是數(shù)據(jù)庫(kù)應(yīng)用的核心。

數(shù)據(jù)庫(kù)設(shè)計(jì)的四個(gè)階段，參見(jiàn)下圖:

從E-R圖向關(guān)系模式轉(zhuǎn)換

參見(jiàn)下表：

E--R模型與關(guān)系間的比較表

模型

E-R關(guān)系模型關(guān)系

-一__.一ER

，一■■■■

屬性

屬性實(shí)體集關(guān)系

___________實(shí)體

元組聯(lián)系關(guān)系

習(xí)題：

（一）選擇題（單選）

1.數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng)中的核心問(wèn)題是（A）

A）數(shù)據(jù)庫(kù)設(shè)計(jì)B）數(shù)據(jù)庫(kù)系統(tǒng)設(shè)計(jì)C）數(shù)據(jù)庫(kù)維護(hù)D）數(shù)據(jù)庫(kù)管理員培訓(xùn)

2.將E-R圖轉(zhuǎn)換為關(guān)系模式討，實(shí)體和聯(lián)系都可以表示為（C）

A）屬性B）鍵C）關(guān)系D）域

3.