計算機二級公共基礎知識-修正版ppt課件

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

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

3、算法的時間量度記作：T(n)=O(f(n)，表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同，稱為算法的(漸進)時間復雜度。,算法的復雜度,何估算算法的時間復雜度？ 任何一個算法都是由一個“控制結構”和若干“原操作”組成的，因此一個算法的執(zhí)行時間可以看成是所有原操作的執(zhí)行時間之和 ( 原操作(i)的執(zhí)行次數(shù)原操作(i)的執(zhí)行時間 )則算法的執(zhí)行時間與所有原操作的執(zhí)行次數(shù)之和成正比。從算法中選取一種對于所研究的問題來說是基本操作的原操作，以該基本操作在算法中重復執(zhí)行的次數(shù)作為算法時間復雜度的依據(jù)。這種衡量效率的辦法所得出的不是時間量，而是一種增長趨勢的量度。它與軟硬件環(huán)境無關，

4、只暴露算法本身執(zhí)行效率的優(yōu)劣。,算法的復雜度,算法的空間復雜度 算法的空間負雜度是指執(zhí)行這個算法所需要的內(nèi)存空間?？臻g復雜度作為算法所需存儲空間的量度，記作：S(n)=O(g(n)，其中n為問題的規(guī)模，表示隨問題規(guī)模的增大，算法運行所需存儲量的增長率與g(n)的增長率相同。,數(shù)據(jù)結構,利用計算機進行數(shù)據(jù)處理是計算機應用的一個重要領域。數(shù)據(jù)結構主要研究和討論以下三個方面的問題： 數(shù)據(jù)集合中各數(shù)據(jù)元素之間的邏輯關系，即數(shù)據(jù)的邏輯結構。 在對數(shù)據(jù)進行處理時，各數(shù)據(jù)元素在計算機中的存儲關系，即數(shù)據(jù)的存儲結構。 對各種數(shù)據(jù)結構進行的運算。,數(shù)據(jù)的邏輯結構,數(shù)據(jù)邏輯結構是對數(shù)據(jù)元素之間存在的邏輯關系的描述

5、，它可以用一個數(shù)據(jù)元素的集合和定義在此集合上的若干關系表示。 與數(shù)據(jù)在計算機中的存儲位置無關，是獨立于計算機的。,數(shù)據(jù)的存儲結構,數(shù)據(jù)的存儲結構是數(shù)據(jù)元素及其關系在計算機存儲器中的表示。存儲結構的主要內(nèi)容是指在存儲空間中使用一個存儲結點來存儲一個數(shù)據(jù)元素，在存儲空間中建立各存儲結點之間的關聯(lián)，來表示數(shù)據(jù)元素之間的邏輯關系。 常見的存儲結構： 順序存儲結構 鏈式存儲結構 索引存儲結構 散列存儲結構,線性結構和非線性結構,線性結構 在數(shù)據(jù)元素的非空有限集合中，線性結構的邏輯特征如下： 存在一個唯一的被稱為“第一個”的數(shù)據(jù)元素 存在一個唯一的被稱為“最后一個”的數(shù)據(jù)元素 除第一個之外，集合中的每個數(shù)

6、據(jù)元素均有且只有一個直接前驅 除最后一個之外，集合中的每個數(shù)據(jù)元素均有且只有一個直接后繼 非線性結構 非線性結構的邏輯特征是： 一個結點可能有多個直接前驅和直接后繼，樹和圖都屬于非線性結構。,線性表,通常以下列 n 個數(shù)據(jù)元素的序列”表示線性表 ： (a1,a2 ,.,ai ,.,an) 序列中數(shù)據(jù)元素的個數(shù) n 定義為線性表的表長；n=0 時的線性表被稱為空表。稱 i 為ai在線性表中的位序。,線性表的順序存儲,線性表的順序存儲結構用一組地址連續(xù)的存儲單元依次存放線性表中的數(shù)據(jù)元素，即以“存儲位置相鄰”表示“位序相繼的兩個數(shù)據(jù)元素之間的前驅和后繼的關系，并以表中第一個元素的存儲位置作為線性表

7、的起始地址，稱作線性表的基地址。,所有數(shù)據(jù)元素的存儲位置均可由第一個數(shù)據(jù)元素的存儲位置得到 ADR(ai) = ADR(a1) + (i-1)C 基地址 一個數(shù)據(jù)元素所占存儲量,線性表的插入和刪除運算,插入運算是指在線性表的某個指定位置增加一個新結點。 一般情況下，要在第i(1in)個元素之前插入一個新元素時，首先要從最后一個元素開始，直到第i個元素之間共n-i+1個元素依次向后移動一個位置，然后將新元素插入到第i項。 刪除運算是指撤銷結構中的某個結點。 一般情況，要刪除第i(1in)個元素，要從第i+1個元素開始，直到第n個元素，共n-i個元素依次向前移動一個位置。,棧,棧是限定僅在表的一端

8、進行插入和刪除操作的線性表。允許插入和刪除的一端稱為棧頂，另一端稱為棧底。 棧頂元素總是最后被插入的元素，從而也是最先被刪除的元素；棧底元素總是最先被插入，也是最后被刪除的元素。因此，棧是一種后進先出的線性表。 通常用指針top指示棧頂位置，用指針bottom指示棧底位置。,棧的順序存儲及運算,用一維數(shù)組S(1:m)作為棧的順序存儲空間，m為棧的最大容量。top=0表示棧為空，top=m表示棧滿。 棧的操作 入棧：在棧頂位置插入一個新元素，棧頂指針top加1。 退棧：取出棧頂元素并賦值給一個指定的變量，棧頂指針top減1。 取棧頂元素：將棧頂元素的值賦給一個指定的變量，不刪除棧頂元素，棧頂指針

9、不變。,隊列,隊列是一種先進先出的線性表，它只允許在表的一端插入元素(隊尾)，在另一端刪除元素(隊頭)。通常定義頭指針front指向隊頭元素的前一個位置，定義尾指針rear指向隊尾元素的位置。 隊列是一種先進先出的數(shù)據(jù)結構。 向隊尾插入一個元素的操作稱為入隊，從隊頭刪除一個元素的操作稱為退隊。,循環(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)隊列為空或為滿時，均有fron

10、t=rear，因此需要設置標志s進行區(qū)分，定義s=0表示隊列為空，s=1表示隊列非空。,單鏈表,線性表的鏈式存儲結構的特點是用一組任意的存儲單元(可以連續(xù)，也可以不連續(xù))存儲線性表的數(shù)據(jù)元素，為了表示每個數(shù)據(jù)元素ai與其直接后繼元素ai+1之間的邏輯關系，對數(shù)據(jù)元素ai來說，除了存儲其本身的信息(數(shù)據(jù)域)之外，還需要存儲其后繼元素的存儲位置信息(指針域)。 指針域中存儲的信息稱為指針或鏈，N個結點鏈接成一個鏈表，即為線性表的鏈式存儲結構。由于結點中只包含一個指針域，故稱為單鏈表。,單鏈表,通常以單鏈表中第一個數(shù)據(jù)元素的存儲地址作為作為單鏈表的地址，稱為頭指針。整個鏈表的存儲必須從頭指針開始(順

11、序存取)，頭指針指示鏈表中第一個結點的存儲位置。最后一個數(shù)據(jù)元素沒有直接后繼，其指針域為空。,單鏈表的插入和刪除,雙向鏈表和循環(huán)鏈表,在雙向鏈表中的結點包含兩個指針域，其中一個指向直接后繼，另一個指向直接前驅。 循環(huán)鏈表的特點是表中最后一個結點的指針域指向第一個結點，整個鏈表成為一個由鏈指針相鏈接的環(huán)。據(jù)此，從表中任一節(jié)點出發(fā)均可找到表中其它結點。在循環(huán)鏈表中增加了一個表頭結點，其指針域指向第一個元素結點，頭指針則指向頭結點。,樹及其基本概念,樹是一種簡單的非線性結構，在樹中，所有的數(shù)據(jù)元素之間具有明顯的層次性關系。 樹是(n0)個結點的有限集合，在任意一棵非空樹中： (1)有且僅有一個特定的

12、結點稱為根結點。 (2)當n1時，其余的結點可分為m個互不相交的子集T1,T2,Tm，其中每個有限子集本身又是一棵樹，并且稱為根的子樹。 集合為空的樹簡稱為空樹；樹中的元素稱為結點。,樹的主要術語,結點的度：結點擁有的子樹數(shù)。 葉節(jié)點(終端結點)：度為0的結點。 雙親、孩子和兄弟：結點的子樹的根節(jié)點稱為該結點的孩子，該結點稱為孩子結點的雙親結點。同一個雙親結點的孩子互稱為兄弟。 層次：結點的層次從根開始定義，根為第一層，根的孩子為第二層。 深度：樹中結點的最大層次稱為樹的深度或高度。,二叉樹,二叉樹是n(n0)個數(shù)據(jù)元素的有限集，它或為空集,或者含有唯一的稱為根的元素，且其余元素分成兩個互不相

13、交的子集，每個子集自身也是一棵二叉樹，分別稱為根的左子樹和右子樹。 二叉樹是另一種樹型結構，其特點是每個結點至多有兩棵子樹，并且二叉樹的子樹有左右之分，其順序不能任意顛倒。,二叉樹的基本性質,性質1 在二叉樹的第i層上至多有2i-1個結點（i1） 性質2 深度為k的二叉樹至多有2k -1個結點（k1） 性質3 對任何一棵二叉樹T，如果其終端結點數(shù)為n0，度為2的結點數(shù)為n2 ，則：n0 =n2+1 性質4 具有n個結點的二叉樹，其深度至少為log2n +1,滿二叉樹和完全二叉樹,滿二叉樹除最后一層外，每一層上的所有結點都有兩個子節(jié)點，也就是說每一層上的結點數(shù)都達到最大值，即在滿二叉樹的第k層上

14、有2k-1個結點，且深度為m的滿二叉樹有2m-1個結點。 完全二叉樹除最后一層外，每一層上的結點數(shù)均達到最大值，在最后一層上只缺少右邊的若干結點。具有n個結點的完全二叉樹，其深度為log2n +1。 從以上定義可知，滿二叉樹也是完全二叉樹，反之則不然。,二叉樹的基本性質,性質5 如果對一棵有 n 個結點的完全二叉樹（其深度為log2n +1）的結點按層序（從第1層到第log2n +1 層，每層從左到右）從1起開始編號，則對任一編號為 i 的結點(1in)，則:(1) 如果 i=1，則編號為 i 的結點是二叉樹的根，無雙親；如果 i1，則其雙親結點 parent(i)的編號是i/2。(2) 如果

15、 2in，則編號為 i 的結點無左孩子（編號為 i 的結點為葉子結點）；否則其左孩子結點 lChild(i) 的編號是 2i 。(3) 如果 2i+1n，則編號為 i 的結點無右孩子；否則其右孩子結點 rChild(i) 的編號是結點 2i+1。,二叉樹的鏈式存儲結構,在二叉樹的鏈式存儲結構中，每個結點設置三個域，即數(shù)據(jù)域，左指針域和右指針域，兩個指針域分別存儲左右子樹根節(jié)點的存儲位置，即指針。,二叉樹的鏈式存儲結構,二叉樹的遍歷,二叉樹的遍歷指不重復地訪問二叉樹的所有結點。從二叉樹的結構定義得知，二叉樹是由根結點、左子樹和右子樹三部分構成，則遍歷二叉樹的操作可分解為訪問根結點、遍歷左子樹和遍

16、歷右子樹三個子操作，并且由二叉樹的遞歸定義可知，遍歷左子樹和遍歷右子樹可如同遍歷二叉樹一樣遞歸進行。,二叉樹的遍歷,先序遍歷：ABDEGHCFIJ 中序遍歷：DBGEHACIJF 后序遍歷：DGHEBJIFCA,查找,查找是指在一個給定的數(shù)據(jù)結構中查找某個指定的元素。 順序查找 順序查找一般是指在線性表中查找指定元素，基本方法如下：從線性表的第一個元素開始，依次將線性表中的元素與被查找元素進行比較，若相等則表示找到，即查找成功；若線性表中的所有元素與被查找元素都不相等，則查找失敗。 如果線性表為無序表，即表中元素的排列是無序的，則不管線性表采用順序存儲還是鏈式存儲，都必須使用順序查找。 如果線

17、性表有序，但采用鏈式存儲結構，則也必須使用順序查找。,查找,二分查找(折半查找) 二分查找法只適用于順序存儲的有序表。先確定待查目標元素所在范圍(區(qū)間)，然后逐步縮小范圍直至找到該元素，或者當查找區(qū)間縮小到0也沒有找到目標元素為止。 查找過程中，給定值首先和處于待查區(qū)間中間位置的關鍵字進行比較，若相等，則查找成功，否則將查找區(qū)間縮小到前半個區(qū)間 或 后半個區(qū)間 之后繼續(xù)進行查找。,折半查找,二分查找,排序,排序是指將一個無序序列整理成按值遞增或遞減(本章均采用遞增規(guī)則)的有序序列。 排序可以在各種不同的存儲結構上實現(xiàn)，本章所介紹的算法以順序存儲的線性表為排序對象，在程序設計語言中就是一維數(shù)組。

18、 排序的算法種類很多，主要包括交換類排序、插入類排序、選擇類排序等。,排序方法,插入排序,選擇排序,交換排序,簡單插入排序,希爾排序,簡單選擇排序,堆排序,冒泡排序,快速排序,交換類排序,冒泡排序 基本思想：從表頭開始掃描線性表，在掃描的過程中依次比較相鄰兩個元素的大小，若前面的元素大于后面的元素，則交換它們的位置。顯然，在掃描過程中，不斷地將將相鄰元素間較大的向后移動，最后將線性表中最大的元素移到表尾。 然后，從后向前掃描剩下的線性表，同樣在掃描的過程中依次比較相鄰兩個元素的大小，若后面的元素小于前面的元素，則交換位置。在掃描過程中，不斷地將將相鄰元素間較小的向前移動，最后將線性表中最小的元

19、素移到表頭。 對剩下的線性表重復上述過程，直到剩余線性表為空為止，此時線性表變?yōu)橛行颉?冒泡排序示例,第一遍(從前向后),第一遍(從后向前),第二遍(從前向后),第二遍(從后向前),快速排序,基本思想：從線性表中選取一個元素，設為T，將線性表后面小于T的元素移動到前面，將前面大于T的元素移動到后面，將線性表分為兩個部分(子表)，T放到分界線的位置，這個過程稱為線性表的分割，通過一次分割，就以T為分界將線性表分為兩個子表，前面的子表中的所有元素均不大于T，而后面子表中的元素均不小于T。按照上述原則對子表繼續(xù)進行分割，直到子表為空，則整個線性表有序。,快速排序,操作步驟： 首先，在表的第一個元素、

20、最后一個元素和中間元素中選取一個中值，設為P(k)，并將P(k)賦值給T，再將表中的第一個元素移到P(k) 的位置。設兩個指針i，j分別指向表的起始和最后位置，反復操作以下兩步： 將j逐漸減小，并逐次比較P(j)和T，直到發(fā)現(xiàn)一個P(j)T為止，并將P(i)移到 P(j)的位置上。 上述兩步操作交替進行，直到i和j指向同一個位置，再將T移動到P(i)的位置上，完成一次分割。,31,暫存樞軸記錄T：,12,12,68,68,23,23,45,45,31,31,快速排序的一次分割過程,31,插入類排序,簡單插入排序 基本思想：將待排序列表分成兩部分：已排序部分和未排序部分。每次掃描將未排序列表中的

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

22、元素進行交換。經(jīng)過一次選擇和交換，列表中已排序部分增加一個元素，未排序部分減少一個元素。每次把一個元素從未排序部分移動到已排序部分稱為完成一次分類掃描或稱為一趟排序。 一個包含n個元素的列表需要進行n-1次掃描完成排序。,簡單選擇排序示例,原始序列,第1趟,第2趟,第3趟,第4趟,第5趟,2堆排序也是一種選擇排序。是具有特定條件的順序存儲的完全二叉樹，其特定條件是：任何一個非葉子結點的關鍵字大于等于（或小于等于）子女的關鍵字的值。 (1) 堆的示例,(a):堆頂元素取最大值,(b):堆頂元素取最小值,(2) 實現(xiàn)堆排序需解決兩個問題： （1） 如何由一個無序序列建成一個堆？ （2） 輸出堆頂元

23、素后，如何將剩余元素調(diào)整成一個新的堆？,堆排序需要比較的次數(shù)為O(nlog2n),第二章 程序設計基礎(15%),考試大綱 1. 程序設計方法與風格。2. 結構化程序設計。3. 面向對象的程序設計方法，對象，方法，屬性及繼承與多態(tài)性。,知識點歸納,程序設計方法 程序設計是一門技術，需要相應的理論、方法和工具來支持。就程序設計方法和技術的發(fā)展而言，主要經(jīng)歷了結構化的程序設計和面向對象的程序設計階段。 在程序設計中，通常采用“自頂向下，逐步求精”的方法，即把一個模塊的功能逐步分解，細化為一系列具體的步驟，進而轉換成一系列用某種程序設計語言編寫的程序。,程序設計風格,除了程序設計設計方法和技術之外，

24、程序風格也是非常重要的。良好的程序設計風格概括起來包括以下及格方面： 源程序文檔化 數(shù)據(jù)說明的方法 語句的結構 輸入和輸出,程序設計風格,源程序文檔化 標識符的命名 程序的注釋 序言性注釋 功能性注釋 程序的視覺組織 數(shù)據(jù)的說明 數(shù)據(jù)說明的次序應該規(guī)范化 說明語句中變量的安排有序化 使用注釋說明復雜的數(shù)據(jù)結構,程序設計風格,語句結構 在一行內(nèi)只寫一條語句 程序編寫應優(yōu)先考慮清晰性 除非對效率有特殊要求，程序編寫要做到清晰第一，效率第二 首先要保證程序正確，然后才要求提高速度 避免使用臨時變量而使程序的可讀性下降 避免不必要的轉移 盡可能使用庫函數(shù) 避免使用復雜的條件語句 盡量減少使用“否定”條

25、件的條件語句 數(shù)據(jù)結構要有利于程序的簡化 要模塊化，使模塊功能盡可能單一化 利用信息隱蔽，確保每一個模塊的獨立性 從數(shù)據(jù)出發(fā)構造程序 不要修補不好的程序，要重寫編寫,程序設計風格,輸入和輸出 對所有輸入數(shù)據(jù)檢驗合法性 檢查輸入項的各種重要組合的合法性 輸入格式要簡單，以使輸入的步驟和操作盡可能簡單 輸入數(shù)據(jù)時，應允許使用自由格式 應允許缺省值 輸入一批數(shù)據(jù)時，最好使用輸入結束標志 在以交互式輸入/輸出方式進行輸入時，要在屏幕上使用提示符明確提示輸入的請求，同時在數(shù)據(jù)輸入結束時，應在屏幕上給出狀態(tài)信息 當程序設計語言對輸入格式有嚴格要求時，應保持輸入格式與輸入語句的一致性；給所有的輸出加注釋，并

26、設計輸出報表格式。,結構化程序設計,結構化程序設計的原則 自頂向下。程序設計時，應先考慮總體，后考慮細節(jié)；先考慮全局目標，后考慮局部目標。不要一開始就過多追求細節(jié)，先從最上層總目標開始設計，逐步使問題具體化。 逐步求精。對復雜的問題，應設計一些子目標過渡，逐步細化。 模塊化。一個復雜問題肯定是有若干簡單問題構成。模塊化是把程序要解決的總目標分解為分目標，再進一步分解為具體的小目標，每個小目標成為一個模塊。 嚴格限制GOTO語句的使用。,結構化程序設計的基本結構和特點,程序由一些基本結構組成，任何一個程序都可以用三種基本控制結構組成：順序結構、選擇結構和循環(huán)結構，并且具有如下特點：單入口、單出口

27、、結構中無死循環(huán)，程序中三種基本控制結構之間形成順序執(zhí)行關系。 一個大型程序應按功能分割成一些模塊，并把這些模塊按層次關系進行組織。 在程序設計時應采用自頂向下、逐步細化的實施方法。,面向對象程序設計,面向對象方法的基本概念 1.對象、類和屬性 在面向對象程序設計中，對象是程序的基本單位。對象可以表示客觀世界中的任何實體，是對問題域中某個實體的抽象。每個對象可以用它本身的一組屬性和它可以執(zhí)行的一組操作來定義。類是對一組具有共同屬性和相似行為的對象的一種抽象，描述了屬于該類的所有對象的性質。 2.方法 方法有稱為操作或服務，它描述了對象執(zhí)行的功能，若通過消息傳遞，還可為其他對象使用。,面向對象方

28、法的基本概念,3.繼承：繼承是對象方法的一個重要特征。指一個類(子類)直接使用另一個類(父類)的所有屬性和方法。它可以減少相似類的重復說明，從而體現(xiàn)一般性和特殊性的原則。 4.多態(tài)性：多態(tài)性可以用“一個對外界面，多個內(nèi)部實現(xiàn)”來表示?？梢酝ㄟ^方法重載和方法重寫來實現(xiàn)多態(tài)。重載指一個類中可以有多個具有相同名稱的方法，由傳遞給它們的不同個數(shù)和類型的參數(shù)來決定執(zhí)行那個方法。重寫指子類可以重新實現(xiàn)父類的某些方法，使其具有自己的特征。多態(tài)性機制增加了面向對象軟件系統(tǒng)的靈活性，提高了軟件的可重用性和可擴充性。 5.消息：面向對象系統(tǒng)中的對象之間是通過消息機制彼此相互合作的，消息是一個對象與另一個對象之間傳

29、遞的信息，它請求對象執(zhí)行某一處理或回答某一要求的信息。,面向對象程序設計的特點,按照人的思維方式對客觀世界進行抽象 穩(wěn)定性好 可重用性好 易于開發(fā)大型軟件 可維護性好,第三章 軟件工程基礎,考試大綱 1. 軟件工程基本概念，軟件生命周期的概念，軟件工具與軟件開發(fā)環(huán)境。2. 結構化分析方法，數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說明書。3. 結構化設計方法，總體設計與詳細設計。4. 軟件測試的方法，白盒測試與黑盒測試，測試用例設計，軟件測試的實施，單元測試、集成測試和系統(tǒng)測試。5. 程序的調(diào)試，靜態(tài)調(diào)試與動態(tài)調(diào)試。,知識點歸納,軟件定義和特點 計算機軟件式計算機系統(tǒng)中與硬件相互依存的另一部分，是包括程

30、序、數(shù)據(jù)及相關文檔的完整集合。計算機軟件具有如下特點： 軟件是一種邏輯實體，具有抽象性 軟件生產(chǎn)沒有明顯的制造過程 軟件在運行、使用期間不存在磨損、老化問題 軟件的開發(fā)、運行對計算機系統(tǒng)具有依賴性 軟件復雜性高，成本昂貴 軟件開發(fā)涉及諸多社會因素,軟件危機,所謂軟件危機是指在計算機軟件開發(fā)和維護過程中所遇到的一系列嚴重問題，包括： 軟件需求的增長得不到滿足 軟件開發(fā)成本和進度無法控制 軟件質量難以保證 軟件不可維護或可維護性低 軟件成本不斷提高 軟件開發(fā)生產(chǎn)率的提高趕不上硬件的發(fā)展和應用需求的增長。,軟件工程,為了消除軟件危機，提出了軟件工程學。軟件工程是應用于計算機軟件定義、開發(fā)和維護的一整

31、套方法、工具、文檔、實踐標準和工序。 軟件工程的三要素 方法 工具 過程,軟件工程過程,軟件工程過程是把輸入轉化為輸出的一組彼此相關的資源和活動。它包括兩方面含義： 1. 軟件工程過程是指為獲得軟件產(chǎn)品，在軟件工具支持下由軟件工程師完成的一系列工程活動。通常包括四種基本活動： P(Plan)：軟件規(guī)格說明 D(Do)：軟件開發(fā) C(Check)：軟件確認 A(Action)：軟件演進 2.從軟件開發(fā)的觀點看，軟件工程過程是使用適當?shù)馁Y源，為開發(fā)軟件進行的一組開發(fā)活動，在活動結束時將輸入(用戶需求)轉化為輸出(軟件產(chǎn)品)。,軟件生命周期,軟件從提出、實現(xiàn)、使用、維護到停止使用的過程稱為軟件的生命

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

