1、全國計算機等級考試全國計算機等級考試二級公共基礎知識二級公共基礎知識第一章 數據結構與算法n 考試大綱1. 算法的基本概念；算法復雜度的概念和意義（時間復雜度與空間復雜度）。2. 數據結構的定義；數據的邏輯結構與存儲結構；數據結構的圖形表示；線性結構與非線性結構的概念。3. 線性表的定義；線性表的順序存儲結構及其插入與刪除運算。4. 棧和隊列的定義；棧和隊列的順序存儲結構及其基本運算。5. 線性單鏈表、雙向鏈表與循環鏈表的結構及其基本運算。6. 樹的基本概念；二叉樹的定義及其存儲結構；二叉樹的前序、中序和后序遍歷。7. 順序查找與二分法查找算法；基本排序算法（交換類排序，選擇類排序，插入類排序

2、）。知識點歸納n算法的基本概念n所謂算法是指解題方案的準確而完整的描述。嚴格來說，一個算法必須具有以下五個主要特征：算法的基本特征算法的基本特征一個算法應該具有以下五個重要的特征：一個算法應該具有以下五個重要的特征：n 有窮性有窮性n 確定性確定性n 輸入輸入n 輸出輸出n 可行性可行性一個算法必須保證執行有限步之后結束；算法的每一步驟必須有確切的定義；一個算法有0個或多個輸入，以刻畫運算對象的初始情況，所謂0個輸入是指算法本身定義了初始條件；一個算法有一個或多個輸出，以反映對輸入數據加工后的結果。沒有輸出的算法是毫無意義的；算法原則上能夠精確地運行算法的基本概念n算法的組成要素n算法中對數據

3、的運算和操作n算法的控制結構n算法設計基本方法n列舉法n歸納法n遞推n遞歸n減半遞推n回溯法n 算術運算算術運算n 關系運算關系運算n 邏輯運算邏輯運算n 數據傳輸數據傳輸n 順序順序n 選擇選擇n 循環循環算法的復雜度n算法的復雜度可分為時間復雜度和空間復雜度，是衡量算法優劣的量度。1.算法的時間復雜度n算法的時間復雜度是指執行算法所需要的工作量。一般情況下，算法中的基本基本操作重復執行的次數操作重復執行的次數是問題規模n的某個函數f(n)f(n)。算法的復雜度n算法的空間復雜度n算法的空間復雜度是指執行這個算法所需要的內存空間?？臻g復雜度作為算法所需存儲空間的量度數據結構n利用計算機進行數

4、據處理是計算機應用的一個重要領域。數據結構主要研究和討論以下三個方面的問題：n數據集合中各數據元素之間的邏輯關系，即數據的邏輯結構。n在對數據進行處理時，各數據元素在計算機中的存儲關系，即數據的存儲結構。1.對各種數據結構進行的運算。數據的邏輯結構n數據邏輯結構是對數據元素之間存在的邏輯關系的描述，它可以用一個數據元素的集合和定義在此集合上的若干關系表示。n與數據在計算機中的存儲位置無關，是獨立于計算機的。 線性結構和非線性結構線性結構n在數據元素的非空有限集合中，線性結構的邏輯特征如下：n存在一個唯一的被稱為“第一個”的數據元素n存在一個唯一的被稱為“最后一個”的數據元素n除第一個之外，集合

5、中的每個數據元素均有且只有一個直接前驅n除最后一個之外，集合中的每個數據元素均有且只有一個直接后繼非線性結構n非線性結構的邏輯特征是：一個結點可能有多個直接前驅和直接后繼，樹和圖都屬于非線性結構。數據的存儲結構n數據的存儲結構是數據元素及其關系在計算機存儲器中的表示。存儲結構的主要內容是指在存儲空間中使用一個存儲結點來存儲一個數據元素，在存儲空間中建立各存儲結點之間的關聯，來表示數據元素之間的邏輯關系。n常見的存儲結構：n順序存儲結構n鏈式存儲結構n索引存儲結構n散列存儲結構線性表n通常以下列 n 個數據元素的序列”表示線性表線性表 ：(a1,a2 ,.,ai ,.,an) n序列中數據元素的

