全國計算機(jī)等級考試公共基礎(chǔ)知識

1、1 第一章數(shù)據(jù)結(jié)構(gòu)與算法 1.1 算法 算法：是指解題方案的準(zhǔn)確而完整的描述。 算法不等于程序，也不等計算機(jī)方法，程序的編 制不可能優(yōu)于算法的設(shè)計。 算法的基本特征：是一組嚴(yán)謹(jǐn)?shù)囟x運算順序的 規(guī)則，每一個規(guī)則都是有效的，是明確的，此順 序?qū)⒃谟邢薜拇螖?shù)下終止。 2 特征包括： （1）可行性；針對實際實際問題設(shè)計的算法， 人們總希望得到滿意的結(jié)果。 （2）確定性，算法中每一步驟都必須有明確 定義，不充許有模棱兩可的解釋，不允許有多 義性； （3）有窮性，算法必須能在有限的時間內(nèi)做 完，即能在執(zhí)行有限個步驟后終止，包括合理 的執(zhí)行時間的含義； （4）擁有足夠的情報。 綜上所述，所謂算法，是一組嚴(yán)

2、謹(jǐn)?shù)囟x運算順 序的規(guī)則，并且每一個規(guī)則都是有效的，且是 明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。 3 算法的基本要素：一是對數(shù)據(jù)對象的運算和操作； 二是算法的控制結(jié)構(gòu)。 指令系統(tǒng)：一個計算機(jī)系統(tǒng)能執(zhí)行的所有指令的集 合。 基本運算和操作包括：算術(shù)運算、邏輯運算、關(guān)系 運算、數(shù)據(jù)傳輸。 算法的控制結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)。 算法基本設(shè)計方法：列舉法、歸納法、遞推、遞歸、 減斗遞推技術(shù)、回溯法。 算法復(fù)雜度：算法時間復(fù)雜度和算法空間復(fù)雜度。 算法時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量。 算法空間復(fù)雜度是指執(zhí)行這個算法所需要的內(nèi)存空 間。 4 1.2 數(shù)據(jù)結(jié)構(gòu)的基本基本概念 數(shù)據(jù)結(jié)構(gòu)研究的

3、三個方面： （1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān) 系，即數(shù)據(jù)的邏輯結(jié)構(gòu)； （2）在對數(shù)據(jù)進(jìn)行處理時，各數(shù)據(jù)元素在計算機(jī) 中的存儲關(guān)系，即數(shù)據(jù)的存儲構(gòu)； （3）對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運算。 數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。 5 數(shù)據(jù)的邏輯結(jié)構(gòu)包含： （1）表示數(shù)據(jù)元素的信息； （2）表示各數(shù)據(jù)元素之間的前后件關(guān)系。 數(shù)據(jù)的存儲結(jié)構(gòu)有順序、鏈接、索引等。 線性結(jié)構(gòu)條件： （1）有且只有一個根結(jié)點； （2）每一個結(jié)點最多有一個前件，也最多 有一個后件。 非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù) 結(jié)構(gòu)。 6 13 線性表及其順序存儲結(jié)構(gòu) 線性表由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位 置只取決于自己

4、的序號，元素之間的 相對位置是線性的。 在復(fù)雜線性表中，由若干項數(shù)據(jù)元素組成的 數(shù)據(jù)元素稱為記錄，而由多個記錄構(gòu) 成的線性表又稱為文件。 7 非空線性表的結(jié)構(gòu)特征： （1）且只有一個根結(jié)點a1，它無前件. （2）有且只有一個終端結(jié)點an，它無后件； （3）除根結(jié)點與終端結(jié)點外，其他所有結(jié) 點有且只有一個前件，也有且只有一個 后件。結(jié)點個數(shù)n稱為線性表的長度，當(dāng) n=0時，稱為空表。 8 線性表的順序存儲結(jié)構(gòu)具有以下兩個基本 特點： （1）線性表中所有元素的所占的存儲空 間是連續(xù)的； （2）線性表中各數(shù)據(jù)元素在存儲空間中 是按邏輯順序依次存放的。 ai的存儲地址為：ADR(ai)=ADR(a1)

