全國計算機二級公共基礎知識復習

1、全國計算機二級公共根底知識一、數據構造與算法數據構造指的是數據之間的相互關系，即數據的組織形式。數據構造用來反映一個數據的內部構成，即一個數據由哪些成分構成、以什么方式構成、呈現什么樣的構造。數據構造有邏輯上的數據構造與物理上的數據構造之分。邏輯上的數據構造反映數據之間的邏輯關系，而物理上的數據構造反映數據在計算機內部的存儲安排。數據構造是數據存在的形式。算法是解題的步驟，是指令的有限序列。它們規(guī)定了解決某一特定類型問題的一系列運算，是對解題方案的準確與完整的描述。一個問題的解決方案要以算法為根底。1.1 概念介紹 算法的時間復雜度：算法的時間復雜度是指執(zhí)行算法所需要的計算工作量。算法的工作量

2、用算法所執(zhí)行的根本運算次數來度量，而算法所執(zhí)行的根本運算次數是問題規(guī)模的函數，即 算法的工作量=f(n)其中n是問題的規(guī)模。 例如，兩個n階矩陣相乘所需要的根本運算(即兩個實數的乘法)次數為n3，即計算工作量為n3，也就是時間復雜度為n3。 算法的空間復雜度：算法的空間復雜度一般是指執(zhí)行這個算法所需要的內存空間。數據的邏輯構造數據元素相互之間的關系，稱為構造。數據的邏輯構造：是指反映數據元素之間邏輯關系的數據構造。數據的存儲構造數據的存儲構造：是數據的邏輯構造在計算機存儲空間中的存放形式。也稱數據的物理構造。各數據元素在計算機存儲空間中的位置關系與它們的邏輯關系不一定是一樣的。同一種數據的邏輯

3、構造可以根據需要表示成任意一種或幾種不同的存儲構造。數據的順序存儲方式：是將邏輯上相鄰的結點存儲在物理位置上亦相鄰的存儲單元里。也就是將所有存儲結點相繼存入在一個連續(xù)相鄰的存儲區(qū)里。數據的鏈式存儲方式：是在存儲每個結點信息的同時，增加一個指針來表示結點間的邏輯關系。該方式不要求邏輯上相鄰結點在物理位置上亦相鄰，結點間的邏輯關系是由附加的指針字段表示的。因此，鏈式存儲構造中的每個結點都由兩局部組成：一局部用于存儲結點本身的信息，稱為數據域；另一局部用于存儲該結點的后繼結點(或前驅結點)的存儲單元地址，稱為指針域。指針域可以包含一個或多個指針，這由結點之間的關系所決定。線性構造與非線性構造如果在一

4、個線性構造中，一個數據元素都沒有，那么稱該數據構造為空數據構造。線性構造的邏輯特征：在一個非空的數據構造中，除第一個數據元素只有一個后繼沒有前驅、最后一個數據元素只有一個前驅沒有后繼外，其他的每一個數據元素僅有一個前驅與一個后繼。線性構造也稱為線性表。注：某個元素直接相鄰的前一個元素稱為此元素的前驅、直接相鄰的后一個元素稱為此元素的后繼。非線性構造的邏輯特征：在一個非空的數據構造中，某數據元素可能有多于一個前驅或后繼。如樹型構造等。習題：一選擇題(單項選擇)1. 算法的時間復雜度是指DA) 算法的執(zhí)行時間B) 算法所處理的數據量C) 算法程序中的語句或指令條數D) 算法在執(zhí)行過程中所需要的根本

5、運算次數1.2線性表線性表是由同一類型的數據元素構成的一種線性的數據構造。是一種最根本、最常用的數據構造。線性表常用的存儲方式有兩種：順序存儲方式與鏈接存儲方式。線性表的數學定義：L=(a1,a2,a3,an)說明：線性表是具有一樣類型的n(n0)個數據元素組成的有限序列。L：為表的名稱。ai(i=1,2, ,n)：為表的元素，也稱為線性表中的一個結點。它可以是一個數、一個字符、一個字符串，也可以是一條記錄，還可以是復雜的數據對象。a1是a2的前驅、a2是a1的后繼， a2是a3的前驅、a3是a2的后繼，依次類推。n：為線性表的長度(元素個數)，當n=0時稱線性表為空表。線性表的特點：在非空的

6、線性表中：存在唯一的一個“第一個元素(根結點)。存在唯一的一個“最后一個元素(終端結點)。除第一個元素外，其他的元素均有唯一的前驅。除最后一個元素外，其他的元素均有唯一的后繼。1.3棧與隊列棧與隊列本質上也是線性表，只是它們的操作受到了限制。1.3.1棧棧是限定僅在表尾進展插入與刪除操作的線性表。表尾稱為棧頂(top)，表頭稱為棧底(bottom)。棧這種數據構造，類似于子彈夾，底端是封閉的，最后壓入的子彈總是最先被彈出，最先壓入的子彈只能最后被彈出。棧頂元素總是最后被插入的元素，從而也是最先能被刪除的元素；棧底元素總是最先被插入的元素，從而也是最后能被刪除的元素。即棧是按照“先進后出或“后進

