計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)課件

計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)第一章數(shù)據(jù)結(jié)構(gòu)與算法(30%)考試大綱 1.算法的基本概念；算法復(fù)雜度的概念和意義（時(shí)間復(fù)雜度與空間復(fù)雜度）。

2.數(shù)據(jù)結(jié)構(gòu)的定義；數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)的圖形表示；線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念。

3.線性表的定義；線性表的順序存儲(chǔ)結(jié)構(gòu)及其插入與刪除運(yùn)算。

4.棧和隊(duì)列的定義；棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算。

5.線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算。

6.樹的基本概念；二叉樹的定義及其存儲(chǔ)結(jié)構(gòu)；二叉樹的前序、中序和后序遍歷。

7.順序查找與二分法查找算法；基本排序算法（交換類排序，選擇類排序，插入類排序）。2021/2/42第一章數(shù)據(jù)結(jié)構(gòu)與算法(30%)考試大綱 1.算法的基本概念；算法復(fù)雜度的概念和意義（時(shí)間復(fù)雜度與空間復(fù)雜度）。

2.數(shù)據(jù)結(jié)構(gòu)的定義；數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)的圖形表示；線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念。

3.線性表的定義；線性表的順序存儲(chǔ)結(jié)構(gòu)及其插入與刪除運(yùn)算。

4.棧和隊(duì)列的定義；棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算。

5.線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算。

6.樹的基本概念；二叉樹的定義及其存儲(chǔ)結(jié)構(gòu)；二叉樹的前序、中序和后序遍歷。

7.順序查找與二分法查找算法；基本排序算法（交換類排序，選擇類排序，插入類排序）。2021/2/42知識(shí)點(diǎn)歸納算法的基本概念所謂算法是指解題方案的準(zhǔn)確而完整的描述。嚴(yán)格來說，一個(gè)算法必須具有以下五個(gè)主要特征：2021/2/43算法的基本特征一個(gè)算法應(yīng)該具有以下五個(gè)重要的特征：有窮性確定性輸入輸出可行性一個(gè)算法必須保證執(zhí)行有限步之后結(jié)束；算法的每一步驟必須有確切的定義；一個(gè)算法有0個(gè)或多個(gè)輸入，以刻畫運(yùn)算對(duì)象的初始情況，所謂0個(gè)輸入是指算法本身定義了初始條件；一個(gè)算法有一個(gè)或多個(gè)輸出，以反映對(duì)輸入數(shù)據(jù)加工后的結(jié)果。沒有輸出的算法是毫無意義的；算法原則上能夠精確地運(yùn)行2021/2/44算法的基本概念算法的組成要素算法中對(duì)數(shù)據(jù)的運(yùn)算和操作算法的控制結(jié)構(gòu)算法設(shè)計(jì)基本方法列舉法歸納法遞推遞歸減半遞推回溯法基本運(yùn)算和操作算術(shù)運(yùn)算關(guān)系運(yùn)算邏輯運(yùn)算數(shù)據(jù)傳輸控制結(jié)構(gòu)

順序選擇循環(huán)2021/2/45算法的復(fù)雜度算法的復(fù)雜度可分為時(shí)間復(fù)雜度和空間復(fù)雜度，是衡量算法優(yōu)劣的量度。1.算法的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的工作量。一般情況下，算法中的基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)f(n)。2021/2/46算法的復(fù)雜度算法的空間復(fù)雜度算法的空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間?？臻g復(fù)雜度作為算法所需存儲(chǔ)空間的量度2021/2/47數(shù)據(jù)結(jié)構(gòu)利用計(jì)算機(jī)進(jìn)行數(shù)據(jù)處理是計(jì)算機(jī)應(yīng)用的一個(gè)重要領(lǐng)域。數(shù)據(jù)結(jié)構(gòu)主要研究和討論以下三個(gè)方面的問題：數(shù)據(jù)集合中各數(shù)據(jù)元素之間的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)。在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。2021/2/48數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)邏輯結(jié)構(gòu)是對(duì)數(shù)據(jù)元素之間存在的邏輯關(guān)系的描述，它可以用一個(gè)數(shù)據(jù)元素的集合和定義在此集合上的若干關(guān)系表示。與數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)位置無關(guān)，是獨(dú)立于計(jì)算機(jī)的。

2021/2/49數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器中的表示。存儲(chǔ)結(jié)構(gòu)的主要內(nèi)容是指在存儲(chǔ)空間中使用一個(gè)存儲(chǔ)結(jié)點(diǎn)來存儲(chǔ)一個(gè)數(shù)據(jù)元素，在存儲(chǔ)空間中建立各存儲(chǔ)結(jié)點(diǎn)之間的關(guān)聯(lián)，來表示數(shù)據(jù)元素之間的邏輯關(guān)系。常見的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)索引存儲(chǔ)結(jié)構(gòu)散列存儲(chǔ)結(jié)構(gòu)2021/2/410線性結(jié)構(gòu)和非線性結(jié)構(gòu)線性結(jié)構(gòu)在數(shù)據(jù)元素的非空有限集合中，線性結(jié)構(gòu)的邏輯特征如下：存在一個(gè)唯一的被稱為“第一個(gè)”的數(shù)據(jù)元素存在一個(gè)唯一的被稱為“最后一個(gè)”的數(shù)據(jù)元素除第一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均有且只有一個(gè)直接前驅(qū)除最后一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均有且只有一個(gè)直接后繼非線性結(jié)構(gòu)非線性結(jié)構(gòu)的邏輯特征是：一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前驅(qū)和直接后繼，樹和圖都屬于非線性結(jié)構(gòu)。2021/2/411線性表 通常以下列n個(gè)數(shù)據(jù)元素的序列”表示線性表：

(a1,a2,...,ai,...,an)序列中數(shù)據(jù)元素的個(gè)數(shù)n定義為線性表的表長(zhǎng)；n=0時(shí)的線性表被稱為空表。稱i為ai在線性表中的位序。2021/2/412線性表的順序存儲(chǔ)線性表的順序存儲(chǔ)結(jié)構(gòu)用一組地址連續(xù)的存儲(chǔ)單元依次存放線性表中的數(shù)據(jù)元素，即以“存儲(chǔ)位置相鄰”表示“位序相繼的兩個(gè)數(shù)據(jù)元素之間的前驅(qū)和后繼的關(guān)系，并以表中第一個(gè)元素的存儲(chǔ)位置作為線性表的起始地址，稱作線性表的基地址。