5、+(i- 1)k,，ADR(a1)為第一個元素的地址，k 代表每個元素占的字節(jié)數(shù)。 順序表的運算：插入、刪除。 （詳見14- -16頁） 9 14 棧和隊列 棧是限定在一端進(jìn)行插入與刪除的線性表，允許 插入與刪除的一端稱為棧頂，不允許插入與刪 除的另一端稱為棧底。 棧按照“先進(jìn)后出”（FILO）或“后進(jìn)先出” （LIFO）組織數(shù)據(jù)，棧具有記憶作用。用top 表示棧頂位置，用bottom表示棧底。 棧的基本運算：（1）插入元素稱為入棧運算； （2）刪除元素稱為退棧運算；（3）讀棧頂元 素是將棧頂元素賦給一個指定的變量，此時指 針無變化。 10 有關(guān)棧的幾個例子: 1: 下列關(guān)于棧的敘述中正確的是

6、_。 A. 在棧中只能插入數(shù)據(jù) B. 在棧中只能刪除數(shù)據(jù) C. 棧是先進(jìn)先出的線性表 D. 棧是先進(jìn)后出的線性表 2: 棧底至棧頂依次存放元素A、B、C、D，在第五個元素E入棧前，棧中元素可以出 棧，則出棧序列可能是_。 A. ABCED B. DBCEA C. CDABE D. DCBEA 3:如果進(jìn)棧序列為e1,e2,e3,e4，則可能的出棧序列是 A）e3,e1,e4,e2 B）e2,e4,e3,e1 C）e3,e4,e1,e2 D）任意順序 4: 棧的基本運算有三種：入棧、退棧和_。 答案:1:(D) 2 :(D) 3: (B) 4: (讀棧) 11 隊列是指允許在一端（隊尾）進(jìn)入插入

7、， 而在另一端（隊頭）進(jìn)行刪除的線性表。 Rear指針指向隊尾，front指針指向隊頭。 隊列是“先進(jìn)行出”（FIFO）或“后進(jìn) 后出”（LILO）的線性表。 隊列運算包括（1）入隊運算：從隊尾插 入一個元素；（2）退隊運算：從隊頭刪 除一個元素。 循環(huán)隊列：s=0表示隊列空，s=1且 front=rear表示隊列滿 12 隊列的二個例子: 1: 下列關(guān)于隊列的敘述中正確的是_。 A. 在隊列中只能插入數(shù)據(jù) B. 在隊列中只能刪除數(shù)據(jù) C. 隊列是先進(jìn)先出的線性表 D. 隊列是先進(jìn)后出的線性表 2: 在一個容量為15的循環(huán)隊列中,若頭指針 front=6,尾指針rear=9,則該循環(huán)隊列中共有

8、( ) 個元素 答案: 1: (B) 2: 3 13 15 線性鏈表 數(shù)據(jù)結(jié)構(gòu)中的每一個結(jié)點對應(yīng)于一個存儲單元，這 種存儲單元稱為存儲結(jié)點，簡稱結(jié)點。 結(jié)點由兩部分組成：（1）用于存儲數(shù)據(jù)元素值， 稱為數(shù)據(jù)域；（2）用于存放指針，稱為指針域， 用于指向前一個或后一個結(jié)點。 在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可 以不連續(xù)，各數(shù)據(jù)結(jié)點的存儲順序與數(shù)據(jù)元素之 間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏 輯關(guān)系是由指針域來確定的。 14 鏈?zhǔn)酱鎯Ψ绞郊纯捎糜诒硎揪€性結(jié)構(gòu)，也 可用于表示非線性結(jié)構(gòu)。 線性鏈表，HEAD稱為頭指針， HEAD=NULL（或0）稱為空表，如果是 兩指針：左指針（Lli

9、nk）指向前件結(jié)點， 右指針（Rlink）指向后件結(jié)點。 線性鏈表的基本運算：查找、插入、刪 除。 15 幾個例子: 1: 在單鏈表中，增加頭結(jié)點的目的是_。 A. 方便運算的實現(xiàn) B. 使單鏈表至少有一個結(jié)點 C. 標(biāo)識表結(jié)點中首結(jié)點的位置 D. 說明單鏈表是線性表的鏈?zhǔn)酱鎯崿F(xiàn) 2: 線性表的順序存儲結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)分別是_。 A. 順序存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu) B. 隨機(jī)存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu) C. 隨機(jī)存取的存儲結(jié)構(gòu)、隨機(jī)存取的存儲結(jié)構(gòu) D. 任意存取的存儲結(jié)構(gòu)、任意存取的存儲結(jié)構(gòu) 3: 用鏈表表示線性表的優(yōu)點是_。 A. 便于插入和刪除操作 B. 數(shù)據(jù)

