計算機二級公共基礎知識課件

計算機二級公共基礎知識計算機二級公共基礎知識計算機二級公共基礎知識第一章數(shù)據(jù)結構與算法(30%)考試大綱 1.算法的基本概念；算法復雜度的概念和意義（時間復雜度與空間復雜度）。

2.數(shù)據(jù)結構的定義；數(shù)據(jù)的邏輯結構與存儲結構；數(shù)據(jù)結構的圖形表示；線性結構與非線性結構的概念。

3.線性表的定義；線性表的順序存儲結構及其插入與刪除運算。

4.棧和隊列的定義；棧和隊列的順序存儲結構及其基本運算。

5.線性單鏈表、雙向鏈表與循環(huán)鏈表的結構及其基本運算。

6.樹的基本概念；二叉樹的定義及其存儲結構；二叉樹的前序、中序和后序遍歷。

7.順序查找與二分法查找算法；基本排序算法（交換類排序，選擇類排序，插入類排序）。2021/2/42第一章數(shù)據(jù)結構與算法(30%)考試大綱 1.算法的基本概念；算法復雜度的概念和意義（時間復雜度與空間復雜度）。

2.數(shù)據(jù)結構的定義；數(shù)據(jù)的邏輯結構與存儲結構；數(shù)據(jù)結構的圖形表示；線性結構與非線性結構的概念。

3.線性表的定義；線性表的順序存儲結構及其插入與刪除運算。

4.棧和隊列的定義；棧和隊列的順序存儲結構及其基本運算。

5.線性單鏈表、雙向鏈表與循環(huán)鏈表的結構及其基本運算。

6.樹的基本概念；二叉樹的定義及其存儲結構；二叉樹的前序、中序和后序遍歷。

7.順序查找與二分法查找算法；基本排序算法（交換類排序，選擇類排序，插入類排序）。2021/2/42知識點歸納算法的基本概念所謂算法是指解題方案的準確而完整的描述。嚴格來說，一個算法必須具有以下五個主要特征：2021/2/43算法的基本特征一個算法應該具有以下五個重要的特征：有窮性確定性輸入輸出可行性一個算法必須保證執(zhí)行有限步之后結束；算法的每一步驟必須有確切的定義；一個算法有0個或多個輸入，以刻畫運算對象的初始情況，所謂0個輸入是指算法本身定義了初始條件；一個算法有一個或多個輸出，以反映對輸入數(shù)據(jù)加工后的結果。沒有輸出的算法是毫無意義的；算法原則上能夠精確地運行2021/2/44算法的基本概念算法的組成要素算法中對數(shù)據(jù)的運算和操作算法的控制結構算法設計基本方法列舉法歸納法遞推遞歸減半遞推回溯法基本運算和操作算術運算關系運算邏輯運算數(shù)據(jù)傳輸控制結構

順序選擇循環(huán)2021/2/45算法的復雜度算法的復雜度可分為時間復雜度和空間復雜度，是衡量算法優(yōu)劣的量度。1.算法的時間復雜度算法的時間復雜度是指執(zhí)行算法所需要的工作量。一般情況下，算法中的基本操作重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f(n)。2021/2/46算法的復雜度算法的空間復雜度算法的空間復雜度是指執(zhí)行這個算法所需要的內存空間?？臻g復雜度作為算法所需存儲空間的量度2021/2/47數(shù)據(jù)結構利用計算機進行數(shù)據(jù)處理是計算機應用的一個重要領域。數(shù)據(jù)結構主要研究和討論以下三個方面的問題：數(shù)據(jù)集合中各數(shù)據(jù)元素之間的邏輯關系，即數(shù)據(jù)的邏輯結構。在對數(shù)據(jù)進行處理時，各數(shù)據(jù)元素在計算機中的存儲關系，即數(shù)據(jù)的存儲結構。對各種數(shù)據(jù)結構進行的運算。2021/2/48數(shù)據(jù)的邏輯結構數(shù)據(jù)邏輯結構是對數(shù)據(jù)元素之間存在的邏輯關系的描述，它可以用一個數(shù)據(jù)元素的集合和定義在此集合上的若干關系表示。與數(shù)據(jù)在計算機中的存儲位置無關，是獨立于計算機的。

