2010計算機二級考試大綱

1、20102010 年計算機等級考試年計算機等級考試( (二級公共基礎二級公共基礎) )考試大綱考試大綱 基本要求1.掌握算法的基本概念。2.掌握基本數(shù)據(jù)結(jié)構(gòu)及其操作。3.掌握基本排序和查找算法。4.掌握逐步求精的結(jié)構(gòu)化程序設計方法。5.掌握軟件工程的基本方法，具有初步應用相關技術進行軟件開發(fā)的能力。6.掌握數(shù)據(jù)庫的基本知識，了解關系數(shù)據(jù)庫的設計。 考試內(nèi)容一、基本數(shù)據(jù)結(jié)構(gòu)與算法1.算法的基本概念;算法復雜度的概念和意義(時間復雜度與空間復雜度)。2.數(shù)據(jù)結(jié)構(gòu)的定義;數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu) ;數(shù)據(jù)結(jié)構(gòu)的圖形表示 ;線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念。3.線性表的定義;線性表的順序存儲結(jié)構(gòu)及其插入與刪除

2、運算。4.棧和隊列的定義;棧和隊列的順序存儲結(jié)構(gòu)及其基本運算。5.線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運算。6.樹的基本概念;二叉樹的定義及其存儲結(jié)構(gòu);二叉樹的前序、中序和后序遍歷。7.順序查找與二分法查找算法;基本排序算法(交換類排序，選擇類排序，插入類排序)。二、程序設計基礎1.程序設計方法與風格。2.結(jié)構(gòu)化程序設計。3.面向?qū)ο蟮某绦蛟O計方法，對象，方法，屬性及繼承與多態(tài)性。三、軟件工程基礎1.軟件工程基本概念，軟件生命周期概念，軟件工具與軟件開發(fā)環(huán)境。2.結(jié)構(gòu)化分析方法，數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說明書。3.結(jié)構(gòu)化設計方法，總體設計與詳細設計。4.軟件測試的方法，白盒測試

3、與黑盒測試，測試用例設計， 軟件測試的實施，單元測試、集成測試和系統(tǒng)測試。5.程序的調(diào)試，靜態(tài)調(diào)試與動態(tài)調(diào)試。四、數(shù)據(jù)庫設計基礎1.數(shù)據(jù)庫的基本概念：數(shù)據(jù)庫，數(shù)據(jù)庫管理系統(tǒng)，數(shù)據(jù)庫系統(tǒng)。2.數(shù)據(jù)模型，實體聯(lián)系模型及 e-r 圖，從 e-r 圖導出關系數(shù)據(jù)模型。3.關系代數(shù)運算，包括集合運算及選擇、投影、連接運算，數(shù)據(jù)庫規(guī)范化理論。4.數(shù)據(jù)庫設計方法和步驟：需求分析、概念設計、邏輯設計和物理設計的相關策略。 考試方式公共基礎知識有 10 道選擇題和 5 道填空題共三十分。二級公共基礎知識總結(jié)二級公共基礎知識總結(jié)第一章第一章 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法1.11.1 算法算法算法：是一組有窮指令集

4、，是解題方案的準確而完整的描述。通俗地說，算法就是計算機解題的過程。算法不等于程序，也不等于計算方法，程序的編制不可能優(yōu)于算法的設計。算法是一組嚴謹?shù)囟x運算順序的規(guī)則， 每一個規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。所以其四個基本特征包括：（1）確定性，算法中每一步驟都必須有明確定義， 不允許有模棱兩可的解釋，不允許有多義性；（2）有窮性，算法必須能在有限的時間內(nèi)做完，即能在執(zhí)行有限個步驟后終止；（3）可行性，算法原則上能夠精確地執(zhí)行；（4）擁有足夠的情報。算法的基本要素：一是對數(shù)據(jù)對象的運算和操作；二是算法的控制結(jié)構(gòu)。指令系統(tǒng)：一個計算機系統(tǒng)能執(zhí)行的所有指令的集合。基本運算

5、和操作包括：算術運算、邏輯運算、關系運算、數(shù)據(jù)傳輸。算法的三種基本控制結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)。算法基本設計方法：列舉法、歸納法、遞推、遞歸、減半遞推技術、回溯法。算法效率的度量算法復雜度：算法時間復雜度 和算法空間復雜度 。算法時間復雜度：指執(zhí)行算法所需要的計算工作量。即算法執(zhí)行過程中所需要的基本運算次數(shù)。 通常，一個算法所用的時間包括編譯時間和運行時間。算法空間復雜度：指執(zhí)行這個算法所需要的內(nèi)存空間。 包括算法程序所占的空間，輸入的初始數(shù)據(jù)所占的空間，算法執(zhí)行過程中所需的額外空間。1.21.2 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)：指相互有關聯(lián)的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)研

6、究的三個方面：（1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；（2）在對數(shù)據(jù)進行處理時，各數(shù)據(jù)元素在計算機中的存儲關系，即 數(shù)據(jù)的存儲結(jié)構(gòu)；（3）對各種數(shù)據(jù)結(jié)構(gòu)進行的運算。數(shù)據(jù)的邏輯結(jié)構(gòu)應包含：（1）表示數(shù)據(jù)元素的信息；（2）表示各數(shù)據(jù)元素之間的前后件關系 (指邏輯關系，與存儲位置無關 )。數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式稱為數(shù)據(jù)的存儲結(jié)構(gòu),也稱數(shù)據(jù)物理結(jié)構(gòu)。數(shù)據(jù)的存儲結(jié)構(gòu)有順序、鏈接、索引等。線性結(jié)構(gòu)的條件，(一個非空數(shù)據(jù)結(jié)構(gòu) )：（1）有且只有一個根結(jié)點； （2）每一個結(jié)點最多有一個前件，也最多有一個后件。非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。1.31.3

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