10、元素的物理順序與邏輯順序相同 C. 花費的存儲空間較順序存儲少 D. 便于隨機(jī)存取 答案: 1: (A) 2: (B) 3: (A) 16 16 樹與二叉樹 樹是一種簡單的非線性結(jié)構(gòu)，所有元素之間具有明 顯的層次特性。 在樹結(jié)構(gòu)中，每一個結(jié)點只有一個前件，稱為父 結(jié)點，沒有前件的結(jié)點只有一個，稱為樹的根結(jié) 點，簡稱樹的根。每一個結(jié)點可以有多個后件， 稱為該結(jié)點的子結(jié)點。沒有后件的結(jié)點稱為葉子 結(jié)點。 在樹結(jié)構(gòu)中，一個結(jié)點所擁有的后件的個數(shù)稱為 該結(jié)點的度，所有結(jié)點中最大的度稱為樹的度。 樹的最大層次稱為樹的深度。(見26面圖1.26) 17 二叉樹的特點： （1）非空二叉樹只有一個根結(jié)點； （

11、2）每一個結(jié)點最多有兩棵子樹，且分別稱為該結(jié) 點的左子樹與右子樹。 二叉樹的基本性質(zhì)： （1）在二叉樹的第k層上，最多有2k-1(k1)個結(jié)點； （2）深度為m的二叉樹最多有2m-1個結(jié)點； （3）度為0的結(jié)點（即葉子結(jié)點）總是比度為2的結(jié)點 多一個； （4）具有n個結(jié)點的二叉樹，其深度至少為log2n+1, 其中l(wèi)og2n表示取log2n的整數(shù)部分； （5）具有n個結(jié)點的完全二叉樹的深度為log2n+1； （6）設(shè)完全二叉樹共有n個結(jié)點。如果從根結(jié)點開始， 按層序（每一層從左到右）用自然數(shù)1，2，.n 18 給結(jié)點進(jìn)行編號（k=1,2.n），有以下結(jié)論： 若k=1，則該結(jié)點為根結(jié)點，它沒有父

12、結(jié)點；若k1， 則該結(jié)點的父結(jié)點編號為INT(k/2)； 若2kn，則編號為k的結(jié)點的左子結(jié)點編號為2k；否 則該結(jié)點無左子結(jié)點（也無右子結(jié)點）； 若2k+1n，則編號為k的結(jié)點的右子結(jié)點編號為 2k+1；否則該結(jié)點無右子結(jié)點。 滿二叉樹是指除最后一層外，每一層上的所有結(jié)點有 兩個子結(jié)點，則k層上有2k-1個結(jié)點深度為m的滿二叉 樹有2m-1個結(jié)點。 完全二叉樹是指除最后一層外，每一層上的結(jié)點數(shù)均 達(dá)到最大值，在最后一層上只缺少右邊的若干結(jié)點。 二叉樹存儲結(jié)構(gòu)采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，對于滿二叉樹與 完全二叉樹可以按層序進(jìn)行順序存儲。 19 二叉樹的遍歷： （1）前序遍歷（DLR），首先訪問根結(jié)點，

13、然后遍歷左子樹，最后遍歷右子樹； （2）中序遍歷（LDR），首先遍歷左子樹， 然后訪問根結(jié)點，最后遍歷右子樹； （3）后序遍歷（LRD）首先遍歷左子樹， 然后訪問遍歷右子樹，最后訪問根結(jié)點。 (見P31面圖1.35(a)和P30面1.33) 20 幾個例子: 1: 在一棵二叉樹上第5層的結(jié)點數(shù)最多是_。 A. 8 B. 16 C. 32 D. 15 2: 設(shè)一棵完全二叉樹共有700個結(jié)點，則在該二叉樹中的葉子結(jié)點數(shù)為_。 A. 349 B. 350 C. 255 D. 351 3: 在深度為5的滿二叉樹中，葉子結(jié)點的個數(shù)為_。 A. 32 B. 31 C. 16 D. 15 4: 已知二叉樹后

14、序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是 _。 A. cedba B. acbed C. decab D. deabc 答案: 1: (B) 2: (B) 3: (C) 4: (A) 21 17 查找技術(shù) 順序查找的使用情況： （1）線性表為無序表； （2）表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。 二分法查找只適用于順序存儲的有序表， 對于長度為n的有序線性表，最壞情況只需 比較log2n次。 22 18 排序技術(shù) 排序是指將一個無序序列整理成按值非遞減 順序排列的有序序列。 交換類排序法：（1）冒泡排序法，需要比 較的次數(shù)為n(n-1)/2； （2）快速排序法。 插入類排序法：（1）