7、先出的原那么組織數據的。因此，棧也被稱為“先進后出表或“后進先出表。由此可以看出，棧具有記憶作用。1.3.2隊列隊列是指只允許在表的一端插入元素、在另一端刪除元素的線性表。允許插入的一端稱為隊尾(rear)，允許刪除的一端稱為隊頭(front)。在隊列這種數據構造中，最先插入的元素將最先能夠被刪除，反之最后插入的元素將最后才能被刪除。因此，隊列又稱為“先進先出或“后進后出的線性表。1.4樹與二叉樹1.4.1樹樹形構造是數據構造中一種很重要的非線性構造。在樹形構造中，所有數據元素之間的關系具有明顯的層次特性。樹形構造很像自然界中的樹，像一棵倒長的樹。在現實生活中，能用樹形構造表示的例子很多。參見

8、下面的圖形：樹形構造的根本特征及根本術語：以以下圖為例：樹的根：在樹形構造中，沒有前驅的結點只有一個，稱為樹的根結點，簡稱為樹的根。如：上圖中的“R。父結點：在樹形構造中，每一個結點(除了樹的根結點)只有一個前驅，稱為父結點。如：上圖中的“R是K、P、Q、D的父結點；“N是X、Y的父結點。子結點：在樹形構造中，每個結點可以有多個后繼，稱為該結點的子結點。如：上圖中的K、P、Q、D是“R的子結點；X、Y是“N的子結點。葉子結點：在樹形構造中，沒有后繼的結點稱為葉子結點，也稱終端結點。如：上圖中的C、M、F、E、X、G、S、L、Z、A均為葉子結點。結點的度：在樹形構造中，一個結點所擁有的后繼個數稱

9、為該結點的度。如：上圖中根結點R的度是4；結點T的度是3；結點P、Q、D、O、Y、W的度都為1。葉子結點的度為0。樹的度：在樹形構造中，所有結點中的最大的度稱為樹的度。如：上圖中樹的度為4，因為結點R的度最大，是4。樹的深度：在樹形構造中，樹的最大層數稱為樹的深度(或高度)。如：上圖中樹的深度是5。說明：樹形構造具有明顯的層次關系，即樹是一種層次構造。在樹形構造中一般按如下原那么分層：1) 根結點在第1層。2) 其余結點的層數等于其父結點的層數加1。子樹：在樹形結中，以某結點的一個子結點為根構成的樹稱為該結點的一棵子樹。如：上圖中，結點R有4棵子樹，它們分別以K、P、Q、D為根結點；結點P有1

10、棵子樹，其根結點為N；結點T有3棵子樹，它們分別以W、Z、A為根結點。在樹形構造中，子樹間互不相交，葉子結點沒有子樹。森林：森林是M(M0)棵互不相交的樹的集合。刪去一棵樹的根，就得到一個森林；反之，加上一個結點作樹根，森林就變?yōu)橐豢脴洹?.4.2二叉樹(1) 二叉樹的特點 非空二叉樹只有一個根結點。 二叉樹中的每個結點，最多有兩棵子樹，分另稱為該結點的左子樹與右子樹。當一個結點即沒有左子樹也沒有右子樹時，該結點就是葉子結點。在下面的圖中，左面是只有根結點的二叉樹，右面是深度為4的二叉樹： (2) 滿二叉樹與完全二叉樹1) 滿二叉樹：滿二叉樹是指除最后一層外，每一層上的所有結點都有兩個子結點。

11、就是說，在滿二叉樹中，每一層上的結點數都到達最大值，即在滿二叉樹的第k層上有2i-1(k1)個結點，且深度為k的滿二叉樹有2k-1(k1)個結點。在以下圖中分別是深度為2、3、4的滿二叉樹：滿二叉樹中不存在度數為1的結點，每個分支結點均有兩棵深度一樣的子樹，且葉子結點都在最下一層。2) 完全二叉樹：假設一棵二叉樹最多只有最下面的兩層上結點的度數可以小于2，并且最下一層上的所有結點都集中在該層最左邊的假設干位置上，那么此二叉樹稱為完全二叉樹。在以下圖的4棵二叉樹中，分別是深度為3與4的完全二叉樹：滿二叉樹是完全二叉樹，完全二叉樹不一定是滿二叉樹。在滿二叉樹的最下一層上，從最右邊開場連續(xù)刪去假設干