所有數(shù)據(jù)元素的存儲(chǔ)位置均可由第一個(gè)數(shù)據(jù)元素的存儲(chǔ)位置得到

ADR(ai)=ADR(a1)+(i-1)×C

↑↑ 基地址一個(gè)數(shù)據(jù)元素所占存儲(chǔ)量

2021/2/413線性表的插入和刪除運(yùn)算插入運(yùn)算是指在線性表的某個(gè)指定位置增加一個(gè)新結(jié)點(diǎn)。一般情況下，要在第i(1≤i≤n)個(gè)元素之前插入一個(gè)新元素時(shí)，首先要從最后一個(gè)元素開始，直到第i個(gè)元素之間共n-i+1個(gè)元素依次向后移動(dòng)一個(gè)位置，然后將新元素插入到第i項(xiàng)。刪除運(yùn)算是指撤銷結(jié)構(gòu)中的某個(gè)結(jié)點(diǎn)。一般情況，要?jiǎng)h除第i(1≤i≤n)個(gè)元素，要從第i+1個(gè)元素開始，直到第n個(gè)元素，共n-i個(gè)元素依次向前移動(dòng)一個(gè)位置。2021/2/414棧棧是限定僅在表的一端進(jìn)行插入和刪除操作的線性表。允許插入和刪除的一端稱為棧頂，另一端稱為棧底。棧頂元素總是最后被插入的元素，從而也是最先被刪除的元素；棧底元素總是最先被插入，也是最后被刪除的元素。因此，棧是一種后進(jìn)先出的線性表。通常用指針top指示棧頂位置，用指針bottom指示棧底位置。2021/2/415棧的順序存儲(chǔ)及運(yùn)算用一維數(shù)組S(1:m)作為棧的順序存儲(chǔ)空間，m為棧的最大容量。top=0表示棧為空，top=m表示棧滿。棧的操作入棧：在棧頂位置插入一個(gè)新元素，棧頂指針top加1。退棧：取出棧頂元素并賦值給一個(gè)指定的變量，棧頂指針top減1。取棧頂元素：將棧頂元素的值賦給一個(gè)指定的變量，不刪除棧頂元素，棧頂指針不變。2021/2/416隊(duì)列隊(duì)列是一種先進(jìn)先出的線性表，它只允許在表的一端插入元素(隊(duì)尾)，在另一端刪除元素(隊(duì)頭)。通常定義頭指針front指向隊(duì)頭元素的前一個(gè)位置，定義尾指針rear指向隊(duì)尾元素的位置。隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)。向隊(duì)尾插入一個(gè)元素的操作稱為入隊(duì)，從隊(duì)頭刪除一個(gè)元素的操作稱為退隊(duì)。2021/2/417循環(huán)隊(duì)列 將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間。循環(huán)隊(duì)列初始狀態(tài)為空，即front=rear=m。入隊(duì)操作時(shí)，rear加1，若rear=m+1，則置rear=1；退隊(duì)操作時(shí)，front加1，若front=m+1，則置front=1。在循環(huán)隊(duì)列為空或?yàn)闈M時(shí)，均有front=rear，因此需要設(shè)置標(biāo)志s進(jìn)行區(qū)分，定義s=0表示隊(duì)列為空，s=1表示隊(duì)列非空。2021/2/418單鏈表線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是用一組任意的存儲(chǔ)單元(可以連續(xù)，也可以不連續(xù))存儲(chǔ)線性表的數(shù)據(jù)元素，為了表示每個(gè)數(shù)據(jù)元素ai與其直接后繼元素ai+1之間的邏輯關(guān)系，對(duì)數(shù)據(jù)元素ai來說，除了存儲(chǔ)其本身的信息(數(shù)據(jù)域)之外，還需要存儲(chǔ)其后繼元素的存儲(chǔ)位置信息(指針域)。指針域中存儲(chǔ)的信息稱為指針或鏈，N個(gè)結(jié)點(diǎn)鏈接成一個(gè)鏈表，即為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。由于結(jié)點(diǎn)中只包含一個(gè)指針域，故稱為單鏈表。2021/2/419單鏈表通常以單鏈表中第一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址作為作為單鏈表的地址，稱為頭指針。整個(gè)鏈表的存儲(chǔ)必須從頭指針開始(順序存取)，頭指針指示鏈表中第一個(gè)結(jié)點(diǎn)的存儲(chǔ)位置。最后一個(gè)數(shù)據(jù)元素沒有直接后繼，其指針域?yàn)榭铡?021/2/420單鏈表的插入和刪除2021/2/421雙向鏈表和循環(huán)鏈表在雙向鏈表中的結(jié)點(diǎn)包含兩個(gè)指針域，其中一個(gè)指向直接后繼，另一個(gè)指向直接前驅(qū)。循環(huán)鏈表的特點(diǎn)是表中最后一個(gè)結(jié)點(diǎn)的指針域指向第一個(gè)結(jié)點(diǎn)，整個(gè)鏈表成為一個(gè)由鏈指針相鏈接的環(huán)。據(jù)此，從表中任一節(jié)點(diǎn)出發(fā)均可找到表中其它結(jié)點(diǎn)。在循環(huán)鏈表中增加了一個(gè)表頭結(jié)點(diǎn)，其指針域指向第一個(gè)元素結(jié)點(diǎn)，頭指針則指向頭結(jié)點(diǎn)。HEAD…∧…∧HEAD…HEAD2021/2/422樹及其基本概念樹是一種簡(jiǎn)單的非線性結(jié)構(gòu)，在樹中，所有的數(shù)據(jù)元素之間具有明顯的層次性關(guān)系。樹是(n≥0)個(gè)結(jié)點(diǎn)的有限集合，在任意一棵非空樹中：(1)有且僅有一個(gè)特定的結(jié)點(diǎn)稱為根結(jié)點(diǎn)。(2)當(dāng)n>1時(shí)，其余的結(jié)點(diǎn)可分為m個(gè)互不相交的子集T1,T2,…Tm，其中每個(gè)有限子集本身又是一棵樹，并且稱為根的子樹。集合為空的樹簡(jiǎn)稱為空樹；樹中的元素稱為結(jié)點(diǎn)。2021/2/423樹的主要術(shù)語(yǔ)結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹數(shù)。葉節(jié)點(diǎn)(終端結(jié)點(diǎn))：度為0的結(jié)點(diǎn)。雙親、孩子和兄弟：結(jié)點(diǎn)的子樹的根節(jié)點(diǎn)稱為該結(jié)點(diǎn)的孩子，該結(jié)點(diǎn)稱為孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)。同一個(gè)雙親結(jié)點(diǎn)的孩子互稱為兄弟。層次：結(jié)點(diǎn)的層次從根開始定義，根為第一層，根的孩子為第二層。深度：樹中結(jié)點(diǎn)的最大層次稱為樹的深度或高度。2021/2/424樹型結(jié)構(gòu)的常用術(shù)語(yǔ)ABDFECGHIJKM