15、簡單插入排序法，最 壞情況需要n(n-1)/2次比較；（2）希爾排 序法，最壞情況需要O(n1.5)次比較。 選擇類排序法：（1）簡單選擇排序法, 最壞情況需要n(n-1)/2次比較；（2）堆排 序法，最壞情況需要O(nlog2n)次比較。 23 二叉樹的遍歷： （1）前序遍歷（DLR），首先訪問根結(jié) 點，然后遍歷左子樹，最后遍歷右子樹； （2）中序遍歷（LDR），首先遍歷左子 樹，然后訪問根結(jié)點，最后遍歷右子樹； （3）后序遍歷（LRD）首先遍歷左子樹， 然后訪問遍歷右子樹，最后訪問根結(jié)點。 24 幾個例子: 1: 希爾排序法屬于哪一種類型的排序法_。(B) A. 交換類排序法 B. 插入類

16、排序法 C. 選擇類排序法 D. 建堆排序法 2: 在下列幾種排序方法中，要求內(nèi)存量最大的是_。(D) A. 插入排序 B. 選擇排序 C. 快速排序 D. 歸并排序 3: 已知數(shù)據(jù)表A中每個元素距其最終位置不遠(yuǎn)，為節(jié)省時間，應(yīng)采用的算法是_。 (B) A. 堆排序 B. 直接插入排序 C. 快速排序 D. 直接選擇排序 4: 在最壞情況下，冒泡排序的時間復(fù)雜度為_。 5 : 在最壞情況下，堆排序需要比較的次數(shù)為_。 答案: 1: (B) 2: (D) 3: (B) 4: n(n-1)/2#n*(n-1)/2#O(n(n-1)/2)#O(n*(n-1)/2) 5: O(nlog2n) 25 第

17、二章程序設(shè)計基礎(chǔ) 21 程序設(shè)計設(shè)計方法和風(fēng)格 如何形成良好的程序設(shè)計風(fēng)格 1、源程序文檔化； 2、數(shù)據(jù)說明的方法； 3、語句的結(jié)構(gòu)； 4、輸入和輸出。 注釋分序言性注釋和功能性注釋，語句結(jié)構(gòu) 清晰第一、效率第二。 26 22 結(jié)構(gòu)化程序設(shè)計 結(jié)構(gòu)化程序設(shè)計方法的四條原則是：1. 自頂向下； 2. 逐步求精；3.模塊化；4.限制使用goto語句。 結(jié)構(gòu)化程序的基本結(jié)構(gòu)和特點： （1）順序結(jié)構(gòu)：一種簡單的程序設(shè)計，最基本、 最常用的結(jié)構(gòu)； （2）選擇結(jié)構(gòu)：又稱分支結(jié)構(gòu)，包括簡單選擇和 多分支選擇結(jié)構(gòu)，可根據(jù)條件，判斷應(yīng)該選擇哪 一條分支來執(zhí)行相應(yīng)的語句序列； （3）重復(fù)結(jié)構(gòu)：又稱循環(huán)結(jié)構(gòu)，可根據(jù)

18、給定條件， 判斷是否需要重復(fù)執(zhí)行某一相同程序段。 27 23 面向?qū)ο蟮某绦蛟O(shè)計 面向?qū)ο蟮某绦蛟O(shè)計：以60年代末挪威奧斯 陸大學(xué)和挪威計算機(jī)中心研制的SIMULA語 言為標(biāo)志。 面向?qū)ο蠓椒ǖ膬?yōu)點： （1）與人類習(xí)慣的思維方法一致； （2）穩(wěn)定性好； （3）可重用性好； （4）易于開發(fā)大型軟件產(chǎn)品； （5）可維護(hù)性好。 28 對象是面向?qū)ο蠓椒ㄖ凶罨镜母拍睿梢?用來表示客觀世界中的任何實體，對象是 實體的抽象。 面向?qū)ο蟮某绦蛟O(shè)計方法中的對象是系統(tǒng) 中用來描述客觀事物的一個實體，是構(gòu)成 系統(tǒng)的一個基本單位，由一組表示其靜態(tài) 特征的屬性和它可執(zhí)行的一組操作組成。 屬性即對象所包含的信息，操