12、結點后得到的二叉樹仍然是一棵完全二叉樹。在完全二叉樹中，假設某個結點沒有左子結點，那么它一定沒有右子結點，即該結點必是葉子結點。(3) 二叉樹的性質假設定義根結點的層數為1(注意：有些資料中規(guī)定根結點的層數為0)。性質1：在二叉樹的第i層上，最多有2i-1(i1)個結點。性質2：深度為k的二叉樹最多有2k-1(k1)個結點。性質3：在任意二叉樹中，假設度為0的結點(即葉子結點)的個數為n0，度為2的結點的個數為n2，那么：n0= n2+1(對于完全二叉樹還有如下屬性)性質4：具有n個結點的完全二叉樹，其深度為log2n+1。注：log2n表示取log2n的整數局部。性質5：如果將一棵有n個結點

13、的完全二叉樹自頂向下、同一層自左向右連續(xù)給結點編號1、2、3、n，那么對于任意結點i(1in)有如下結論：1) 如果i=1，此結點為根結點，無前驅(即無父結點)；如果i>1，那么該結點的父結點編號為Int(i/2)。也可表示成i/2，都表示取整數。2)如果2i>n，那么結點i無左子結點，顯然也沒有右子結點，是葉子結點。如果2in，那么結點i的左子結點是編號為2i的結點。3) 如果2i+1>n，那么結點i無右子結點。如果2i+1n，那么結點i的右子結點的編號為2i+1。(4) 二叉樹的遍歷二叉樹的遍歷就是遵從某種次序，訪問二叉樹中的所有結點，使得每個結點僅被訪問一次。一棵非空二

14、叉樹是由根結點、左子樹與右子樹三局部組成。因此遍歷一棵非空二叉樹的問題就可以分解為三項“子任條： 訪問根結點(假設用D表示)。 遍歷左子樹(假設用L表示)。 遍歷右子樹(假設用R表示)。在遍歷二叉樹的過程中，一般先遍歷左子樹，然后再遍歷右子樹。在先左后右的原那么下，根據訪問根結點的次序，二叉樹的遍歷可分為三種：前序遍歷(DLR)、中序遍歷(LDR)、后序遍歷(LRD)。 以以下圖中的二叉樹為例： 前序遍歷(DLR)： 首先訪問根結點，然后遍歷左子樹，最后遍歷右子樹。在遍歷左、右子樹時，仍然先訪問子樹的根結點，然后遍歷其左子樹，最后遍歷其右子樹。即，前序遍歷是指訪問所有的根結點(包括子樹的根結點

15、)都在遍歷其左、右子樹之前。 前序遍歷的操作： 假設二叉樹為空，那么完畢反返回。否那么： 訪問根結點 前序遍歷左子樹 前序遍歷右子樹如，對上圖中的二叉樹進展前序遍歷的結果是：F C A D B E G H P 中序遍歷(LDR)： 首先遍歷左子樹，然后訪問根結點，最后遍歷右子樹。在遍歷左、右子樹時，仍然先遍歷其左子樹，然后訪問子樹的根結點，最后遍歷其右子樹。即，中序遍歷是指訪問所有的根結點(包括子樹的根結點)都在遍歷其左子樹之后、在遍歷其右子樹之前。 中序遍歷的操作： 假設二叉樹為空，那么完畢反返回。否那么： 中序遍歷左子樹 訪問根結點 中序遍歷右子樹如，對上圖中的二叉樹進展中序遍歷的結果是：

16、A C B D F E H G P 后序遍歷(LRD)： 首先遍歷左子樹，然后遍歷右子樹，最后訪問根結點。在遍歷左、右子樹時，仍然先遍歷其左子樹，然后遍歷其右子樹，最后訪問子樹的根結點。即，后序遍歷是指訪問所有的根結點(包括子樹的根結點)都在遍歷其左、右子樹之后。 后序遍歷的操作： 假設二叉樹為空，那么完畢反返回。否那么： 后序遍歷左子樹 后序遍歷右子樹 訪問根結點如，對上圖中的二叉樹進展后序遍歷的結果是：A B D C H P G E F1.5查找查找又稱檢索。查找是指在一個給定的數據構造中查找某個指定的元素。通常，根據不同的數據構造，應采用不同的查找方法。1.5.1 順序查找順序查找又稱順

17、序搜索或線性查找。順序查找一般是指在線性表中查找指定的元素。順序查找的根本思想：在n個結點組成的線性表中，從線性表的一端開場，依次將線性表中的元素與被查元素進展比擬，假設相等那么表示找到，即查找成功；假設線性表中所有的元素都與被查元素進展了比擬但都不相等，那么表示線性表中沒有要找的元素，即查找失敗。在順序查找中，查找成功時最多需要比擬n次、最少比擬1次、平均比擬次數約為表長的一半。查找失敗時比擬n+1次。順序查找的時間復雜度為O(n)。對于無序表(即表中的元素的排列是無序的)與鏈式存儲構造的線性表(有序的與無序的)，只能用順序查找。順序查找的優(yōu)點：算法簡單而適用范圍廣。對表中元素的排列次序無要