2021/2/49數(shù)據(jù)的存儲結構數(shù)據(jù)的存儲結構是數(shù)據(jù)元素及其關系在計算機存儲器中的表示。存儲結構的主要內容是指在存儲空間中使用一個存儲結點來存儲一個數(shù)據(jù)元素，在存儲空間中建立各存儲結點之間的關聯(lián)，來表示數(shù)據(jù)元素之間的邏輯關系。常見的存儲結構：順序存儲結構鏈式存儲結構索引存儲結構散列存儲結構2021/2/410線性結構和非線性結構線性結構在數(shù)據(jù)元素的非空有限集合中，線性結構的邏輯特征如下：存在一個唯一的被稱為“第一個”的數(shù)據(jù)元素存在一個唯一的被稱為“最后一個”的數(shù)據(jù)元素除第一個之外，集合中的每個數(shù)據(jù)元素均有且只有一個直接前驅除最后一個之外，集合中的每個數(shù)據(jù)元素均有且只有一個直接后繼非線性結構非線性結構的邏輯特征是：一個結點可能有多個直接前驅和直接后繼，樹和圖都屬于非線性結構。2021/2/411線性表 通常以下列n個數(shù)據(jù)元素的序列”表示線性表：

(a1,a2,...,ai,...,an)序列中數(shù)據(jù)元素的個數(shù)n定義為線性表的表長；n=0時的線性表被稱為空表。稱i為ai在線性表中的位序。2021/2/412線性表的順序存儲線性表的順序存儲結構用一組地址連續(xù)的存儲單元依次存放線性表中的數(shù)據(jù)元素，即以“存儲位置相鄰”表示“位序相繼的兩個數(shù)據(jù)元素之間的前驅和后繼的關系，并以表中第一個元素的存儲位置作為線性表的起始地址，稱作線性表的基地址。

所有數(shù)據(jù)元素的存儲位置均可由第一個數(shù)據(jù)元素的存儲位置得到

ADR(ai)=ADR(a1)+(i-1)×C

↑↑ 基地址一個數(shù)據(jù)元素所占存儲量

2021/2/413線性表的插入和刪除運算插入運算是指在線性表的某個指定位置增加一個新結點。一般情況下，要在第i(1≤i≤n)個元素之前插入一個新元素時，首先要從最后一個元素開始，直到第i個元素之間共n-i+1個元素依次向后移動一個位置，然后將新元素插入到第i項。刪除運算是指撤銷結構中的某個結點。一般情況，要刪除第i(1≤i≤n)個元素，要從第i+1個元素開始，直到第n個元素，共n-i個元素依次向前移動一個位置。2021/2/414棧棧是限定僅在表的一端進行插入和刪除操作的線性表。允許插入和刪除的一端稱為棧頂，另一端稱為棧底。棧頂元素總是最后被插入的元素，從而也是最先被刪除的元素；棧底元素總是最先被插入，也是最后被刪除的元素。因此，棧是一種后進先出的線性表。通常用指針top指示棧頂位置，用指針bottom指示棧底位置。2021/2/415棧的順序存儲及運算用一維數(shù)組S(1:m)作為棧的順序存儲空間，m為棧的最大容量。top=0表示棧為空，top=m表示棧滿。棧的操作入棧：在棧頂位置插入一個新元素，棧頂指針top加1。退棧：取出棧頂元素并賦值給一個指定的變量，棧頂指針top減1。取棧頂元素：將棧頂元素的值賦給一個指定的變量，不刪除棧頂元素，棧頂指針不變。2021/2/416隊列隊列是一種先進先出的線性表，它只允許在表的一端插入元素(隊尾)，在另一端刪除元素(隊頭)。通常定義頭指針front指向隊頭元素的前一個位置，定義尾指針rear指向隊尾元素的位置。隊列是一種先進先出的數(shù)據(jù)結構。向隊尾插入一個元素的操作稱為入隊，從隊頭刪除一個元素的操作稱為退隊。2021/2/417循環(huán)隊列 將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間。循環(huán)隊列初始狀態(tài)為空，即front=rear=m。入隊操作時，rear加1，若rear=m+1，則置rear=1；退隊操作時，front加1，若front=m+1，則置front=1。在循環(huán)隊列為空或為滿時，均有front=rear，因此需要設置標志s進行區(qū)分，定義s=0表示隊列為空，s=1表示隊列非空。2021/2/418單鏈表線性表的鏈式存儲結構的特點是用一組任意的存儲單元(可以連續(xù)，也可以不連續(xù))存儲線性表的數(shù)據(jù)元素，為了表示每個數(shù)據(jù)元素ai與其直接后繼元素ai+1之間的邏輯關系，對數(shù)據(jù)元素ai來說，除了存儲其本身的信息(數(shù)據(jù)域)之外，還需要存儲其后繼元素的存儲位置信息(指針域)。指針域中存儲的信息稱為指針或鏈，N個結點鏈接成一個鏈表，即為線性表的鏈式存儲結構。由于結點中只包含一個指針域，故稱為單鏈表。2021/2/419單鏈表通常以單鏈表中第一個數(shù)據(jù)元素的存儲地址作為作為單鏈表的地址，稱為頭指針。整個鏈表的存儲必須從頭指針開始(順序存取)，頭指針指示鏈表中第一個結點的存儲位置。最后一個數(shù)據(jù)元素沒有直接后繼，其指針域為空。2021/2/420單鏈表的插入和刪除2021/2/421雙向鏈表和循環(huán)鏈表在雙向鏈表中的結點包含兩個指針域，其中一個指向直接后繼，另一個指向直接前驅。循環(huán)鏈表的特點是表中最后一個結點的指針域指向第一個結點，整個鏈表成為一個由鏈指針相鏈接的環(huán)。據(jù)此，從表中任一節(jié)點出發(fā)均可找到表中其它結點。在循環(huán)鏈表中增加了一個表頭結點，其指針域指向第一個元素結點，頭指針則指向頭結點。HEAD…∧…∧HEAD…HEAD2021/2/422樹及其基本概念樹是一種簡單的非線性結構，在樹中，所有的數(shù)據(jù)元素之間具有明顯的層次性關系。樹是(n≥0)個結點的有限集合，在任意一棵非空樹中：(1)有且僅有一個特定的結點稱為根結點。(2)當n>1時，其余的結點可分為m個互不相交的子集T1,T2,…Tm，其中每個有限子集本身又是一棵樹，并且稱為根的子樹。集合為空的樹簡稱為空樹；樹中的元素稱為結點。2021/2/423樹的主要術語結點的度：結點擁有的子樹數(shù)。葉節(jié)點(終端結點)：度為0的結點。雙親、孩子和兄弟：結點的子樹的根節(jié)點稱為該結點的孩子，該結點稱為孩子結點的雙親結點。同一個雙親結點的孩子互稱為兄弟。層次：結點的層次從根開始定義，根為第一層，根的孩子為第二層。深度：樹中結點的最大層次稱為樹的深度或高度。2021/2/424樹型結構的常用術語ABDFECGHIJKM