33、，稱為計算機輔助軟件工程(CASE)。CASE集成了軟件、硬件和一個軟件工程數(shù)據(jù)庫(包含了有關分析、設計、程序構造和測試的重要信息)從而創(chuàng)建了一個軟件開發(fā)環(huán)境。,結構化分析方法,結構化分析方法大多使用自頂向下、逐層分解的系統(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ù)字典 判定樹 判定表,數(shù)據(jù)流圖,數(shù)據(jù)流圖是

34、描述數(shù)據(jù)處理過程的工具，它從數(shù)據(jù)傳遞和加工的角度，來刻畫數(shù)據(jù)流從輸入系統(tǒng)到從系統(tǒng)輸入的移動變換過程。 數(shù)據(jù)流圖的基本元素 外部實體 數(shù)據(jù)流 處理(加工) 數(shù)據(jù)存儲,數(shù)據(jù)字典,數(shù)據(jù)字典是關于數(shù)據(jù)的信息的集合，對數(shù)據(jù)流圖中的各個元素進行完整的定義和說明。數(shù)據(jù)流圖和數(shù)據(jù)字典共同構成系統(tǒng)的邏輯模型。 數(shù)據(jù)字典通常包含的信息有：名稱、別名、何處使用、如何使用、內(nèi)容描述以及補充信息等。,軟件需求,軟件需求包括：功能需求、性能需求、環(huán)境需求、可靠性需求、安全保密需求、用戶界面需求、資源使用需求、成本消耗需求、開發(fā)進度需求等。 需求分析應交付的主要文檔是軟件需求規(guī)格說明書(SRS)。,結構化設計,結構化設計就