18、求，既可以是按關鍵字排列的有序表，也可以是無序表；對表的存儲構造也無任何要求，既適用于順序存儲的順序表，也適用于鏈接存儲的鏈表。 順序查找的缺點： 查找效率低，平均查找長度較大。當n很大時不宜采用順序查找。1.5.2 二分查找二分查找又稱折半查找。它是一種查找效率較高的查找方法。該方法只適用于順序存儲構造的有序表。通常是指有序表中的元素按值升序排列(非遞減有序排列)。二分查找不能用于鏈式存儲構造的線性表。 二分查找的根本思想：參見“C語言程序設計或“VB程序設計課件的相應內容動畫。 對于長度為n的有序線性表，查找成功時最多需要比擬log2(n+1)次、最少比擬1次、平均查找長度近似log2n。

19、當查找失敗時，比擬log2n或log2(n+1)次。 不管二分查找成功與否，其時間復雜度均為O(log2n)。 二分查找的最壞性能與平均性能相當接近。1.6 排序 排序就是將文件中的記錄進展整理，使之按照關鍵字進展遞增或遞減的順序排列起來，成為一個有序序列的過程。在本節(jié)所介紹的排序方法中，其排序的對象一般認為是順序存儲的線性表，在程序設計語言中就是一維數組。 這里的排序算法，都是針對升序排序。1.6.1 交換排序 交換排序是兩兩比擬待排序記錄的關鍵字，假設發(fā)現兩個記錄關鍵字的次序相反時即進展交換，直到沒有反序的記錄為止。下面介紹兩種常用的交換排序。(1) 冒泡排序冒泡排序的根本思想：參見“C語

20、言程序設計或“VB程序設計課件的相應內容動畫。 對于長度為n的線性表，在最壞情況下，冒泡排序需要經過n/2遍的掃描，比擬次數為n(n-1)/2。 冒泡排序算法的平均時間復雜度為O(n2)，空間復雜度為O(1)。(2) 快速排序快速排序的根本思想： 參見以下圖： 從線性表中選取一個元素，設為T，將線性表后面小于T的元素移到前面，將線性表前面大于T的元素移到后面，結果就把線性表分成了兩局部(稱為兩個子表)，T插入到其分界限的位置處，這個過程稱為線性表的分割。通過對線性表的一次分割，就以T為分界限，將線性表分成了前后兩個子表，且前面子表中的所有元素均不大于T，后面子表中的所有元素均不小于T。 如果對

21、分割后的各子表再按上述原那么進展分割，并且這種分割過程可以一直做下去，隨著對各子表不斷地進展分割，劃分出的子表會越來越多(一次只能對一個子表進展再分割處理)，直到所有子表中的元素都排好序為止，那么此時的線性表就變成了有序表。 對于長度為n的線性表：在最壞情況下，快速排序比擬次數為n(n-1)/2。算法的時間復雜度為O(n2)，空間復雜度為O(n)。 在最好情況下，快速排序算法的時間復雜度為O(nlog2n)，空間復雜度為O(log2n)。快速排序算法的平均時間復雜度是O(nlog2n)，平均比擬次數不大于(n+1)log2n1.6.2 插入排序 插入排序是每次將一個待排序的記錄按其關鍵字大小，

22、插入到前面已排好的序列中的適當位置，直到全部記錄插入為止。(1) 直接插入排序 快速排序的根本思想：請查看相關資料。 對于長度為n的線性表：在最壞情況下，直接插入排序比擬次數為n(n-1)/2。算法的時間復雜度為O(n2)。(2) 希爾排序 希爾排序的根本思想：請查看相關資料。 對于長度為n的線性表：在最壞情況下希爾排序比擬次數為O(n1.5)。1.6.3 選擇排序 選擇排序的根本思想是：每一遍在n-i+1(i=1,2,n-1)個待排序記錄中選取關鍵字最小的記錄作為有序序列中第i個記錄，直到全部記錄排完為止。(1) 直接選擇排序 選擇排序的根本思想：參見“C語言程序設計或“VB程序設計課件的相

23、應內容動畫。 在最壞情況下，直接選擇排序比擬次數為n(n-1)/2。(2) 堆排序 希爾排序的根本思想：請查看相關資料。 在最壞情況下，堆排序比擬次數為O(nlog2n)。習題：一選擇題(單項選擇)1. 以下表達中正確的選項是( D )A棧是“先進先出的線性表B隊列是“先進后出的線性表C循環(huán)隊列是非線性構造D有序線性表既可以采用順序存儲構造，也可以采用鏈式存儲構造2. 以下關于棧的表達中正確的選項是( A )A) 棧頂元素最先被刪除 B) 棧頂元素最后才能被刪除C) 棧底元素永遠不能被刪除 D) 以上三種說法都不對3. 以下表達中正確的選項是( B )A) 有一個以上根結點的數據構造不一定是非