結(jié)點(diǎn)的度一個(gè)結(jié)點(diǎn)的子樹的個(gè)數(shù)；Q：結(jié)點(diǎn)A、G的度數(shù)？

樹的度樹中所有結(jié)點(diǎn)度的最大值；Q：右圖中樹的度？

終端結(jié)點(diǎn)度為0的結(jié)點(diǎn)；Q：圖中葉子結(jié)點(diǎn)有幾個(gè)？7

非終端結(jié)點(diǎn)

度不為0的結(jié)點(diǎn)；Q：圖中非終端結(jié)點(diǎn)有幾個(gè)？52021/2/425樹型結(jié)構(gòu)的常用術(shù)語(yǔ)ABDFECGHIJKM

結(jié)點(diǎn)的層次樹中根結(jié)點(diǎn)的層次為1，根結(jié)點(diǎn)子樹的根為第2層，以此類推；樹的深度

樹中所有結(jié)點(diǎn)層次的最大值；Q：圖中樹的深度？①②③④2021/2/426二叉樹二叉樹是n(n≥0)個(gè)數(shù)據(jù)元素的有限集，它或?yàn)榭占?或者含有唯一的稱為根的元素，且其余元素分成兩個(gè)互不相交的子集，每個(gè)子集自身也是一棵二叉樹，分別稱為根的左子樹和右子樹。二叉樹是另一種樹型結(jié)構(gòu)，其特點(diǎn)是每個(gè)結(jié)點(diǎn)至多有兩棵子樹，并且二叉樹的子樹有左右之分，其順序不能任意顛倒。2021/2/427二叉樹的基本性質(zhì)性質(zhì)1在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)（i≥1）性質(zhì)2深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)（k≥1）性質(zhì)3對(duì)任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則：n0=n2+1性質(zhì)4具有n個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為[log2n]+12021/2/428滿二叉樹和完全二叉樹滿二叉樹除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)，也就是說每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值，即在滿二叉樹的第k層上有2k-1個(gè)結(jié)點(diǎn)，且深度為m的滿二叉樹有2m-1個(gè)結(jié)點(diǎn)。完全二叉樹除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值，在最后一層上只缺少右邊的若干結(jié)點(diǎn)。具有n個(gè)結(jié)點(diǎn)的完全二叉樹，其深度為[log2n]+1。從以上定義可知，滿二叉樹也是完全二叉樹，反之則不然。滿二叉樹

最大層的結(jié)點(diǎn)均向左靠齊

完全二叉樹

ADCBEF2021/2/429二叉樹的基本性質(zhì)性質(zhì)5如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹（其深度為[log2n]+1）的結(jié)點(diǎn)按層序（從第1層到第[log2n]+1層，每層從左到右）從1起開始編號(hào)，則對(duì)任一編號(hào)為i的結(jié)點(diǎn)(1≤i≤n)，則:

(1)如果i=1，則編號(hào)為i的結(jié)點(diǎn)是二叉樹的根，無雙親；如果i>1，則其雙親結(jié)點(diǎn)parent(i)的編號(hào)是[i/2]。

(2)如果2i>n，則編號(hào)為i的結(jié)點(diǎn)無左孩子（編號(hào)為i的結(jié)點(diǎn)為葉子結(jié)點(diǎn)）；否則其左孩子結(jié)點(diǎn)lChild(i)的編號(hào)是2i。

(3)如果2i+1>n，則編號(hào)為i的結(jié)點(diǎn)無右孩子；否則其右孩子結(jié)點(diǎn)rChild(i)的編號(hào)是結(jié)點(diǎn)2i+1。

2021/2/430二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)在二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)設(shè)置三個(gè)域，即數(shù)據(jù)域，左指針域和右指針域，兩個(gè)指針域分別存儲(chǔ)左右子樹根節(jié)點(diǎn)的存儲(chǔ)位置，即指針。L(i)V(i)R(i)LchildvalueRchild2021/2/431二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2021/2/432二叉樹的遍歷二叉樹的遍歷指不重復(fù)地訪問二叉樹的所有結(jié)點(diǎn)。從二叉樹的結(jié)構(gòu)定義得知，二叉樹是由"根結(jié)點(diǎn)"、"左子樹"和"右子樹"三部分構(gòu)成，則遍歷二叉樹的操作可分解為"訪問根結(jié)點(diǎn)"、"遍歷左子樹"和"遍歷右子樹"三個(gè)子操作，并且由二叉樹的遞歸定義可知，遍歷左子樹和遍歷右子樹可如同遍歷二叉樹一樣"遞歸"進(jìn)行。

先序遍歷二叉樹中序遍歷二叉樹后序遍歷二叉樹若二叉樹為空，則空操作；

否則

(1)訪問根結(jié)點(diǎn)；

(2)先序遍歷左子樹；

(3)先序遍歷右子樹。若二叉樹為空，則空操作；

否則

(1)中序遍歷左子樹；

(2)訪問根結(jié)點(diǎn)；

(3)中序遍歷右子樹。若二叉樹為空，則空操作；