19、作描述了對 象執(zhí)行的功能，操作也稱為方法或服務(wù)。 29 對象的基本特點： （1）標(biāo)識惟一性； （2）分類性； （3）多態(tài)性； （4）封裝性； （5）模塊獨立性好。 類是指具有共同屬性、共同方法的對象的集 合。所以類是對象的抽象，對象是對應(yīng)類 的一個實例。 消息是一個實例與另一個實例之間傳遞的 信息。 30 消息的組成包括（1）接收消息的對象的名稱； （2）消息標(biāo)識符，也稱消息名；（3）零 個或多個參數(shù)。 繼承是指能夠直接獲得已有的性質(zhì)和特征， 而不必重復(fù)定義他們。 繼承分單繼承和多重繼承。單繼承指一個 類只允許有一個父類，多重繼承指一個類 允許有多個父類。 多態(tài)性是指同樣的消息被不同的對象接受

20、 時可導(dǎo)致完全不同的行動的現(xiàn)象。 31 第三章軟件工程基礎(chǔ) 31 軟件工程基本概念 計算機(jī)軟件是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。 軟件的特點包括： （1）軟件是一種邏輯實體； （2）軟件的生產(chǎn)與硬件不同，它沒有明顯的制作過程； （3）軟件在運行、使用期間不存在磨損、老化問題； （4）軟件的開發(fā)、運行對計算機(jī)系統(tǒng)具有依賴性，受計 算機(jī)系統(tǒng)的限制，這導(dǎo)致了軟件移植的問題； （5）軟件復(fù)雜性高，成本昂貴； （6）軟件開發(fā)涉及諸多的社會因素。 32 軟件按功能分為應(yīng)用軟件、系統(tǒng)軟件、支撐 軟件（或工具軟件）。 軟件危機(jī)主要表現(xiàn)在成本、質(zhì)量、生產(chǎn)率 等問題。 軟件工程是應(yīng)用于計算機(jī)軟件的定義、開 發(fā)

21、和維護(hù)的一整套方法、工具、文檔、實 踐標(biāo)準(zhǔn)和工序。 軟件工程包括3個要素：方法、工具和過程。 33 軟件工程過程是把軟件轉(zhuǎn)化為輸出的一組彼 此相關(guān)的資源和活動，包含4種基本活動： （1）P軟件規(guī)格說明； （2）D軟件開發(fā)； （3）C軟件確認(rèn)； （4）A軟件演進(jìn)。 軟件周期：軟件產(chǎn)品從提出、實現(xiàn)、使用 維護(hù)到停止使用退役的過程。 34 軟件生命周期三個階段:軟件定義、軟件開發(fā)、運行 維護(hù)，主要活動階段是： （1）可行性研究與計劃制定； （2）需求分析； （3）軟件設(shè)計； （4）軟件實現(xiàn)； （5）軟件測試； （6）運行和維護(hù)。 軟件工程的目標(biāo)和與原則： 目標(biāo)：在給定成本、進(jìn)度的前提下，開發(fā)出具有

22、有效性、可靠性、可理解性、可維護(hù)性、可重用 性、可適應(yīng)性、可移植性、可追蹤性和可互操作 性且滿足用戶需求的產(chǎn)品。 35 基本目標(biāo)：付出較低的開發(fā)成本；達(dá)到要求的軟件 功能；取得較好的軟件性能；開發(fā)軟件易于移植； 需要較低的費用；能按時完成開發(fā)，及時交付使 用。 基本原則：抽象、信息隱蔽、模塊化、局部化、 確定性、一致性、完備性和可驗證性。 軟件工程的理論和技術(shù)性研究的內(nèi)容主要包括： 軟件開發(fā)技術(shù)和軟件工程管理。 軟件開發(fā)技術(shù)包括：軟件開發(fā)方法學(xué)、開發(fā)過程、 開發(fā)工具和軟件工程環(huán)境。 軟件工程管理包括：軟件管理學(xué)、軟件工程經(jīng)濟(jì) 學(xué)、軟件心理學(xué)等內(nèi)容。 36 軟件管理學(xué)包括人員組織、進(jìn)度安排、質(zhì)量

23、 保證、配置管理、項目計劃等。 軟件工程原則包括抽象、信息隱蔽、模塊 化、局部化、確定性、一致性、完備性和 可驗證性。 37 32 結(jié)構(gòu)化分析方法 結(jié)構(gòu)化方法的核心和基礎(chǔ)是結(jié)構(gòu)化程序設(shè)計 理論。 需求分析方法有（1）結(jié)構(gòu)化需求分析方法； （2）面向?qū)ο蟮姆治龅姆椒ā?從需求分析建立的模型的特性來分：靜態(tài) 分析和動態(tài)分析。 結(jié)構(gòu)化分析方法的實質(zhì)：著眼于數(shù)據(jù)流， 自頂向下，逐層分解，建立系統(tǒng)的處理流 程，以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具,建 立系統(tǒng)的邏輯模型。 38 結(jié)構(gòu)化分析的常用工具 （1）數(shù)據(jù)流圖(DFD)； （2）數(shù)據(jù)字典(DD)； （3）判定樹； （4）判定表。 數(shù)據(jù)流圖：描述數(shù)據(jù)處理過程