結點的度一個結點的子樹的個數(shù)；Q：結點A、G的度數(shù)？

樹的度樹中所有結點度的最大值；Q：右圖中樹的度？

終端結點度為0的結點；Q：圖中葉子結點有幾個？7

非終端結點

度不為0的結點；Q：圖中非終端結點有幾個？52021/2/425樹型結構的常用術語ABDFECGHIJKM

結點的層次樹中根結點的層次為1，根結點子樹的根為第2層，以此類推；樹的深度

樹中所有結點層次的最大值；Q：圖中樹的深度？①②③④2021/2/426二叉樹二叉樹是n(n≥0)個數(shù)據(jù)元素的有限集，它或為空集,或者含有唯一的稱為根的元素，且其余元素分成兩個互不相交的子集，每個子集自身也是一棵二叉樹，分別稱為根的左子樹和右子樹。二叉樹是另一種樹型結構，其特點是每個結點至多有兩棵子樹，并且二叉樹的子樹有左右之分，其順序不能任意顛倒。2021/2/427二叉樹的基本性質性質1在二叉樹的第i層上至多有2i-1個結點（i≥1）性質2深度為k的二叉樹至多有2k-1個結點（k≥1）性質3對任何一棵二叉樹T，如果其終端結點數(shù)為n0，度為2的結點數(shù)為n2，則：n0=n2+1性質4具有n個結點的二叉樹，其深度至少為[log2n]+12021/2/428滿二叉樹和完全二叉樹滿二叉樹除最后一層外，每一層上的所有結點都有兩個子節(jié)點，也就是說每一層上的結點數(shù)都達到最大值，即在滿二叉樹的第k層上有2k-1個結點，且深度為m的滿二叉樹有2m-1個結點。完全二叉樹除最后一層外，每一層上的結點數(shù)均達到最大值，在最后一層上只缺少右邊的若干結點。具有n個結點的完全二叉樹，其深度為[log2n]+1。從以上定義可知，滿二叉樹也是完全二叉樹，反之則不然。滿二叉樹

最大層的結點均向左靠齊

完全二叉樹

ADCBEF2021/2/429二叉樹的基本性質性質5如果對一棵有n個結點的完全二叉樹（其深度為[log2n]+1）的結點按層序（從第1層到第[log2n]+1層，每層從左到右）從1起開始編號，則對任一編號為i的結點(1≤i≤n)，則:

(1)如果i=1，則編號為i的結點是二叉樹的根，無雙親；如果i>1，則其雙親結點parent(i)的編號是[i/2]。

(2)如果2i>n，則編號為i的結點無左孩子（編號為i的結點為葉子結點）；否則其左孩子結點lChild(i)的編號是2i。

(3)如果2i+1>n，則編號為i的結點無右孩子；否則其右孩子結點rChild(i)的編號是結點2i+1。