否則

(1)后序遍歷左子樹；

(2)后序遍歷右子樹；

(3)訪問根結(jié)點(diǎn)。2021/2/433二叉樹的遍歷先序遍歷：ABDEGHCFIJ中序遍歷：DBGEHACIJF后序遍歷：DGHEBJIFCA2021/2/434查找查找是指在一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)中查找某個(gè)指定的元素。順序查找順序查找一般是指在線性表中查找指定元素，基本方法如下：從線性表的第一個(gè)元素開始，依次將線性表中的元素與被查找元素進(jìn)行比較，若相等則表示找到，即查找成功；若線性表中的所有元素與被查找元素都不相等，則查找失敗。順序查找：最好情況比較1次，最壞情況比較n次如果線性表為無序表，即表中元素的排列是無序的，則不管線性表采用順序存儲(chǔ)還是鏈?zhǔn)酱鎯?chǔ)，都必須使用順序查找。如果線性表有序，但采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，則也必須使用順序查找。2021/2/435查找二分查找(折半查找)二分查找法只適用于順序存儲(chǔ)的有序表。先確定待查目標(biāo)元素所在范圍(區(qū)間)，然后逐步縮小范圍直至找到該元素，或者當(dāng)查找區(qū)間縮小到0也沒有找到目標(biāo)元素為止。查找過程中，給定值首先和處于待查區(qū)間"中間位置"的關(guān)鍵字進(jìn)行比較，若相等，則查找成功，否則將查找區(qū)間縮小到"前半個(gè)區(qū)間"或"后半個(gè)區(qū)間"之后繼續(xù)進(jìn)行查找。2021/2/436折半查找二分查找2021/2/437查找二分查找(折半查找)：由于每次都可以減少一半的元素，所以最壞時(shí)間復(fù)雜度為log(2n)2021/2/438排序 排序是指將一個(gè)無序序列整理成按值遞增或遞減(本章均采用遞增規(guī)則)的有序序列。排序可以在各種不同的存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)，本章所介紹的算法以順序存儲(chǔ)的線性表為排序?qū)ο螅诔绦蛟O(shè)計(jì)語(yǔ)言中就是一維數(shù)組。排序的算法種類很多，主要包括交換類排序、插入類排序、選擇類排序等。2021/2/439排序技術(shù)交換類排序法

冒泡排序快速排序插入類排序法簡(jiǎn)單插入排序希爾排序選擇類排序法簡(jiǎn)單選擇排序堆排序2021/2/440排序法小結(jié)：最壞時(shí)間復(fù)雜度：冒泡排序法、快速排序、簡(jiǎn)單選擇排序法、簡(jiǎn)單插入排序：

最壞情況需要n(n-1)/2次比較；希爾排序法：最壞情況需要O(n1.5)次比較；堆排序法,最壞情況需要O(nlog2n)次比較；平均速度最快排序：快速排序最好、最壞、平均三種復(fù)雜度都相同的排序方法：堆排序2021/2/441第二章程序設(shè)計(jì)基礎(chǔ)(15%)考試大綱1.程序設(shè)計(jì)方法與風(fēng)格。

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

3.面向?qū)ο蟮某绦蛟O(shè)計(jì)方法，對(duì)象，方法，屬性及繼承與多態(tài)性。

2021/2/442知識(shí)點(diǎn)歸納程序設(shè)計(jì)方法程序設(shè)計(jì)是一門技術(shù)，需要相應(yīng)的理論、方法和工具來支持。就程序設(shè)計(jì)方法和技術(shù)的發(fā)展而言，主要經(jīng)歷了結(jié)構(gòu)化的程序設(shè)計(jì)和面向?qū)ο蟮某绦蛟O(shè)計(jì)階段。在程序設(shè)計(jì)中，通常采用“自頂向下，逐步求精”的方法，即把一個(gè)模塊的功能逐步分解，細(xì)化為一系列具體的步驟，進(jìn)而轉(zhuǎn)換成一系列用某種程序設(shè)計(jì)語(yǔ)言編寫的程序。2021/2/443程序設(shè)計(jì)風(fēng)格除了程序設(shè)計(jì)設(shè)計(jì)方法和技術(shù)之外，程序風(fēng)格也是非常重要的。良好的程序設(shè)計(jì)風(fēng)格概括起來包括以下及格方面：源程序文檔化數(shù)據(jù)說明的方法語(yǔ)句的結(jié)構(gòu)輸入和輸出2021/2/444程序設(shè)計(jì)風(fēng)格源程序文檔化標(biāo)識(shí)符的命名程序的注釋序言性注釋功能性注釋程序的視覺組織數(shù)據(jù)的說明數(shù)據(jù)說明的次序應(yīng)該規(guī)范化說明語(yǔ)句中變量的安排有序化使用注釋說明復(fù)雜的數(shù)據(jù)結(jié)構(gòu)2021/2/445程序設(shè)計(jì)風(fēng)格語(yǔ)句結(jié)構(gòu)在一行內(nèi)只寫一條語(yǔ)句程序編寫應(yīng)優(yōu)先考慮清晰性除非對(duì)效率有特殊要求，程序編寫要做到清晰第一，效率第二首先要保證程序正確，然后才要求提高速度避免使用臨時(shí)變量而使程序的可讀性下降避免不必要的轉(zhuǎn)移盡可能使用庫(kù)函數(shù)避免使用復(fù)雜的條件語(yǔ)句盡量減少使用“否定”條件的條件語(yǔ)句數(shù)據(jù)結(jié)構(gòu)要有利于程序的簡(jiǎn)化要模塊化，使模塊功能盡可能單一化利用信息隱蔽，確保每一個(gè)模塊的獨(dú)立性從數(shù)據(jù)出發(fā)構(gòu)造程序不要修補(bǔ)不好的程序，要重寫編寫2021/2/446程序設(shè)計(jì)風(fēng)格輸入和輸出對(duì)所有輸入數(shù)據(jù)檢驗(yàn)合法性檢查輸入項(xiàng)的各種重要組合的合法性輸入格式要簡(jiǎn)單，以使輸入的步驟和操作盡可能簡(jiǎn)單輸入數(shù)據(jù)時(shí)，應(yīng)允許使用自由格式應(yīng)允許缺省值輸入一批數(shù)據(jù)時(shí)，最好使用輸入結(jié)束標(biāo)志在以交互式輸入/輸出方式進(jìn)行輸入時(shí)，要在屏幕上使用提示符明確提示輸入的請(qǐng)求，同時(shí)在數(shù)據(jù)輸入結(jié)束時(shí)，應(yīng)在屏幕上給出狀態(tài)信息當(dāng)程序設(shè)計(jì)語(yǔ)言對(duì)輸入格式有嚴(yán)格要求時(shí)，應(yīng)保持輸入格式與輸入語(yǔ)句的一致性；給所有的輸出加注釋，并設(shè)計(jì)輸出報(bào)表格式。2021/2/447結(jié)構(gòu)化程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)的原則自頂向下。程序設(shè)計(jì)時(shí)，應(yīng)先考慮總體，后考慮細(xì)節(jié)；先考慮全局目標(biāo)，后考慮局部目標(biāo)。不要一開始就過多追求細(xì)節(jié)，先從最上層總目標(biāo)開始設(shè)計(jì)，逐步使問題具體化。逐步求精。對(duì)復(fù)雜的問題，應(yīng)設(shè)計(jì)一些子目標(biāo)過渡，逐步細(xì)化。模塊化。一個(gè)復(fù)雜問題肯定是有若干簡(jiǎn)單問題構(gòu)成。模塊化是把程序要解決的總目標(biāo)分解為分目標(biāo)，再進(jìn)一步分解為具體的小目標(biāo)，每個(gè)小目標(biāo)成為一個(gè)模塊。嚴(yán)格限制GOTO語(yǔ)句的使用。2021/2/448結(jié)構(gòu)化程序設(shè)計(jì)的基本結(jié)構(gòu)和特點(diǎn)程序由一些基本結(jié)構(gòu)組成，任何一個(gè)程序都可以用三種基本控制結(jié)構(gòu)組成：順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)，并且具有如下特點(diǎn)：?jiǎn)稳肟凇纬隹?、結(jié)構(gòu)中無死循環(huán)，程序中三種基本控制結(jié)構(gòu)之間形成順序執(zhí)行關(guān)系。一個(gè)大型程序應(yīng)按功能分割成一些模塊，并把這些模塊按層次關(guān)系進(jìn)行組織。在程序設(shè)計(jì)時(shí)應(yīng)采用自頂向下、逐步細(xì)化的實(shí)施方法。2021/2/449面向?qū)ο蟪绦蛟O(shè)計(jì)