24、線性構造B) 只有一個根結點的數據構造不一定是線性構造C) 循環(huán)鏈表是非線性構造D) 雙向鏈表是非線性構造4. 支持子程序調用的數據構造是( A )A) 棧 B) 樹 C) 隊列 D) 二叉樹5. 某二叉樹有5個度為2的結點，那么該二叉樹中的葉子結點數是( C )A10 B8 C6 D4提示：在任意二叉樹中，假設度為0的結點(即葉子結點)的個數為n0，度為2的結點的個數為n2，那么：n0= n2+1 即 n0(葉子結點數)=5+1=66. 某二叉樹共有7個結點，其中葉子結點只有1個，那么該二叉樹的深度為(假設根結點在第一層)( D )A) 3 B) 4 C) 6 D)77. 以下排序方法中，最

25、壞情況下比擬次數最少的是( D )A冒泡排序 B簡單項選擇擇排序 C直接插入排序 D堆排序8. 以下表達中正確的選項是( A )A) 對長度為n的有序鏈表進展查找，最壞的情況下需要的比擬次數為nB) 對長度為n的有序鏈表進展對分查找，最壞的情況下需要的比擬次數為n/2C) 對長度為n的有序鏈表進展對分查找，最壞的情況下需要的比擬次數為(log2n)D) 對長度為n的有序鏈表進展對分查找，最壞的情況下需要的比擬次數為(nlog2n)(二) 填空題1. 假設用一個長度為50的數組數組元素的下標從0到49作為棧的存儲空間，棧底指針bottom指向棧底元素，棧頂指針top指向棧頂元素，如果bottom

26、=49,top=30(數組下標)，那么棧中具有_個元素。 答案：202. 一個隊列的初始狀態(tài)為空。現將元素A、B、C、D、E、F、5、4、3、2、1一次入隊，然后再一次退隊，那么元素退隊的順序為_。答案：A、B、C、D、E、F、5、4、3、2、13. 設某循環(huán)隊列的容量為50，如果頭指針front=45(指向隊頭元素的前一個位置)，尾指針rear=10指向隊尾元素，那么該循環(huán)隊列中共有_個元素。答案：154. 設二叉樹如下：ABCDEFGH對該二叉樹進展后序遍歷的結果為_。答案：E、D、B、G、H、F、C、A5. 一棵二叉樹的中序遍歷結果為DBEAFC，前序遍歷結果為ABDECF，那么后序遍歷

27、結果為_。答案：DEBFCA6. 有序線性表能進展二分查找的前提是該線性表必須是_存儲。答案：順序二、軟件工程根底計算機軟件是計算機系統中與硬件相互依存的另一局部，是包括程序、數據及相關文檔的完整集合。軟件由兩局部組成：一是機器可執(zhí)行的程序與數據；二是機器不可執(zhí)行的，與軟件開發(fā)、運行、維護、使用等有關的文檔。軟件的分類 軟件按功能可以分為：應用軟件、系統軟件、支撐軟件(或工具軟件)。 應用軟件：是為解決特定領域的應用而開發(fā)的軟件。 系統軟件：是計算機管理自身資源，提高計算機使用效率并為計算機用戶提供各種效勞的軟件。支撐軟件：是介于系統軟件與應用軟件之間，協助用戶開發(fā)軟件的工具性軟件。軟件生命周

28、期通常將軟件產品從提出、實現、使用維護到停頓使用退役的過程稱為軟件生命周期。參見以下圖：構造化分析方法構造化分析的常用工具：數據流圖(DFD)：是描述數據處理過程的工具，是需求理解的邏輯模型的圖形表示，它直接支持系統的功能建模。數據字典(DD)：是構造化分析方法的核心。判定樹判定表構造化設計方法常見的過程設計工具：圖形工具：程序流程圖，N-S圖，PAD圖(問題分析圖)，HIPO表格工具：判定表。語言工具：PDL(偽碼)軟件設計的根本原理 1) 抽象：是一種思維工具，就是把事物本質的共同特性提取出來而不考慮其他細節(jié)。 2) 模塊化：是指把一個待開發(fā)的軟件分解成假設干小的簡單的局部。如高級語言中的