2021/2/430二叉樹的鏈式存儲結構在二叉樹的鏈式存儲結構中，每個結點設置三個域，即數(shù)據(jù)域，左指針域和右指針域，兩個指針域分別存儲左右子樹根節(jié)點的存儲位置，即指針。L(i)V(i)R(i)LchildvalueRchild2021/2/431二叉樹的鏈式存儲結構2021/2/432二叉樹的遍歷二叉樹的遍歷指不重復地訪問二叉樹的所有結點。從二叉樹的結構定義得知，二叉樹是由"根結點"、"左子樹"和"右子樹"三部分構成，則遍歷二叉樹的操作可分解為"訪問根結點"、"遍歷左子樹"和"遍歷右子樹"三個子操作，并且由二叉樹的遞歸定義可知，遍歷左子樹和遍歷右子樹可如同遍歷二叉樹一樣"遞歸"進行。

先序遍歷二叉樹中序遍歷二叉樹后序遍歷二叉樹若二叉樹為空，則空操作；

否則

(1)訪問根結點；

(2)先序遍歷左子樹；

(3)先序遍歷右子樹。若二叉樹為空，則空操作；

否則

(1)中序遍歷左子樹；

(2)訪問根結點；

(3)中序遍歷右子樹。若二叉樹為空，則空操作；

否則

(1)后序遍歷左子樹；

(2)后序遍歷右子樹；

(3)訪問根結點。2021/2/433二叉樹的遍歷先序遍歷：ABDEGHCFIJ中序遍歷：DBGEHACIJF后序遍歷：DGHEBJIFCA2021/2/434查找查找是指在一個給定的數(shù)據(jù)結構中查找某個指定的元素。順序查找順序查找一般是指在線性表中查找指定元素，基本方法如下：從線性表的第一個元素開始，依次將線性表中的元素與被查找元素進行比較，若相等則表示找到，即查找成功；若線性表中的所有元素與被查找元素都不相等，則查找失敗。順序查找：最好情況比較1次，最壞情況比較n次如果線性表為無序表，即表中元素的排列是無序的，則不管線性表采用順序存儲還是鏈式存儲，都必須使用順序查找。如果線性表有序，但采用鏈式存儲結構，則也必須使用順序查找。2021/2/435查找二分查找(折半查找)二分查找法只適用于順序存儲的有序表。先確定待查目標元素所在范圍(區(qū)間)，然后逐步縮小范圍直至找到該元素，或者當查找區(qū)間縮小到0也沒有找到目標元素為止。查找過程中，給定值首先和處于待查區(qū)間"中間位置"的關鍵字進行比較，若相等，則查找成功，否則將查找區(qū)間縮小到"前半個區(qū)間"或"后半個區(qū)間"之后繼續(xù)進行查找。2021/2/436折半查找二分查找2021/2/437查找二分查找(折半查找)：由于每次都可以減少一半的元素，所以最壞時間復雜度為log(2n)2021/2/438排序 排序是指將一個無序序列整理成按值遞增或遞減(本章均采用遞增規(guī)則)的有序序列。排序可以在各種不同的存儲結構上實現(xiàn)，本章所介紹的算法以順序存儲的線性表為排序對象，在程序設計語言中就是一維數(shù)組。排序的算法種類很多，主要包括交換類排序、插入類排序、選擇類排序等。2021/2/439排序技術交換類排序法

冒泡排序快速排序插入類排序法簡單插入排序希爾排序選擇類排序法簡單選擇排序堆排序2021/2/440排序法小結：最壞時間復雜度：冒泡排序法、快速排序、簡單選擇排序法、簡單插入排序：

最壞情況需要n(n-1)/2次比較；希爾排序法：最壞情況需要O(n1.5)次比較；堆排序法,最壞情況需要O(nlog2n)次比較；平均速度最快排序：快速排序最好、最壞、平均三種復雜度都相同的排序方法：堆排序2021/2/441第二章程序設計基礎(15%)考試大綱1.程序設計方法與風格。

2.結構化程序設計。

3.面向對象的程序設計方法，對象，方法，屬性及繼承與多態(tài)性。