6、個數 n 定義為線性表的表長表長；n=0 時的線性表被稱為空表空表。稱 i 為ai在線性表中的位序位序。線性表的順序存儲n線性表的順序存儲結構用一組地址連續地址連續的存儲單元依次存放依次存放線性表中的數據元素，即以“存儲位置相鄰存儲位置相鄰”表示“位序相繼的兩個數據元素之間的前驅和后繼的關系，并以表中第一個元素的存儲位置作為線性表的起始地址，稱作線性表的基地址線性表的基地址。 所有數據元素的存儲位置均可由第一個數據元素的存儲位置得到 ADR(ai) = ADR(a1) + (i-1)C 基地址基地址 一個數據元素所占存儲量一個數據元素所占存儲量 線性表的插入和刪除運算n插入運算是指在線性表的某

7、個指定位置增加一個新結點。n一般情況下，要在第i(1in)個元素之前插入一個新元素時，首先要從最后一個元素開始，直到第i個元素之間共n-i+1個元素依次向后移動一個位置，然后將新元素插入到第i項。n刪除運算是指撤銷結構中的某個結點。n一般情況，要刪除第i(1in)個元素，要從第i+1個元素開始，直到第n個元素，共n-i個元素依次向前移動一個位置。棧n棧是限定僅在表的一端進行插入和刪除操作的線性表。允許插入和刪除的一端稱為棧頂，另一端稱為棧底。n棧頂元素總是最后被插入的元素，從而也是最先被刪除的元素；棧底元素總是最先被插入，也是最后被刪除的元素。因此，棧是一種后進先出后進先出(也稱先進后出）也稱

8、先進后出）的線性表。n通常用指針top指示棧頂位置，用指針bottom指示棧底位置。棧的順序存儲及運算n用一維數組S(1:m)作為棧的順序存儲空間，m為棧的最大容量。top=0表示棧為空，top=m表示棧滿。n棧的操作n入棧：在棧頂位置插入一個新元素，棧頂指針top加1。n退棧：取出棧頂元素并賦值給一個指定的變量，棧頂指針top減1。n取棧頂元素：將棧頂元素的值賦給一個指定的變量，不刪除棧頂元素，棧頂指針不變。隊列n隊列是一種先進先出的線性表，它只允許在表的一端插入元素(隊尾)，在另一端刪除元素(隊頭)。通常定義頭指針front指向隊頭元素的前一個位置，定義尾指針rear指向隊尾元素的位置。n

9、隊列是一種先進先出（也稱后進后出）先進先出（也稱后進后出）的線性表線性表。n向隊尾插入一個元素的操作稱為入隊，從隊頭刪除一個元素的操作稱為退隊。循環隊列n將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環狀空間。n循環隊列初始狀態為空，即front=rear=m。n入隊操作時，rear加1，若rear=m+1，則置rear=1；n退隊操作時，front加1，若front=m+1，則置front=1。n在循環隊列為空或為滿時，均有front=rear，因此需要設置標志s進行區分，定義s=0表示隊列為空，s=1表示隊列非空。單鏈表n線性表的鏈式存儲結構的特點是用一組任意的存儲單元(可以連續

10、，也可以不連續)存儲線性表的數據元素，為了表示每個數據元素ai與其直接后繼元素ai+1之間的邏輯關系，對數據元素ai來說，除了存儲其本身的信息(數據域)之外，還需要存儲其后繼元素的存儲位置信息(指針域)。n指針域中存儲的信息稱為指針或鏈，N個結點鏈接成一個鏈表，即為線性表的鏈式存儲結構。由于結點中只包含一個指針域，故稱為單鏈表。單鏈表n通常以單鏈表中第一個數據元素的存儲地址作為作為單鏈表的地址，稱為頭指針。整個鏈表的存儲必須從頭指針開始(順序存取)，頭指針指示鏈表中第一個結點的存儲位置。最后一個數據元素沒有直接后繼，其指針域為空。單鏈表的插入和刪除雙向鏈表和循環鏈表n在雙向鏈表中的結點包含兩個

11、指針域，其中一個指向直接后繼，另一個指向直接前驅。n循環鏈表的特點是表中最后一個結點的指針域指向第一個結點，整個鏈表成為一個由鏈指針相鏈接的環。據此，從表中任一節點出發均可找到表中其它結點。在循環鏈表中增加了一個表頭結點，其指針域指向第一個元素結點，頭指針則指向頭結點。HEADHEADHEADHEADHEADHEAD樹及其基本概念n樹是一種簡單的非線性結構，在樹中，所有的數據元素之間具有明顯的層次性關系。n樹是(n0)個結點的有限集合，在任意一棵非空樹中： (1)有且僅有一個特定的結點稱為根結點。 (2)當n1時，其余的結點可分為m個互不相交的子集T1,T2,Tm，其中每個有限子集本身又是一棵

12、樹，并且稱為根的子樹。n集合為空的樹簡稱為空樹；樹中的元素稱為結點。ABDFECGHIJKMn 一個結點的子樹的一個結點的子樹的個數；個數； Q：結點結點A、G的度數？的度數？n 樹中所有結點度的最樹中所有結點度的最大值；大值；Q：右圖中樹的度？右圖中樹的度？n 度為度為0的結點；的結點； Q：圖中葉子結點有幾個？圖中葉子結點有幾個？7 度不為度不為0的結點；的結點； Q：圖中非終端結點有幾個？圖中非終端結點有幾個？ 5ABDFECGHIJKMn 樹中根結點的層樹中根結點的層次為次為1，根結點子樹的根為第，根結點子樹的根為第2層，層，以此類推；以此類推；樹中所有結點層次的樹中所有結點層次的最大

13、值；最大值； Q：圖中樹的深度？圖中樹的深度？二叉樹n二叉樹是n(n0)個數據元素的有限集，它或為空集,或者含有唯一的稱為根的元素，且其余元素分成兩個互不相交的子集，每個子集自身也是一棵二叉樹，分別稱為根的左子樹和右子樹。n二叉樹是另一種樹型結構，其特點是每個結點至多有兩棵子樹，并且二叉樹的子樹有左右之分，其順序不能任意顛倒。二叉樹的基本性質n性質性質1 1 在二叉樹的第i層上至多有2i-1個結點（i1）n性質性質2 2 深度為k的二叉樹至多有2k -1個結點（k1）n性質性質3 3 對任何一棵二叉樹T，如果其終端結點數為n0，度為2的結點數為n2 ，則：n0 =n2+1n性質性質4 4 具有

14、n個結點的二叉樹，其深度至少為log2n +1滿二叉樹和完全二叉樹n滿二叉樹滿二叉樹除最后一層外，每一層上的所有結點都有兩個子節點，也就是說每一層上的結點數都達到最大值，即在滿二叉樹的第k層上有2k-1個結點，且深度為m的滿二叉樹有2m-1個結點。n完全二叉樹完全二叉樹除最后一層外，每一層上的結點數均達到最大值，在最后一層上只缺少右邊的若干結點（即在最后一層按從右向左依次刪除若干節點）。具有n個結點的完全二叉樹，其深度為log2n +1。n從以上定義可知，滿二叉樹也是完全二叉樹，反之則不然。滿二叉樹滿二叉樹 最大層的結點最大層的結點均向左靠齊均向左靠齊 完全二叉樹完全二叉樹 ADCBEF二叉樹

15、的基本性質性質性質5 5 如果對一棵有 n 個結點的完全二叉樹（其深度為log2n +1）的結點按層序（從第1層到第log2n +1 層，每層從左到右）從1起開始編號，則對任一編號為 i 的結點(1in)，則:(1) 如果 i=1，則編號為 i 的結點是二叉樹的根，無雙親；如果 i1，則其雙親結點 parent(i)的編號是i/2。(2) 如果 2in，則編號為 i 的結點無左孩子（編號為 i 的結點為葉子結點）；否則其左孩子結點 lChild(i) 的編號是 2i 。(3) 如果 2i+1n，則編號為 i 的結點無右孩子；否則其右孩子結點 rChild(i) 的編號是結點 2i+1。 二叉樹

16、的鏈式存儲結構n在二叉樹的鏈式存儲結構中，每個結點設置三個域，即數據域，左指針域和右指針域，兩個指針域分別存儲左右子樹根節點的存儲位置，即指針。L(i)V(i)R(i)LchildvalueRchild二叉樹的鏈式存儲結構二叉樹的遍歷n二叉樹的遍歷指不重復地訪問二叉樹的所有結點。從二叉樹的結構定義得知，二叉樹是由根結點、左子樹和右子樹三部分構成，則遍歷二叉樹的操作可分解為訪問根結點、遍歷左子樹和遍歷右子樹三個子操作，并且由二叉樹的遞歸定義可知，遍歷左子樹和遍歷右子樹可如同遍歷二叉樹一樣遞歸進行。 先序遍歷二叉樹先序遍歷二叉樹中序遍歷二叉樹中序遍歷二叉樹后序遍歷二叉樹后序遍歷二叉樹若二叉樹為空，

17、則空操作；否則(1) 訪問根結點；(2) 先序遍歷左子樹；(3) 先序遍歷右子樹。 若二叉樹為空，則空操作；否則(1) 中序遍歷左子樹；(2) 訪問根結點；(3) 中序遍歷右子樹。 若二叉樹為空，則空操作；否則(1) 后序遍歷左子樹；(2) 后序遍歷右子樹；(3) 訪問根結點。二叉樹的遍歷先序遍歷：ABDEGHCFIJ中序遍歷：DBGEHACIJF后序遍歷：DGHEBJIFCA查找n查找是指在一個給定的數據結構中查找某個指定的元素。n順序查找n順序查找一般是指在線性表中查找指定元素，基本方法如下：從線性表的第一個元素開始，依次將線性表中的元素與被查找元素進行比較，若相等則表示找到，即查找成功；

18、若線性表中的所有元素與被查找元素都不相等，則查找失敗。n順序查找：最好情況比較1次，最壞情況比較n次n如果線性表為無序表，即表中元素的排列是無序的，則不管線性表采用順序存儲還是鏈式存儲，都必須使用順序查找。n如果線性表有序，但采用鏈式存儲結構，則也必須使用順序查找。查找n二分查找(折半查找)n二分查找法只適用于順序存儲的有序表順序存儲的有序表。先確定待查目標元素所在范圍(區間)，然后逐步縮小范圍直至找到該元素，或者當查找區間縮小到0也沒有找到目標元素為止。n查找過程中，給定值首先和處于待查區間中間位置的關鍵字進行比較，若相等，則查找成功，否則將查找區間縮小到前半個區間 或 后半個區間 之后繼續

19、進行查找。折半查找二分查找查找 二分查找(折半查找)：由于每次都可以減少一半的元素，所以最壞時間復雜度為log(2n) 比如：在n=1024數中二分查找，最多只需要比較10次排序n排序是指將一個無序序列整理成按值遞增或遞減(本章均采用遞增規則)的有序序列。n排序可以在各種不同的存儲結構上實現，本章所介紹的算法以順序存儲的線性表為排序對象，在程序設計語言中就是一維數組。n排序的算法種類很多，主要包括交換類排序、插入類排序、選擇類排序等。交換類排序法交換類排序法 n冒泡排序冒泡排序n快速排序快速排序 插入類排序法插入類排序法n簡單插入排序簡單插入排序n希爾排序希爾排序選擇類排序法選擇類排序法n簡單

20、選擇排序簡單選擇排序n堆排序堆排序最壞時間復雜度：最壞時間復雜度：n冒泡排序法、快速排序、簡單選擇排序法、簡單插冒泡排序法、快速排序、簡單選擇排序法、簡單插入排序：入排序： 最壞情況需要最壞情況需要n(n-1)/2次比較；次比較；n希爾排序法：希爾排序法： 最壞情況需要最壞情況需要O(n1.5)次比較；次比較；n堆排序法堆排序法, 最壞情況需要最壞情況需要O(nlog2n)次比較；次比較； 平均速度最快排序：平均速度最快排序：快速排序快速排序最好、最壞、平均三種復雜度都相同的排序方法：最好、最壞、平均三種復雜度都相同的排序方法：堆排序堆排序第二章 程序設計基礎n考試大綱n1. 程序設計方法與風

21、格。2. 結構化程序設計。3. 面向對象的程序設計方法，對象，方法，屬性及繼承與多態性。 知識點歸納n程序設計方法n程序設計是一門技術，需要相應的理論、方法和工具來支持。就程序設計方法和技術的發展而言，主要經歷了結構化的程序設計和面向對象的程序設計階段。n在程序設計中，通常采用“自頂向下，逐步求精”的方法，即把一個模塊的功能逐步分解，細化為一系列具體的步驟，進而轉換成一系列用某種程序設計語言編寫的程序。n程序設計口號是：清晰第一，效率第二清晰第一，效率第二程序設計風格n除了程序設計設計方法和技術之外，程序風格也是非常重要的。良好的程序設計風格概括起來包括以下及格方面：n源程序文檔化n數據說明的

22、方法n語句的結構n輸入和輸出程序設計風格n源程序文檔化n標識符的命名n程序的注釋n序言性注釋n功能性注釋n程序的視覺組織n數據的說明n數據說明的次序應該規范化n說明語句中變量的安排有序化n使用注釋說明復雜的數據結構程序設計風格n語句結構語句結構n在一行內只寫一條語句n程序編寫應優先考慮清晰性n除非對效率有特殊要求，程序編寫要做到清晰第一，效率第二n首先要保證程序正確，然后才要求提高速度n避免使用臨時變量而使程序的可讀性下降n避免不必要的轉移n盡可能使用庫函數n避免使用復雜的條件語句n盡量減少使用“否定”條件的條件語句n數據結構要有利于程序的簡化n要模塊化，使模塊功能盡可能單一化n利用信息隱蔽，

23、確保每一個模塊的獨立性n從數據出發構造程序n不要修補不好的程序，要重寫編寫程序設計風格n輸入和輸出n對所有輸入數據檢驗合法性n檢查輸入項的各種重要組合的合法性n輸入格式要簡單，以使輸入的步驟和操作盡可能簡單n輸入數據時，應允許使用自由格式n應允許缺省值n輸入一批數據時，最好使用輸入結束標志n在以交互式輸入/輸出方式進行輸入時，要在屏幕上使用提示符明確提示輸入的請求，同時在數據輸入結束時，應在屏幕上給出狀態信息n當程序設計語言對輸入格式有嚴格要求時，應保持輸入格式與輸入語句的一致性；給所有的輸出加注釋，并設計輸出報表格式。結構化程序設計n結構化程序設計的原則n自頂向下自頂向下。程序設計時，應先考

24、慮總體，后考慮細節；先考慮全局目標，后考慮局部目標。不要一開始就過多追求細節，先從最上層總目標開始設計，逐步使問題具體化。n逐步求精逐步求精。對復雜的問題，應設計一些子目標過渡，逐步細化。n模塊化模塊化。一個復雜問題肯定是有若干簡單問題構成。模塊化是把程序要解決的總目標分解為分目標，再進一步分解為具體的小目標，每個小目標成為一個模塊。n限制使用限制使用GOTOGOTO語句語句。結構化程序設計的基本結構和特點n程序由一些基本結構組成，任何一個程序都可以用三種基本控制結構組成：順序結構、選擇結構和循環結構，并且具有如下特點：單入口、單出口、結構中無死循環，程序中三種基本控制結構之間形成順序執行關系

25、。n一個大型程序應按功能分割成一些模塊，并把這些模塊按層次關系進行組織。n在程序設計時應采用自頂向下、逐步細化的實施方法。面向對象程序設計n 面向對象方法的基本概念1.對象、類和屬性 在面向對象程序設計中，對象是程序的基本單位。對象可以表示客觀世界中的任何實體，是對問題域中某個實體的抽象。n每個對象可以用它本身的一組屬性和它可以執行的一組操作來定義每個對象可以用它本身的一組屬性和它可以執行的一組操作來定義。n類是對一組具有共同屬性和相似行為的對象的一種抽象類是對一組具有共同屬性和相似行為的對象的一種抽象，描述了屬于該類的所有對象的性質。n類是對象的模板或框架，對象是類的實例類是對象的模板或框架

26、，對象是類的實例 對象的基本特點：對象的基本特點： 1 1）標識唯一性；）標識唯一性；2 2）分類性；）分類性；3 3）多態性）多態性 4 4）封裝性：）封裝性：信息隱蔽信息隱蔽模塊獨立模塊獨立 5 5）模塊獨立性好。）模塊獨立性好。 2.方法 方法有稱為操作或服務，它描述了對象執行的功能，若通過消息傳遞，還可為其他對象使用。面向對象方法的基本概念3.3.繼承：繼承：繼承是對象方法的一個重要特征。指一個類指一個類( (子類子類) )直接使用另一個直接使用另一個類類( (父類父類) )的所有屬性和方法。的所有屬性和方法。它可以減少相似類的重復說明，從而體現一般性和特殊性的原則。4.4.多態性：多

27、態性：多態性可以用“一個對外界面，多個內部實現”來表示?？梢酝ㄟ^方法重載和方法重寫來實現多態。重載指一個類中可以有多個具有相同名稱的方法，由傳遞給它們的不同個數和類型的參數來決定執行那個方法。重寫指子類可以重新實現父類的某些方法，使其具有自己的特征。多態性機制增加了面向對象軟件系統的靈活性，提高了軟件的可重用性和可擴充性。5.5.消息：消息：面向對象系統中的對象之間是通過消息機制彼此相互合作的，消息是一個對象與另一個對象之間傳遞的信息，它請求對象執行某一處理或回答某一要求的信息。面向對象程序設計的特點n按照人的思維方式對客觀世界進行抽象n穩定性好n可重用性好n易于開發大型軟件n可維護性好第三章

28、 軟件工程基礎n考試大綱n1. 軟件工程基本概念，軟件生命周期的概念，軟件工具與軟件開發環境。2. 結構化分析方法，數據流圖，數據字典，軟件需求規格說明書。3. 結構化設計方法，總體設計與詳細設計。4. 軟件測試的方法，白盒測試與黑盒測試，測試用例設計，軟件測試的實施，單元測試、集成測試和系統測試。5. 程序的調試，靜態調試與動態調試。 知識點歸納n軟件定義和特點n計算機軟件式計算機系統中與硬件相互依存的另一部分，是包括程序、數據及相關文檔的完整集合。 軟件程序軟件程序+數據數據+文檔文檔計算機軟件具有如下特點：n軟件是一種邏輯實體，具有抽象性n軟件生產沒有明顯的制造過程n軟件在運行、使用期間

29、不存在磨損、老化問題n軟件的開發、運行對計算機系統具有依賴性n軟件復雜性高，成本昂貴n軟件開發涉及諸多社會因素軟件危機n所謂軟件危機是指在計算機軟件開發和維護過程中所遇到的一系列嚴重問題，包括：n軟件需求的增長得不到滿足n軟件開發成本和進度無法控制n軟件質量難以保證n軟件不可維護或可維護性低n軟件成本不斷提高n軟件開發生產率的提高趕不上硬件的發展和應用需求的增長。歸結起來主要包括三個方面：成本、質量、效率成本、質量、效率軟件工程n為了消除軟件危機，提出了軟件工程學。軟件工程是應用于計算機軟件定義、開發和維護的一整套方法、工具、文檔、實踐標準和工序。n軟件工程的三要素n方法：指技術手段方法：指技

30、術手段n工具：硬件和軟件工具工具：硬件和軟件工具n過程：過程中控制和管理過程：過程中控制和管理軟件工程過程n軟件工程過程是把輸入轉化為輸出的一組彼此相關的資源和活動。它包括兩方面含義：n1. 軟件工程過程是指為獲得軟件產品，在軟件工具支持下由軟件工程師完成的一系列工程活動。通常包括四種基本活動：nP(Plan)：軟件規格說明nD(Do)：軟件開發nC(Check)：軟件確認nA(Action)：軟件演進n2.從軟件開發的觀點看，軟件工程過程是使用適當的資源，為開發軟件進行的一組開發活動，在活動結束時將輸入(用戶需求)轉化為輸出(軟件產品)。軟件生命周期n軟件從提出、實現、使用、維護到停止使用的

31、過程稱為軟件的生命周期。一般包括以下幾個階段：可行性研究與計劃制定需求分析軟件設計軟件實現軟件測試運行和維護定義階段開發階段（使用）維護階段軟件工程目標與原則n軟件工程的目標是在給定成本、進度的前提下，開發出具有有效性、可靠性、可理解性、可維護性、可重用性、可適應性、可移植性、可追蹤性和可互操作性且滿足用戶需求的軟件產品。n為達到上述目標，在軟件開發的過程中，必須遵循軟件工程的基本原則：n抽象n信息隱蔽n模塊化n局部化n確定性n一致性n完備性n可驗證性軟件開發工具與軟件開發環境n軟件開發工具對過程和方法提供自動或半自動的支持。當這些工具被集成起來使得一個工具產生的信息可以被另外一個工具使用時，

32、一個支持軟件開發的系統就建立起來了，稱為計算機輔助軟件工程(CASE)。CASE集成了軟件、硬件和一個軟件工程數據庫(包含了有關分析、設計、程序構造和測試的重要信息)從而創建了一個軟件開發環境。結構化分析方法n結構化分析方法大多使用自頂向下、逐層分解的系統分析方法來定義系統需求。在結構化分析的基礎上，完成系統的規格說明，建立系統的一個自頂向下的任務分析模型。結構化分析方法是一種建模技術，模型的核心是數據辭典，它描述了所有在目標系統中使用和生成的數據對象。結構化分析常用的工具：n數據流圖(DFD):描述數據在系統中如何被傳送或變換以及描述如何對數據流進行變換的功能，用于功能建模。n數據字典n判定

33、樹n判定表數據流圖(DFD)n數據流圖是描述數據處理過程的工具，它從數據傳遞和加工的角度，來刻畫數據流從輸入系統到從系統輸入的移動變換過程。n數據流圖的基本元素n外部實體(源，潭）n數據流 n處理(加工)n數據存儲數據字典（DD）n數據字典是關于數據的信息的集合，對數據流圖中的各個元素進行完整的定義和說明。數據流圖和數據字典共同構成系統的邏輯模型。n數據字典通常包含的信息有：名稱、別名、何處使用、如何使用、內容描述以及補充信息等。軟件需求n軟件需求包括：功能需求、性能需求、環境需求、可靠性需求、安全保密需求、用戶界面需求、資源使用需求、成本消耗需求、開發進度需求等。n需求分析應交付的主要文檔是

34、軟件需求軟件需求規格說明書規格說明書(SRS)(SRS)。結構化設計n結構化設計就是采用最佳的可能方法設計系統的各個組成部分以及個成分之間的內部聯系的技術。也就是說，結構化設計是這樣一個過程：它決定用哪些方法把哪些部分聯系起來，才能解決好某個具體的有清楚定義的問題。從工程管理的角度看，軟件設計分兩步完成：n1.1.概要設計，即總體設計概要設計，即總體設計。將軟件需求轉化為數據結構和軟件的系統結構(即劃分功能模塊）。常用的軟件結構設計工具是結構圖(SC-Structure Chart)。n2.2.詳細設計：詳細設計：即過程設計。通過對結構表示進行細化，得到軟件詳細的數據結構和算法。過程設計常用的

35、工具有：程序流程圖（PFD)、N-S圖、PAD圖、過程設計語言PDL(偽碼)。軟件測試n定義：n使用人工或自動手段來運行或測定某個系統的過程，其目的在于檢驗它是否滿足規定的需求或弄清預期結果與實際結果之間的差別。n軟件測試是為了發現錯誤而執行程序的過程。軟件測試是為了發現錯誤而執行程序的過程。n一個好的測試用例是指可能找到迄今為止尚未發現的錯誤的用例。n一個成功的測試是發現了至今尚未發現的錯誤的測試。n測試不能表明軟件中不存在錯誤。測試技術與方法綜述n從是否需要執行被測試軟件的角度，可將測試分為靜態測試和動態測試。n靜態測試主要包括代碼檢查、靜態結構分析、代碼質量度量等(不運行程序）。n動態測

36、試是基于計算機的測試，是為了發現錯誤而執行程序的過程，或者說，是根據軟件開發的各個階段的規格說明和程序的內部結構而精心設計的一批測試用例，并利用這些測試用例去運行程序，以發現程序錯誤的過程。測試技術與方法綜述n按照功能劃分，可將軟件測試分為黑盒測試和白盒測試。n黑盒測試將測試對象看作一個黑盒，不考慮程序內部的邏輯結構和內部特性，只依據程序的需求規格說明，檢查程序的功能是否符合它的功能說明。這種測試又稱為功能測試或數據驅動測試。n白盒測試把測試對象看作一個透明的盒子，利用程序內部的邏輯機構及有關信息，設計或選擇測試用例，對程序的所有邏輯路徑進行測試。通過在不同點檢查程序的狀態，確定實際的狀態是否

37、與預期的一致。這種測試又稱為結構測試或邏輯驅動測試。軟件測試的實施n軟件測試按四個步驟進行：n單元測試：對軟件設計的最小單位模塊進行正確性的測試，其目的是發現各模塊內部可能存在的各種錯誤。n集成測試：是測試和組裝軟件的過程，它是在把模塊按照設計要求組裝起來的同時進行測試，主要目的是發現與接口有關的錯誤。n確認測試：任務是驗證軟件的功能和性能以及其他特性是否滿足了需求規格說明中確定的各種需求，以及軟件配置是否完全、正確。n系統測試：將通過確認測試的軟件，作為整個計算機系統的一個元素，與計算機硬件、外設、支持軟件、數據以及人員等其他系統元素組合在一起，在實際運行環境中對其進行一系列的集成測試和確認

38、測試。（即試運行）程序調試n程序調試的任務是診斷和改正程序中的錯誤。n調試的方法：n強行排錯法n回溯法n原因排除法第四章 數據庫設計基礎n考試大綱n1. 數據庫的基本概念：數據庫，數據庫管理系統，數據庫系統。2. 數據模型，實體聯系模型及E-R圖，從E-R圖導出關系數據模型。3. 關系代數運算，包括集合運算及選擇、投影、連接運算，數據庫規范化理論。4. 數據庫設計方法和步驟：需求分析、概念設計、邏輯設計和物理設計的相關策略。知識點歸納n數據庫的定義n1.長期存放在計算機內，有組織的、可共享的數據集合。數據庫中的數據按一定的數據模型組織、描述和存儲，具有較小的冗余度、較高的數據獨立性和易擴展性。

39、n2.數據庫是由一個互相關聯的數據的集合和一組用以訪問這些數據的程序組成的。數據庫管理系統(DBMS)n數據庫管理系統是一個幫助用戶創建和管理數據庫的應用程序的集合。因此，數據庫管理系統也就是一個可以幫助完成定義、構造和操縱數據庫等處理目的的通用軟件系統。其主要功能如下：n數據模式定義n數據存取的物理構建n數據操縱n數據的完整性、安全性定義和檢查n數據庫的并發控制和故障恢復n數據的服務n為完成上述功能，DBMS提供了相應的語言：n數據定義語言(DDL)n數據操縱語言(DML)n數據控制語言(DCL)數據庫系統n數據庫系統（DBS)組成：n數據庫數據庫(DB)n數據庫管理系統數據庫管理系統(DB

40、MS)n數據庫管理員數據庫管理員(DBA)及其它用戶及其它用戶n硬件平臺硬件平臺n操作系統等其它軟件平臺操作系統等其它軟件平臺 等幾個部分組成的完整的運行實體，其中核心為DBMS。n數據庫系統的特點n數據的集成性n數據的高共享性和低冗余性n數據的獨立性n數據統一管理和控制數據庫系統的內部體系結構n三級模式n概念模式：數據庫系統中全局數據邏輯結構的描述，全體用戶的數據視圖n外模式：又稱為用戶模式，是每個用戶的局部數據描述，用戶的數據視圖n內模式：又稱為物理模式，是數據庫物理存儲結構和物理存取方法的描述n二級映射n概念模式到內模式的映射n外模式到概念模式的映射數據模型n數據是現實世界符號的抽象，數

41、據模型是現實世界數據特征的抽象，它從抽象層次上描述了系統的靜態特征、動態行為和約束條件，為數據庫系統的信息表示和操作提供一個抽象的框架。數據模型描述的內容包括三部分：n數據結構n數據操作n數據約束n數據模型按不同的應用層次分成三種類型：n概念數據模型n邏輯數據模型n物理數據模型實體聯系(ER)模型n概念模型是面向現實世界的，其出發點是有效地模擬顯示世界，給出數據的概念化結構。實體聯系模型是一種廣泛使用的概念模型，該模型將現實世界的要求轉化為實體實體、聯系聯系和屬性屬性等幾個基本概念，并用ER圖直觀地表示出來。n建立ER圖即做數據庫概念設計ER模型的基本概念n實體：概念世界中的基本單位，它們是客觀存在且能相互區別的事物。凡具有共性的實體可以組成一個集合稱為實體集實體集。n屬性：屬性用來描述實體的特征。一個實體可以有多個屬性，每個屬性可以有值，一個屬性的取值范圍稱為該屬性的值域值域。n聯系：聯系反映概念世界中的實體集之間存在的一定關系。n一對一聯系(1:1)n一對多聯系(1:N)n多對多聯系(M:N)ER圖nER圖是實體聯系模型的直