8、邏輯順序依次存放的。元素ai 的存儲地址為： adr(ai)=adr(a1)+(i-1)k ，adr(a1)為第一個元素的地址， k代表每個元素占的字節(jié)數(shù)。順序表的運算：查找、插入、刪除。1.41.4 線性鏈表線性鏈表數(shù)據(jù)結(jié)構(gòu)中的每一個結(jié)點對應于一個存儲單元，這種存儲單元稱為存儲結(jié)點，簡稱結(jié)點。結(jié)點由兩部分組成：(1) 用于存儲數(shù)據(jù)元素值，稱為 數(shù)據(jù)域；(2) 用于存放指針，稱為 指針域，用于指向前一個或后一個結(jié)點。在鏈式存儲結(jié)構(gòu)中，存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以不連續(xù)， 各數(shù)據(jù)結(jié)點的存儲順序與數(shù)據(jù)元素之間的邏輯關系可以不一致，而數(shù)據(jù)元素之間的邏輯關系是由指針域來確定的。鏈式存儲方式即可用于表示線

9、性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。線性單鏈表中，head 稱為頭指針， head=null（或 0）稱為空表。如果是雙項鏈表的兩指針：左指針（ llink）指向前件結(jié)點， 右指針（rlink）指向后件結(jié)點。線性鏈表的基本運算：查找、插入、刪除。1.51.5 棧和隊列棧和隊列棧：限定在一端進行插入與刪除的線性表。其允許插入與刪除的一端稱為棧頂，用指針 top 表示棧頂位置。不允許插入與刪除的另一端稱為棧底，用指針 bottom 表示棧底。棧按照“先進后出”（filo）或“后進先出”（lifo）組織數(shù)據(jù)，棧具有記憶作用。棧的存儲方式有順序存儲和鏈式存儲。棧的基本運算：(1) 入棧運算，在棧頂位置插入

10、元素；(2) 退棧運算，刪除元素(取出棧頂元素并賦給一個指定的變量 )；(3) 讀棧頂元素，將棧頂元素賦給一個指定的變量，此時指針無變化。隊列：指允許在一端（隊尾）進入插入，而在另一端（隊頭）進行刪除的線性表。用 rear 指針指向隊尾，用 front 指針指向隊頭元素的前一個位置。隊列是“先進先出”（fifo）或“后進后出”（lilo）的線性表。隊列運算包括：(1) 入隊運算：從隊尾插入一個元素；(2) 退隊運算：從隊頭刪除一個元素。隊列的順序存儲結(jié)構(gòu)一般采用隊列循環(huán)的形式。循環(huán)隊列 s=0 表示隊列空；s=1 且 front =rear 表示隊列滿。計算循環(huán)隊列的元素個數(shù)： “尾指針減頭指

11、針” ，若為負數(shù)，再加其容量即可。1.61.6 樹與二叉樹樹與二叉樹樹是一種簡單的非線性結(jié)構(gòu)，其所有元素之間具有明顯的層次特性。在樹結(jié)構(gòu)中，每一個結(jié)點只有一個前件，稱為父結(jié)點。沒有前件的結(jié)點只有一個，稱為樹的根結(jié)點，簡稱樹的根。每一個結(jié)點可以有多個后件，稱為該結(jié)點的子結(jié)點。沒有后件的結(jié)點稱為葉子結(jié)點。在樹結(jié)構(gòu)中，一個結(jié)點所擁有的后件的個數(shù)稱為該結(jié)點的度，所有結(jié)點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。二叉樹的特點：(1) 非空二叉樹只有一個根結(jié)點；(2) 每一個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹與右子樹。滿二叉樹是指除最后一層外，每一層上的所有結(jié)點有兩個子結(jié)點，則k 層上有2

12、k-1個結(jié)點深度為 m的滿二叉樹有 2m-1 個結(jié)點。完全二叉樹是指除最后一層外，每一層上的結(jié)點數(shù)均達到最大值，在最后一層上只缺少右邊的若干結(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) 設完全二叉樹共有 n 個結(jié)點。如果從根結(jié)點開始，按層序（每一層從左到右）用自然數(shù) 1,

13、2,n 給結(jié)點進行編號（ k=1,2.n） ，有以下結(jié)論：若 k=1，則該結(jié)點為根結(jié)點，它沒有父結(jié)點；若 k1，則該結(jié)點的父結(jié)點編號為 int(k/2)；若 2kn，則 k結(jié)點的左子結(jié)點編號為 2k；否則該結(jié)點無左子結(jié)點（也無右子結(jié)點） ；若 2k+1n，則編號為 k 的結(jié)點的右子結(jié)點編號為 2k+1；否則該結(jié)點無右子結(jié)點。補充：增加度為 1 的結(jié)點不會影響二叉樹的葉子結(jié)點數(shù)，每增加一個度為 2 的結(jié)點便會增加一個葉子結(jié)點，沒有度為 2 的結(jié)點時葉子結(jié)點數(shù)為 1。已知完全二叉樹有 x 個結(jié)點，求其葉子結(jié)點數(shù)：確定層數(shù)為 k；第 k 層的結(jié)點數(shù) y=x-(2 k-1-1)；第 k-1層的葉子結(jié)點