2021/2/442知識點歸納程序設計方法程序設計是一門技術，需要相應的理論、方法和工具來支持。就程序設計方法和技術的發(fā)展而言，主要經歷了結構化的程序設計和面向對象的程序設計階段。在程序設計中，通常采用“自頂向下，逐步求精”的方法，即把一個模塊的功能逐步分解，細化為一系列具體的步驟，進而轉換成一系列用某種程序設計語言編寫的程序。2021/2/443程序設計風格除了程序設計設計方法和技術之外，程序風格也是非常重要的。良好的程序設計風格概括起來包括以下及格方面：源程序文檔化數(shù)據(jù)說明的方法語句的結構輸入和輸出2021/2/444程序設計風格源程序文檔化標識符的命名程序的注釋序言性注釋功能性注釋程序的視覺組織數(shù)據(jù)的說明數(shù)據(jù)說明的次序應該規(guī)范化說明語句中變量的安排有序化使用注釋說明復雜的數(shù)據(jù)結構2021/2/445程序設計風格語句結構在一行內只寫一條語句程序編寫應優(yōu)先考慮清晰性除非對效率有特殊要求，程序編寫要做到清晰第一，效率第二首先要保證程序正確，然后才要求提高速度避免使用臨時變量而使程序的可讀性下降避免不必要的轉移盡可能使用庫函數(shù)避免使用復雜的條件語句盡量減少使用“否定”條件的條件語句數(shù)據(jù)結構要有利于程序的簡化要模塊化，使模塊功能盡可能單一化利用信息隱蔽，確保每一個模塊的獨立性從數(shù)據(jù)出發(fā)構造程序不要修補不好的程序，要重寫編寫2021/2/446程序設計風格輸入和輸出對所有輸入數(shù)據(jù)檢驗合法性檢查輸入項的各種重要組合的合法性輸入格式要簡單，以使輸入的步驟和操作盡可能簡單輸入數(shù)據(jù)時，應允許使用自由格式應允許缺省值輸入一批數(shù)據(jù)時，最好使用輸入結束標志在以交互式輸入/輸出方式進行輸入時，要在屏幕上使用提示符明確提示輸入的請求，同時在數(shù)據(jù)輸入結束時，應在屏幕上給出狀態(tài)信息當程序設計語言對輸入格式有嚴格要求時，應保持輸入格式與輸入語句的一致性；給所有的輸出加注釋，并設計輸出報表格式。2021/2/447結構化程序設計結構化程序設計的原則自頂向下。程序設計時，應先考慮總體，后考慮細節(jié)；先考慮全局目標，后考慮局部目標。不要一開始就過多追求細節(jié)，先從最上層總目標開始設計，逐步使問題具體化。逐步求精。對復雜的問題，應設計一些子目標過渡，逐步細化。模塊化。一個復雜問題肯定是有若干簡單問題構成。模塊化是把程序要解決的總目標分解為分目標，再進一步分解為具體的小目標，每個小目標成為一個模塊。嚴格限制GOTO語句的使用。2021/2/448結構化程序設計的基本結構和特點程序由一些基本結構組成，任何一個程序都可以用三種基本控制結構組成：順序結構、選擇結構和循環(huán)結構，并且具有如下特點：單入口、單出口、結構中無死循環(huán)，程序中三種基本控制結構之間形成順序執(zhí)行關系。一個大型程序應按功能分割成一些模塊，并把這些模塊按層次關系進行組織。在程序設計時應采用自頂向下、逐步細化的實施方法。2021/2/449面向對象程序設計

面向對象方法的基本概念1.對象、類和屬性在面向對象程序設計中，對象是程序的基本單位。對象可以表示客觀世界中的任何實體，是對問題域中某個實體的抽象。每個對象可以用它本身的一組屬性和它可以執(zhí)行的一組操作來定義。類是對一組具有共同屬性和相似行為的對象的一種抽象，描述了屬于該類的所有對象的性質。2.方法方法有稱為操作或服務，它描述了對象執(zhí)行的功能，若通過消息傳遞，還可為其他對象使用。2021/2/450面向對象方法的基本概念3.繼承：繼承是對象方法的一個重要特征。指一個類(子類)直接使用另一個類(父類)的所有屬性和方法。它可以減少相似類的重復說明，從而體現(xiàn)一般性和特殊性的原則。4.多態(tài)性：多態(tài)性可以用“一個對外界面，多個內部實現(xiàn)”來表示。可以通過方法重載和方法重寫來實現(xiàn)多態(tài)。重載指一個類中可以有多個具有相同名稱的方法，由傳遞給它們的不同個數(shù)和類型的參數(shù)來決定執(zhí)行那個方法。重寫指子類可以重新實現(xiàn)父類的某些方法，使其具有自己的特征。多態(tài)性機制增加了面向對象軟件系統(tǒng)的靈活性，提高了軟件的可重用性和可擴充性。5.消息：面向對象系統(tǒng)中的對象之間是通過消息機制彼此相互合作的，消息是一個對象與另一個對象之間傳遞的信息，它請求對象執(zhí)行某一處理或回答某一要求的信息。2021/2/451面向對象程序設計的特點按照人的思維方式對客觀世界進行抽象穩(wěn)定性好可重用性好易于開發(fā)大型軟件可維護性好2021/2/452第三章軟件工程基礎考試大綱1.軟件工程基本概念，軟件生命周期的概念，軟件工具與軟件開發(fā)環(huán)境。