24、的工具，是需求理 解的邏輯模型的圖形表示，它直接支持系統(tǒng)功能 建模。 數(shù)據(jù)字典：對所有與系統(tǒng)相關(guān)的數(shù)據(jù)元素的一個 有組織的列表，以及精確的、嚴(yán)格的定義，使得 用戶和系統(tǒng)分析員對于輸入、輸出、存儲成分和 中間計算結(jié)果有共同的理解。 判定樹：從問題定義的文字描述中分清哪些是判 定的條件，哪些是判定的結(jié)論，根據(jù)描述材料中 的連接詞找出判定條件之間的從屬關(guān)系、并列關(guān) 系、選擇關(guān)系，根據(jù)它們構(gòu)造判定樹。 39 判定表：與判定樹相似，當(dāng)數(shù)據(jù)流圖中的加工要依 賴于多個邏輯條件的取值，即完成該加工的一組 動作是由于某一組條件取值的組合而引發(fā)的，使 用判定表描述比較適宜。 數(shù)據(jù)字典是結(jié)構(gòu)化分析的核心。 軟件需求

25、規(guī)格說明書(SRS)的特點： （1）正確性； （2）無岐義性； （3）完整性； （4）可驗證性； （5）一致性； （6）可理解性； （7）可追蹤性。 40 33 結(jié)構(gòu)化設(shè)計方法 軟件設(shè)計是開發(fā)階段最重要的步驟，是將需求準(zhǔn)確 地轉(zhuǎn)化為完整的軟件產(chǎn)品或系統(tǒng)的唯一途徑。 從技術(shù)觀點來看，軟件設(shè)計包括軟件結(jié)構(gòu)設(shè)計、 數(shù)據(jù)設(shè)計、接口設(shè)計、過程設(shè)計。 結(jié)構(gòu)設(shè)計：定義軟件系統(tǒng)各主要部件之間的關(guān)系。 數(shù)據(jù)設(shè)計：將分析時創(chuàng)建的模型轉(zhuǎn)化為數(shù)據(jù)結(jié)構(gòu) 的定義。 接口設(shè)計：描述軟件內(nèi)部、軟件和協(xié)作系統(tǒng)之間 以及軟件與人之間如何通信。 過程設(shè)計：把系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過程描 述。 41 從工程管理角度來看：概要設(shè)計和

26、詳細(xì)設(shè)計。 軟件設(shè)計的一般過程：軟件設(shè)計是一個迭 代的過程；先進(jìn)行高層次的結(jié)構(gòu)設(shè)計；后 進(jìn)行低層次的過程設(shè)計；穿插進(jìn)行數(shù)據(jù)設(shè) 計和接口設(shè)計。 衡量軟件模塊獨立性使用耦合性和內(nèi)聚性 兩個定性的度量標(biāo)準(zhǔn)。 在程序結(jié)構(gòu)中各模塊的內(nèi)聚性越強(qiáng)，則耦 合性越弱。優(yōu)秀軟件應(yīng)高內(nèi)聚，低耦合。 42 軟件概要設(shè)計的基本任務(wù)是： （1）設(shè)計軟件系統(tǒng)結(jié)構(gòu)； （2）數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù) 庫設(shè)計； （3）編寫概要設(shè)計文檔； （4）概要設(shè)計文檔評 審。 模塊用一個矩形表示，箭頭表示模塊間的調(diào)用關(guān) 系。 在結(jié)構(gòu)圖中還可以用帶注釋的箭頭表示模塊調(diào)用 過程中來回傳遞的信息。還可用帶實心圓的箭頭 表示傳遞的是控制信息，空心圓箭心表示傳