29、過程、函數、子程序等。每個模塊可以完成一個特定的子功能，各個模塊可以按一定的方法組裝起來成為一個整體，從而實現整個系統的功能。 3) 信息隱蔽：是指在一個模塊內包含的信息(過程或數據)，對于不需要這些信息的其他模塊來說是不能訪問的。4) 模塊獨立性：是指每個模塊只完成系統要求的獨立的子功能，并且與其他模塊的聯系最少且接口簡單。模塊的獨立程度是評價設計好壞的重要度量標準。衡量軟件的模塊獨立性使用耦合性與內聚性兩個定性的度量標準。內聚性：是一個模塊內部各個元素間彼此結合的嚴密程度的度量。內聚是從功能角度來度量模塊內的聯系。內聚性是信息隱蔽與局部化概念的自然擴展。一個模塊的內聚性越強那么該模塊的模塊

30、獨立性越強。作為軟件構造設計的設計原那么，要求每一個模塊的內部都具有很強的內聚性，它的各個組成局部彼此都密切相關。耦合性：耦合性是模塊間相互連接的嚴密程度的度量。一個模塊與其他模塊的耦合性越強那么該模塊的模塊獨立性越弱。原那么上講，模塊化設計總是希望模塊間的耦合表現為非直接耦合方式。但是，由于問題所固有的復雜性與構造化設計的原那么，非直接耦合往往是不存在的。耦合性與內聚性是模塊獨立性的兩個定性標準，耦合性與內聚性是相互聯系的。在程序構造中，各模塊的內聚性越強，那么耦合性越弱。一般優(yōu)秀的軟件設計，應盡量做到高內聚，低耦合，即減弱模塊之間的耦合性與提高模塊內的的內聚性，有利于提高模塊的獨立性。軟件

31、測試軟件測試是在軟件投入運行前對軟件需求、設計、編碼的最后審核。軟件測試是為了發(fā)現錯誤而執(zhí)行程序的過程。軟件測試應當制定明確的測試方案并按方案執(zhí)行。軟件測試的目的：是發(fā)現錯誤。軟件測試方法與技術：假設從是否需要執(zhí)行被測軟件的角度，可以分為靜態(tài)測試與動態(tài)測試方法。假設按照功能劃分可以分為白盒測試與黑盒測試方法。靜態(tài)測試：包括代碼檢查、靜態(tài)構造分析、代碼質量度量等。靜態(tài)測試不實際運行軟件，主要通過人工進展。動態(tài)測試：是基于計算機的測試，是為了發(fā)現錯誤而執(zhí)行程序的過程。需要精心設計一批測試用例，并利用這些測試用例去運行程序，以發(fā)現程序錯誤的過程。測試用例的格式為： (輸入值集),(輸出值集)白盒測試

32、：也稱構造測試或邏輯驅動測試。它是根據軟件產品的內部工作過程，檢查內部成分，以確認每種內部操作符合設計規(guī)格要求。白盒測試把測試對象看作一個翻開的盒子，允許測試人員利用程序內部的邏輯構造及有關信息來設計或選擇測試用例，對程序所有的邏輯路徑進展測試。通過在不同點檢查程序的狀態(tài)來了解實際的運行狀態(tài)是否與預期的一致。所以，白盒測試是在程序內部進展，主要用于完成軟件內部操作的驗證。白盒測試的主要方法有邏輯覆蓋、根本路徑測試等。黑盒測試：也稱功能測試或數據驅動測試。黑盒測試是對軟件已經實現的功能是否滿足需求進展測試與驗證。黑盒測試完全不考慮程序內部的邏輯構造與內部特征，只依據程序的需求與功能規(guī)格說明，檢查

33、程序的功能是否符合它的功能說明。所以，黑盒測試是在軟件接口處進展，完成功能驗證。黑盒測試只檢查程序功能是否按照需求規(guī)格說明書的規(guī)定正常使用，程序是否能適當地接收輸入數據而產生正確的輸出信息，并且保持外部信息(如數據庫或文件)的完整性。黑盒測試主要診斷功能不對或遺漏、界面錯誤、數據構造或外部數據庫訪問錯誤、性能錯誤、初始化與終止條件錯誤。黑盒測試方法主要有等價類劃分法、邊界值分析法、錯誤推測法、因果圖等，主要用于軟件確認測試。程序調試在對程序進展了成功的測試之后，將進入程序調試(通常稱Debug，即排錯)。程序調試的任務是診斷與改正程序中的錯誤。它與軟件測試不同，軟件測試是盡可能多地發(fā)現軟件中的

34、錯誤，并找出軟件錯誤的具體位置。軟件測試貫穿整個軟件生命期，調試主要在開發(fā)階段。習題：一選擇題(單項選擇)1. 軟件按功能可以分為：應用軟件、系統軟件與支撐軟件或工具軟件。下面屬于應用軟件的是( C )A) 編譯程序 B) 操作系統 C) 教務管理系統 D) 匯編程序2. 軟件按功能可分為：應用軟件、系統軟件、與支撐軟件或工具軟件。下面屬于系統軟件的是( B )A) 編輯軟件 B)操作系統 C)教務管理系統 D)瀏覽器、3. 軟件(程序)調試的任務是( A )A) 診斷與改正程序中的錯誤 B) 盡可能多的發(fā)現程序中的錯誤C) 發(fā)現并改正程序中的所有錯誤 D) 確定程序中錯誤的性質4. 下面表達