14、數(shù) n=2 (k-1)-1-y/2； 最后 y+n。二叉樹存儲結(jié)構(gòu)采用鏈式存儲結(jié)構(gòu)，對于滿二叉樹與完全二叉樹可以按層序進行順序存儲。二叉樹的遍歷：（1）前序遍歷（ dlr） ，首先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹；（樹根在第一，下走不跳結(jié)點）（2）中序遍歷（ldr） ，首先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹；（有左先左，再尋根，后找右。最左邊的結(jié)點最先遍歷，最右邊的結(jié)點最后遍歷）（3）后序遍歷（lrd）首先遍歷左子樹，然后訪問遍歷右子樹，最后訪問根結(jié)點。（有左先左，再找右，后尋根，到最右一路上行，樹根在最后）小結(jié)：邏輯結(jié)構(gòu)可分為線性表和非線性表。線性表包括棧、隊列，其存儲方式

15、為順序存儲、鏈式存儲均可。鏈式型有：線性鏈表，帶鏈的棧，帶鏈的隊列，循環(huán)鏈表等。非線性表包括樹(二叉樹)，其存儲方式為鏈式存儲。1.71.7 查找技術查找技術只能使用順序查找的兩種情況：（1）線性表為無序表，不管是順序存儲還是鏈式存儲；（2）表采用鏈式存儲結(jié)構(gòu)，即使是有序線性表。二分法查找只適用于順序存儲的有序表，對于長度為n 的有序線性表，最壞情況只需比較log2n 次，而順序查找需要比較 n 次。1.81.8 排序技術排序技術排序是指將一個無序序列整理成按值非遞減順序排列的有序序列。交換類排序法： （1）冒泡排序法，需要比較的次數(shù)為 n(n-1)/2；(2 ) 快速排序法。插入類排序法：

16、（1）簡單插入排序法，最壞情況需要 n(n-1)/2 次比較；(2) 希爾排序法，最壞情況需要 o(n1.5)次比較。選擇類排序法： （1）簡單選擇排序法, 最壞情況需要 n(n-1)/2 次比較；(2) 堆排序法，最壞情況需要 o(nlog2n)次比較。相比以上幾種(除希爾排序法外 )，堆排序法的時間復雜度最小。第二章第二章 程序設計基礎程序設計基礎2.12.1 程序設計設計方法和風格程序設計設計方法和風格“清晰第一、效率第二”已成為當今主導的程序設計風格。形成良好的程序設計風格需注意： (詳見書 p27)1、源程序文檔化； 2、數(shù)據(jù)說明的方法； 3、語句的結(jié)構(gòu)；4、輸入和輸出。注釋分序言性

17、注釋和功能性注釋。語句結(jié)構(gòu)清晰第一、效率第二。2.22.2 結(jié)構(gòu)化程序設計結(jié)構(gòu)化程序設計結(jié)構(gòu)化程序設計方法的四條原則是：1、自頂向下 ； 2、逐步求精 ； 3、模塊化； 4、限制使用 goto 語句。結(jié)構(gòu)化程序的基本結(jié)構(gòu)及特點：（1）順序結(jié)構(gòu)：一種簡單的程序設計，最基本、最常用的結(jié)構(gòu)；（2）選擇結(jié)構(gòu)：又稱分支結(jié)構(gòu)，包括簡單選擇和多分支選擇結(jié)構(gòu)，可根據(jù)條件，判斷應該選擇哪一條分支來執(zhí)行相應的語句序列；（3）循環(huán)結(jié)構(gòu)：又稱重復結(jié)構(gòu)，可根據(jù)給定條件，判斷是否需要重復執(zhí)行某一相同或類似的程序段。結(jié)構(gòu)化程序設計的特點：只有一個入口和出口2.32.3 面向?qū)ο蟮某绦蛟O計面向?qū)ο蟮某绦蛟O計面向 對象 的程

18、序設 計的 首次提 出以 60 年代末 挪威 奧斯陸 大學 和挪 威計 算機 中心研 制的simula 語言為標志。面向?qū)ο蠓椒ǖ膬?yōu)點：（1）與人類習慣的思維方法一致；（2）穩(wěn)定性好； （3）可重用性好；（4）易于開發(fā)大型軟件產(chǎn)品； （5）可維護性好。對象是面向?qū)ο蠓椒ㄖ凶罨镜母拍?，可以用來表示客觀世界中的任何實體，對象是實體的抽象。面向?qū)ο蟮某绦蛟O計方法中，對象是由數(shù)據(jù)的容許的操作組成的封裝體， 是系統(tǒng)中用來描述客觀事物的一個實體，是構(gòu)成系統(tǒng)的一個基本單位，由一組表示其靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成。屬性即對象所包含的信息，它在設計對象時確定，一般只能通過執(zhí)行對象的操作來改變。操作

19、描述了對象執(zhí)行的功能，是對象的動態(tài)屬性，操作也稱為 方法或 服務。對象的基本特點：（1）標識惟一性； （2）分類性； （3）多態(tài)性； （4）封裝性； （5）模塊獨立性好。類是指具有共同屬性、共同方法的對象的集合。類是關于對象性質(zhì)的描述。類是對象的抽象，對象是其對應類的一個實例。消息是一個實例與另一個實例之間傳遞的信息。對象間的通信靠消息傳遞。它請求對象執(zhí)行某一處理或回答某一要求的信息，它統(tǒng)一了數(shù)據(jù)流和控制流。消息的組成包括：（1）接收消息的對象的名稱；（2）消息標識符，也稱消息名；（3）零個或多個參數(shù)。繼承是使用已有的類定義作為基礎建立新類的定義技術，廣義指能夠直接獲得已有的性質(zhì)和特征，而不必