面向?qū)ο蠓椒ǖ幕靖拍?.對(duì)象、類和屬性在面向?qū)ο蟪绦蛟O(shè)計(jì)中，對(duì)象是程序的基本單位。對(duì)象可以表示客觀世界中的任何實(shí)體，是對(duì)問題域中某個(gè)實(shí)體的抽象。每個(gè)對(duì)象可以用它本身的一組屬性和它可以執(zhí)行的一組操作來定義。類是對(duì)一組具有共同屬性和相似行為的對(duì)象的一種抽象，描述了屬于該類的所有對(duì)象的性質(zhì)。2.方法方法有稱為操作或服務(wù)，它描述了對(duì)象執(zhí)行的功能，若通過消息傳遞，還可為其他對(duì)象使用。2021/2/450面向?qū)ο蠓椒ǖ幕靖拍?.繼承：繼承是對(duì)象方法的一個(gè)重要特征。指一個(gè)類(子類)直接使用另一個(gè)類(父類)的所有屬性和方法。它可以減少相似類的重復(fù)說明，從而體現(xiàn)一般性和特殊性的原則。4.多態(tài)性：多態(tài)性可以用“一個(gè)對(duì)外界面，多個(gè)內(nèi)部實(shí)現(xiàn)”來表示?？梢酝ㄟ^方法重載和方法重寫來實(shí)現(xiàn)多態(tài)。重載指一個(gè)類中可以有多個(gè)具有相同名稱的方法，由傳遞給它們的不同個(gè)數(shù)和類型的參數(shù)來決定執(zhí)行那個(gè)方法。重寫指子類可以重新實(shí)現(xiàn)父類的某些方法，使其具有自己的特征。多態(tài)性機(jī)制增加了面向?qū)ο筌浖到y(tǒng)的靈活性，提高了軟件的可重用性和可擴(kuò)充性。5.消息：面向?qū)ο笙到y(tǒng)中的對(duì)象之間是通過消息機(jī)制彼此相互合作的，消息是一個(gè)對(duì)象與另一個(gè)對(duì)象之間傳遞的信息，它請(qǐng)求對(duì)象執(zhí)行某一處理或回答某一要求的信息。2021/2/451面向?qū)ο蟪绦蛟O(shè)計(jì)的特點(diǎn)按照人的思維方式對(duì)客觀世界進(jìn)行抽象穩(wěn)定性好可重用性好易于開發(fā)大型軟件可維護(hù)性好2021/2/452第三章軟件工程基礎(chǔ)考試大綱1.軟件工程基本概念，軟件生命周期的概念，軟件工具與軟件開發(fā)環(huán)境。

2.結(jié)構(gòu)化分析方法，數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說明書。

3.結(jié)構(gòu)化設(shè)計(jì)方法，總體設(shè)計(jì)與詳細(xì)設(shè)計(jì)。

4.軟件測(cè)試的方法，白盒測(cè)試與黑盒測(cè)試，測(cè)試用例設(shè)計(jì)，軟件測(cè)試的實(shí)施，單元測(cè)試、集成測(cè)試和系統(tǒng)測(cè)試。

5.程序的調(diào)試，靜態(tài)調(diào)試與動(dòng)態(tài)調(diào)試。

