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

2、類排序，插入類排序）。.3知識點歸納n算法的基本概念n所謂算法是指解題方案的準確而完整的描述。嚴格來說，一個算法必須具有以下五個主要特征：n可行性n確定性n有窮性n輸入n輸出n綜上，所謂算法，是一組嚴格定義運算順序的規則，而且每一個規則都是有效且明確的，此順序將在有限的次數終止。.4算法的基本概念n算法的組成要素n算法中對數據的運算和操作n算法的控制結構n算法設計基本方法n列舉法n歸納法n遞推n遞歸n減半遞推n回溯法.5算法的復雜度n算法的復雜度可分為時間復雜度和空間復雜度，是衡量算法優劣的量度。1.算法的時間復雜度n算法的時間復雜度是指執行算法所需要的工作量。一般情況下，算法中的基本操作重復

3、執行的次數是問題規模n的某個函數f(n)f(n)。算法的時間量度記作：T(n)=O(f(n)T(n)=O(f(n)，表示隨問題規模n n的增大，算法執行時間的增長率和f(n)f(n)的增長率相同，稱為算法的(漸進)時間復雜度。.6算法的復雜度n何估算算法的時間復雜度？ 任何一個算法都是由一個“控制結構”和若干“原操作原操作”組成的，因此一個算法的執行時間可以看成是所有原操作的執行時間之和 ( ( 原操作原操作(i)(i)的執行次數的執行次數原操作原操作(i)(i)的執行時間的執行時間 ) )則算法的執行時間與所有原操作的執行次數之和成正比。從算法中選取一種對于所研究的問題來說是基本操作的原操作

4、，以該基本操作在算法中重復執行的次數作為算法時間復雜度的依據。這種衡量效率的辦法所得出的不是時間量，而是一種增長趨勢的量度。它與軟硬件環境無關，只暴露算法本身執行效率的優劣。 .7算法的復雜度n算法的空間復雜度n算法的空間復雜度是指執行這個算法所需要的內存空間。空間復雜度作為算法所需存儲空間的量度，記作：S(n)=O(g(n)S(n)=O(g(n)，其中n n為問題的規模，表示隨問題規模的增大，算法運行所需存儲量的增長率與g(n)g(n)的增長率相同。.8數據結構n利用計算機進行數據處理是計算機應用的一個重要領域。數據結構主要研究和討論以下三個方面的問題：n數據集合中各數據元素之間的邏輯關系，

5、即數據的邏輯結構。n在對數據進行處理時，各數據元素在計算機中的存儲關系，即數據的存儲結構。1.對各種數據結構進行的運算。.9數據的邏輯結構n數據邏輯結構是對數據元素之間存在的邏輯關系的描述，它可以用一個數據元素的集合和定義在此集合上的若干關系表示。n與數據在計算機中的存儲位置無關，是獨立于計算機的。 .10數據的存儲結構n數據的存儲結構是數據元素及其關系在計算機存儲器中的表示。存儲結構的主要內容是指在存儲空間中使用一個存儲結點來存儲一個數據元素，在存儲空間中建立各存儲結點之間的關聯，來表示數據元素之間的邏輯關系。n常見的存儲結構：n順序存儲結構n鏈式存儲結構n索引存儲結構n散列存儲結構.11線

6、性結構和非線性結構線性結構n在數據元素的非空有限集合中，線性結構的邏輯特征如下：n存在一個唯一的被稱為“第一個”的數據元素n存在一個唯一的被稱為“最后一個”的數據元素n除第一個之外，集合中的每個數據元素均有且只有一個直接前驅n除最后一個之外，集合中的每個數據元素均有且只有一個直接后繼非線性結構n非線性結構的邏輯特征是：一個結點可能有多個直接前驅和直接后繼，樹和圖都屬于非線性結構。.12線性表n通常以下列 n 個數據元素的序列”表示線性表線性表 ：(a1,a2 ,.,ai ,.,an) n序列中數據元素的個數 n 定義為線性表的表長表長；n=0 時的線性表被稱為空表空表。稱 i 為ai在線性表中

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

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

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

10、的操作稱為退隊。.18循環隊列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表示隊列非空。.19單鏈表n線性表的鏈式存儲結構的特點是用一組任意的存儲單元(可以連續，也可以不連續)存儲線性表的數據元素，為了表示每個數據元素ai與其直接后繼元素ai+1之間的邏輯關系，對數據元素ai

11、來說，除了存儲其本身的信息(數據域)之外，還需要存儲其后繼元素的存儲位置信息(指針域)。n指針域中存儲的信息稱為指針或鏈，N個結點鏈接成一個鏈表，即為線性表的鏈式存儲結構。由于結點中只包含一個指針域，故稱為單鏈表。.20單鏈表n通常以單鏈表中第一個數據元素的存儲地址作為作為單鏈表的地址，稱為頭指針。整個鏈表的存儲必須從頭指針開始(順序存取)，頭指針指示鏈表中第一個結點的存儲位置。最后一個數據元素沒有直接后繼，其指針域為空。.21單鏈表的插入和刪除.22雙向鏈表和循環鏈表n在雙向鏈表中的結點包含兩個指針域，其中一個指向直接后繼，另一個指向直接前驅。n循環鏈表的特點是表中最后一個結點的指針域指向第

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

13、的度：結點擁有的子樹數。n葉節點(終端結點)：度為0的結點。n雙親、孩子和兄弟：結點的子樹的根節點稱為該結點的孩子，該結點稱為孩子結點的雙親結點。同一個雙親結點的孩子互稱為兄弟。n層次：結點的層次從根開始定義，根為第一層，根的孩子為第二層。n深度：樹中結點的最大層次稱為樹的深度或高度。.25二叉樹n二叉樹是n(n0)個數據元素的有限集，它或為空集,或者含有唯一的稱為根的元素，且其余元素分成兩個互不相交的子集，每個子集自身也是一棵二叉樹，分別稱為根的左子樹和右子樹。n二叉樹是另一種樹型結構，其特點是每個結點至多有兩棵子樹，并且二叉樹的子樹有左右之分，其順序不能任意顛倒。.26二叉樹的基本性質n性

14、質性質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 具有n個結點的二叉樹，其深度至少為log2n +1.27滿二叉樹和完全二叉樹n滿二叉樹滿二叉樹除最后一層外，每一層上的所有結點都有兩個子節點，也就是說每一層上的結點數都達到最大值，即在滿二叉樹的第k層上有2k-1個結點，且深度為m的滿二叉樹有2m-1個結點。n完全二叉樹完全二叉樹除最后一層外，每一層上的結點數均達到最大值，在最后一層上只缺少右邊的若干

15、結點。具有n個結點的完全二叉樹，其深度為log2n +1。n從以上定義可知，滿二叉樹也是完全二叉樹，反之則不然。滿二叉樹滿二叉樹 最大層的結點最大層的結點均向左靠齊均向左靠齊 完全二叉樹完全二叉樹 ADCBEF.28二叉樹的基本性質性質性質5 5 如果對一棵有 n 個結點的完全二叉樹（其深度為log2n +1）的結點按層序（從第1層到第log2n +1 層，每層從左到右）從1起開始編號，則對任一編號為 i 的結點(1in)，則:(1) 如果 i=1，則編號為 i 的結點是二叉樹的根，無雙親；如果 i1，則其雙親結點 parent(i)的編號是i/2。(2) 如果 2in，則編號為 i 的結點無

16、左孩子（編號為 i 的結點為葉子結點）；否則其左孩子結點 lChild(i) 的編號是 2i 。(3) 如果 2i+1n，則編號為 i 的結點無右孩子；否則其右孩子結點 rChild(i) 的編號是結點 2i+1。 .29二叉樹的鏈式存儲結構n在二叉樹的鏈式存儲結構中，每個結點設置三個域，即數據域，左指針域和右指針域，兩個指針域分別存儲左右子樹根節點的存儲位置，即指針。L(i)V(i)R(i)LchildvalueRchild.30二叉樹的鏈式存儲結構.31二叉樹的遍歷n二叉樹的遍歷指不重復地訪問二叉樹的所有結點。從二叉樹的結構定義得知，二叉樹是由根結點、左子樹和右子樹三部分構成，則遍歷二叉樹

17、的操作可分解為訪問根結點、遍歷左子樹和遍歷右子樹三個子操作，并且由二叉樹的遞歸定義可知，遍歷左子樹和遍歷右子樹可如同遍歷二叉樹一樣遞歸進行。 先序遍歷二叉樹先序遍歷二叉樹中序遍歷二叉樹中序遍歷二叉樹后序遍歷二叉樹后序遍歷二叉樹若二叉樹為空，則空操作；否則(1) 訪問根結點；(2) 先序遍歷左子樹；(3) 先序遍歷右子樹。 若二叉樹為空，則空操作；否則(1) 中序遍歷左子樹；(2) 訪問根結點；(3) 中序遍歷右子樹。 若二叉樹為空，則空操作；否則(1) 后序遍歷左子樹；(2) 后序遍歷右子樹；(3) 訪問根結點。.32二叉樹的遍歷先序遍歷：ABDEGHCFIJ中序遍歷：DBGEHACIJF后序

18、遍歷：DGHEBJIFCA.33查找n查找是指在一個給定的數據結構中查找某個指定的元素。n順序查找n順序查找一般是指在線性表中查找指定元素，基本方法如下：從線性表的第一個元素開始，依次將線性表中的元素與被查找元素進行比較，若相等則表示找到，即查找成功；若線性表中的所有元素與被查找元素都不相等，則查找失敗。n如果線性表為無序表，即表中元素的排列是無序的，則不管線性表采用順序存儲還是鏈式存儲，都必須使用順序查找。n如果線性表有序，但采用鏈式存儲結構，則也必須使用順序查找。.34查找n二分查找(折半查找)n二分查找法只適用于順序存儲的有序表。先確定待查目標元素所在范圍(區間)，然后逐步縮小范圍直至找

19、到該元素，或者當查找區間縮小到0也沒有找到目標元素為止。n查找過程中，給定值首先和處于待查區間中間位置的關鍵字進行比較，若相等，則查找成功，否則將查找區間縮小到前半個區間 或 后半個區間 之后繼續進行查找。.35折半查找二分查找.36排序n排序是指將一個無序序列整理成按值遞增或遞減(本章均采用遞增規則)的有序序列。n排序可以在各種不同的存儲結構上實現，本章所介紹的算法以順序存儲的線性表為排序對象，在程序設計語言中就是一維數組。n排序的算法種類很多，主要包括交換類排序、插入類排序、選擇類排序等。.37交換類排序n冒泡排序n基本思想：從表頭開始掃描線性表，在掃描的過程中依次比較相鄰兩個元素的大小，

20、若前面的元素大于后面的元素，則交換它們的位置。顯然，在掃描過程中，不斷地將將相鄰元素間較大的向后移動，最后將線性表中最大的元素移到表尾。n然后，從后向前掃描剩下的線性表，同樣在掃描的過程中依次比較相鄰兩個元素的大小，若后面的元素小于前面的元素，則交換位置。在掃描過程中，不斷地將將相鄰元素間較小的向前移動，最后將線性表中最小的元素移到表頭。n對剩下的線性表重復上述過程，直到剩余線性表為空為止，此時線性表變為有序。.38冒泡排序示例第一遍第一遍( (從前向后從前向后) )第一遍第一遍( (從后向前從后向前) )第二遍第二遍( (從前向后從前向后) )第二遍第二遍( (從后向前從后向前) ).39快

21、速排序n基本思想：從線性表中選取一個元素，設為T，將線性表后面小于T的元素移動到前面，將前面大于T的元素移動到后面，將線性表分為兩個部分(子表)，T放到分界線的位置，這個過程稱為線性表的分割，通過一次分割，就以T為分界將線性表分為兩個子表，前面的子表中的所有元素均不大于T，而后面子表中的元素均不小于T。按照上述原則對子表繼續進行分割，直到子表為空，則整個線性表有序。.40快速排序n操作步驟：n首先，在表的第一個元素、最后一個元素和中間元素中選取一個中值，設為P(k)，并將P(k)賦值給T，再將表中的第一個元素移到P(k) 的位置。設兩個指針i，j分別指向表的起始和最后位置，反復操作以下兩步：n

22、 將j逐漸減小，并逐次比較P(j)和T，直到發現一個P(j)T為止，并將P(i)移到 P(j)的位置上。上述兩步操作交替進行，直到i和j指向同一個位置，再將T移動到P(i)的位置上，完成一次分割。.4131 68 45 90 23 39 54 12 87 7631暫存樞軸記錄暫存樞軸記錄T T：lowhighhighhigh1212low6868highhighhigh2323low4545highhigh3131快速排序的一次分割過程快速排序的一次分割過程31.42插入類排序n簡單插入排序n基本思想：將待排序列表分成兩部分：已排序部分和未排序部分。每次掃描將未排序列表中的第一個元素取出并插入

23、到已排序列表中的合適位置。包含n個元素的列表最多需要n-1次掃描。.43簡單插入排序示例原始序列第1趟第2趟第3趟第4趟第5趟.44希爾排序n基本思想：將整個無序序列分割成若干個小的子序列分別進行插入排序。n子序列的分割方法：將相隔某個增量h的元素構成一個子序列，在排序過程中，逐次減小這個增量，最后當h減到1時，進行一次插入排序，排序完成。n增量序列一般取ht=n/2k(k=1,2log2n).45希爾排序h=6h=6h=1h=1h=3h=3完成完成.46選擇類排序n簡單選擇排序n基本思想：將待排序列表分成兩部分：已排序部分和未排序部分。找到未排序部分中的最小元素并把它和未排序部分中的第一個元

24、素進行交換。經過一次選擇和交換，列表中已排序部分增加一個元素，未排序部分減少一個元素。每次把一個元素從未排序部分移動到已排序部分稱為完成一次分類掃描分類掃描或稱為一趟排序一趟排序。n一個包含n個元素的列表需要進行n-1次掃描完成排序。.47簡單選擇排序示例原始序列第1趟第2趟第3趟第4趟第5趟.48第二章 程序設計基礎(15%)n考試大綱n1. 程序設計方法與風格。2. 結構化程序設計。3. 面向對象的程序設計方法，對象，方法，屬性及繼承與多態性。 .49知識點歸納n程序設計方法n程序設計是一門技術，需要相應的理論、方法和工具來支持。就程序設計方法和技術的發展而言，主要經歷了結構化的程序設計和

25、面向對象的程序設計階段。n在程序設計中，通常采用“自頂向下，逐步求精”的方法，即把一個模塊的功能逐步分解，細化為一系列具體的步驟，進而轉換成一系列用某種程序設計語言編寫的程序。.50程序設計風格n除了程序設計設計方法和技術之外，程序風格也是非常重要的。良好的程序設計風格概括起來包括以下及格方面：n源程序文檔化n數據說明的方法n語句的結構n輸入和輸出.51程序設計風格n源程序文檔化n標識符的命名n程序的注釋n序言性注釋n功能性注釋n程序的視覺組織n數據的說明n數據說明的次序應該規范化n說明語句中變量的安排有序化n使用注釋說明復雜的數據結構.52程序設計風格n語句結構語句結構n在一行內只寫一條語句

26、n程序編寫應優先考慮清晰性n除非對效率有特殊要求，程序編寫要做到清晰第一，效率第二n首先要保證程序正確，然后才要求提高速度n避免使用臨時變量而使程序的可讀性下降n避免不必要的轉移n盡可能使用庫函數n避免使用復雜的條件語句n盡量減少使用“否定”條件的條件語句n數據結構要有利于程序的簡化n要模塊化，使模塊功能盡可能單一化n利用信息隱蔽，確保每一個模塊的獨立性n從數據出發構造程序n不要修補不好的程序，要重寫編寫.53程序設計風格n輸入和輸出n對所有輸入數據檢驗合法性n檢查輸入項的各種重要組合的合法性n輸入格式要簡單，以使輸入的步驟和操作盡可能簡單n輸入數據時，應允許使用自由格式n應允許缺省值n輸入一

27、批數據時，最好使用輸入結束標志n在以交互式輸入/輸出方式進行輸入時，要在屏幕上使用提示符明確提示輸入的請求，同時在數據輸入結束時，應在屏幕上給出狀態信息n當程序設計語言對輸入格式有嚴格要求時，應保持輸入格式與輸入語句的一致性；給所有的輸出加注釋，并設計輸出報表格式。.54結構化程序設計n結構化程序設計的原則n自頂向下。程序設計時，應先考慮總體，后考慮細節；先考慮全局目標，后考慮局部目標。不要一開始就過多追求細節，先從最上層總目標開始設計，逐步使問題具體化。n逐步求精。對復雜的問題，應設計一些子目標過渡，逐步細化。n模塊化。一個復雜問題肯定是有若干簡單問題構成。模塊化是把程序要解決的總目標分解為

28、分目標，再進一步分解為具體的小目標，每個小目標成為一個模塊。n嚴格限制GOTO語句的使用。.55結構化程序設計的基本結構和特點n程序由一些基本結構組成，任何一個程序都可以用三種基本控制結構組成：順序結構、選擇結構和循環結構，并且具有如下特點：單入口、單出口、結構中無死循環，程序中三種基本控制結構之間形成順序執行關系。n一個大型程序應按功能分割成一些模塊，并把這些模塊按層次關系進行組織。n在程序設計時應采用自頂向下、逐步細化的實施方法。.56面向對象程序設計n 面向對象方法的基本概念1.對象、類和屬性 在面向對象程序設計中，對象是程序的基本單位。對象可以表示客觀世界中的任何實體，是對問題域中某個

29、實體的抽象。每個對象可以用它本身的一組屬性和它可以執行的一組操作來定義。類是對一組具有共同屬性和相似行為的對象的一種抽象，描述了屬于該類的所有對象的性質。2.方法 方法有稱為操作或服務，它描述了對象執行的功能，若通過消息傳遞，還可為其他對象使用。.57面向對象方法的基本概念3.繼承：繼承是對象方法的一個重要特征。指一個類(子類)直接使用另一個類(父類)的所有屬性和方法。它可以減少相似類的重復說明，從而體現一般性和特殊性的原則。4.多態性：多態性可以用“一個對外界面，多個內部實現”來表示。可以通過方法重載和方法重寫來實現多態。重載指一個類中可以有多個具有相同名稱的方法，由傳遞給它們的不同個數和類

30、型的參數來決定執行那個方法。重寫指子類可以重新實現父類的某些方法，使其具有自己的特征。多態性機制增加了面向對象軟件系統的靈活性，提高了軟件的可重用性和可擴充性。5.消息：面向對象系統中的對象之間是通過消息機制彼此相互合作的，消息是一個對象與另一個對象之間傳遞的信息，它請求對象執行某一處理或回答某一要求的信息。.58面向對象程序設計的特點n按照人的思維方式對客觀世界進行抽象n穩定性好n可重用性好n易于開發大型軟件n可維護性好.59第三章 軟件工程基礎n考試大綱n1. 軟件工程基本概念，軟件生命周期的概念，軟件工具與軟件開發環境。2. 結構化分析方法，數據流圖，數據字典，軟件需求規格說明書。3.

31、結構化設計方法，總體設計與詳細設計。4. 軟件測試的方法，白盒測試與黑盒測試，測試用例設計，軟件測試的實施，單元測試、集成測試和系統測試。5. 程序的調試，靜態調試與動態調試。 .60知識點歸納n軟件定義和特點n計算機軟件式計算機系統中與硬件相互依存的另一部分，是包括程序、數據及相關文檔的完整集合。計算機軟件具有如下特點：n軟件是一種邏輯實體，具有抽象性n軟件生產沒有明顯的制造過程n軟件在運行、使用期間不存在磨損、老化問題n軟件的開發、運行對計算機系統具有依賴性n軟件復雜性高，成本昂貴n軟件開發涉及諸多社會因素.61軟件危機n所謂軟件危機是指在計算機軟件開發和維護過程中所遇到的一系列嚴重問題，

32、包括：n軟件需求的增長得不到滿足n軟件開發成本和進度無法控制n軟件質量難以保證n軟件不可維護或可維護性低n軟件成本不斷提高n軟件開發生產率的提高趕不上硬件的發展和應用需求的增長。.62軟件工程n為了消除軟件危機，提出了軟件工程學。軟件工程是應用于計算機軟件定義、開發和維護的一整套方法、工具、文檔、實踐標準和工序。n軟件工程的三要素n方法n工具n過程.63軟件工程過程n軟件工程過程是把輸入轉化為輸出的一組彼此相關的資源和活動。它包括兩方面含義：n1. 軟件工程過程是指為獲得軟件產品，在軟件工具支持下由軟件工程師完成的一系列工程活動。通常包括四種基本活動：nP(Plan)：軟件規格說明nD(Do)

33、：軟件開發nC(Check)：軟件確認nA(Action)：軟件演進n2.從軟件開發的觀點看，軟件工程過程是使用適當的資源，為開發軟件進行的一組開發活動，在活動結束時將輸入(用戶需求)轉化為輸出(軟件產品)。.64軟件生命周期n軟件從提出、實現、使用、維護到停止使用的過程稱為軟件的生命周期。一般包括以下幾個階段：n可行性研究與計劃制定n需求分析n軟件設計n軟件實現n軟件測試n運行和維護.65軟件工程目標與原則n軟件工程的目標是在給定成本、進度的前提下，開發出具有有效性、可靠性、可理解性、可維護性、可重用性、可適應性、可移植性、可追蹤性和可互操作性且滿足用戶需求的軟件產品。n為達到上述目標，在軟

34、件開發的過程中，必須遵循軟件工程的基本原則：n抽象n信息隱蔽n模塊化n局部化n確定性n一致性n完備性n可驗證性.66軟件開發工具與軟件開發環境n軟件開發工具對過程和方法提供自動或半自動的支持。當這些工具被集成起來使得一個工具產生的信息可以被另外一個工具使用時，一個支持軟件開發的系統就建立起來了，稱為計算機輔助軟件工程(CASE)。CASE集成了軟件、硬件和一個軟件工程數據庫(包含了有關分析、設計、程序構造和測試的重要信息)從而創建了一個軟件開發環境。.67結構化分析方法n結構化分析方法大多使用自頂向下、逐層分解的系統分析方法來定義系統需求。在結構化分析的基礎上，完成系統的規格說明，建立系統的一

35、個自頂向下的任務分析模型。結構化分析方法是一種建模技術，模型的核心是數據辭典，它描述了所有在目標系統中使用和生成的數據對象。結構化分析常用的工具：n數據流圖(DFD):描述數據在系統中如何被傳送或變換以及描述如何對數據流進行變換的功能，用于功能建模。n數據字典n判定樹n判定表.68數據流圖n數據流圖是描述數據處理過程的工具，它從數據傳遞和加工的角度，來刻畫數據流從輸入系統到從系統輸入的移動變換過程。n數據流圖的基本元素n外部實體n數據流n處理(加工)n數據存儲.69數據字典n數據字典是關于數據的信息的集合，對數據流圖中的各個元素進行完整的定義和說明。數據流圖和數據字典共同構成系統的邏輯模型。n

36、數據字典通常包含的信息有：名稱、別名、何處使用、如何使用、內容描述以及補充信息等。.70軟件需求n軟件需求包括：功能需求、性能需求、環境需求、可靠性需求、安全保密需求、用戶界面需求、資源使用需求、成本消耗需求、開發進度需求等。n需求分析應交付的主要文檔是軟件需求規格說明書(SRS)。.71結構化設計n結構化設計就是采用最佳的可能方法設計系統的各個組成部分以及個成分之間的內部聯系的技術。也就是說，結構化設計是這樣一個過程：它決定用哪些方法把哪些部分聯系起來，才能解決好某個具體的有清楚定義的問題。從工程管理的角度看，軟件設計分兩步完成：n1.概要設計，即總體設計。將軟件需求轉化為數據結構和軟件的系

37、統結構。常用的軟件結構設計工具是結構圖(Structure Chart)。n2.詳細設計：即過程設計。通過對結構表示進行細化，得到軟件詳細的數據結構和算法。過程設計常用的工具有：程序流程圖、N-S圖、PAD圖、過程設計語言PDL(偽碼)。.72軟件測試n定義：n使用人工或自動手段來運行或測定某個系統的過程，其目的在于檢驗它是否滿足規定的需求或弄清預期結果與實際結果之間的差別。n軟件測試是為了發現錯誤而執行程序的過程。n一個好的測試用例是指可能找到迄今為止尚未發現的錯誤的用例。n一個成功的測試是發現了至今尚未發現的錯誤的測試。n測試不能表明軟件中不存在錯誤，它只能說明軟件中存在錯誤。.73測試技

38、術與方法綜述n從是否需要執行被測試軟件的角度，可將測試分為靜態測試和動態測試。n靜態測試主要包括代碼檢查、靜態結構分析、代碼質量度量等。n動態測試是基于計算機的測試，是為了發現錯誤而執行程序的過程，或者說，是根據軟件開發的各個階段的規格說明和程序的內部結構而精心設計的一批測試用例，并利用這些測試用例去運行程序，以發現程序錯誤的過程。.74測試技術與方法綜述n按照功能劃分，可將軟件測試分為黑盒測試和白盒測試。n黑盒測試將測試對象看作一個黑盒，不考慮程序內部的邏輯結構和內部特性，只依據程序的需求規格說明，檢查程序的功能是否符合它的功能說明。這種測試又稱為功能測試或數據驅動測試。n白盒測試把測試對象

39、看作一個透明的盒子，利用程序內部的邏輯機構及有關信息，設計或選擇測試用例，對程序的所有邏輯路徑進行測試。通過在不同點檢查程序的狀態，確定實際的狀態是否與預期的一致。這種測試又稱為結構測試或邏輯驅動測試。.75軟件測試的實施n軟件測試按四個步驟進行：n單元測試：對軟件設計的最小單位模塊進行正確性的測試，其目的是發現各模塊內部可能存在的各種錯誤。n集成測試：是測試和組裝軟件的過程，它是在把模塊按照設計要求組裝起來的同時進行測試，主要目的是發現與接口有關的錯誤。n確認測試：任務是驗證軟件的功能和性能以及其他特性是否滿足了需求規格說明中確定的各種需求，以及軟件配置是否完全、正確。n系統測試：將通過確認

40、測試的軟件，作為整個計算機系統的一個元素，與計算機硬件、外設、支持軟件、數據以及人員等其他系統元素組合在一起，在實際運行環境中對其進行一系列的集成測試和確認測試。.76程序調試n程序調試的任務是診斷和修正程序中的錯誤。n調試的方法：n強行排錯法n回溯法n原因排除法.77第四章 數據庫設計基礎n考試大綱n1. 數據庫的基本概念：數據庫，數據庫管理系統，數據庫系統。2. 數據模型，實體聯系模型及E-R圖，從E-R圖導出關系數據模型。3. 關系代數運算，包括集合運算及選擇、投影、連接運算，數據庫規范化理論。4. 數據庫設計方法和步驟：需求分析、概念設計、邏輯設計和物理設計的相關策略。.78知識點歸納

41、n數據庫的定義n1.長期存放在計算機內，有組織的、可共享的數據集合。數據庫中的數據按一定的數據模型組織、描述和存儲，具有較小的冗余度、較高的數據獨立性和易擴展性。n2.數據庫是由一個互相關聯的數據的集合和一組用以訪問這些數據的程序組成的。.79數據庫管理系統(DBMS)n數據庫管理系統是一個幫助用戶創建和管理數據庫的應用程序的集合。因此，數據庫管理系統也就是一個可以幫助完成定義、構造和操縱數據庫等處理目的的通用軟件系統。其主要功能如下：n數據模式定義n數據存取的物理構建n數據操縱n數據的完整性、安全性定義和檢查n數據庫的并發控制和故障恢復n數據的服務n為完成上述功能，DBMS提供了相應的語言：

42、n數據定義語言(DDL)n數據操縱語言(DML)n數據控制語言(DCL).80數據庫系統n數據庫系統是由數據庫、數據庫管理系統、數據庫管理員、硬件平臺和軟件平臺等幾個部分組成的完整的運行實體。n數據庫系統的特點n數據的集成性n數據的高共享性和低冗余性n數據的獨立性n數據統一管理和控制.81數據庫系統的內部體系結構n三級模式n概念模式：數據庫系統中全局數據邏輯結構的描述，全體用戶的數據視圖n外模式：又稱為用戶模式，是每個用戶的局部數據描述，用戶的數據視圖n內模式：又稱為物理模式，是數據庫物理存儲結構和物理存取方法的描述n二級映射n概念模式到內模式的映射n外模式到概念模式的映射.82數據模型n數據

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