27、遞的 是數(shù)據(jù)。 結(jié)構(gòu)圖的基本形式：基本形式、順序形式、重復(fù)形 式、選擇形式。 結(jié)構(gòu)圖有四種模塊類型：傳入模塊、傳出模塊、 變換模塊和協(xié)調(diào)模塊。 43 34 軟件測試 軟件測試定義：使用人工或自動手段來運行 或測定某個系統(tǒng)的過程，其目的在于檢驗 它是否滿足規(guī)定的需求或是弄清預(yù)期結(jié)果 與實際結(jié)果之間的差別。 軟件測試的目的：發(fā)現(xiàn)錯誤而執(zhí)行程序的 過程。 軟件測試方法：靜態(tài)測試和動態(tài)測試。 靜態(tài)測試包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、 代碼質(zhì)量度量。不實際運行軟件，主要通 過人工進(jìn)行。 44 動態(tài)測試：是基本計算機(jī)的測試，主要包括白盒測 試方法和黑盒測試方法。 白盒測試：在程序內(nèi)部進(jìn)行，主要用于完成軟件 內(nèi)

28、部操作的驗證。主要方法有邏輯覆蓋、基本基 路徑測試。 黑盒測試：主要診斷功能不對或遺漏、界面錯誤、 數(shù)據(jù)結(jié)構(gòu)或外部數(shù)據(jù)庫訪問錯誤、性能錯誤、初 始化和終止條件錯，用于軟件確認(rèn)。主要方法有 等價類劃分法、邊界值分析法、錯誤推測法、因 果圖等。 軟件測試過程一般按4個步驟進(jìn)行：單元測試、集 成測試、驗收測試（確認(rèn)測試）和系統(tǒng)測試。 45 35 程序的調(diào)試 程序調(diào)試的任務(wù)是診斷和改正程序中的錯誤，主要 在開發(fā)階段進(jìn)行。 程序調(diào)試的基本步驟： （1）錯誤定位； （2）修改設(shè)計和代碼，以排除錯誤； （3）進(jìn)行回歸測試，防止引進(jìn)新的錯誤。 軟件調(diào)試可分表靜態(tài)調(diào)試和動態(tài)調(diào)試。靜態(tài)調(diào)試 主要是指通過人的思維來

29、分析源程序代碼和排錯， 是主要的設(shè)計手段，而動態(tài)調(diào)試是輔助靜態(tài)調(diào)試。 主要調(diào)試方法有： （1）強(qiáng)行排錯法； （2）回溯法； （3）原因排除法。 46 典型的數(shù)據(jù)流類型有兩種：變換型和事務(wù)型。 變換型系統(tǒng)結(jié)構(gòu)圖由輸入、中心變換、輸出三部 分組成。 事務(wù)型數(shù)據(jù)流的特點是：接受一項事務(wù)，根據(jù)事 務(wù)處理的特點和性質(zhì)，選擇分派一個適當(dāng)?shù)奶幚?單元，然后給出結(jié)果。 詳細(xì)設(shè)計：是為軟件結(jié)構(gòu)圖中的每一個模塊確定 實現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用某種選定的表達(dá)工 具表示算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)。 常見的過程設(shè)計工具有：圖形工具（程序流程 圖）、表格工具（判定表）、語言工具（PDL）。 47 第四章 數(shù)據(jù)庫應(yīng)用 41 數(shù)據(jù)

30、庫系統(tǒng)的基本概念 數(shù)據(jù)：實際上就是描述事物的符號記錄。 數(shù)據(jù)的特點：有一定的結(jié)構(gòu)，有型與值之 分，如整型、實型、字符型等。而數(shù)據(jù)的 值給出了符合定型的值，如整型值15。 數(shù)據(jù)庫：是數(shù)據(jù)的集合，具有統(tǒng)一的結(jié)構(gòu) 形式并存放于統(tǒng)一的存儲介質(zhì)內(nèi)，是多種 應(yīng)用數(shù)據(jù)的集成，并可被各個應(yīng)用程序共 享。 48 數(shù)據(jù)庫存放數(shù)據(jù)是按數(shù)據(jù)所提供的數(shù)據(jù)模式存放的， 具有集成與共享的特點。 數(shù)據(jù)庫管理系統(tǒng)：一種系統(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ù)模式的物理