2021/2/453知識(shí)點(diǎn)歸納軟件定義和特點(diǎn)計(jì)算機(jī)軟件式計(jì)算機(jī)系統(tǒng)中與硬件相互依存的另一部分，是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。計(jì)算機(jī)軟件具有如下特點(diǎn)：軟件是一種邏輯實(shí)體，具有抽象性軟件生產(chǎn)沒有明顯的制造過程軟件在運(yùn)行、使用期間不存在磨損、老化問題軟件的開發(fā)、運(yùn)行對(duì)計(jì)算機(jī)系統(tǒng)具有依賴性軟件復(fù)雜性高，成本昂貴軟件開發(fā)涉及諸多社會(huì)因素2021/2/454軟件危機(jī)所謂軟件危機(jī)是指在計(jì)算機(jī)軟件開發(fā)和維護(hù)過程中所遇到的一系列嚴(yán)重問題，包括：軟件需求的增長(zhǎng)得不到滿足軟件開發(fā)成本和進(jìn)度無法控制軟件質(zhì)量難以保證軟件不可維護(hù)或可維護(hù)性低軟件成本不斷提高軟件開發(fā)生產(chǎn)率的提高趕不上硬件的發(fā)展和應(yīng)用需求的增長(zhǎng)。2021/2/455軟件工程為了消除軟件危機(jī)，提出了軟件工程學(xué)。軟件工程是應(yīng)用于計(jì)算機(jī)軟件定義、開發(fā)和維護(hù)的一整套方法、工具、文檔、實(shí)踐標(biāo)準(zhǔn)和工序。軟件工程的三要素方法工具過程2021/2/456軟件工程過程軟件工程過程是把輸入轉(zhuǎn)化為輸出的一組彼此相關(guān)的資源和活動(dòng)。它包括兩方面含義：1.軟件工程過程是指為獲得軟件產(chǎn)品，在軟件工具支持下由軟件工程師完成的一系列工程活動(dòng)。通常包括四種基本活動(dòng)：P(Plan)：軟件規(guī)格說明D(Do)：軟件開發(fā)C(Check)：軟件確認(rèn)A(Action)：軟件演進(jìn)2.從軟件開發(fā)的觀點(diǎn)看，軟件工程過程是使用適當(dāng)?shù)馁Y源，為開發(fā)軟件進(jìn)行的一組開發(fā)活動(dòng)，在活動(dòng)結(jié)束時(shí)將輸入(用戶需求)轉(zhuǎn)化為輸出(軟件產(chǎn)品)。2021/2/457軟件生命周期軟件從提出、實(shí)現(xiàn)、使用、維護(hù)到停止使用的過程稱為軟件的生命周期。一般包括以下幾個(gè)階段：可行性研究與計(jì)劃制定需求分析軟件設(shè)計(jì)軟件實(shí)現(xiàn)軟件測(cè)試運(yùn)行和維護(hù)2021/2/458軟件工程目標(biāo)與原則軟件工程的目標(biāo)是在給定成本、進(jìn)度的前提下，開發(fā)出具有有效性、可靠性、可理解性、可維護(hù)性、可重用性、可適應(yīng)性、可移植性、可追蹤性和可互操作性且滿足用戶需求的軟件產(chǎn)品。為達(dá)到上述目標(biāo)，在軟件開發(fā)的過程中，必須遵循軟件工程的基本原則：抽象信息隱蔽模塊化局部化確定性一致性完備性可驗(yàn)證性2021/2/459軟件開發(fā)工具與軟件開發(fā)環(huán)境軟件開發(fā)工具對(duì)過程和方法提供自動(dòng)或半自動(dòng)的支持。當(dāng)這些工具被集成起來使得一個(gè)工具產(chǎn)生的信息可以被另外一個(gè)工具使用時(shí)，一個(gè)支持軟件開發(fā)的系統(tǒng)就建立起來了，稱為計(jì)算機(jī)輔助軟件工程(CASE)。CASE集成了軟件、硬件和一個(gè)軟件工程數(shù)據(jù)庫(kù)(包含了有關(guān)分析、設(shè)計(jì)、程序構(gòu)造和測(cè)試的重要信息)從而創(chuàng)建了一個(gè)軟件開發(fā)環(huán)境。2021/2/460結(jié)構(gòu)化分析方法結(jié)構(gòu)化分析方法大多使用自頂向下、逐層分解的系統(tǒng)分析方法來定義系統(tǒng)需求。在結(jié)構(gòu)化分析的基礎(chǔ)上，完成系統(tǒng)的規(guī)格說明，建立系統(tǒng)的一個(gè)自頂向下的任務(wù)分析模型。結(jié)構(gòu)化分析方法是一種建模技術(shù)，模型的核心是數(shù)據(jù)辭典，它描述了所有在目標(biāo)系統(tǒng)中使用和生成的數(shù)據(jù)對(duì)象。結(jié)構(gòu)化分析常用的工具：數(shù)據(jù)流圖(DFD):描述數(shù)據(jù)在系統(tǒng)中如何被傳送或變換以及描述如何對(duì)數(shù)據(jù)流進(jìn)行變換的功能，用于功能建模。數(shù)據(jù)字典判定樹判定表2021/2/461數(shù)據(jù)流圖數(shù)據(jù)流圖是描述數(shù)據(jù)處理過程的工具，它從數(shù)據(jù)傳遞和加工的角度，來刻畫數(shù)據(jù)流從輸入系統(tǒng)到從系統(tǒng)輸入的移動(dòng)變換過程。數(shù)據(jù)流圖的基本元素外部實(shí)體數(shù)據(jù)流處理(加工)數(shù)據(jù)存儲(chǔ)2021/2/462數(shù)據(jù)字典數(shù)據(jù)字典是關(guān)于數(shù)據(jù)的信息的集合，對(duì)數(shù)據(jù)流圖中的各個(gè)元素進(jìn)行完整的定義和說明。數(shù)據(jù)流圖和數(shù)據(jù)字典共同構(gòu)成系統(tǒng)的邏輯模型。數(shù)據(jù)字典通常包含的信息有：名稱、別名、何處使用、如何使用、內(nèi)容描述以及補(bǔ)充信息等。2021/2/463軟件需求軟件需求包括：功能需求、性能需求、環(huán)境需求、可靠性需求、安全保密需求、用戶界面需求、資源使用需求、成本消耗需求、開發(fā)進(jìn)度需求等。需求分析應(yīng)交付的主要文檔是軟件需求規(guī)格說明書(SRS)。2021/2/464結(jié)構(gòu)化設(shè)計(jì)結(jié)構(gòu)化設(shè)計(jì)就是采用最佳的可能方法設(shè)計(jì)系統(tǒng)的各個(gè)組成部分以及個(gè)成分之間的內(nèi)部聯(lián)系的技術(shù)。也就是說，結(jié)構(gòu)化設(shè)計(jì)是這樣一個(gè)過程：它決定用哪些方法把哪些部分聯(lián)系起來，才能解決好某個(gè)具體的有清楚定義的問題。從工程管理的角度看，軟件設(shè)計(jì)分兩步完成：1.概要設(shè)計(jì)，即總體設(shè)計(jì)。將軟件需求轉(zhuǎn)化為數(shù)據(jù)結(jié)構(gòu)和軟件的系統(tǒng)結(jié)構(gòu)。常用的軟件結(jié)構(gòu)設(shè)計(jì)工具是結(jié)構(gòu)圖(StructureChart)。2.詳細(xì)設(shè)計(jì)：即過程設(shè)計(jì)。通過對(duì)結(jié)構(gòu)表示進(jìn)行細(xì)化，得到軟件詳細(xì)的數(shù)據(jù)結(jié)構(gòu)和算法。過程設(shè)計(jì)常用的工具有：程序流程圖、N-S圖、PAD圖、過程設(shè)計(jì)語(yǔ)言PDL(偽碼)。2021/2/465軟件測(cè)試定義：使用人工或自動(dòng)手段來運(yùn)行或測(cè)定某個(gè)系統(tǒng)的過程，其目的在于檢驗(yàn)它是否滿足規(guī)定的需求或弄清預(yù)期結(jié)果與實(shí)際結(jié)果之間的差別。軟件測(cè)試是為了發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過程。一個(gè)好的測(cè)試用例是指可能找到迄今為止尚未發(fā)現(xiàn)的錯(cuò)誤的用例。一個(gè)成功的測(cè)試是發(fā)現(xiàn)了至今尚未發(fā)現(xiàn)的錯(cuò)誤的測(cè)試。測(cè)試不能表明軟件中不存在錯(cuò)誤，它只能說明軟件中存在錯(cuò)誤。2021/2/466測(cè)試技術(shù)與方法綜述從是否需要執(zhí)行被測(cè)試軟件的角度，可將測(cè)試分為靜態(tài)測(cè)試和動(dòng)態(tài)測(cè)試。靜態(tài)測(cè)試主要包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量等。動(dòng)態(tài)測(cè)試是基于計(jì)算機(jī)的測(cè)試，是為了發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過程，或者說，是根據(jù)軟件開發(fā)的各個(gè)階段的規(guī)格說明和程序的內(nèi)部結(jié)構(gòu)而精心設(shè)計(jì)的一批測(cè)試用例，并利用這些測(cè)試用例去運(yùn)行程序，以發(fā)現(xiàn)程序錯(cuò)誤的過程。2021/2/467測(cè)試技術(shù)與方法綜述按照功能劃分，可將軟件測(cè)試分為黑盒測(cè)試和白盒測(cè)試。黑盒測(cè)試將測(cè)試對(duì)象看作一個(gè)黑盒，不考慮程序內(nèi)部的邏輯結(jié)構(gòu)和內(nèi)部特性，只依據(jù)程序的需求規(guī)格說明，檢查程序的功能是否符合它的功能說明。這種測(cè)試又稱為功能測(cè)試或數(shù)據(jù)驅(qū)動(dòng)測(cè)試。白盒測(cè)試把測(cè)試對(duì)象看作一個(gè)透明的盒子，利用程序內(nèi)部的邏輯機(jī)構(gòu)及有關(guān)信息，設(shè)計(jì)或選擇測(cè)試用例，對(duì)程序的所有邏輯路徑進(jìn)行測(cè)試。通過在不同點(diǎn)檢查程序的狀態(tài)，確定實(shí)際的狀態(tài)是否與預(yù)期的一致。這種測(cè)試又稱為結(jié)構(gòu)測(cè)試或邏輯驅(qū)動(dòng)測(cè)試。2021/2/468軟件測(cè)試的實(shí)施軟件測(cè)試按四個(gè)步驟進(jìn)行：?jiǎn)卧獪y(cè)試：對(duì)軟件設(shè)計(jì)的最小單位－模塊進(jìn)行正確性的測(cè)試，其目的是發(fā)現(xiàn)各模塊內(nèi)部可能存在的各種錯(cuò)誤。集成測(cè)試：是測(cè)試和組裝軟件的過程，它是在把模塊按照設(shè)計(jì)要求組裝起來的同時(shí)進(jìn)行測(cè)試，主要目的是發(fā)現(xiàn)與接口有關(guān)的錯(cuò)誤。確認(rèn)測(cè)試：任務(wù)是驗(yàn)證軟件的功能和性能以及其他特性是否滿足了需求規(guī)格說明中確定的各種需求，以及軟件配置是否完全、正確。系統(tǒng)測(cè)試：將通過確認(rèn)測(cè)試的軟件，作為整個(gè)計(jì)算機(jī)系統(tǒng)的一個(gè)元素，與計(jì)算機(jī)硬件、外設(shè)、支持軟件、數(shù)據(jù)以及人員等其他系統(tǒng)元素組合在一起，在實(shí)際運(yùn)行環(huán)境中對(duì)其進(jìn)行一系列的集成測(cè)試和確認(rèn)測(cè)試。2021/2/469程序調(diào)試程序調(diào)試的任務(wù)是診斷和修正程序中的錯(cuò)誤。調(diào)試的方法：強(qiáng)行排錯(cuò)法回溯法原因排除法2021/2/470第四章數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)考試大綱1.數(shù)據(jù)庫(kù)的基本概念：數(shù)據(jù)庫(kù)，數(shù)據(jù)庫(kù)管理系統(tǒng)，數(shù)據(jù)庫(kù)系統(tǒng)。