20、重復定義他們。繼承具有傳遞性，一個類實際上繼承了他上層的全部基類的特性。繼承分單繼承和多重繼承。單繼承指一個類只允許有一個父類，即類等級為樹形結(jié)構(gòu)； 多重繼承指一個類允許有多個父類。多態(tài)性是指同樣的消息被不同的對象接受時可導致完全不同的行動的現(xiàn)象第三章第三章 軟件工程基礎軟件工程基礎3.13.1 軟件工程基本概念軟件工程基本概念計算機軟件是包括程序 、數(shù)據(jù) 及相關文檔的完整集合。軟件的特點包括：（1）軟件是一種邏輯實體，具有抽象性；（2）軟件的生產(chǎn)與硬件不同，它沒有明顯的制作過程；（3）軟件在運行、使用期間不存在磨損、老化問題；（4）軟件的開發(fā)、運行對計算機系統(tǒng)具有依賴性，受計算機系統(tǒng)的限制，

21、這導致了軟件移植的問題；（5）軟件復雜性高，成本昂貴；（6）軟件開發(fā)涉及諸多的社會因素。軟件按功能分為應用軟件、系統(tǒng)軟件、支撐軟件 (或工具軟件)。軟件危機主要表現(xiàn)在成本、質(zhì)量、生產(chǎn)率等問題。軟件工程是應用于計算機軟件的定義、開發(fā)和維護的一整套方法、工具、文檔、實踐標準和工序。簡單的說就是使軟件走向工程化。軟件工程的核心思想是把軟件產(chǎn)品看作是一個工程產(chǎn)品來處理。軟件工程包括 3 個要素：方法 、工具 和過程 。軟件工程過程是把軟件轉(zhuǎn)化為輸出的一組彼此相關的資源活動，包含4 種基本活動：（1）p(plan)軟件規(guī)格說明；（2）d(do)軟件開發(fā)；（3）c(check) 軟件確認；（4）a(act

22、ion) 軟件演進。軟件生命周期：軟件產(chǎn)品從提出、實現(xiàn)、使用維護到停止使用退役的過程。軟件生命周期分三個階段：軟件定義 、軟件開發(fā)、 運行維護，主要活動階段是：（1）可行性研究與計劃制定；（2）需求分析；（3）軟件設計（概要設計和詳細設計）； （4）軟件實現(xiàn)； （5）軟件測試；（6）運行和維護。軟件工程的目標：在給定成本、進度的前提下，開發(fā)出具有有效性、可靠性、可理解性、可維護性、可重用性、可適應性、可移植性、可追蹤性和可互操作性且滿足用戶需求的產(chǎn)品。基本目標：付出較低的開發(fā)成本；達到要求的軟件功能；取得較好的軟件性能；開發(fā)軟件易于移植；需要較低的費用；能按時完成開發(fā)，及時交付使用。軟件工程的

23、理論和技術性研究的內(nèi)容主要包括：軟件開發(fā)技術和軟件工程管理。軟件開發(fā)技術包括：軟件開發(fā)方法學 、開發(fā)過程、 開發(fā)工具和 軟件工程環(huán)境 。軟件開發(fā)環(huán)境或軟件工程環(huán)境是指全面支持軟件開發(fā)全過程的軟件工具的集合。軟件工程管理包括：軟件管理學、軟件工程經(jīng)濟學、軟件心理學等內(nèi)容。軟件管理學包括人員組織、進度安排、質(zhì)量保證、配置管理、項目計劃等。軟件工程基本原則：抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗證性。3.23.2 結(jié)構(gòu)化分析方法結(jié)構(gòu)化分析方法結(jié)構(gòu)化方法的核心和基礎是結(jié)構(gòu)化程序設計理論。軟件定義階段中，可行性研究與計劃的制定是確定待開發(fā)目標和總的要求，給出它的功能、性能、可靠性以

24、及接口等方面的可能方案，制定完成開發(fā)的實施計劃。需求分析，對待開發(fā)軟件提出的需求分析并給出詳細的定義。需求分析階段的工作：需求獲取，需求分析，編寫需求規(guī)格說明書，需求評審。需求分析方法有： （1）結(jié)構(gòu)化需求分析方法 ；面向數(shù)據(jù)結(jié)構(gòu)的 jackson 方法（isd） ；面向數(shù)據(jù)流的結(jié)構(gòu)化分析方法（sa） ；面向數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)化數(shù)據(jù)系統(tǒng)開發(fā)方法（dssd） ；（2）面向?qū)ο蟮姆治龅姆椒ǎ╫oa） 。從需求分析建立的模型的特性來分： 靜態(tài)分析和動態(tài)分析 。結(jié)構(gòu)化分析方法的實質(zhì)：著眼于數(shù)據(jù)流，自頂向下，逐層分解，建立系統(tǒng)的處理流程，以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具，建立系統(tǒng)的邏輯模型。結(jié)構(gòu)化分析的常用工

25、具：數(shù)據(jù)流圖； 數(shù)據(jù)字典；判定樹； 判定表。（1）數(shù)據(jù)流圖（dfd 圖）：描述數(shù)據(jù)處理過程的工具，是需求理解的邏輯模型的圖形表示，它直接支持系統(tǒng)功能建模。加工（轉(zhuǎn)換）圓框，輸入數(shù)據(jù)經(jīng)加工變換產(chǎn)生的輸出。數(shù)據(jù)流箭頭，沿箭頭方向傳遞數(shù)據(jù)的通道，一般在旁邊標注數(shù)據(jù)流名。存儲文件（數(shù)據(jù)源）雙橫線，表示處理過程中存放各種數(shù)據(jù)的文件。源、潭方框，表示系統(tǒng)和環(huán)境的接口，屬系統(tǒng)之外的實體。（2）數(shù)據(jù)字典：對所有與系統(tǒng)相關的數(shù)據(jù)元素的一個有組織的列表， 以及精確的、嚴格的定義，使得用戶和系統(tǒng)分析員對于輸入、輸出、存儲成分和中間計算結(jié)果有共同的理解。數(shù)據(jù)字典是結(jié)構(gòu)化分析的核心。（3）判定樹：從問題定義的文字描述中