31、存 取與構(gòu)建提供有效的存取方法與手段； （3）數(shù)據(jù)操縱：為用戶使用數(shù)據(jù)庫的數(shù)據(jù)提供方 便，如查詢、插入、修改、刪除等以及簡單的算 術(shù)運算及統(tǒng)計； 49 （4）數(shù)據(jù)的完整性、安生性定義與檢查； （5）數(shù)據(jù)庫的并發(fā)控制與故障恢復(fù)； （6）數(shù)據(jù)的服務(wù)：如拷貝、轉(zhuǎn)存、重組、性能監(jiān) 測、分析等。 為完成以上六個功能，數(shù)據(jù)庫管理系統(tǒng)提供以下 的數(shù)據(jù)語言： （1）數(shù)據(jù)定義語言：負(fù)責(zé)數(shù)據(jù)的模式定義與數(shù)據(jù) 的物理存取構(gòu)建； （2）數(shù)據(jù)操縱語言：負(fù)責(zé)數(shù)據(jù)的操縱，如查詢與 增、刪、改等； （3）數(shù)據(jù)控制語言：負(fù)責(zé)數(shù)據(jù)完整性、安全性的 定義與檢查以及并發(fā)控制、故障恢復(fù)等。 數(shù)據(jù)語言按其使用方式具有兩種結(jié)構(gòu)形式：交互

32、式命令(又稱自含型或自主型語言)宿主型語言（一 般可嵌入某些宿主語言中）。 50 數(shù)據(jù)庫管理員：對數(shù)據(jù)庫進(jìn)行規(guī)劃、設(shè)計、維護(hù)、 監(jiān)視等的專業(yè)管理人員。 數(shù)據(jù)庫系統(tǒng)：由數(shù)據(jù)庫（數(shù)據(jù)）、數(shù)據(jù)庫管理系 統(tǒng)（軟件）、數(shù)據(jù)庫管理員（人員）、硬件平臺 （硬件）、軟件平臺（軟件）五個部分構(gòu)成的運 行實體。 數(shù)據(jù)庫應(yīng)用系統(tǒng)：由數(shù)據(jù)庫系統(tǒng)、應(yīng)用軟件及應(yīng) 用界面三者組成。 文件系統(tǒng)階段：提供了簡單的數(shù)據(jù)共享與數(shù)據(jù)管 理能力，但是它無法提供完整的、統(tǒng)一的、管理 和數(shù)據(jù)共享的能力。 層次數(shù)據(jù)庫與網(wǎng)狀數(shù)據(jù)庫系統(tǒng)階段 ：為統(tǒng)一與共 享數(shù)據(jù)提供了有力支撐。 51 關(guān)系數(shù)據(jù)庫系統(tǒng)階段 數(shù)據(jù)庫系統(tǒng)的基本特點：數(shù)據(jù)的集成性 、數(shù)

33、據(jù)的 高共享性與低冗余性 、數(shù)據(jù)獨立性（物理獨立性 與邏輯獨立性）、數(shù)據(jù)統(tǒng)一管理與控制。 數(shù)據(jù)庫系統(tǒng)的三級模式： （1）概念模式：數(shù)據(jù)庫系統(tǒng)中全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu) 的描述，全體用戶公共數(shù)據(jù)視圖； （2）外模式：也稱子模式與用戶模式。是用戶的 數(shù)據(jù)視圖，也就是用戶所見到的數(shù)據(jù)模式； （3）內(nèi)模式：又稱物理模式，它給出了數(shù)據(jù)庫物 理存儲結(jié)構(gòu)與物理存取方法。 52 數(shù)據(jù)庫系統(tǒng)的兩級映射： （1）概念模式到內(nèi)模式的映射； （2）外模式到概念模式的映射。 53 4.2 數(shù)據(jù)模型 數(shù)據(jù)模型的概念：是數(shù)據(jù)特征的抽象，從抽 象層次上描述了系統(tǒng)的靜態(tài)特征、動態(tài)行 為和約束條件，為數(shù)據(jù)庫系統(tǒng)的信息表與 操作提供一個抽象的框架。描述了數(shù)據(jù)結(jié) 構(gòu)、數(shù)據(jù)操作及數(shù)據(jù)約束。 E-R模型的基本概念 （1）實體：現(xiàn)實世界中的事物； （2）屬性：事物的特性； （3）聯(lián)系：現(xiàn)實世界中事物間的關(guān)系。實 體集的關(guān)系有一對一、一對多、多對多的 聯(lián)系。 54 E-R模型三個基本概念之間的聯(lián)接關(guān)系：實體是概 念世界中的基本單位，屬性有屬性域，每個實體 可取屬性域內(nèi)的值。一個實體的所有屬性值叫元 組。 E-R模型的圖示法：（1）實體集表示法； （2） 屬性表法； （3）聯(lián)系表示法。 層次模型的基本結(jié)構(gòu)是樹形結(jié)構(gòu)，具有以下特點： （1）每棵樹有且僅有一個無雙親結(jié)點，稱為根； （2）樹中除根外所有結(jié)點有且僅有一個雙親。 從圖論上看，網(wǎng)狀