35、是采用最佳的可能方法設計系統(tǒng)的各個組成部分以及個成分之間的內(nèi)部聯(lián)系的技術。也就是說，結構化設計是這樣一個過程：它決定用哪些方法把哪些部分聯(lián)系起來，才能解決好某個具體的有清楚定義的問題。從工程管理的角度看，軟件設計分兩步完成： 1.概要設計，即總體設計。將軟件需求轉化為數(shù)據(jù)結構和軟件的系統(tǒng)結構。常用的軟件結構設計工具是結構圖(Structure Chart)。 2.詳細設計：即過程設計。通過對結構表示進行細化，得到軟件詳細的數(shù)據(jù)結構和算法。過程設計常用的工具有：程序流程圖、N-S圖、PAD圖、過程設計語言PDL(偽碼)。,軟件測試,定義： 使用人工或自動手段來運行或測定某個系統(tǒng)的過程，其目的在于

36、檢驗它是否滿足規(guī)定的需求或弄清預期結果與實際結果之間的差別。 軟件測試是為了發(fā)現(xiàn)錯誤而執(zhí)行程序的過程。 一個好的測試用例是指可能找到迄今為止尚未發(fā)現(xiàn)的錯誤的用例。 一個成功的測試是發(fā)現(xiàn)了至今尚未發(fā)現(xiàn)的錯誤的測試。 測試不能表明軟件中不存在錯誤，它只能說明軟件中存在錯誤。,測試技術與方法綜述,從是否需要執(zhí)行被測試軟件的角度，可將測試分為靜態(tài)測試和動態(tài)測試。 靜態(tài)測試主要包括代碼檢查、靜態(tài)結構分析、代碼質量度量等。 動態(tài)測試是基于計算機的測試，是為了發(fā)現(xiàn)錯誤而執(zhí)行程序的過程，或者說，是根據(jù)軟件開發(fā)的各個階段的規(guī)格說明和程序的內(nèi)部結構而精心設計的一批測試用例，并利用這些測試用例去運行程序，以發(fā)現(xiàn)程序