2.數(shù)據(jù)模型，實(shí)體聯(lián)系模型及E-R圖，從E-R圖導(dǎo)出關(guān)系數(shù)據(jù)模型。

3.關(guān)系代數(shù)運(yùn)算，包括集合運(yùn)算及選擇、投影、連接運(yùn)算，數(shù)據(jù)庫(kù)規(guī)范化理論。

4.數(shù)據(jù)庫(kù)設(shè)計(jì)方法和步驟：需求分析、概念設(shè)計(jì)、邏輯設(shè)計(jì)和物理設(shè)計(jì)的相關(guān)策略。2021/2/471知識(shí)點(diǎn)歸納數(shù)據(jù)庫(kù)的定義1.長(zhǎng)期存放在計(jì)算機(jī)內(nèi)，有組織的、可共享的數(shù)據(jù)集合。數(shù)據(jù)庫(kù)中的數(shù)據(jù)按一定的數(shù)據(jù)模型組織、描述和存儲(chǔ)，具有較小的冗余度、較高的數(shù)據(jù)獨(dú)立性和易擴(kuò)展性。2.數(shù)據(jù)庫(kù)是由一個(gè)互相關(guān)聯(lián)的數(shù)據(jù)的集合和一組用以訪問這些數(shù)據(jù)的程序組成的。2021/2/472數(shù)據(jù)庫(kù)管理系統(tǒng)(DBMS)數(shù)據(jù)庫(kù)管理系統(tǒng)是一個(gè)幫助用戶創(chuàng)建和管理數(shù)據(jù)庫(kù)的應(yīng)用程序的集合。因此，數(shù)據(jù)庫(kù)管理系統(tǒng)也就是一個(gè)可以幫助完成定義、構(gòu)造和操縱數(shù)據(jù)庫(kù)等處理目的的通用軟件系統(tǒng)。其主要功能如下：數(shù)據(jù)模式定義數(shù)據(jù)存取的物理構(gòu)建數(shù)據(jù)操縱數(shù)據(jù)的完整性、安全性定義和檢查數(shù)據(jù)庫(kù)的并發(fā)控制和故障恢復(fù)數(shù)據(jù)的服務(wù)為完成上述功能，DBMS提供了相應(yīng)的語(yǔ)言：數(shù)據(jù)定義語(yǔ)言(DDL)數(shù)據(jù)操縱語(yǔ)言(DML)數(shù)據(jù)控制語(yǔ)言(DCL)2021/2/473數(shù)據(jù)庫(kù)系統(tǒng)數(shù)據(jù)庫(kù)系統(tǒng)是由數(shù)據(jù)庫(kù)、數(shù)據(jù)庫(kù)管理系統(tǒng)、數(shù)據(jù)庫(kù)管理員、硬件平臺(tái)和軟件平臺(tái)等幾個(gè)部分組成的完整的運(yùn)行實(shí)體。數(shù)據(jù)庫(kù)系統(tǒng)的特點(diǎn)數(shù)據(jù)的集成性數(shù)據(jù)的高共享性和低冗余性數(shù)據(jù)的獨(dú)立性數(shù)據(jù)統(tǒng)一管理和控制2021/2/474數(shù)據(jù)庫(kù)系統(tǒng)的內(nèi)部體系結(jié)構(gòu)三級(jí)模式概念模式：數(shù)據(jù)庫(kù)系統(tǒng)中全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu)的描述，全體用戶的數(shù)據(jù)視圖外模式：又稱為用戶模式，是每個(gè)用戶的局部數(shù)據(jù)描述，用戶的數(shù)據(jù)視圖內(nèi)模式：又稱為物理模式，是數(shù)據(jù)庫(kù)物理存儲(chǔ)結(jié)構(gòu)和物理存取方法的描述二級(jí)映射概念模式到內(nèi)模式的映射外模式到概念模式的映射2021/2/475數(shù)據(jù)模型數(shù)據(jù)是現(xiàn)實(shí)世界符號(hào)的抽象，數(shù)據(jù)模型是現(xiàn)實(shí)世界數(shù)據(jù)特征的抽象，它從抽象層次上描述了系統(tǒng)的靜態(tài)特征、動(dòng)態(tài)行為和約束條件，為數(shù)據(jù)庫(kù)系統(tǒng)的信息表示和操作提供一個(gè)抽象的框架。數(shù)據(jù)模型描述的內(nèi)容包括三部分：數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)操作數(shù)據(jù)約束數(shù)據(jù)模型按不同的應(yīng)用層次分成三種類型：概念數(shù)據(jù)模型邏輯數(shù)據(jù)模型物理數(shù)據(jù)模型2021/2/476實(shí)體聯(lián)系(ER)模型概念模型是面向現(xiàn)實(shí)世界的，其出發(fā)點(diǎn)是有效地模擬顯示世界，給出數(shù)據(jù)的概念化結(jié)構(gòu)。實(shí)體聯(lián)系模型是一種廣泛使用的概念模型，該模型將現(xiàn)實(shí)世界的要求轉(zhuǎn)化為實(shí)體、聯(lián)系和屬性等幾個(gè)基本概念，并用ER圖直觀地表示出來。2021/2/477ER模型的基本概念實(shí)體：概念世界中的基本單位，它們是客觀存在且能相互區(qū)別的事物。凡具有共性的實(shí)體可以組成一個(gè)集合稱為實(shí)體集。屬性：屬性用來描述實(shí)體的特征。一個(gè)實(shí)體可以有多個(gè)屬性，每個(gè)屬性可以有值，一個(gè)屬性的取值范圍稱為該屬性的值域。聯(lián)系：聯(lián)系反映概念世界中的實(shí)體集之間存在的一定關(guān)系。一對(duì)一聯(lián)系(1:1)一對(duì)多聯(lián)系(1:M)多對(duì)多聯(lián)系(M:N)2021/2/478ER圖ER圖是實(shí)體聯(lián)系模型的直觀圖形表示。實(shí)體用矩形表示，并在矩形中標(biāo)明實(shí)體的名稱。屬性用標(biāo)有屬性名稱的橢圓表示，而且必須用線將屬性與其所屬的實(shí)現(xiàn)相連。關(guān)系用標(biāo)明關(guān)系名稱的菱形表示，關(guān)系的名稱一般是動(dòng)詞。