35、中錯誤的選項是( A )A) 軟件測試的目的是發(fā)現錯誤并改正錯誤B) 對被調試的程序進展“錯誤定位是程序調試的必要步驟C) 程序調試通常也稱為DebugD) 軟件測試應嚴格執(zhí)行測試方案，排除測試的隨意性5. 耦合性與內聚性是對模塊獨立性度量的兩個標準。以下表達中正確的選項是( B )A) 提高耦合性、降低內聚性有利于提高模塊的獨立性B) 降低耦合性、提高內聚性有利于提高模塊的獨立性C) 耦合性是指一個模塊內部各個元素間彼此結合的嚴密程度D) 內聚性是指模塊間互相連接的嚴密程度6. 數據流圖(DFD圖)是( C )A) 軟件概要設計的工具 B) 軟件詳細設計的工具C) 構造化方法的需求分析工具

36、D) 面向對象方法的需求分析工具7. 軟件生命周期可分為定義階段，開發(fā)階段與維護階段。詳細設計屬于( B )A) 定義階段 B) 開發(fā)階段 C) 維護階段 D) 上述三個階段8. 在軟件開發(fā)中，需求分析階段產生的主要文檔是( D )A) 軟件集成測試方案 B) 軟件詳細設計說明書 C) 用戶手冊 D) 軟件需求規(guī)格說明書9. 構造化程序所要求的根本構造不包括( B )A) 順序構造 B) GOTO跳轉 C) 選擇(分支)構造 D) 重復(循環(huán))構造10. 下面描述中錯誤的選項是( A )A) 系統總體構造圖支持軟件系統的詳細設計B) 軟件設計是將軟件需求轉換為軟件表示的過程C) 數據構造與數據

37、庫設計是軟件設計的任務之一D) PAD圖是軟件詳細設計的表示工具(二) 填空題1. 軟件測試可分為白盒測試與黑盒測試。根本路徑測試屬于_測試。答案：白盒2. 符合構造化原那么的三種根本控制構造是：選擇構造、循環(huán)構造與_。答案：順序構造3. 軟件是_、數據與文檔的集合。答案：程序4. 對軟件設計的最小單位(模塊或程序單元)進展的測試通常為_測試。答案：單元 或 模塊三、數據庫設計根底計算機應用的三大領域：科學計算、數據處理、過程控制。數據庫系統的根本概念數據(Data)：就是描述事物的符號記錄。數據庫(DB)：是數據的集合，它具有統一的構造形式并存放于統一的存儲介質內，是多種應用數據的集成，并可

38、被各個應用程序所共享。數據庫中的數據具有“集成、“共享的特點。數據庫管理系統(DBMS)：是數據庫的機構，是一種系統軟件，負責數據庫中的數據組織、數據操縱、數據維護、控制及保護與數據效勞等。數據庫管理系統是數據庫系統的核心。數據庫管理系統一般提供相應的數據語言(Data Language)來完成相應的功能：數據定義語言(DDL)：負責數據的模式定義與數據的物理存取構建。數據操縱語言(DML)：負責數據的操縱，包括查詢及增、刪、改等操作。數據控制語言(DCL)：負責數據完整性、平安性的定義與檢查以及并發(fā)控制、故障恢復等功能，包括系統初啟程序、文件讀寫與維護程序、存取路徑管理程序、緩沖區(qū)管理程序、

39、平安性控制程序、完整性檢查程序、并發(fā)控制程序、事務管理程序、運行日志管理程序、數據庫恢復程序等。數據庫管理員(DBA)：由于數據庫的共享性，因此對數據庫的規(guī)劃、設計、維護、監(jiān)視等需要有專人管理，稱他們?yōu)閿祿旃芾韱T。數據庫系統(DBS)：由數據庫(數據)、數據庫管理系統(軟件)、數據庫管理員(人員)、系統硬件平臺(硬件)、系統軟件平臺(軟件)這五局部組成，稱為數據庫系統。數據庫應用系統(DBAS)：是數據庫系統再加上應用軟件及應用界面這三者所組成。E-R模型該模型將現實世界的要求轉化成實體、聯系、屬性等幾個根本概念，以及它們間的兩種根本聯接關系，并且可以用一種圖非常直觀地表示出來。下面是E-R