37、錯誤的過程。,測試技術與方法綜述,按照功能劃分，可將軟件測試分為黑盒測試和白盒測試。 黑盒測試將測試對象看作一個黑盒，不考慮程序內(nèi)部的邏輯結構和內(nèi)部特性，只依據(jù)程序的需求規(guī)格說明，檢查程序的功能是否符合它的功能說明。這種測試又稱為功能測試或數(shù)據(jù)驅動測試。 白盒測試把測試對象看作一個透明的盒子，利用程序內(nèi)部的邏輯機構及有關信息，設計或選擇測試用例，對程序的所有邏輯路徑進行測試。通過在不同點檢查程序的狀態(tài)，確定實際的狀態(tài)是否與預期的一致。這種測試又稱為結構測試或邏輯驅動測試。,軟件測試的實施,軟件測試按四個步驟進行： 單元測試：對軟件設計的最小單位模塊進行正確性的測試，其目的是發(fā)現(xiàn)各模塊內(nèi)部可能存

38、在的各種錯誤。 集成測試：是測試和組裝軟件的過程，它是在把模塊按照設計要求組裝起來的同時進行測試，主要目的是發(fā)現(xiàn)與接口有關的錯誤。 確認測試：任務是驗證軟件的功能和性能以及其他特性是否滿足了需求規(guī)格說明中確定的各種需求，以及軟件配置是否完全、正確。 系統(tǒng)測試：將通過確認測試的軟件，作為整個計算機系統(tǒng)的一個元素，與計算機硬件、外設、支持軟件、數(shù)據(jù)以及人員等其他系統(tǒng)元素組合在一起，在實際運行環(huán)境中對其進行一系列的集成測試和確認測試。,程序調(diào)試,程序調(diào)試的任務是診斷和修正程序中的錯誤。 調(diào)試的方法： 強行排錯法 回溯法 原因排除法,第四章 數(shù)據(jù)庫設計基礎,考試大綱 1. 數(shù)據(jù)庫的基本概念：數(shù)據(jù)庫，數(shù)

39、據(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ù)庫設計方法和步驟：需求分析、概念設計、邏輯設計和物理設計的相關策略。,知識點歸納,數(shù)據(jù)庫的定義 1.長期存放在計算機內(nèi)，有組織的、可共享的數(shù)據(jù)集合。數(shù)據(jù)庫中的數(shù)據(jù)按一定的數(shù)據(jù)模型組織、描述和存儲，具有較小的冗余度、較高的數(shù)據(jù)獨立性和易擴展性。 2.數(shù)據(jù)庫是由一個互相關聯(lián)的數(shù)據(jù)的集合和一組用以訪問這些數(shù)據(jù)的程序組成的。,數(shù)據(jù)庫管理系統(tǒng)(DBMS),數(shù)據(jù)庫管理系統(tǒng)是一個幫助用戶創(chuàng)建和管理數(shù)據(jù)庫的應用程序的集合。因此，數(shù)據(jù)庫

40、管理系統(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),數(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)一管理和控制,數(shù)據(jù)庫系統(tǒng)的內(nèi)部體系結構,三級模式 概念模式：數(shù)據(jù)庫系統(tǒng)中全局數(shù)

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