26、分清哪些是判定的條件，哪些是判定的結(jié)論，根據(jù)描述材料中的連接詞找出判定條件之間的從屬關系、并列關系、選擇關系，根據(jù)它們構(gòu)造判定樹。（4）判定表：與判定樹相似，當數(shù)據(jù)流圖中的加工要依賴于多個邏輯條件的取值，即完成該加工的一組動作是由于某一組條件取值的組合而引發(fā)的，使用判定表描述比較適宜。軟件需求規(guī)格說明書的特點：正確性；無岐義性； 完整性； 可驗證性；一致性； 可理解性； 可修改性； 可追蹤性。3.33.3 結(jié)構(gòu)化設計方法結(jié)構(gòu)化設計方法軟件設計是確定系統(tǒng)的物理模型。軟件設計是開發(fā)階段最重要的步驟，是將需求準確地轉(zhuǎn)化為完整的軟件產(chǎn)品或系統(tǒng)的唯一途徑。系統(tǒng)設計人員和程序設計人員應該在反復理解軟件需求

27、的基礎上，給出軟件結(jié)構(gòu)、模塊的劃分、功能的分配以及處理流程。軟件設計的基本目標是用比較抽象概括的方式確定目標系統(tǒng)如何完成預定的任務。從技術觀點來看，軟件設計包括軟件 結(jié)構(gòu)設計、數(shù)據(jù)設計 、接口設計 、過程設計。結(jié)構(gòu)設計：定義軟件系統(tǒng)各主要部件之間的關系。數(shù)據(jù)設計：將分析時創(chuàng)建的模型轉(zhuǎn)化為數(shù)據(jù)結(jié)構(gòu)的定義。接口設計：描述軟件內(nèi)部、軟件和協(xié)作系統(tǒng)之間以及軟件與人之間如何通信。過程設計：把系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過程描述。從工程管理角度來看，軟件設計分兩步：概要設計 和詳細設計 。軟件設計的一般過程：軟件設計是一個迭代的過程； 先進行高層次的結(jié)構(gòu)設計；后進行低層次的過程設計；穿插進行數(shù)據(jù)設計和接口設計

28、。軟件設計的基本原理是： （1）抽象； （2）模塊化； （3）信息隱蔽； （4）模塊獨立性。衡量軟件模塊獨立性使用耦合性和內(nèi)聚性兩個定性的度量標準。耦合性是模塊見相互連接的緊密程度的度量。耦合程度取決于各個模塊之間接口的復雜程度、調(diào)用方式以及哪些信息通過接口。內(nèi)聚性是一個模塊內(nèi)部各個元素間彼此結(jié)合的緊密程度的度量。在程序結(jié)構(gòu)中各模塊的內(nèi)聚性越強，則耦合性越弱。優(yōu)秀軟件應高內(nèi)聚，低耦合，有利于提高模塊的獨立性。軟件概要設計的基本任務是：（1）設計軟件系統(tǒng)結(jié)構(gòu)；（2）數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫設計；（3）編寫概要設計文檔；（4）概要設計文檔評審。在結(jié)構(gòu)圖中，模塊用一個矩形表示，箭頭表示模塊間的調(diào)用關系?？梢?/p>

29、用帶注釋的箭頭表示模塊調(diào)用過程中來回傳遞的信息。還可用帶實心圓的箭頭表示傳遞的是控制信息，空心圓箭心表示傳遞的是數(shù)據(jù)。結(jié)構(gòu)圖的基本形式：基本形式、順序形式、重復形式、選擇形式。結(jié)構(gòu)圖有四種模塊類型：傳入模塊、傳出模塊、變換模塊和協(xié)調(diào)模塊。典型的數(shù)據(jù)流類型有兩種：變換型和 事務型。變換型系統(tǒng)結(jié)構(gòu)圖由輸入、中心變換、輸出三部分組成。事務型數(shù)據(jù)流的特點是：接受一項事務，根據(jù)事務處理的特點和性質(zhì)，選擇分派一個適當?shù)奶幚韱卧?，然后給出結(jié)果。詳細設計：是為軟件結(jié)構(gòu)圖中的每一個模塊確定實現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)， 用某種選定的表達工具表示算法和數(shù)據(jù)結(jié)構(gòu)的細節(jié)。常見的過程設計工具有：圖形工具（程序流程圖(pfd)

30、、n-s 圖、 pad 圖、） ，表格工具（判定表） ，語言工具（pdl） 。程序流程圖中：箭頭為控制流、方框為加工步驟、菱形為邏輯條件。3.43.4 軟件測試軟件測試軟件測試定義：使用人工或自動手段來運行或測定某個系統(tǒng)的過程， 其目的在于檢驗它是否滿足規(guī)定的需求或是弄清預期結(jié)果與實際結(jié)果之間的差別。軟件測試的目的：發(fā)現(xiàn)錯誤而執(zhí)行程序的過程。軟件測試方法： 靜態(tài)測試和動態(tài)測試 。靜態(tài)測試包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量。不實際運行軟件，主要通過人工進行。動態(tài)測試：是基本計算機的測試，主要包括白盒測試方法和黑盒測試方法。白盒測試：也稱結(jié)構(gòu)測試或邏輯測試。在程序內(nèi)部進行，主要用于完成軟件內(nèi)

