全國計算機等級考試 - 二級公共基礎(chǔ)知識輔導(dǎo)講義-

1、全國計算機等級考試二級公共基礎(chǔ)知識輔導(dǎo)講義第一章數(shù)據(jù)結(jié)構(gòu)與算法1.1 算法 1描述。*:算法不等于程序,也不等于計算方法。程序的編制不可能優(yōu)于算法的設(shè)計。2、算法的基本特征(1可行性。針對實際問題而設(shè)計的算法,執(zhí)行后能夠得到滿意的結(jié)果。(2確定性。每一條指令的含義明確,無二義性。并且在任何條件下,算法只有唯一的一條執(zhí)行路徑,即相同的輸入只能得出相同的輸出。(3有窮性。算法必須在有限的時間內(nèi)完成。有兩重含義,一是算法中的操作步驟為有限個,二是每個步驟都能在有限時間內(nèi)完成。(4擁有足夠的情報。算法中各種運算總是要施加到各個運算對象上,而這些運算對象又可能具有某種初始狀態(tài),這就是算法執(zhí)行的起點或依據(jù)

2、。因此,一個算法執(zhí)行的結(jié)果總是與輸入的初始數(shù)據(jù)有關(guān),不同的輸入將會有不同的結(jié)果輸出。當(dāng)輸入不夠或輸入錯誤時,算法將無法執(zhí)行或執(zhí)行有錯。一般說來,當(dāng)算法擁有足夠的情報時,此算法才是有效的;而當(dāng)提供的情報不夠時,算法可能無效。*:綜上所述,所謂算法,是一組嚴謹?shù)囟x運算順序的規(guī)則,并且每一個規(guī)則都是有效的,且是明確的,此順序?qū)⒃谟邢薜拇螖?shù)下終止。3、算法復(fù)雜度主要包括時間復(fù)雜度和空間復(fù)雜度。(1算法時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量,可以用執(zhí)行算法的過程中所需基 1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念 12、數(shù)據(jù)結(jié)構(gòu)主要研究和討論以下三個方面的問題:(1數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系,即數(shù)據(jù)的

3、邏輯結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)包含:1表示數(shù)據(jù)元素的信息;2表示各數(shù)據(jù)元素之間的前后件關(guān)系。(2在對數(shù)據(jù)進行處理時,各數(shù)據(jù)元素在計算機中的存儲關(guān)系,即數(shù)據(jù)的存儲結(jié)構(gòu)。數(shù)據(jù)的存儲結(jié)構(gòu)有順序、鏈接、索引等。1順序存儲。它是把邏輯上相鄰的結(jié)點存儲在物理位置相鄰的存儲單元里,結(jié)點間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。由此得到的存儲表示稱為順序存儲結(jié)構(gòu)。2鏈接存儲。它不要求邏輯上相鄰的結(jié)點在物理位置上亦相鄰,結(jié)點間的邏輯關(guān)系是由附加的指針字段表示的。由此得到的存儲表示稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)。3索引存儲:除建立存儲結(jié)點信息外,還建立附加的索引表來標(biāo)識結(jié)點的地址。*:數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系,數(shù)據(jù)的存

4、儲結(jié)構(gòu)(也稱數(shù)據(jù)的物理結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式。同一種邏輯結(jié)構(gòu)的數(shù)據(jù)可以采用不同的存儲結(jié)構(gòu),但影響數(shù)據(jù)處理效率。(3對各種數(shù)據(jù)結(jié)構(gòu)進行的運算。3、數(shù)據(jù)結(jié)構(gòu)的圖形表示一個數(shù)據(jù)結(jié)構(gòu)除了用二元關(guān)系表示外,還可以直觀地用圖形表示。在數(shù)據(jù)結(jié)構(gòu)的圖形表示中,對于數(shù)據(jù)集合D中的每一個數(shù)據(jù)元素用中間標(biāo)有元素值的方框表示,一般稱之為數(shù)據(jù)結(jié)點,并簡稱為結(jié)點;為了進一步表示各數(shù)據(jù)元素之間的前后件關(guān)系,對于關(guān)系R中的每一個二元組,用一條有向線段從前件結(jié)點指向后件結(jié)點。4、數(shù)據(jù)結(jié)構(gòu)分為兩大類型:線性結(jié)構(gòu)和非線性結(jié)構(gòu)。 (11有且只有一個根結(jié)點;2每一個結(jié)點最多有一個前件,也最多有一個后件。*:常

5、見的線性結(jié)構(gòu)有線性表、棧、隊列和線性鏈表等。 (2*:常見的非線性結(jié)構(gòu)有樹、二叉樹和圖等。1.3 線性表及其順序存儲結(jié)構(gòu) 1置是線性的。線性表是由n(n0個數(shù)據(jù)元素組成的一個有限序列,表中的每一個數(shù)據(jù)元素,除了第一個外,有且只有一個前件,除了最后一個外,有且只有一個后件。線性表中數(shù)據(jù)元素的個數(shù)稱為線性表的長度。線性表可以為空表。*:線性表是一種存儲結(jié)構(gòu),它的存儲方式:順序和鏈?zhǔn)健?、線性表的順序存儲結(jié)構(gòu)具有兩個基本特點:(1線性表中所有元素所占的存儲空間是連續(xù)的;(2線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。*:由此可以看出,在線性表的順序存儲結(jié)構(gòu)中,其前后件兩個元素在存儲空間中是

6、緊鄰的,且前件元素一定存儲在后件元素的前面,可以通過計算機直接確定第i個結(jié)點的存儲地址。3、順序表的插入、刪除運算(1順序表的插入運算:在一般情況下,要在第i(1in個元素之前插入一個新元素時,首先要從最后一個(即第n個元素開始,直到第i個元素之間共n-i+1個元素依次向后移動一個位置,移動結(jié)束后,第i個位置就被空出,然后將新元素插入到第i項。插入結(jié)束后,線性表的長度就增加了1。*:順性表的插入運算時需要移動元素,在等概率情況下,平均需要移動n/2個元素。(2順序表的刪除運算:在一般情況下,要刪除第i(1in個元素時,則要從第i+1個元素開始,直到第n個元素之間共n-i個元素依次向前移動一個位

7、置。刪除結(jié)束后,線性表的長度就減小了1。*:進行順性表的刪除運算時也需要移動元素,在等概率情況下,平均需要移動(n-1/2個元素。插入、刪除運算不方便。1.4 棧和隊列1、棧及其基本運算 在棧中,允許插入與刪除的一端稱為棧頂,不允許插入與刪除的另一端稱為棧底。棧頂元素總是最后被插入的元素,棧底元素總是最先被插入的元素。即棧是按照“先進后出”或“后進先出”的原則組織數(shù)據(jù)的。棧具有記憶作用。棧的基本運算:1插入元素稱為入棧運算;2刪除元素稱為退棧運算;3讀棧頂元素是將棧頂元素賦給一個指定的變量,此時指針無變化。棧的存儲方式和線性表類似,也有兩種,即順序棧和鏈?zhǔn)綏！?、隊列及其基本運算 (Rear

8、指向隊尾元素,頭指針(front 指向排頭元素的前一個位置(隊頭。 隊列是“先進先出”或“后進后出”的線性表。隊列運算包括:1入隊運算:從隊尾插入一個元素;2退隊運算:從隊頭刪除一個元素。 循環(huán)隊列及其運算:所謂循環(huán)隊列,就是將隊列存儲空間的最后一個位置繞到第一個位置,形成邏輯上的環(huán)狀空間,供隊列循環(huán)使用。在循環(huán)隊列中,用隊尾指針rear 指向隊列中的隊尾元素,用排頭指針front 指向排頭元素的前一個位置,因此,從頭指針front 指向的后一個位置直到隊尾指針rear 指向的位置之間,所有的元素均為隊列中的元素。*:循環(huán)隊列中元素的個數(shù)=rear-front 。 1.5 線性鏈表 1、線性表

9、順序存儲的缺點:(1插入或刪除的運算效率很低。在順序存儲的線性表中,插入或刪除數(shù)據(jù)元素時需要移動大量的數(shù)據(jù)元素;(2線性表的順序存儲結(jié)構(gòu)下,線性表的存儲空間不便于擴充;(3線性表的順序存儲結(jié)構(gòu)不便于對存儲空間的動態(tài)分配。2、線性鏈表:線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表,是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu),數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接來實現(xiàn)的。因此,在鏈?zhǔn)酱鎯Ψ绞街?每個結(jié)點由兩部分組成:一部分用于存放數(shù)據(jù)元素的值,稱為數(shù)據(jù)域;另一部分用于存放指針,稱為指針域,用于指向該結(jié)點的前一個或后一個結(jié)點(即前件或后件,如下圖所示: 線性鏈表分為單鏈表、雙向鏈表和循環(huán)鏈表三種類型。在單

10、鏈表中,每一個結(jié)點只有一個指針域,由這個指針只能找到其后件結(jié)點,而不能找到其前件結(jié)點。因此,在某些應(yīng)用中,對于線性鏈表中的每個結(jié)點設(shè)置兩個指針,一個稱為左指針,指向其前件結(jié)點;另一個稱為右指針,指向其后件結(jié)點,這種鏈表稱為雙向鏈表,如下圖所示: 3、線性鏈表的基本運算(1在線性鏈表中包含指定元素的結(jié)點之前插入一個新元素。*:在線性鏈表中插入元素時,不需要移動數(shù)據(jù)元素,只需要修改相關(guān)結(jié)點指針即可,也不會出現(xiàn)“上溢”現(xiàn)象。(2在線性鏈表中刪除包含指定元素的結(jié)點。*:在線性鏈表中刪除元素時,也不需要移動數(shù)據(jù)元素,只需要修改相關(guān)結(jié)點指針即可。(3將兩個線性鏈表按要求合并成一個線性鏈表。(4將一個線性鏈

11、表按要求進行分解。(5逆轉(zhuǎn)線性鏈表。(6復(fù)制線性鏈表。(7線性鏈表的排序。(8線性鏈表的查找。*:線性鏈表不能隨機存取。 數(shù)據(jù)域指針域HEAD (a結(jié)點結(jié)構(gòu)(b一個非空的線性鏈表示意圖右指針左指針數(shù)據(jù)域(a結(jié)點結(jié)構(gòu)HEAD (b一個非空的雙向鏈表示意圖4、循環(huán)鏈表及其基本運算在線性鏈表中,其插入與刪除的運算雖然比較方便,但還存在一個問題,在運算過程中對于空表和對第一個結(jié)點的處理必須單獨考慮,使空表與非空表的運算不統(tǒng)一。為了克服線性鏈表的這個缺點,可以采用另一種鏈接方式,即循環(huán)鏈表。與前面所討論的線性鏈表相比,循環(huán)鏈表具有以下兩個特點:1在鏈表中增加了一個表頭結(jié)點,其數(shù)據(jù)域為任意或者根據(jù)需要來設(shè)

12、置,指針域指向線性表的第一個元素的結(jié)點,而循環(huán)鏈表的頭指針指向表頭結(jié)點;2循環(huán)鏈表中最后一個結(jié)點的指針域不是空,而是指向表頭結(jié)點。即在循環(huán)鏈表中,所有結(jié)點的指針構(gòu)成了一個環(huán)狀鏈。下圖a 是一個非空的循環(huán)鏈表,圖b 是一個空的循環(huán)鏈表: 循環(huán)鏈表的優(yōu)點主要體現(xiàn)在兩個方面:一是在循環(huán)鏈表中,只要指出表中任何一個結(jié)點的位置,就可以從它出發(fā)訪問到表中其他所有的結(jié)點,而線性單鏈表做不到這一點;二是由于在循環(huán)鏈表中設(shè)置了一個表頭結(jié)點,在任何情況下,循環(huán)鏈表中至少有一個結(jié)點存在,從而使空表與非空表的運算統(tǒng)一。*:循環(huán)鏈表是在單鏈表的基礎(chǔ)上增加了一個表頭結(jié)點,其插入和刪除運算與單鏈表相同。但它可以從任一結(jié)點出

13、發(fā)來訪問表中其他所有結(jié)點,并實現(xiàn)空表與非空表的運算的統(tǒng)一。1.6 樹與二叉樹1、樹的基本概念層次特性。 2、二叉樹及其基本性質(zhì) (1什么是二叉樹它具有以下兩個特點:1非空二叉樹只有一個根結(jié)點;2每一個結(jié)點最多有兩棵子樹,且分別稱為該結(jié)點的左子樹與右子樹。 *:根據(jù)二叉樹的概念可知,二叉樹的度可以為0(葉結(jié)點、1(只有一棵子樹或2(有2棵子樹。(2二叉樹的基本性質(zhì)性質(zhì)1 在二叉樹的第k 層上,最多有 個結(jié)點。性質(zhì)2 深度為m 的二叉樹最多有個 個結(jié)點。 性質(zhì)3 在任意一棵二叉樹中,度數(shù)為0的結(jié)點(即葉子結(jié)點總比度為2的結(jié)點多一個。性質(zhì)4 具有n 個結(jié)點的二叉樹,其深度至少為 ,其中表示取 的整數(shù)

14、部分。3、滿二叉樹與完全二叉樹滿二叉樹:除最后一層外,每一層上的所有結(jié)點都有兩個子結(jié)點。1(21-k k 12-m 1log 2+n log 2n n 2log完全二叉樹:除最后一層外,每一層上的結(jié)點數(shù)均達到最大值;在最后一層上只缺少右邊的若干結(jié)點。*:根據(jù)完全二叉樹的定義可得出:度為1的結(jié)點的個數(shù)為0或1。下圖a 表示的是滿二叉樹,下圖b 表示的是完全二叉樹: 完全二叉樹還具有如下兩個特性:性質(zhì)5 具有n 個結(jié)點的完全二叉樹深度為 。性質(zhì)6 設(shè)完全二叉樹共有n 個結(jié)點,如果從根結(jié)點開始,按層序(每一層從左到右用自然數(shù)1,2,n 給結(jié)點進行編號,則對于編號為k (k=1,2,n 的結(jié)點有以下結(jié)

15、論: 若k=1,則該結(jié)點為根結(jié)點,它沒有父結(jié)點;若k>1,則該結(jié)點的父結(jié)點的編號為INT(k/2。 若2k n ,則編號為k 的左子結(jié)點編號為2k ;否則該結(jié)點無左子結(jié)點(顯然也沒有右子結(jié)點。若2k+1n ,則編號為k 的右子結(jié)點編號為2k+1;否則該結(jié)點無右子結(jié)點。4、二叉樹的存儲結(jié)構(gòu)在計算機中,二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。與線性鏈表類似,用于存儲二叉樹中各元素的存儲結(jié)點也由兩部分組成:數(shù)據(jù)域和指針域。但在二叉樹中,由于每一個元素可以有兩個后件(即兩個子結(jié)點,因此,用于存儲二叉樹的存儲結(jié)點的指針域有兩個:一個用于指向該結(jié)點的左子結(jié)點的存儲地址,稱為左指針域;另一個用于指向該結(jié)點的右子結(jié)

16、點的存儲地址,稱為右指針域。*:一般二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu),對于滿二叉樹與完全二叉樹來說,可以按層序進行順序存儲。5、二叉樹的遍歷二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有結(jié)點。二叉樹的遍歷可以分為以下三種:(1前序遍歷(DLR :若二叉樹為空,則結(jié)束返回。否則:首先訪問根結(jié)點,然后遍歷左子樹,最后遍歷右子樹;并且,在遍歷左右子樹時,仍然先訪問根結(jié)點,然后遍歷左子樹,最后遍歷右子樹。(2中序遍歷(LDR :若二叉樹為空,則結(jié)束返回。否則:首先遍歷左子樹,然后訪問根結(jié)點,最后遍歷右子樹;并且,在遍歷左、右子樹時,仍然先遍歷左子樹,然后訪問根結(jié)點,最后遍歷右子樹。(a滿二叉樹(b完全二叉樹1l

17、og 2 n(3后序遍歷(LRD:若二叉樹為空,則結(jié)束返回。否則:首先遍歷左子樹,然后遍歷右子樹,最后訪問根結(jié)點,并且,在遍歷左、右子樹時,仍然先遍歷左子樹,然后遍歷右子樹,最后訪問根結(jié)點。1.7 查找技術(shù)查找:根據(jù)給定的某個值,在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素。查找結(jié)果:(查找成功:找到;查找不成功:沒找到。平均查找長度:查找過程中關(guān)鍵字和給定值比較的平均次數(shù)。1、順序查找基本思想:從表中的第一個元素開始,將給定的值與表中逐個元素的關(guān)鍵字進行比較,直到兩者相符,查到所要找的元素為止。否則就是表中沒有要找的元素,查找不成功。在平均情況下,利用順序查找法在線性表中查找一個元素,大約

18、要與線性表中一半的元素進行比較,最壞情況下需要比較n次。順序查找一個具有n個元素的線性表,其平均復(fù)雜度為O(n。下列兩種情況下只能采用順序查找:1如果線性表是無序表(即表中的元素是無序的,則不管是順序存儲結(jié)構(gòu)還是鏈?zhǔn)酱鎯Y(jié)構(gòu),都只能用順序查找。2即使是有序線性表,如果采用鏈?zhǔn)酱鎯Y(jié)構(gòu),也只能用順序查找。2、二分法查找思想:先確定待查找記錄所在的范圍,然后逐步縮小范圍,直到找到或確認找不到該記錄為止。前提:必須在具有順序存儲結(jié)構(gòu)的有序表中進行。查找過程:1若中間項(中間項mid=(n-1/2,mid的值四舍五入取整的值等于x,則說明已查到;2若x小于中間項的值,則在線性表的前半部分查找;3若x大

19、于中間項的值,則在線性表的后半部分查找。特點:比順序查找方法效率高。最壞的情況下,需要比較log2n次。*:二分法查找只適用于順序存儲的線性表,且表中元素必須按關(guān)鍵字有序(升序排列。對于無序線性表和線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)只能用順序查找。在長度為n的有序線性表中進行二分法查找,其時間復(fù)雜度為O(log2n。1.8 排序技術(shù)排序是指將一個無序序列整理成按值非遞減順序排列的有序序列,即是將無序的記錄序列調(diào)整為有序記錄序列的一種操作。1、交換類排序法(方法:冒泡排序,快速排序。2、插入類排序法(方法:簡單插入排序,希爾排序。3、選擇類排序法(方法:簡單選擇排序,堆排序?？偨Y(jié):各種排序法比較: 本章應(yīng)考點

20、撥:本章內(nèi)容在筆試中會出現(xiàn)5-6個題目,是公共基礎(chǔ)知識部分出題量比較多的一章,所占分值也比較大,約10分。第二章程序設(shè)計基礎(chǔ)2.1 程序設(shè)計風(fēng)格程序設(shè)計的風(fēng)格主要強調(diào):“清晰第一,效率第二”。主要應(yīng)注重和考慮下述一些因素: (1源程序文檔化。1符號名的命名。符號名能反映它所代表的實際東西,應(yīng)有一定的實際含義。2程序的注釋。分為序言性注釋和功能性注釋。序言性注釋:位于程序開頭部分,包括程序標(biāo)題、程序功能說明、主要算法、接口說明、程序位置、開發(fā)簡歷、程序設(shè)計者、復(fù)審者、復(fù)審日期及修改日期等。功能性注釋:嵌在源程序體之中,用于描述其后的語句或程序的主要功能。3視覺組織。利用空格、空行、縮進等技巧使程

21、序?qū)哟吻逦?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避免使用臨時變量而使程序的可讀性下降;6避免不必要的轉(zhuǎn)移;7盡量使用庫函數(shù);8避免采用復(fù)雜的條件語句;9盡量減少使用“否定”條件語句;10數(shù)據(jù)結(jié)構(gòu)要有利于程序的簡化;11要模塊化,使模塊功能盡可能單一化;12利用信息隱蔽,確保每一個模塊的獨立性;13從數(shù)據(jù)出發(fā)去構(gòu)造程序;14不要修補不好的程序,要重新編寫。(4輸入和輸出。1對輸入數(shù)據(jù)檢驗數(shù)據(jù)

22、的合法性;2檢查輸入項的各種重要組合的合法性;3輸入格式要簡單,使得輸入的步驟和操作盡可能簡單;4輸入數(shù)據(jù)時,應(yīng)允許使用自由格式;5應(yīng)允許缺省值;6輸入一批數(shù)據(jù)時,最好使用輸入結(jié)束標(biāo)志;7在以交互式輸入/輸出方式進行輸入時,要在屏幕上使用提示符明確提示輸入的請求,同時在數(shù)據(jù)輸入過程中和輸入結(jié)束時,應(yīng)在屏幕上給出狀態(tài)信息;8當(dāng)程序設(shè)計語言對輸入格式有嚴格要求時,應(yīng)保持輸入格式與輸入語句的一致性;給所有的輸出加注釋,并設(shè)計輸出報表格式。2.2 結(jié)構(gòu)化程序設(shè)計(面向過程的程序設(shè)計方法1、結(jié)構(gòu)化程序設(shè)計方法的主要原則可以概括為:自頂向下,逐步求精,模塊化,限制使用goto語句。(1自頂向下。程序設(shè)計時

23、,應(yīng)先考慮總體,后考慮細節(jié);先考慮全局目標(biāo),后考慮局部目標(biāo)。不要一開始就過多追求眾多的細節(jié),先從最上層總目標(biāo)開始設(shè)計,逐步使問題具體化。(2逐步求精。對復(fù)雜問題,應(yīng)設(shè)計一些子目標(biāo)作過渡,逐步細化。(3模塊化。一個復(fù)雜問題,肯定是由若干稍簡單的問題構(gòu)成。模塊化是把程序要解決的總目標(biāo)分解為分目標(biāo),再進一步分解為具體的小目標(biāo),把每個小目標(biāo)稱為一個模塊。(4限制使用goto語句。2、結(jié)構(gòu)化程序的基本結(jié)構(gòu):順序結(jié)構(gòu),選擇結(jié)構(gòu),重復(fù)結(jié)構(gòu)。1順序結(jié)構(gòu)。一種簡單的程序設(shè)計,即按照程序語句行的自然順序,一條語句一條語句地執(zhí)行程序,它是最基本、最常用的結(jié)構(gòu)。2選擇結(jié)構(gòu)。又稱分支結(jié)構(gòu),包括簡單選擇和多分支選擇結(jié)構(gòu),

24、可根據(jù)條件,判斷應(yīng)該選擇哪一條分支來執(zhí)行相應(yīng)的語句序列。3重復(fù)結(jié)構(gòu)。又稱循環(huán)結(jié)構(gòu),可根據(jù)給定的條件,判斷是否需要重復(fù)執(zhí)行某一相同的或類似的程序段。僅僅使用順序、選擇和循環(huán)三種基本控制結(jié)構(gòu)就足以表達各種其他形式結(jié)構(gòu),從而實現(xiàn)任何單入口/單出口的程序。2.3 面向?qū)ο蟮某绦蛟O(shè)計客觀世界中任何一個事物都可以被看成是一個對象,面向?qū)ο蠓椒ǖ谋举|(zhì)就是主張從客觀世界固有的事物出發(fā)來構(gòu)造系統(tǒng),提倡人們在現(xiàn)實生活中常用的思維來認識、理解和描述客觀事物,強調(diào)最終建立的系統(tǒng)能夠映射問題域。也就是說,系統(tǒng)中的對象及對象之間的關(guān)系能夠如實地反映問題域中固有的事物及其關(guān)系。面向?qū)ο蠓椒ǖ闹饕獌?yōu)點:(1與人類習(xí)慣的思維方

25、法一致;(2穩(wěn)定性好;(3可重用性好;(4易于開發(fā)大型軟件產(chǎn)品;(5可維護性好。*:面向?qū)ο蟮某绦蛟O(shè)計主要考慮的是提高軟件的可重用性。 的抽象。面向?qū)ο蟮某绦蛟O(shè)計方法中的對象是系統(tǒng)中用來描述客觀事物的一個實體,是構(gòu)成系統(tǒng)的一個基本單位,由一組表示其靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成。對象是屬操作描述了對象執(zhí)行的功能,操作也稱為方法或服務(wù)。操作是對象的動態(tài)屬性。*:一個對象由對象名、屬性和操作三部分組成。對象的基本特點:標(biāo)識惟一性,分類性,多態(tài)性,封裝性,模塊獨立性好。(1標(biāo)識惟一性。指對象是可區(qū)分的,并且由對象的內(nèi)在本質(zhì)來區(qū)分,而不是通過描述來區(qū)分。(2分類性。指可以將具有相同屬性的操作的

26、對象抽象成類。(3多態(tài)性。指同一個操作可以是不同對象的行為。(4封裝性。從外面看只能看到對象的外部特性,即只需知道數(shù)據(jù)的取值范圍和可以對該數(shù)據(jù)施加的操作,根本無需知道數(shù)據(jù)的具體結(jié)構(gòu)以及實現(xiàn)操作的算法。對象的內(nèi)部,即處理能力的實行和內(nèi)部狀態(tài),對外是不可見的。從外面不能直接使用對象的處理能力,也不能直接修改其內(nèi)部狀態(tài),對象的內(nèi)部狀態(tài)只能由其自身改變。*:信息隱蔽是通過對象的封裝性來實現(xiàn)的。(5模塊獨立性好。對象是面向?qū)ο蟮能浖幕灸K,它是由數(shù)據(jù)及可以對這些數(shù)據(jù)施加的操作所組成的統(tǒng)一體,而且對象是以數(shù)據(jù)為中心的,操作圍繞對其數(shù)據(jù)所需做的處理來設(shè)置,沒有無關(guān)的操作。從模塊的獨立性考慮,對象內(nèi)部各種

27、元素彼此結(jié)合得很緊密,內(nèi)聚性強。類是指具有共同屬性、共同方法的對象的集合。所以類是對象的抽象,對象是對應(yīng)類的一 (1接收消息的對象的名稱;(2消息標(biāo)識符,也稱消息名;(3零個或多個參數(shù)。*:在面向?qū)ο蠓椒ㄖ?一個對象請求另一個對象為其服務(wù)的方式是通過發(fā)送消息。 承。單繼承指一個類只允許有一個父類,多重繼承指一個類允許有多個父類。*:類的繼承性是類之間共享屬性和操作的機制,它提高了軟件的可重用性。 本章應(yīng)考點撥:本章在考試中會出現(xiàn)約1個題目,所占分值大約占2分,是出題量較小的一章。本章內(nèi)容比較少,也很簡單,掌握住基本的概念就可以輕松應(yīng)對考試了,所以在這部分丟分,比較可惜。第三章軟件工程基礎(chǔ)3.1

28、 軟件工程基本概念1、軟件的相關(guān)概念計算機軟件是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。軟件的特點包括:1軟件是一種邏輯實體,而不是物理實體,具有抽象性;2軟件的生產(chǎn)與硬件不同,它沒有明顯的制作過程;3軟件在運行、使用期間不存在磨損、老化問題;4軟件的開發(fā)、運行對計算機系統(tǒng)具有依賴性,受計算機系統(tǒng)的限制,這導(dǎo)致了軟件移植的問題;5軟件復(fù)雜性高,成本昂貴;6軟件開發(fā)涉及諸多的社會因素。2、軟件危機與軟件工程軟件工程源自軟件危機。所謂軟件危機是泛指在計算機軟件的開發(fā)和維護過程中所遇到的一系列嚴重問題。具體的說,在軟件開發(fā)和維護過程中,軟件危機主要表現(xiàn)在:1軟件需求的增長得不到滿足。用戶對系統(tǒng)不滿意的情

29、況經(jīng)常發(fā)生。2軟件開發(fā)成本和進度無法控制。開發(fā)成本超出預(yù)算,開發(fā)周期大大超過規(guī)定日期的情況經(jīng)常發(fā)生。3軟件質(zhì)量難以保證。4軟件不可維護或維護程度非常低。5軟件的成本不斷提高。6軟件開發(fā)生產(chǎn)率的提高跟不上硬件的發(fā)展和應(yīng)用需求的增長?？傊?可以將軟件危機可以歸結(jié)為成本、質(zhì)量、生產(chǎn)率等問題。 和工序。軟件工程的目的就是要建造一個優(yōu)良的軟件系統(tǒng),它所包含的內(nèi)容概括為以下兩點:1軟件開發(fā)技術(shù),主要有軟件開發(fā)方法學(xué)、軟件工具、軟件工程環(huán)境。2軟件工程管理,主要有軟件管理、軟件工程經(jīng)濟學(xué)。軟件工程的主要思想是將工程化原則運用到軟件開發(fā)過程,它包括3個要素:方法、工具和過程。方法是完成軟件工程項目的技術(shù)手段;

30、工具是支持軟件的開發(fā)、管理、文檔生成;過程支持軟件開發(fā)的各個環(huán)節(jié)的控制、管理。軟件工程過程是把輸入轉(zhuǎn)化為輸出的一組彼此相關(guān)的資源和活動。3、軟件生命周期 軟件生命周期分為軟件定義、軟件開發(fā)及軟件運行維護三個階段:1軟件定義階段:包括制定計劃和需求分析。制定計劃:確定總目標(biāo);可行性研究;探討解決方案;制定開發(fā)計劃。需求分析:對待開發(fā)軟件提出的需求進行分析并給出詳細的定義。2軟件開發(fā)階段:軟件設(shè)計:分為概要設(shè)計和詳細設(shè)計兩個部分。軟件實現(xiàn):把軟件設(shè)計轉(zhuǎn)換成計算機可以接受的程序代碼。軟件測試:在設(shè)計測試用例的基礎(chǔ)上檢驗軟件的各個組成部分。3軟件運行維護階段:軟件投入運行,并在使用中不斷地維護,進行必

31、要的擴充和刪改。*:軟件生命周期中所花費最多的階段是軟件運行維護階段。4、軟件工程的目標(biāo)和與原則(1軟件工程目標(biāo):在給定成本、進度的前提下,開發(fā)出具有有效性、可靠性、可理解性、可維護性、可重用性、可適應(yīng)性、可移植性、可追蹤性和可互操作性且滿足用戶需求的產(chǎn)品。(2軟件工程需要達到的基本目標(biāo)應(yīng)是:付出較低的開發(fā)成本;達到要求的軟件功能;取得較好的軟件性能;開發(fā)的軟件易于移植;需要較低的維護費用;能按時完成開發(fā),及時交付使用。(3軟件工程原則:抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗證性。 逐層細化的辦法控制軟件開發(fā)過程的復(fù)雜性。 23模塊的大小要適中,模塊過大會使模塊內(nèi)部的復(fù)雜

32、性增加,不利于模塊的理解和修改,也不利于模塊的調(diào)試和重用;模塊太小會導(dǎo)致整個系統(tǒng)表示過于復(fù)雜,不利于控制系統(tǒng)的復(fù)雜性。 456785、軟件開發(fā)工具與軟件開發(fā)環(huán)境(1軟件開發(fā)工具軟件開發(fā)工具的完善和發(fā)展將促使軟件開發(fā)方法的進步和完善,促進軟件開發(fā)的高速度和高質(zhì)量。軟件開發(fā)工具的發(fā)展是從單項工具的開發(fā)逐步向集成工具發(fā)展的,軟件開發(fā)工具為軟件工程方法提供了自動的或半自動的軟件支撐環(huán)境。同時,軟件開發(fā)方法的有效應(yīng)用也必須得到相應(yīng)工具的支持,否則方法將難以有效的實施。(2軟件開發(fā)環(huán)境軟件開發(fā)環(huán)境(或稱軟件工程環(huán)境是全面支持軟件開發(fā)全過程的軟件工具集合。 CASE,Computer Aided Softw

33、are Engineering將各種軟件工具、開發(fā)機器和一個存放開發(fā)過程信息的中心數(shù)據(jù)庫組合起來,形成軟件工程環(huán)境。它將極大降低軟件開發(fā)的技術(shù)難度并保證軟件開發(fā)的質(zhì)量。3.2 結(jié)構(gòu)化分析方法結(jié)構(gòu)化方法的核心和基礎(chǔ)是結(jié)構(gòu)化程序設(shè)計理論。1、需求分析需求分析方法有:1結(jié)構(gòu)化需求分析方法;2面向?qū)ο蟮姆治龇椒ā?*:需求分析一般分為需求獲取、需求分析、編寫需求規(guī)格說明書和需求評審四個步驟進行。2、結(jié)構(gòu)化分析方法結(jié)構(gòu)化分析方法是結(jié)構(gòu)化程序設(shè)計理論在軟件需求分析階段的應(yīng)用。結(jié)構(gòu)化分析方法的實質(zhì):著眼于數(shù)據(jù)流,自頂向下,逐層分解,建立系統(tǒng)的處理流程,以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具,建立系統(tǒng)的邏輯模型。結(jié)構(gòu)

34、化分析的常用工具:1數(shù)據(jù)流圖(DFD ;2數(shù)據(jù)字典(DD ;3判定樹;4判定表。輯功能,是結(jié)構(gòu)化分析方法中用于表示系統(tǒng)邏輯模型的一種工具。 上圖是數(shù)據(jù)流圖的基本圖形元素:輸入數(shù)據(jù)經(jīng)加工變換產(chǎn)生輸出。 :表示處理過程中存放各種數(shù)據(jù)的文件。畫數(shù)據(jù)流圖的基本步驟:自外向內(nèi),自頂向下,逐層細化,完善求精。 下圖是一個數(shù)據(jù)流圖的示例: 使得用戶和系統(tǒng)分析員對于輸入、輸出、存儲成分和中間計算結(jié)果有共同的理解。 *:數(shù)據(jù)字典的作用是對數(shù)據(jù)流圖中出現(xiàn)的被命名的圖形元素的確切解釋。*:數(shù)據(jù)字典是結(jié)構(gòu)化分析方法的核心。3、軟件需求規(guī)格說明書(SRS 和行為描述、性能需求和設(shè)計約束的說明、合適的驗收標(biāo)準(zhǔn),給出對目標(biāo)

35、軟件的各種需求。 3.3 結(jié)構(gòu)化設(shè)計方法1、軟件設(shè)計的基礎(chǔ)*:需求分析主要解決“做什么”的問題,而軟件設(shè)計主要解決“怎么做”的問題。從技術(shù)觀點來看,軟件設(shè)計包括軟件結(jié)構(gòu)設(shè)計、數(shù)據(jù)設(shè)計、接口設(shè)計、過程設(shè)計。 從工程角度來看,軟件設(shè)計分兩步完成,即概要設(shè)計和詳細設(shè)計。結(jié)構(gòu)或數(shù)據(jù)庫模式。加工數(shù)據(jù)流存儲文件源、潭 細節(jié)。 軟件設(shè)計的基本原理包括:抽象、模塊化、信息隱蔽和模塊獨立性。1抽象。抽象是一種思維工具,就是把事物本質(zhì)的共同特性提取出來而不考慮其他細節(jié)。2模塊化。解決一個復(fù)雜問題時自頂向下逐步把軟件系統(tǒng)劃分成一個個較小的、相對獨立但又不相互關(guān)聯(lián)的模塊的過程。3信息隱蔽。每個模塊的實施細節(jié)對于其他模

36、塊來說是隱蔽的。4模塊獨立性。軟件系統(tǒng)中每個模塊只涉及軟件要求的具體的子功能,而和軟件系統(tǒng)中其他的模塊的接口是簡單的。*:模塊分解的主要指導(dǎo)思想是信息隱蔽和模塊獨立性。 模塊的耦合性和內(nèi)聚性是衡量軟件的模塊獨立性的兩個定性指標(biāo)。 *:按內(nèi)聚性由弱到強排列,內(nèi)聚可以分為以下幾種:偶然內(nèi)聚、邏輯內(nèi)聚、時間內(nèi)聚、過程內(nèi)聚、通信內(nèi)聚、順序內(nèi)聚及功能內(nèi)聚。 *:按耦合性由高到低排列,耦合可以分為以下幾種:內(nèi)容耦合、公共耦合、外部耦合、控制耦合、標(biāo)記耦合、數(shù)據(jù)耦合以及非直接耦合。一個設(shè)計良好的軟件系統(tǒng)應(yīng)具有高內(nèi)聚、低耦合的特征。在結(jié)構(gòu)化程序設(shè)計中,模塊劃分的原則是:模塊內(nèi)具有高內(nèi)聚度,模塊間具有低耦合度。

37、2、總體設(shè)計(概要設(shè)計和詳細設(shè)計(1總體設(shè)計(概要設(shè)計軟件概要設(shè)計的基本任務(wù)是:1設(shè)計軟件系統(tǒng)結(jié)構(gòu);2數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫設(shè)計;3編寫概要設(shè)計文檔;4概要設(shè)計文檔評審。常用的軟件結(jié)構(gòu)設(shè)計工具是結(jié)構(gòu)圖,也稱程序結(jié)構(gòu)圖。程序結(jié)構(gòu)圖的基本圖符:模塊用一個矩形表示,箭頭表示模塊間的調(diào)用關(guān)系。在結(jié)構(gòu)圖中還可以用帶注釋的箭頭表示模塊調(diào)用過程中來回傳遞的信息。還可用帶實心圓的箭頭表示傳遞的是控制信息,空心圓箭心表示傳遞的是數(shù)據(jù)信息。 經(jīng)常使用的結(jié)構(gòu)圖有四種模塊類型:傳入模塊、傳出模塊、變換模塊和協(xié)調(diào)模塊。其表示形式如下圖: 它們的含義分別是: 程序結(jié)構(gòu)圖的例圖及有關(guān)術(shù)語列舉如下:一般模塊數(shù)據(jù)信息控制信息 上級模

38、塊、從屬模塊:上、下兩層模塊a和b,且有a調(diào)用b,則a是上級模塊,b是從屬模塊。 原子模塊:樹中位于葉子結(jié)點的模塊。面向數(shù)據(jù)流的設(shè)計方法定義了一些不同的映射方法,利用這些方法可以把數(shù)據(jù)流圖變換成結(jié)構(gòu)圖表示軟件的結(jié)構(gòu)。數(shù)據(jù)流的類型:大體可以分為兩種類型,變換型和事務(wù)型。A、變換型:變換型數(shù)據(jù)處理問題的工作過程大致分為三步,即取得數(shù)據(jù)、變換數(shù)據(jù)和輸出數(shù)據(jù)。變換型系統(tǒng)結(jié)構(gòu)圖由輸入、中心變換、輸出三部分組成。B、事務(wù)型:事務(wù)型數(shù)據(jù)處理問題的工作機理是接受一項事務(wù),根據(jù)事務(wù)處理的特點和性質(zhì),選擇分派一個適當(dāng)?shù)奶幚韱卧?然后給出結(jié)果。(2詳細設(shè)計詳細設(shè)計是為軟件結(jié)構(gòu)圖中的每一個模塊確定實現(xiàn)算法和局部數(shù)據(jù)結(jié)

39、構(gòu),用某種選定的表達工具表示算法和數(shù)據(jù)結(jié)構(gòu)的細節(jié)。*:詳細設(shè)計的任務(wù)是確定實現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu),不同于編碼或編程。常用的過程設(shè)計(即詳細設(shè)計工具有以下幾種:圖形工具:程序流程圖、N-S(方盒圖、PAD(問題分析圖和HIPO(層次圖+輸入/處理/輸出圖。表格工具:判定表。語言工具:PDL(偽碼3.4 軟件測試1、軟件測試定義:使用人工或自動手段來運行或測定某個系統(tǒng)的過程,其目的在于檢驗它是否滿足規(guī)定的需求或是弄清預(yù)期結(jié)果與實際結(jié)果之間的差別。*:軟件測試的目的:盡可能地多發(fā)現(xiàn)程序中的錯誤,不能也不可能證明程序沒有錯誤。軟件測試的關(guān)鍵是設(shè)計測試用例,一個好的測試用例能找到迄今為止尚未發(fā)現(xiàn)的錯誤。

40、2、軟件測試方法:靜態(tài)測試和動態(tài)測試。 工進行。動態(tài)測試:是基于計算機的測試,主要包括白盒測試方法和黑盒測試方法。(1白盒測試白盒測試方法也稱為結(jié)構(gòu)測試或邏輯驅(qū)動測試。它是根據(jù)軟件產(chǎn)品的內(nèi)部工作過程,檢查內(nèi)部成分,以確認每種內(nèi)部操作符合設(shè)計規(guī)格要求。白盒測試的基本原則:保證所測模塊中每一獨立路徑至少執(zhí)行一次;保證所測模塊所有判斷的每一分支至少執(zhí)行一次;保證所測模塊每一循環(huán)都在邊界條件和一般條件下至少各執(zhí)行一次;驗證所有內(nèi)部數(shù)據(jù)結(jié)構(gòu)的有效性。*:白盒測試法的測試用例是根據(jù)程序的內(nèi)部邏輯來設(shè)計的,主要用軟件的單元測試,主要方法有邏輯覆蓋、基本路徑測試等。A、邏輯覆蓋。邏輯覆蓋泛指一系列以程序內(nèi)部的

41、邏輯結(jié)構(gòu)為基礎(chǔ)的測試用例設(shè)計技術(shù)。通常程序中的邏輯表示有判斷、分支、條件等幾種表示方法。語句覆蓋:選擇足夠的測試用例,使得程序中每一個語句至少都能被執(zhí)行一次。路徑覆蓋:執(zhí)行足夠的測試用例,使程序中所有的可能的路徑都至少經(jīng)歷一次。判定覆蓋:使設(shè)計的測試用例保證程序中每個判斷的每個取值分支(T或F至少經(jīng)歷一次。條件覆蓋:設(shè)計的測試用例保證程序中每個判斷的每個條件的可能取值至少執(zhí)行一次。判斷-條件覆蓋:設(shè)計足夠的測試用例,使判斷中每個條件的所有可能取值至少執(zhí)行一次,同時每個判斷的所有可能取值分支至少執(zhí)行一次。*:邏輯覆蓋的強度依次是:語句覆蓋<路徑覆蓋<判定覆蓋<條件覆蓋<判

42、斷-條件覆蓋。B、基本路徑測試。其思想和步驟是,根據(jù)軟件過程性描述中的控制流程確定程序的環(huán)路復(fù)雜性度量,用此度量定義基本路徑集合,并由此導(dǎo)出一組測試用例,對每一條獨立執(zhí)行路徑進行測試。(2黑盒測試黑盒測試方法也稱為功能測試或數(shù)據(jù)驅(qū)動測試。黑盒測試是對軟件已經(jīng)實現(xiàn)的功能是否滿足需求進行測試和驗證。黑盒測試主要診斷功能不對或遺漏、接口錯誤、數(shù)據(jù)結(jié)構(gòu)或外部數(shù)據(jù)庫訪問錯誤、性能錯誤、初始化和終止條件錯誤。黑盒測試不關(guān)心程序內(nèi)部的邏輯,只是根據(jù)程序的功能說明來設(shè)計測試用例,主要方法有等價類劃分法、邊界值分析法、錯誤推測法等,主要用軟件的確認測試。成若干部分(及若干等價類,然后從每個等價類中選取數(shù)據(jù)作為測

43、試用例。 BC編寫檢查這些錯誤的用例。3、軟件測試過程一般按4個步驟進行:單元測試、集成測試、確認測試和系統(tǒng)測試。(1單元測試 發(fā)現(xiàn)各模塊內(nèi)部可能存在的各種錯誤。單元測試根據(jù)程序的內(nèi)部結(jié)構(gòu)來設(shè)計測試用例,其依據(jù)是詳細設(shè)計說明書和源程序。單元測試的技術(shù)可以采用靜態(tài)分析和動態(tài)測試。對動態(tài)測試通常以白盒測試為主,輔之以黑盒測試。單元測試的內(nèi)容包括:模塊接口測試、局部數(shù)據(jù)結(jié)構(gòu)測試、錯誤處理測試和邊界測試。*:在進行單元測試時,要用一些輔助模塊去模擬與被測模塊相聯(lián)系的其他模塊,即為被測 子模塊的所有功能帶入。(2集成測試 主要目的是發(fā)現(xiàn)與接口有關(guān)的錯誤。集成測試的依據(jù)是概要設(shè)計說明書。集成測試所涉及的內(nèi)

44、容包括:軟件單元的接口測試、全局數(shù)據(jù)結(jié)構(gòu)測試、邊界條件和非法輸入的測試等。集成測試通常采用兩種方式:非增量方式組裝與增量方式組裝。 所有模塊組裝在一起進行測試,最終得到要求的軟件系統(tǒng)。 逐步組裝成較大的系統(tǒng),在組裝的過程中邊連接邊測試,以發(fā)現(xiàn)連接過程中產(chǎn)生的問題。最后通過增殖逐步組裝成要求的軟件系統(tǒng)。增量方式組裝又包括自頂向下、自底向上、自頂向下與自底向上相結(jié)合等三種方式。(3確認測試確認測試的任務(wù)是驗證軟件的有效性,即驗證軟件的功能和性能及其他特性是否與用戶的要求一致。確認測試的主要依據(jù)是軟件需求規(guī)格說明書。確認測試主要運用黑盒測試法。(4系統(tǒng)測試 矛盾的地方。系統(tǒng)測試的測試用例應(yīng)根據(jù)需求分

45、析規(guī)格說明來設(shè)計,并在實際使用環(huán)境下來運行。系統(tǒng)測試的具體實施一般包括:功能測試、性能測試、操作測試、配置測試、外部接口測試、安全性測試等。3.5 程序的調(diào)試程序調(diào)試的任務(wù)是診斷和改正程序中的錯誤,主要在開發(fā)階段進行,調(diào)試程序應(yīng)該由編制源程序的程序員來完成。程序調(diào)試的基本步驟:(1錯誤定位;(2糾正錯誤;(3回歸測試。*:軟件的調(diào)試后要進行回歸測試,防止引進新的錯誤。軟件調(diào)試可分為靜態(tài)調(diào)試和動態(tài)調(diào)試。靜態(tài)調(diào)試主要是指通過人的思維來分析源程序代碼和排錯,是主要的調(diào)試手段,而動態(tài)調(diào)試是輔助靜態(tài)調(diào)試。對軟件主要的調(diào)試方法可以采用:(1強行排錯法。主要方法有:通過內(nèi)存全部打印來排錯;在程序特定部位設(shè)置

46、打印語句;自動調(diào)試工具。(2回溯法。發(fā)現(xiàn)了錯誤,分析錯誤征兆,確定發(fā)現(xiàn)“癥狀”的位置。一般用于小程序。(3原因排除法。是通過演繹、歸納和二分法來實現(xiàn)的。1演繹法。根據(jù)已有的測試用例,設(shè)想及枚舉出所有可能出錯的原因作為假設(shè);然后再用原始測試數(shù)據(jù)或新的測試,從中逐個排除不可能正確的假設(shè);最后,再用測試數(shù)據(jù)驗證余下的假設(shè)確定出錯的原因。2歸納法。從錯誤征兆著手,通過分析它們之間的關(guān)系來找出錯誤。大致分四步:收集有關(guān)的數(shù)據(jù);組織數(shù)據(jù);提出假設(shè);證明假設(shè)。3二分法。在程序的關(guān)鍵點給變量賦正確值,然后運行程序并檢查程序的輸出。如果輸出結(jié)果正確,則錯誤原因在程序的前半部分;反之,錯誤原因在程序的后半部分。本

47、章應(yīng)考點撥:本章在筆試中一般占8分左右,約3道選擇題,1道填空題,是公共基礎(chǔ)部分比較重要的一章。從出題的深度來看,本章主要考察對基本概念的識記,有少量對基本原理的理解,沒有實際運用,因此考生在復(fù)習(xí)本章時,重點應(yīng)放在基本概念的記憶和基本原理的理解上。第四章數(shù)據(jù)庫設(shè)計基礎(chǔ)4.1 數(shù)據(jù)庫系統(tǒng)的基本概念1、數(shù)據(jù)、數(shù)據(jù)庫、數(shù)據(jù)管理系統(tǒng)(1數(shù)據(jù):實際上就是描述事物的符號記錄。數(shù)據(jù)的特點:有一定的結(jié)構(gòu),有型與值之分。數(shù)據(jù)的型給出了數(shù)據(jù)表示的類型,如整型、實型、字符型等。而數(shù)據(jù)的值給出了符合給定型的值,如整型(INT值15。 (2多種應(yīng)用數(shù)據(jù)的集成,并可被各個應(yīng)用程序所共享。數(shù)據(jù)庫存放數(shù)據(jù)是按數(shù)據(jù)所提供的數(shù)據(jù)

48、模式存放的,具有集成與共享的特點,亦即是數(shù)據(jù)庫集中了各種應(yīng)用的數(shù)據(jù),進行統(tǒng)一的構(gòu)造和存儲,而使它們可被不同應(yīng)用程序所使用。 (3據(jù)維護、控制及保護和數(shù)據(jù)服務(wù)等,是數(shù)據(jù)庫的核心。數(shù)據(jù)庫管理系統(tǒng)功能:1數(shù)據(jù)模式定義。數(shù)據(jù)庫管理系統(tǒng)負責(zé)為數(shù)據(jù)庫構(gòu)建模式,也就是為數(shù)據(jù)庫構(gòu)建其數(shù)據(jù)框架。2數(shù)據(jù)存取的物理構(gòu)建。數(shù)據(jù)庫管理系統(tǒng)負責(zé)為數(shù)據(jù)模式的物理存取與構(gòu)建提供有效的存取方法與手段。3數(shù)據(jù)操縱。數(shù)據(jù)庫管理系統(tǒng)為用戶使用數(shù)據(jù)庫中的數(shù)據(jù)提供方便,它一般提供如查詢、插入、修改以及刪除數(shù)據(jù)的功能。此外,它自身還具有做簡單的算術(shù)運算及統(tǒng)計的能力,而且還可以與某些過程性語言結(jié)合,使其具有強大的過程性操作能力。4數(shù)據(jù)的完整

49、性、安生性定義與檢查。數(shù)據(jù)庫中的數(shù)據(jù)具有內(nèi)在語義上的關(guān)聯(lián)性與一致性,它們構(gòu)成了數(shù)據(jù)的完整性,數(shù)據(jù)的完整性是保證數(shù)據(jù)庫中數(shù)據(jù)正確的必要條件,因此必須經(jīng)常檢查以維護數(shù)據(jù)正確。數(shù)據(jù)庫中的數(shù)據(jù)具有共享性,而數(shù)據(jù)共享可能會引發(fā)數(shù)據(jù)的非法使用,因此必須要對數(shù)據(jù)正確使用做出必要的規(guī)定,并在使用時做檢查,這就是數(shù)據(jù)的安全性。數(shù)據(jù)完整性與安全性的維護是數(shù)據(jù)庫系統(tǒng)的基本功能。5數(shù)據(jù)庫的并發(fā)控制與故障恢復(fù)。數(shù)據(jù)庫是一個集成、共享的數(shù)據(jù)集合體,它能為多個應(yīng)用程序服務(wù),所以就存在著多個應(yīng)用程序?qū)?shù)據(jù)庫的并發(fā)操作。在并發(fā)操作中如果不加控制和管理,多個應(yīng)用程序間就會相互干擾,從而對數(shù)據(jù)庫中的數(shù)據(jù)造成破壞。因此,數(shù)據(jù)庫管理系

50、統(tǒng)必須對多個應(yīng)用程序的并發(fā)操作做必要的控制以保證數(shù)據(jù)不受破壞,這就是數(shù)據(jù)庫的并發(fā)控制。數(shù)據(jù)庫中的數(shù)據(jù)一旦遭到破壞,數(shù)據(jù)庫管理系統(tǒng)必須有能力及時進行恢復(fù),這就是數(shù)據(jù)庫的故障恢復(fù)。6數(shù)據(jù)的服務(wù)。數(shù)據(jù)庫管理系統(tǒng)提供對數(shù)據(jù)庫中數(shù)據(jù)的多種服務(wù)功能,如數(shù)據(jù)拷貝、轉(zhuǎn)存、重組、性能監(jiān)測、分析等。(4(5:由數(shù)據(jù)庫(數(shù)據(jù)、數(shù)據(jù)庫管理系統(tǒng)(軟件、數(shù)據(jù)庫管理員(人員、硬件平臺(硬件、軟件平臺(軟件五個部分構(gòu)成的運行實體。(6數(shù)據(jù)庫應(yīng)用系統(tǒng):由數(shù)據(jù)庫系統(tǒng)、應(yīng)用軟件及應(yīng)用界面三者組成。*:數(shù)據(jù)庫技術(shù)的根本目標(biāo)是解決數(shù)據(jù)的共享問題。2、數(shù)據(jù)庫系統(tǒng)的發(fā)展數(shù)據(jù)庫管理發(fā)展至今已經(jīng)歷了三個階段:人工管理階段、文件系統(tǒng)階段和數(shù)據(jù)庫

51、系統(tǒng)階段。下表是數(shù)據(jù)管理三個階段的比較: 3、數(shù)據(jù)庫系統(tǒng)的基本特點(1數(shù)據(jù)的高集成性。(2數(shù)據(jù)的高共享性與低冗余性。*:數(shù)據(jù)庫系統(tǒng)可以減少數(shù)據(jù)冗余,但無法避免一切冗余。(3數(shù)據(jù)獨立性:數(shù)據(jù)獨立性是數(shù)據(jù)與程序間的互不依賴性,即數(shù)據(jù)庫中數(shù)據(jù)獨立于應(yīng)用程序而不依賴于應(yīng)用程序。也就是說,數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)與存取方式的改變不會影響應(yīng)用程序。數(shù)據(jù)獨立性一般分為物理獨立性與邏輯獨立性兩級。 1如存儲設(shè)備的更換、物理存儲的更換、存取方式改變等都不影響數(shù)據(jù)庫的邏輯結(jié)構(gòu),從而不致引起應(yīng)用程序的變化。2數(shù)據(jù)間聯(lián)系等,不需要相應(yīng)修改應(yīng)用程序,這就是數(shù)據(jù)的邏輯獨立性。 (4數(shù)據(jù)統(tǒng)一管理與控制。數(shù)據(jù)統(tǒng)一管理與控制主

52、要包含以下三個方面:1數(shù)據(jù)的完整性檢查:檢查數(shù)據(jù)庫中數(shù)據(jù)的正確性以保證數(shù)據(jù)的正確。2數(shù)據(jù)的安全性保護:檢查數(shù)據(jù)庫訪問者以防止非法訪問。3并發(fā)控制:控制多個應(yīng)用的并發(fā)訪問所產(chǎn)生的相互干擾以保證其正確性。4、數(shù)據(jù)庫系統(tǒng)的內(nèi)部結(jié)構(gòu)體系(1數(shù)據(jù)庫系統(tǒng)的三級模式:1 它由概念模式推導(dǎo)而出。 3性主要體現(xiàn)在操作系統(tǒng)及文件級上,它還未深入到設(shè)備級上(如磁盤及磁盤操作。內(nèi)模式對一般用戶是透明的,但它的設(shè)計直接影響數(shù)據(jù)庫的性能。(2數(shù)據(jù)庫系統(tǒng)的兩級映射: 1結(jié)構(gòu)發(fā)生變化時,通過修改相應(yīng)的概念模式/內(nèi)模式的映射,使得數(shù)據(jù)庫的邏輯模式不變,其外模式不變,應(yīng)用程序不用修改,從而保證數(shù)據(jù)具有很高的物理獨立性。 2變化時

53、,通過修改相應(yīng)的外模式/邏輯模式映射,使得用戶所使用的那部分外模式不變,從而應(yīng)用程序不必修改,保證數(shù)據(jù)具有較高的邏輯獨立性。4.2 數(shù)據(jù)模型1、數(shù)據(jù)模型(1數(shù)據(jù)模型的概念:是數(shù)據(jù)特征的抽象,它從抽象層次上描述了系統(tǒng)的靜態(tài)特征、動態(tài)行為和約束條件,為數(shù)據(jù)庫系統(tǒng)的信息表示與操作提供一個抽象的框架。(2數(shù)據(jù)模型所描述的內(nèi)容有三個部分,它們是數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操作與數(shù)據(jù)約束。1數(shù)據(jù)結(jié)構(gòu):數(shù)據(jù)結(jié)構(gòu)是所研究的對象類型的集合,包括與數(shù)據(jù)類型、內(nèi)容、性質(zhì)有關(guān)的對象,以及與數(shù)據(jù)之間聯(lián)系有關(guān)的對象。它用于描述系統(tǒng)的靜態(tài)特性。2數(shù)據(jù)操作:數(shù)據(jù)操作是對數(shù)據(jù)庫中各種對象(型的實例(值允許執(zhí)行的操作的集合,包括操作的含義、符

54、號、操作規(guī)則及實現(xiàn)操作的語句等。它用于描述系統(tǒng)的動態(tài)特性。3數(shù)據(jù)的約束條件:數(shù)據(jù)的約束條件是一組完整性規(guī)則的集合。完整性規(guī)則是給定的數(shù)據(jù)模型中數(shù)據(jù)及其聯(lián)系所具有的制約和依存規(guī)則,用以限定符號數(shù)據(jù)模型的數(shù)據(jù)庫狀態(tài)及狀態(tài)的變化,以保證數(shù)據(jù)的正確、有效和相容。(3數(shù)據(jù)模型分為概念模型、邏輯數(shù)據(jù)模型和物理模型三類:1概念數(shù)據(jù)模型:簡稱概念模型,是對客觀世界復(fù)雜事物的結(jié)構(gòu)描述及它們之間的內(nèi)在聯(lián)系的刻畫。概念模型主要有:E-R模型(實體聯(lián)系模型、擴充的E-R模型、面向?qū)ο竽Ｐ图爸^詞模型等。2邏輯數(shù)據(jù)模型:又稱數(shù)據(jù)模型,是一種面向數(shù)據(jù)庫系統(tǒng)的模型,該模型著重于在數(shù)據(jù)庫系統(tǒng)一級的實現(xiàn)。邏輯數(shù)據(jù)模型主要有:層次

55、模型、網(wǎng)狀模型、關(guān)系模型、面向?qū)ο竽Ｐ偷取?物理數(shù)據(jù)模型:又稱物理模型,它是一種面向計算機物理表示的模型,此模型給出了數(shù)據(jù)模型在計算機上物理結(jié)構(gòu)的表示。2、實體聯(lián)系模型及E-R圖(1E-R模型的基本概念:1實體:現(xiàn)實世界中的事物。2屬性:事物的特性。3聯(lián)系:現(xiàn)實世界中事物間的關(guān)系。實體集的關(guān)系有一對一、一對多、多對多的聯(lián)系。E-R模型三個基本概念之間的聯(lián)接關(guān)系:1實體集(聯(lián)系與屬性間的聯(lián)接關(guān)系;2實體(集與聯(lián)系。*:E-R模型的基本成分是實體和聯(lián)系。(2E-R模型的圖示法:1實體集:用矩形表示。20 帶格式的: 字體: 五號 格式的 全國計算機等級考試二級公共基礎(chǔ)知識輔導(dǎo)講義 全國計算機等級考

56、試二級公共基礎(chǔ)知識輔導(dǎo)講義 帶格式的: 右側(cè): 格式的 0.63 厘米 2）屬性：用橢圓形表示。 3）聯(lián)系：用菱形表示。 4）實體集與屬性間的聯(lián)接關(guān)系：用無向線段表示。 5）實體集與聯(lián)系間的聯(lián)接關(guān)系：用無向線段表示。 學(xué)生 M 選課 N 課程 學(xué)號 姓名 性別 出生年月 系 課號 課程名 學(xué)分 成績 選修時間 （3）數(shù)據(jù)庫管理系統(tǒng)常見的數(shù)據(jù)模型有層次模型、網(wǎng)狀模型和關(guān)系模型三種。 1）層次模型的基本結(jié)構(gòu)是樹形結(jié)構(gòu)，具有以下特點：A、每棵樹有且僅有一個無雙親結(jié)點， 稱為根；B、樹中除根外所有結(jié)點有且僅有一個雙親。 部門 管理 銷售 員工 商品 2）網(wǎng)狀模型是層次模型的一個特例，從圖論上看，網(wǎng)狀模

57、型是一個不加任何條件限制的無 向圖。 學(xué)校 工人 領(lǐng)導(dǎo) 領(lǐng)導(dǎo) 使用 教師 班組 維護 教學(xué) 管理 設(shè)備 學(xué)生 (a教學(xué)關(guān)系E-R圖 (b工作與設(shè)備 3）關(guān)系模型采用二維表來表示，簡稱表，由表框架及表的元組組成。一個二維表就是一個 關(guān)系。 20 21 帶格式的: 字體: 五號 格式的 全國計算機等級考試二級公共基礎(chǔ)知識輔導(dǎo)講義 全國計算機等級考試二級公共基礎(chǔ)知識輔導(dǎo)講義 帶格式的: 右側(cè): 格式的 0.63 厘米 二維表的表框架由 n 個命名的屬性組成，n 稱為屬性元數(shù)。每個屬性有一個取值范圍稱為值 域。表框架對應(yīng)了關(guān)系的模式，即類型的概念。在表框架中按行可以存放數(shù)據(jù)，每行數(shù)據(jù)稱 為元組，實際上，一個元組是由 n 個元組分量所組成，每