2.結構化分析方法，數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說明書。

3.結構化設計方法，總體設計與詳細設計。

4.軟件測試的方法，白盒測試與黑盒測試，測試用例設計，軟件測試的實施，單元測試、集成測試和系統(tǒng)測試。

5.程序的調試，靜態(tài)調試與動態(tài)調試。

2021/2/453知識點歸納軟件定義和特點計算機軟件式計算機系統(tǒng)中與硬件相互依存的另一部分，是包括程序、數(shù)據(jù)及相關文檔的完整集合。計算機軟件具有如下特點：軟件是一種邏輯實體，具有抽象性軟件生產沒有明顯的制造過程軟件在運行、使用期間不存在磨損、老化問題軟件的開發(fā)、運行對計算機系統(tǒng)具有依賴性軟件復雜性高，成本昂貴軟件開發(fā)涉及諸多社會因素2021/2/454軟件危機所謂軟件危機是指在計算機軟件開發(fā)和維護過程中所遇到的一系列嚴重問題，包括：軟件需求的增長得不到滿足軟件開發(fā)成本和進度無法控制軟件質量難以保證軟件不可維護或可維護性低軟件成本不斷提高軟件開發(fā)生產率的提高趕不上硬件的發(fā)展和應用需求的增長。2021/2/455軟件工程為了消除軟件危機，提出了軟件工程學。軟件工程是應用于計算機軟件定義、開發(fā)和維護的一整套方法、工具、文檔、實踐標準和工序。軟件工程的三要素方法工具過程2021/2/456軟件工程過程軟件工程過程是把輸入轉化為輸出的一組彼此相關的資源和活動。它包括兩方面含義：1.軟件工程過程是指為獲得軟件產品，在軟件工具支持下由軟件工程師完成的一系列工程活動。通常包括四種基本活動：P(Plan)：軟件規(guī)格說明D(Do)：軟件開發(fā)C(Check)：軟件確認A(Action)：軟件演進2.從軟件開發(fā)的觀點看，軟件工程過程是使用適當?shù)馁Y源，為開發(fā)軟件進行的一組開發(fā)活動，在活動結束時將輸入(用戶需求)轉化為輸出(軟件產品)。2021/2/457軟件生命周期軟件從提出、實現(xiàn)、使用、維護到停止使用的過程稱為軟件的生命周期。一般包括以下幾個階段：可行性研究與計劃制定需求分析軟件設計軟件實現(xiàn)軟件測試運行和維護2021/2/458軟件工程目標與原則軟件工程的目標是在給定成本、進度的前提下，開發(fā)出具有有效性、可靠性、可理解性、可維護性、可重用性、可適應性、可移植性、可追蹤性和可互操作性且滿足用戶需求的軟件產品。為達到上述目標，在軟件開發(fā)的過程中，必須遵循軟件工程的基本原則：抽象信息隱蔽模塊化局部化確定性一致性完備性可驗證性2021/2/459軟件開發(fā)工具與軟件開發(fā)環(huán)境軟件開發(fā)工具對過程和方法提供自動或半自動的支持。當這些工具被集成起來使得一個工具產生的信息可以被另外一個工具使用時，一個支持軟件開發(fā)的系統(tǒng)就建立起來了，稱為計算機輔助軟件工程(CASE)。CASE集成了軟件、硬件和一個軟件工程數(shù)據(jù)庫(包含了有關分析、設計、程序構造和測試的重要信息)從而創(chuàng)建了一個軟件開發(fā)環(huán)境。2021/2/460結構化分析方法結構化分析方法大多使用自頂向下、逐層分解的系統(tǒng)分析方法來定義系統(tǒng)需求。在結構化分析的基礎上，完成系統(tǒng)的規(guī)格說明，建立系統(tǒng)的一個自頂向下的任務分析模型。結構化分析方法是一種建模技術，模型的核心是數(shù)據(jù)辭典，它描述了所有在目標系統(tǒng)中使用和生成的數(shù)據(jù)對象。結構化分析常用的工具：數(shù)據(jù)流圖(DFD):描述數(shù)據(jù)在系統(tǒng)中如何被傳送或變換以及描述如何對數(shù)據(jù)流進行變換的功能，用于功能建模。數(shù)據(jù)字典判定樹判定表2021/2/461數(shù)據(jù)流圖數(shù)據(jù)流圖是描述數(shù)據(jù)處理過程的工具，它從數(shù)據(jù)傳遞和加工的角度，來刻畫數(shù)據(jù)流從輸入系統(tǒng)到從系統(tǒng)輸入的移動變換過程。數(shù)據(jù)流圖的基本元素外部實體數(shù)據(jù)流處理(加工)數(shù)據(jù)存儲2021/2/462數(shù)據(jù)字典數(shù)據(jù)字典是關于數(shù)據(jù)的信息的集合，對數(shù)據(jù)流圖中的各個元素進行完整的定義和說明。數(shù)據(jù)流圖和數(shù)據(jù)字典共同構成系統(tǒng)的邏輯模型。數(shù)據(jù)字典通常包含的信息有：名稱、別名、何處使用、如何使用、內容描述以及補充信息等。2021/2/463軟件需求軟件需求包括：功能需求、性能需求、環(huán)境需求、可靠性需求、安全保密需求、用戶界面需求、資源使用需求、成本消耗需求、開發(fā)進度需求等。需求分析應交付的主要文檔是軟件需求規(guī)格說明書(SRS)。2021/2/464結構化設計結構化設計就是采用最佳的可能方法設計系統(tǒng)的各個組成部分以及個成分之間的內部聯(lián)系的技術。也就是說，結構化設計是這樣一個過程：它決定用哪些方法把哪些部分聯(lián)系起來，才能解決好某個具體的有清楚定義的問題。從工程管理的角度看，軟件設計分兩步完成：1.概要設計，即總體設計。將軟件需求轉化為數(shù)據(jù)結構和軟件的系統(tǒng)結構。常用的軟件結構設計工具是結構圖(StructureChart)。2.詳細設計：即過程設計。通過對結構表示進行細化，得到軟件詳細的數(shù)據(jù)結構和算法。過程設計常用的工具有：程序流程圖、N-S圖、PAD圖、過程設計語言PDL(偽碼)。2021/2/465軟件測試定義：使用人工或自動手段來運行或測定某個系統(tǒng)的過程，其目的在于檢驗它是否滿足規(guī)定的需求或弄清預期結果與實際結果之間的差別。軟件測試是為了發(fā)現(xiàn)錯誤而執(zhí)行程序的過程。一個好的測試用例是指可能找到迄今為止尚未發(fā)現(xiàn)的錯誤的用例。一個成功的測試是發(fā)現(xiàn)了至今尚未發(fā)現(xiàn)的錯誤的測試。測試不能表明軟件中不存在錯誤，它只能說明軟件中存在錯誤。2021/2/466測試技術與方法綜述從是否需要執(zhí)行被測試軟件的角度，可將測試分為靜態(tài)測試和動態(tài)測試。靜態(tài)測試主要包括代碼檢查、靜態(tài)結構分析、代碼質量度量等。動態(tài)測試是基于計算機的測試，是為了發(fā)現(xiàn)錯誤而執(zhí)行程序的過程，或者說，是根據(jù)軟件開發(fā)的各個階段的規(guī)格說明和程序的內部結構而精心設計的一批測試用例，并利用這些測試用例去運行程序，以發(fā)現(xiàn)程序錯誤的過程。2021/2/467測試技術與方法綜述按照功能劃分，可將軟件測試分為黑盒測試和白盒測試。黑盒測試將測試對象看作一個黑盒，不考慮程序內部的邏輯結構和內部特性，只依據(jù)程序的需求規(guī)格說明，檢查程序的功能是否符合它的功能說明。這種測試又稱為功能測試或數(shù)據(jù)驅動測試。白盒測試把測試對象看作一個透明的盒子，利用程序內部的邏輯機構及有關信息，設計或選擇測試用例，對程序的所有邏輯路徑進行測試。通過在不同點檢查程序的狀態(tài)，確定實際的狀態(tài)是否與預期的一致。這種測試又稱為結構測試或邏輯驅動測試。2021/2/468軟件測試的實施軟件測試按四個步驟進行：單元測試：對軟件設計的最小單位－模塊進行正確性的測試，其目的是發(fā)現(xiàn)各模塊內部可能存在的各種錯誤。集成測試：是測試和組裝軟件的過程，它是在把模塊按照設計要求組裝起來的同時進行測試，主要目的是發(fā)現(xiàn)與接口有關的錯誤。確認測試：任務是驗證軟件的功能和性能以及其他特性是否滿足了需求規(guī)格說明中確定的各種需求，以及軟件配置是否完全、正確。系統(tǒng)測試：將通過確認測試的軟件，作為整個計算機系統(tǒng)的一個元素，與計算機硬件、外設、支持軟件、數(shù)據(jù)以及人員等其他系統(tǒng)元素組合在一起，在實際運行環(huán)境中對其進行一系列的集成測試和確認測試。2021/2/469程序調試程序調試的任務是診斷和修正程序中的錯誤。調試的方法：強行排錯法回溯法原因排除法2021/2/470第四章數(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ù)庫設計方法和步驟：需求分析、概念設計、邏輯設計和物理設計的相關策略。2021/2/471知識點歸納數(shù)據(jù)庫的定義1.長期存放在計算機內，有組織的、可共享的數(shù)據(jù)集合。數(shù)據(jù)庫中的數(shù)據(jù)按一定的數(shù)據(jù)模型組織、描述和存儲，具有較小的冗余度、較高的數(shù)據(jù)獨立性和易擴展性。2.數(shù)據(jù)庫是由一個互相關聯(lián)的數(shù)據(jù)的集合和一組用以訪問這些數(shù)據(jù)的程序組成的。2021/2/472數(shù)據(jù)庫管理系統(tǒng)(DBMS)數(shù)據(jù)庫管理系統(tǒng)是一個幫助用戶創(chuàng)建和管理數(shù)據(jù)庫的應用程序的集合。因此，數(shù)據(jù)庫管理系統(tǒng)也就是一個可以幫助完成定義、構造和操縱數(shù)據(jù)庫等處理目的的通用軟件系統(tǒng)。其主要功能如下：數(shù)據(jù)模式定義數(shù)據(jù)存取的物理構建數(shù)據(jù)操縱數(shù)據(jù)的完整性、安全性定義和檢查數(shù)據(jù)庫的并發(fā)控制和故障恢復數(shù)據(jù)的服務為完成上述功能，DBMS提供了相應的語言：數(shù)據(jù)定義語言(DDL)數(shù)據(jù)操縱語言(DML)數(shù)據(jù)控制語言(DCL)2021/2/473數(shù)據(jù)庫系統(tǒng)數(shù)據(jù)庫系統(tǒng)是由數(shù)據(jù)庫、數(shù)據(jù)庫管理系統(tǒng)、數(shù)據(jù)庫管理員、硬件平臺和軟件平臺等幾個部分組成的完整的運行實體。數(shù)據(jù)庫系統(tǒng)的特點數(shù)據(jù)的集成性數(shù)據(jù)的高共享性和低冗余性數(shù)據(jù)的獨立性數(shù)據(jù)統(tǒng)一管理和控制2021/2/474數(shù)據(jù)庫系統(tǒng)的內部體系結構三級模式概念模式：數(shù)據(jù)庫系統(tǒng)中全局數(shù)據(jù)邏輯結構的描述，全體用戶的數(shù)據(jù)視圖外模式：又稱為用戶模式，是每個用戶的局部數(shù)據(jù)描述，用戶的數(shù)據(jù)視圖內模式：又稱為物理模式，是數(shù)據(jù)庫物理存儲結構和物理存取方法的描述二級映射概念模式到內模式的映射外模式到概念模式的映射2021/2/475數(shù)據(jù)模型數(shù)據(jù)是現(xiàn)實世界符號的抽象，數(shù)據(jù)模型是現(xiàn)實世界數(shù)據(jù)特征的抽象，它從抽象層次上描述了系統(tǒng)的靜態(tài)特征、動態(tài)行為和約束條件，為數(shù)據(jù)庫系統(tǒng)的信息表示和操作提供一個抽象的框架。數(shù)據(jù)模型描述的內容包括三部分：數(shù)據(jù)結構數(shù)據(jù)操作數(shù)據(jù)約束數(shù)據(jù)模型按不同的應用層次分成三種類型：概念數(shù)據(jù)模型邏輯數(shù)據(jù)模型物理數(shù)據(jù)模型2021/2/476實體聯(lián)系(ER)模型概念模型是面向現(xiàn)實世界的，其出發(fā)點是有效地模擬顯示世界，給出數(shù)據(jù)的概念化結構。實體聯(lián)系模型是一種廣泛使用的概念模型，該模型將現(xiàn)實世界的要求轉化為實體、聯(lián)系和屬性等幾個基本概念，并用ER圖直觀地表示出來。2021/2/477ER模型的基本概念實體：概念世界中的基本單位，它們是客觀存在且能相互區(qū)別的事物。凡具有共性的實體可以組成一個集合稱為實體集。屬性：屬性用來描述實體的特征。一個實體可以有多個屬性，每個屬性可以有值，一個屬性的取值范圍稱為該屬性的值域。聯(lián)系：聯(lián)系反映概念世界中的實體集之間存在的一定關系。一對一聯(lián)系(1:1)一對多聯(lián)系(1:M)多對多聯(lián)系(M:N)2021/2/478ER圖ER圖是實體聯(lián)系模型的直觀圖形表示。實體用矩形表示，并在矩形中標明實體的名稱。屬性用標有屬性名稱的橢圓表示，而且必須用線將屬性與其所屬的實現(xiàn)相連。關系用標明關系名稱的菱形表示，關系的名稱一般是動詞。