40、模型的根本概念。目前較為有名的概念模型有E-R模型、擴大的E-R模型、面向對象模型及謂詞模型等。實體：現實世界中的事物可以抽象成為實體。實體是概念世界中的根本單位，它們是客觀存在的且又相互區(qū)別的事物。但凡有共性的實體可組成一個集合稱實體集。如學生A與學生B，他們都是實體，他們又都是學生，從而組成一個學生實體集。 屬性：現實世界中的事物均有一些特性，這些特性可以用屬性來表示。屬性刻畫了實體的特征。一個實體往往可以有假設干個屬性。 聯系：現實世界中事物間的關聯稱為聯系。在概念世界中聯系反映了實體集間的一定關系。如工人與設備間的操作關系，上、下級間的領導關系等。 實體集間的聯系有多種，就實體集的個數

41、而言有： 1) 兩個實體集間的聯系。2) 多個實體集間的聯系。3) 一個實體集內部的聯系：是一個實體集內的不同實體間的聯系。實體集間聯系的個數可以是單個也可以是多個，包括：一對一的聯系，簡記為1:1一對多或多對一的聯系，簡記為1:M或M:1 (其中M也可以小寫)多對多的聯系，簡記為M:N 或 m:n E-R模型由上面三個根本概念組成。由實體、聯系、屬性三者結合起來才能表示現實世界。 E-R圖：E-R模型可以用一種非常直觀的圖的形式表示，這種圖稱為E-R圖。在E-R圖中我們分別用下面不同的幾何圖形表示E-R模型中的三個概念與兩個聯接關系。 1) 實體集表示法 用矩形表示實體集，在矩形內寫上該實體

42、集的名字。如實體集學生(student)、課程(course)可表示為： 2) 屬性表示法 用橢圓形表示屬性，在橢圓形內寫上該屬性的名稱。如學生有屬性：學號(S#)、姓名(Sn)及年齡(Sa)，可表示為： 3) 聯系表示法 用菱形表示聯系，在菱形內寫上聯系名。如學生與課程間的聯系SC，可表示為：上面是三個根本概念分別用三種幾何圖形表示。下面是它們之間的聯接關系的圖形表示。 4) 實體集或聯系與屬性間的聯接關系屬性依附于實體集，屬性也依附于聯系，因此它們之間分別有聯接關系。參見以下圖：其中：C#(課程號)、Cn(課程名)、P#(預修課號) 5) 實體集與聯系間的聯接關系 如以下圖表示實體集與聯系

43、間的聯接關系： 還可以在線段邊上注明其對應的函數關系，如1:1、1:n、n:m等。以下圖表示student與course間有多對多聯系：兩個實體集間聯系叫二元聯系，多個實體集間聯系叫多元聯系。以下圖聯系FPU是一種三元聯系(工廠、產品與用戶間的聯系)： 下面是實體間多種聯系圖： (a)圖：公司職工(enployee)間上、下級管理(manage)的聯系。即一個實體集內部可以有多種聯系。(b)圖：教師(T)與學生(S)之間可以有教學(E)聯系也可以有管理(M)聯系。即實體集間可以有多種聯系。下面是E-R圖的一個實例圖關系模型關系模型采用二維表來表示，簡稱表。二維表由表框架(Frame)及表的元組

44、(Tuple)組成。表框架由n個命名的屬性(Attribute)組成，n稱為屬性元數(Arity)。每個屬性有一個取值范圍，稱為值域(Domain)。表框架對應了關系的模式，即類型的概念。在表框架中按行可以存放數據，每行數據稱為元組，實際上，一個元組是由n個元組分量所組成，每個元組分量是表框架中每個屬性的投影值。一個表框架可以存放m個元組，m稱為表的基數(Cardinality)。一個n元表框架及框架內m個元組構成了一個完整的二維表。 關系框架與關系元組構成了一個關系。一個語義相關的關系集合構成一個關系數據庫。關系的框架稱為關系模式，而語義相關的關系模式集合構成了關系數據庫模式。 滿足下面7個

45、性質的二維表稱為關系(Relation)： 1) 元組個數有限性：二維表中元組個數是有限的。2) 元組的惟一性：二維表中元組均不一樣。3) 元組的次序無關性：二維表中元組的次序可以任意交換。4) 元組分量的原子性：二維表中元組的分量是不可分割的根本數據項。5) 屬性名惟一性：二維表中屬性名各不一樣。6) 屬性的次序無關性：二維表中屬性與次序無關，可任意交換。7) 分量值域的同一性：二維表屬性的分量具有與該屬性一樣的值域。以二維表(關系)為根本構造所建立的模型稱為關系模型。 在關系模型中的一個重要概念是鍵(Key)或碼。鍵具有標識元組、建立元組間聯系等重要作用。鍵或碼：在二維表中凡能惟一標識元組的最小屬性集稱為該表的鍵或碼。候選鍵或候選碼：二維表中可能有假設