31、部操作的驗證。白盒測試主要考慮內(nèi)部的邏輯結(jié)構(gòu)。主要方法有邏輯覆蓋、基本路徑測試。黑盒測試：也稱功能測試或數(shù)據(jù)驅(qū)動測試。是在軟件接口處進行，完成功能驗證。黑盒測試完全不考慮程序內(nèi)部的邏輯結(jié)構(gòu)和內(nèi)部特性，只依據(jù)程序的需求和功能規(guī)格說明，檢查程序的功能是否符合它的設計要求。主要診斷功能不對或遺漏、界面錯誤、數(shù)據(jù)結(jié)構(gòu)或外部數(shù)據(jù)庫訪問錯誤、性能錯誤、初始化和終止條件錯，用于軟件確認測試。主要方法有等價類劃分法、邊界值分析法、錯誤推測法、因果圖等。驅(qū)動測試相當于被測模塊的主程序，它接收測試數(shù)據(jù)，并傳給被測模塊，輸出實際測試結(jié)果。軟件測試過程一般按 4 個步驟進行：單元測試、集成測試、驗收測試（確認測試）和

32、系統(tǒng)測試。單元測試是對模塊（程序單元）進行，靜態(tài)動態(tài)均有，動態(tài)時以白盒為主輔之以黑盒。集成測試是測試、組裝軟件。確認測試的任務是驗證軟件的功能和性能及其他特性是否滿足了需求規(guī)格說明中的各項需求以及軟件配置是否完全正確，先用黑盒。3.53.5 程序的調(diào)試程序的調(diào)試程序調(diào)試的任務是診斷和改正程序中的錯誤，主要在開發(fā)階段進行。程序調(diào)試的基本步驟：（1）錯誤定位；（2）修改設計和代碼，以排除錯誤；（3）進行回歸測試，防止引進新的錯誤。軟件調(diào)試可分為靜態(tài)調(diào)試和動態(tài)調(diào)試。靜態(tài)調(diào)試主要是指通過人的思維來分析源程序代碼和排錯，是主要的設計手段，而動態(tài)調(diào)試是輔助靜態(tài)調(diào)試。主要調(diào)試方法有： （1）強行排錯法；（2

33、）回溯法；（3）原因排除法。第四章第四章 數(shù)據(jù)庫設計基礎數(shù)據(jù)庫設計基礎4.14.1 數(shù)據(jù)庫系統(tǒng)的基本概念數(shù)據(jù)庫系統(tǒng)的基本概念數(shù)據(jù)：實際上就是描述事物的符號記錄。軟件的數(shù)據(jù)是有一定的結(jié)構(gòu)，有型與值之分，如整型、實型、字符型等。而數(shù)據(jù)的值給出了符合定型的值，如整型值 15。數(shù)據(jù)庫：是指在已有數(shù)據(jù)庫管理系統(tǒng)的基礎上建立數(shù)據(jù)庫，是數(shù)據(jù)的集合，具有統(tǒng)一的結(jié)構(gòu)形式并存放于統(tǒng)一的存儲介質(zhì)內(nèi)，是多種應用數(shù)據(jù)的集成，并可被各個應用程序共享。數(shù)據(jù)庫存放數(shù)據(jù)是按數(shù)據(jù)所提供的數(shù)據(jù)模式存放的，具有集成與共享的特點。數(shù)據(jù)庫管理系統(tǒng) ：一種系統(tǒng)軟件，負責數(shù)據(jù)庫中的數(shù)據(jù)組織、數(shù)據(jù)操縱、數(shù)據(jù)維護、控制及保護和數(shù)據(jù)服務等，數(shù)據(jù)庫

34、系統(tǒng)中實現(xiàn)各種數(shù)據(jù)管理功能的核心軟件稱為數(shù)據(jù)庫管理系統(tǒng)。數(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ù)提供方便，如查詢、插入、修改、刪除等以及簡單的算術運算及統(tǒng)計；（4）數(shù)據(jù)的完整性、安全性定義與檢查；（5）數(shù)據(jù)庫的并發(fā)控制與故障恢復；（6）數(shù)據(jù)的服務：如拷貝、轉(zhuǎn)存、重組、性能監(jiān)測、分析等。為完成以上功能，數(shù)據(jù)庫管理系統(tǒng)提供以下的數(shù)據(jù)語言：（1）數(shù)據(jù)定義語言(ddl)：負責數(shù)據(jù)的模式定義與數(shù)據(jù)的物理存取構(gòu)建；（2）數(shù)據(jù)操縱語言(dml)：負責數(shù)據(jù)的操縱，

35、如查詢與增、刪、改等；（3）數(shù)據(jù)控制語言(dcl)：負責數(shù)據(jù)完整性、安全性的定義與檢查以及并發(fā)控制、 故障恢復等。數(shù)據(jù)語言按其使用方式具有兩種結(jié)構(gòu)形式：交互式命令(又稱自含型或自主型語言 )；宿主型語言（一般可嵌入某些宿主語言中）。數(shù)據(jù)庫管理員：對數(shù)據(jù)庫進行規(guī)劃、設計、維護、監(jiān)視等的專業(yè)管理人員。數(shù)據(jù)庫系統(tǒng)：由數(shù)據(jù)庫（數(shù)據(jù)） 、數(shù)據(jù)庫管理系統(tǒng)（軟件） 、數(shù)據(jù)庫管理員（人員） 、硬件平臺（硬件） 、軟件平臺（軟件）五個部分構(gòu)成的運行實體。對數(shù)據(jù)庫系統(tǒng)需要操作系統(tǒng)的支持.數(shù)據(jù)庫應用系統(tǒng)：由數(shù)據(jù)庫系統(tǒng)、應用軟件及應用界面三者組成。數(shù)據(jù)管理發(fā)展的三個階段：人工管理階段，文件系統(tǒng)階段，數(shù)據(jù)庫系統(tǒng)階段。而

36、數(shù)據(jù)獨立性最高的是數(shù)據(jù)庫系統(tǒng)。文件系統(tǒng)階段：提供了簡單的數(shù)據(jù)共享與數(shù)據(jù)管理能力，但是它無法提供完整的、 統(tǒng)一的、管理和數(shù)據(jù)共享的能力。層次數(shù)據(jù)庫與網(wǎng)狀數(shù)據(jù)庫系統(tǒng)階段：為統(tǒng)一與共享數(shù)據(jù)提供了有力支撐。數(shù)據(jù)庫系統(tǒng)的基本特點：數(shù)據(jù)的集成性、數(shù)據(jù)的高共享性與低冗余性、數(shù)據(jù)獨立性（物理獨立性與邏輯獨立性） 、數(shù)據(jù)統(tǒng)一管理與控制。物理獨立性：用戶的應用程序與存儲在磁盤在磁盤等介質(zhì)上的數(shù)據(jù)庫是相互獨立的。數(shù)據(jù)庫系統(tǒng)的三級模式：（1）概念模式：數(shù)據(jù)庫系統(tǒng)中全局數(shù)據(jù)邏輯結(jié)構(gòu)的描述，全體用戶公共數(shù)據(jù)視圖；（2）外模式：也稱子模式與用戶模式。是用戶的數(shù)據(jù)視圖，也就是用戶所見到的數(shù)據(jù)模式；（3）內(nèi)模式：又稱物理模式，

37、它給出了數(shù)據(jù)庫物理存儲結(jié)構(gòu)與物理存取方法。數(shù)據(jù)庫系統(tǒng)的兩級映射：（1）概念模式到內(nèi)模式的映射；（2）外模式到概念模式的映射。4.24.2 數(shù)據(jù)模型數(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ù)約束。關系模型屬于非格式化模型，而模型和網(wǎng)狀模型屬于格式化模型。e-r 模型(實體聯(lián)系模型)的基本概念（1）實體：現(xiàn)實世界中的事物；（2）屬性：事物的特性；（3）聯(lián)系：現(xiàn)實世界中事物間的關系。實體集間的聯(lián)系有一對一、一對多、多對多的聯(lián)系。e-r 模型基本概念之間的聯(lián)接關系：實體是概念世

38、界中的基本單位，屬性有屬性域，每個實體可取屬性域內(nèi)的值。一個實體的所有屬性值叫元組。e-r 模型的圖示法：（1）實體集表示法矩形；（2）屬性表法橢圓形； （3）聯(lián)系表示法菱形。層次模型的基本結(jié)構(gòu)是樹形結(jié)構(gòu)，具有以下特點：（1）每棵樹有且僅有一個無雙親結(jié)點，稱為根；（2）樹中除根外所有結(jié)點有且僅有一個雙親。從圖論觀點看，網(wǎng)狀模型是一個不加任何條件限制的無向圖。關系模型是數(shù)學化的模型。要用到集合論、離散數(shù)學等理論知識。關系模型采用二維表來表示，簡稱表 ，由表框架及表的元組組成。一個二維表就是一個關系。每行數(shù)據(jù)稱為元組。在二維表中凡能唯一標識元組的最小屬性稱為鍵或碼。從所有侯選鍵中選取一個作為用戶使

39、用的鍵稱主鍵。表 a 中的某屬性是某表 b 的鍵，則稱該屬性集為 a 的外鍵或外碼。關系中的數(shù)據(jù)約束：（1）實體完整性約束：約束關系的主鍵中屬性值不能為空值；（2）參照完全性約束：是關系之間的基本約束；（3）用戶定義的完整性約束：它反映了具體應用中數(shù)據(jù)的語義要求。4.34.3 關系代數(shù)關系代數(shù)關系數(shù)據(jù)庫系統(tǒng)的特點之一是它建立在數(shù)據(jù)理論的基礎之上，有很多數(shù)據(jù)理論可以表示關系模型的數(shù)據(jù)操作，其中最為著名的是關系代數(shù)與關系演算。關系數(shù)據(jù)庫管理系統(tǒng)能實現(xiàn)的專門關系運算包括：選擇、投影、連接。關系模型的基本運算：（1）插入（2）刪除(3)修改（4）查詢（包括投影、選擇、笛卡爾積運算）還有擴充運算交、除、

40、連接及自然連接運算。在關系運算中，連接運算后得到的新表的屬性是運算前表中屬性相加。即多于原來關系中屬性的個數(shù)。4.44.4 數(shù)據(jù)庫設計與管理數(shù)據(jù)庫設計與管理數(shù)據(jù)庫設計是數(shù)據(jù)應用的核心 。數(shù)據(jù)庫設計的根本目標是解決數(shù)據(jù)共享問題.數(shù)據(jù)庫設計的兩種方法：（1）面向數(shù)據(jù)：以信息需求為主，兼顧處理需求；（2）面向過程：以處理需求為主，兼顧信息需求。數(shù)據(jù)庫的生命周期：需求分析階段、概念設計階段、邏輯設計階段、物理設計階段、編碼階段、測試階段、運行階段、進一步修改階段。數(shù)據(jù)庫設計分為四個階段：需求分析階段，概念設計階段，邏輯設計階段，物理設計階段。需求分析常用結(jié)構(gòu)析方法和面向?qū)ο蟮姆椒?。結(jié)構(gòu)化分析（簡稱

41、sa）方法用自頂向下、逐層分解的方式分析系統(tǒng)。用數(shù)據(jù)流圖表達數(shù)據(jù)和處理過程的關系。 對數(shù)據(jù)庫設計來講，數(shù)據(jù)字典是進行詳細的數(shù)據(jù)收集和數(shù)據(jù)分析所獲得的主要結(jié)果。數(shù)據(jù)字典是各類數(shù)據(jù)描述的集合，包括 5 個部分：數(shù)據(jù)項、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)流（可以是數(shù)據(jù)項，也可以是數(shù)據(jù)結(jié)構(gòu)） 、數(shù)據(jù)存儲、處理過程。數(shù)據(jù)庫概念設計的目的是分析數(shù)據(jù)內(nèi)在語義關系。設計的方法有兩種（1）集中式模式設計法（適用于小型或并不復雜的單位或部門） ；（2）視圖集成設計法。使用 e-r模型與視圖集成進行設計。視圖設計一般有三種設計次序：自頂向下、由底向上、由內(nèi)向外。視圖集成的幾種沖突：命名沖突、概念沖突、域沖突、約束沖突。關系視圖設計又稱

42、外模式設計。關系視圖的主要作用：（1）提供數(shù)據(jù)邏輯獨立性； （2）能適應用戶對數(shù)據(jù)的不同需求； （3）有一定數(shù)據(jù)保密功能。數(shù)據(jù)庫的物理設計主要目標是對數(shù)據(jù)內(nèi)部物理結(jié)構(gòu)作調(diào)整并選擇合理的存取路徑， 以提高數(shù)據(jù)庫訪問速度有效利用存儲空間。一般rdbms 中留給用戶參與物理設計的內(nèi)容大致有索引設計、集成簇設計和分區(qū)設計。數(shù)據(jù)庫管理的內(nèi)容：（1）數(shù)據(jù)庫的建立； （2）數(shù)據(jù)庫的調(diào)整； （3）數(shù)據(jù)庫的重組；（4）數(shù)據(jù)庫安全性與完整性控制；（5）數(shù)據(jù)庫的故障恢復； （6）數(shù)據(jù)庫監(jiān)控。使用說明：公共基礎的復習沒有技巧，就是背誦、背誦、再背誦，就是要把這 10 頁紙背下來。劃線字體是至關重要的部分，框起來的字體

43、為填空題的常考詞匯，一定要背熟牢記，這里面有 100 分里 30 分的原題。復習及應試建議：1考生的復習必須遵守：“80/20 的原則”二級考試的公共知識部分的覆蓋面廣，至少涵蓋了計算機應用專業(yè)的四門核心課程：算法及數(shù)據(jù)結(jié)構(gòu)、程序設計基礎、軟件工程基礎和數(shù)據(jù)庫。事實上，這些課程本身的涉及面就很廣，難度系數(shù)較大。因此，這些課程甚至也是計算機專業(yè)學生最頭疼的課程，對大多數(shù)考生來說其難度之大不言而喻。所以，考生應把 80%的時間用在 20%的重點知識點上，爭取用 20%的重點知識點來答對 80%的考題，這是考生復習二級考試的公共知識部分的總體思路。2復習的關鍵是考生必須準確判斷和掌握常見考點考生必須

44、能夠準確判斷和掌握常見考點，例如： 算法部分主要考查算法的概念及算法的復雜度；數(shù)據(jù)結(jié)構(gòu)部分主要考查最基本的概念、最典型的數(shù)據(jù)結(jié)構(gòu)和最常見的操作；程序設計部分主要考查程序設計風格的基本要求、 結(jié)構(gòu)化程序設計的最基本知識和面向?qū)ο蟪绦蛟O計的最常見概念； 軟件工程基礎部分主要考查軟件工程的基本概念及軟件生命周期的各個階段的基礎知識；數(shù)據(jù)庫基礎部分主要考查數(shù)據(jù)庫基本概念、數(shù)據(jù)模型、關系代數(shù)基礎知識、數(shù)據(jù)庫設計方法和步驟。對常見考點的準確把握會使考生避免盲目學習，從而能夠輕松面對考試。3 考生必須在準確把握知識點的基礎上，學會把“知識點”連成“知識鏈”，并把 “知識鏈”織成“知識網(wǎng)”。很多考生在復習該部

45、分時都會發(fā)現(xiàn)一個問題， 例如： 內(nèi)容零散， 知識點之間的跳躍性大，似乎沒有連續(xù)性。所以掌握起來很困難，似懂非懂，對知識點處于模糊認知狀態(tài)。4 考生一定不要采取題海戰(zhàn)術，更不能在知道正確答案的同時記住三個錯誤答案。對二級考試公共知識部分， 沒有必要做大量的題目， 更不能為了應付考試記住一大堆錯誤答案，只記住正確答案就可以了。這是多數(shù)考生常犯的錯誤之一。5 考生不要太追求靈活掌握該部分的內(nèi)容，最好經(jīng)歷一個“先死后活、熟能生巧”的過程，這是多數(shù)考生常犯的另一種錯誤。二級考試中要求的知識點都是最基本的、最簡單的，真正需要“靈活”掌握的考點極少。很多考生在考試過程中可能已經(jīng)發(fā)現(xiàn)，該部分的題目“會做就是不懂”。所以建議在復習過程中不要急于“靈活”，其實等到把基本的知識點掌握后自然就“靈活”了。6 最后給大家一個答題技