計算機二級公共基礎知識總結-計算機二級公共基礎知識總結-計算機二級公共基礎知識總結-xxx公司計算機二級公共基礎知識總結-文件編號：文件日期：修訂次數：第1.0次更改批準審核制定方案設計，管理制度第1章數據結構與算法算法的復雜度1.算法的基本概念1、算法是指解題方案的準確而完整的描述。換句話說，算法是對特定問題求解步驟的一種描述。*算法不等于程序，也不等計算機方法，程序的編制不可能優于算法的設計。（1）算法的基本特征算法一般具有4個基本特征：可行性、確定性、有窮性、擁有足夠的情報。注:&確定性，算法中每一步驟都必須有明確定義，不充許有模棱兩可的解釋，不允許有多義性；

&有窮性，算法必須能在有限的時間內做完，即能在執行有限個步驟后終止，包括合理的執行時間的含義；*算法的基本要素：一是對數據對象的運算和操作；二是算法的控制結構。（2）*算法的基本運算和操作包括：算術運算、邏輯運算、關系運算、數據傳輸。（3）*算法的3種基本控制結構是：順序結構、選擇結構、循環結構。（4）算法基本設計方法：列舉法、歸納法、遞推、遞歸、減半遞推技術、回溯法。（5）指令系統:指的是一個計算機系統能執行的所有指令的集合。2.算法復雜度*算法復雜度包括時間復雜度和空間復雜度。注意兩者的區別，無混淆，見表1-1。可以用執行算法的過程中所需基本運算的執行次數來度量。表1-1算法復雜性可以用執行算法的過程中所需基本運算的執行次數來度量。名稱描述時間復雜度執行算法所需要的計算工作量空間復雜度執行這個算法所需要的內存空間數據結構邏輯結構和存儲結構1.數據結構的基本概念（1）*數據結構:指相互有關聯的數據元素的集合。(2)數據結構研究的三個方面：

Ⅰ、數據集合中各數據元素之間所固有的邏輯關系，即數據的邏輯結構；

Ⅱ、在對數據進行處理時，各數據元素在計算機中的存儲關系，即數據的存儲結構；

Ⅲ、對各種數據結構進行的運算。2.邏輯結構數據的邏輯結構是對數據元素之間的邏輯關系的描述。數據的邏輯結構有兩個要素：一是數據元素的集合，通常記為D；二是D上的關系，它反映了數據元素之間的前后件關系，通常記為R。一個數據結構可以表示成：B=(D,R)3.存儲結構數據的存儲結構有順序、鏈接、索引等。注：順序存儲方式主要用于線性的數據結構，它把邏輯上相鄰的數據元素存儲在物理上相鄰的存儲單元里，結點之間的關系由存儲單元的鄰接關系來體現。鏈式存儲結構就是在每個結點中至少包含一個指針域，用指針來體現數據元素之間邏輯上的聯系。*：數據的邏輯結構反映數據元素之間的邏輯關系，數據的存儲結構（也稱數據的物理結構）是數據的邏輯結構在計算機存儲空間中的存放形式。同一種邏輯結構的數據可以采用不同的存儲結構，但影響數據處理效率。線性結構和非線性結構根據數據結構中各數據元素之間前后件關系的復雜程度，一般將數據結構分為兩大類型：線性結構與非線性結構。（1）如果一個非空的數據結構滿足下列兩個條件：*①有且只有一個根結點；②每一個結點最多有一個前件，也最多有一個后件。則稱該數據結構為線性結構。線性結構又稱線性表。在一個線性結構中插入或刪除任何一個結點后還應是線性結構。棧、隊列、串、線性鏈表等都為線性結構。如果一個數據結構不是線性結構，則稱之為非線性結構。數組、廣義表、樹和圖等數據結構都是非線性結構。線性表及其順序存儲結構線性表的存儲結構主要分為順序存儲結構和鏈式存儲結構線性表是由一組數據元素構成，數據元素的位置只取決于自己的序號，元素之間的相對位置是線性的。

在復雜線性表中，由若干項數據元素組成的數據元素稱為記錄，而由多個記錄構成的線性表又稱為文件。非空線性表的結構特征：

（1）且只有一個根結點a1，它無前件；

（2）有且只有一個終端結點an，它無后件；

（3）除根結點與終端結點外，其他所有結點有且只有一個前件，也有且只有一個后件。結點個數n稱為線性表的長度，當n=0時，稱為空表。

*線性表的順序存儲結構具有以下兩個基本特點：

（1）線性表中所有元素的所占的存儲空間是連續的；

（2）線性表中各數據元素在存儲空間中是按邏輯順序依次存放的。

ai的存儲地址為：ADR(ai)=ADR(a1)+(i-1)k,，ADR(a1)為第一個元素的地址，k代表每個元素占的字節數。

順序表的運算：查找、插入、刪除3種。棧（重點）1.棧的基本概念（棧（stack）是一種特殊的線性表）棧是限定在一端進行插入與刪除運算的線性表。在棧中，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧頂元素總是最后被插入的元素，棧底元素總是最先被插入的元素。即棧是按照“先進后出”（FILO）或“后進先出”(LIFO)的原則組織數據的。棧具有記憶作用。注：用top表示棧頂位置，用bottom表示棧底。當表中沒有元素時稱為空棧2.棧的基本運算：（1）插入元素稱為入棧運算；（2）刪除元素稱為退棧運算；（3）讀棧頂元素是將棧頂元素賦給一個指定的變量，此時指針無變化。計算棧的個數：棧底–棧頂+1隊列(重點)1.隊列的基本概念隊列是指允許在一端（隊尾）進入插入，而在另一端（隊頭）進行刪除的線性表。Rear指針指向隊尾，front指針指向隊頭。

隊列是“先進先出”（FIFO）或“后進后出”（LILO）的線性表。2.隊列運算入隊運算是往隊列隊尾插入一個數據元素；退隊運算是從隊列的隊頭刪除一個數據元素。隊列的順序存儲結構一般采用隊列循環的形式。循環隊列s=0表示隊列空；s=1且front=rear表示隊列滿。計算循環隊列的元素個數：“尾指針減頭指針”，若為負數，再加其容量即可。隊列是一種特殊的線性表，循環隊列是隊列的順序存儲結構。鏈表數據結構中的每一個結點對應于一個存儲單元，這種存儲單元稱為存儲結點，簡稱結點。

結點由兩部分組成：（1）用于存儲數據元素值，稱為數據域；（2）用于存放指針，稱為指針域，用于指向前一個或后一個結點。

在鏈式存儲結構中，存儲數據結構的存儲空間可以不連續，各數據結點的存儲順序與數據元素之間的邏輯關系可以不一致，而數據元素之間的邏輯關系是由指針域來確定的。

鏈式存儲方式即可用于表示線性結構，也可用于表示非線性結構。線性鏈表，HEAD稱為頭指針，HEAD=NULL（或0）稱為空表，如果是兩指針：左指針（Llink）指向前件結點，右指針（Rlink）指向后件結點。

線性鏈表的基本運算：查找、插入、刪除。樹與二叉樹★★★★★1、樹的基本概念樹是一種簡單的非線性結構，所有元素之間具有明顯的層次特性。

在樹結構中，每一個結點只有一個前件，稱為父結點，沒有前件的結點只有一個，稱為樹的根結點，簡稱樹的根。每一個結點可以有多個后件，稱為該結點的子結點。沒有后件的結點稱為葉子結點。

在樹結構中，一個結點所擁有的后件的個數稱為該結點的度，所有結點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。2、二叉樹及其基本性質二叉樹是一種很有用的非線性結構，具有以下兩個特點：（1）非空二叉樹只有一個根結點；（2）每一個結點最多有兩棵子樹，且分別稱為該結點的左子樹與右子樹。基本性質：性質1在二叉樹的第k層上，最多有個結點。

性質2深度為m的二叉樹最多有個個結點。

性質3在任意一棵二叉樹中，度數為0的結點（即葉子結點）總比度為2的結點多一個。

性質4具有n個結點的二叉樹，其深度至少為，其中表示取的整數部分3.滿二叉樹與完全二叉樹滿二叉樹：除最后一層外，每一層上的所有結點都有兩個子結點。完全二叉樹：除最后一層外，每一層上的結點數均達到最大值；在最后一層上只缺少右邊的若干結點。注意：深度為m的滿二叉樹最多有個個結點完全二叉樹具有以下兩個性質：性質1：具有n個結點的完全二叉樹的深度為。性質2：設完全二叉樹共有n個結點。如果從根結點開始，按層次（每一層從左到右）用自然數1，2，……，n給結點進行編號，則對于編號為k（k=1，2，……，n）的結點有以下結論：①若k=1，則該結點為根結點，它沒有父結點；若k>1，則該結點的父結點編號為INT（k/2）；②若2k≤n，則編號為k的結點的左子結點編號為2k；否則該結點無左子結點（顯然也沒有右子結點）；③若2k+1≤n，則編號為k的結點的右子結點編號為2k+1；否則該結點無右子結點。二叉樹存儲結構采用鏈式存儲結構，對于滿二叉樹與完全二叉樹可以按層序進行順序存儲4、二叉樹的遍歷★★★★二叉樹的遍歷是指不重復地訪問二叉樹中的所有結點。二叉樹的遍歷可以分為以下三種前序遍歷(DLR)：若二叉樹為空，則結束返回。否則：首先訪問根結點，然后遍歷左子樹，最后遍歷右子樹；并且，在遍歷左右子樹時，仍然先訪問根結點，然后遍歷左子樹，最后遍歷右子樹。中序遍歷(LDR)：若二叉樹為空，則結束返回。否則：首先遍歷左子樹，然后訪問根結點，最后遍歷右子樹；并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后訪問根結點，最后遍歷右子樹。后序遍歷(LRD)：若二叉樹為空，則結束返回。否則：首先遍歷左子樹，然后遍歷右子樹，最后訪問根結點，并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結點.查找技術查找：根據給定的某個值，在查找表中確定一個其關鍵字等于給定值的數據元素。查找成功/查找失敗在下列兩種情況下也只能采用順序查找：①如果線性表為無序表，則不管是順序存儲結構還是鏈式存儲結構，只能用順序查找；②即使是有序線性表，如果采用鏈式存儲結構，也只能用順序查找。查找分為:順序查找二分法查找二分法查找只適用于順序存儲的有序表(能使用二分法查找的線性表必須滿足用順序存儲結構和線性表是有序表兩個條件。)對于長度為n的有序線性表，最壞情況只需比較次，而順序查找需要比較n次。注：“有序”是特指元素按非遞減排列，即從小到大排列，但允許相鄰元素相等。下一節排序中，有序的含義也是如此排序技術排序是指將一個無序序列整理成按值非遞減順序排列的有序序列。

1、交換類排序法（冒泡排序，快速排序）

2、插入類排序法（簡單插入排序，希爾排序）

3、選擇類排序法（簡單選擇排序，堆排序）冒泡排序法,快速排序法,簡單插入排序法,簡單選擇排序法,最壞需要比較的次數為n(n-1)/2希爾排序,最壞需要比較的次數為

堆排序,最壞需要比較的次數為相比以上幾種（除希爾排序法外），堆排序法的時間復雜度最小。（本章應考點撥：本章內容在筆試中會出現5-6個題目，是公共基礎知識部分出題量比較多的一章，所占分值也比較大，約10分。）第2章程序設計基礎程序設計的方法與風格"清晰第一、效率第二"已成為當今主導的程序設計風格。

形成良好的程序設計風格需注意：

1、源程序文檔化；

2、數據說明的方法；

3、語句的結構；

4、輸入和輸出。

注釋分序言性注釋和功能性注釋。語句結構清晰第一、效率第二。結構化程序設計1、結構化程序設計方法的四條原則是：1.自頂向下；2.逐步求精；3.模塊化；4.限制使用goto語句。2、結構化程序的基本結構及特點：

(1)順序結構：一種簡單的程序設計，最基本、最常用的結構；

(2)選擇結構：又稱分支結構，包括簡單選擇和多分支選擇結構，可根據條件，判斷應該選擇哪一條分支來執行相應的語句序列；

(3)循環結構：又稱重復結構，可根據給定條件，判斷是否需要重復執行某一相同或類似的程序段。

結構化程序設計的特點：只有一個入口和出口面向對象方法面向對象的程序設計：以60年代末挪威奧斯陸大學和挪威計算機中心研制的SIMULA語言為標志。面向對象方法的優點：

（1）與人類習慣的思維方法一致；（2）穩定性好；（3）可重用性好；（4）易于開發大型軟件產品；

（5）可維護性好。*：面向對象的程序設計主要考慮的是提高軟件的可重用性。對象是屬性和方法的封裝體。*：一個對象由對象名、屬性和操作三部分組成。面向對象的基本特點：繼承性，多態性，封裝性*：信息隱蔽是通過對象的封裝性來實現的。對象是面向對象方法中最基本的概念，可以用來表示客觀世界中的任何實體，對象是實體的抽象。面向對象的程序設計方法中的對象是系統中用來描述客觀事物的一個實體，是構成系統的一個基本單位由一組表示其靜態特征的屬性和它可執行的一組操作組成。屬性即對象所包含的信息，操作描述了對象執行的功能，是對象的動態屬性，操作也稱為方法或服務。對象的基本特點：（1）標識惟一性；（2）分類性；（3）多態性；（4）封裝性；（5）模塊獨立性好。類是指具有共同屬性、共同方法的對象的集合。所以類是對象的抽象，對象是對應類的一個實例。消息是一個實例與另一個實例之間傳遞的信息。對象間的通信靠消息傳遞。它請求對象執行某一處理回答某一要求的信息，它統一了數據流和控制流消息是一個實例與另一個實例之間傳遞的信息。消息的組成包括（1）接收消息的對象的名稱；（2）消息標識符，也稱消息名；（3）零個或多個參數。繼承是指能夠直接獲得已有的性質和特征，而不必重復定義他們。繼承分單繼承和多重繼承。單繼承指一個類只允許有一個父類，多重繼承指一個類允許有多個父類。多態性是指同樣的消息被不同的對象接受時可導致完全不同的行動的現象*：在面向對象方法中，一個對象請求另一個對象為其服務的方式是通過發送消息。（本章應考點撥：本章在考試中會出現約1個題目，所占分值大約占2分，是出題量較小的一章。本章內容比較少，也很單，掌握住基本的概念就可以輕松應對考試了，所以在這部分丟分，比較可惜。）第3章軟件工程基礎軟件工程基本概念1.軟件定義與軟件特點軟件指的是計算機系統中與硬件相互依存的另一部分，包括程序、數據和相關文檔的完整集合。根據應用目標的不同，軟件可分應用軟件、系統軟件和支撐軟件（或工具軟件）軟件的特點包括：（1）軟件是一種邏輯實體；（2）軟件的生產與硬件不同，它沒有明顯的制作過程（3）軟件在運行、使用期間不存在磨損、老化問題；（4）軟件的開發、運行對計算機系統具有依賴性，受計算機系統的限制，這導致了軟件移植的問題；（5）軟件復雜性高，成本昂貴；（6）軟件開發涉及諸多的社會因素。2.軟件工程軟件工程源自軟件危機。所謂軟件危機是泛指在計算機軟件的開發和維護過程中所遇到的一系列嚴重問題軟件工程的主要思想是將工程化原則運用到軟件開發過程，它包括3個要素：方法、工具和過程。方法完成軟件工程項目的技術手段；工具是支持軟件的開發、管理、文檔生成；過程支持軟件開發的各個環的控制、管理。軟件工程過程是把輸入轉化為輸出的一組彼此相關的資源和活動。包含4種基本活動：（1）P——軟件規格說明；（2）D——軟件開發；（3）C——軟件確認；（4）A——軟件演進。軟件生命周期1、軟件生命周期：軟件產品從提出、實現、使用維護到停止使用退役的過程。2、軟件生命周期分為軟件定義、軟件開發及軟件運行維護三個階段：

1）軟件定義階段：包括制定計劃和需求分析。制定計劃：確定總目標；可行性研究；探討解決方案；制定開發計劃。需求分析：對待開發軟件提出的需求進行分析并給出詳細的定義。軟件需求規格說明書2）軟件開發階段：軟件設計：分為概要設計和詳細設計兩個部分。軟件實現：把軟件設計轉換成計算機可以接受的程序代碼。軟件測試：在設計測試用例的基礎上檢驗軟件的各個組成部分。3）軟件運行維護階段：軟件投入運行，并在使用中不斷地維護，進行必要的擴充和刪改。*：軟件生命周期中所花費最多的階段是軟件運行維護階段3、(1)軟件工程目標：在給定成本、進度的前提下，開發出具有有效性、可靠性、可理解性、可維護性、可重用性、可適應性、可移植性、可追蹤性和可互操作性且滿足用戶需求的產品。(2)軟件工程需要達到的基本目標應是：付出較低的開發成本；達到要求的軟件功能；取得較好的軟件性能；開發的軟件易于移植；需要較低的維護費用；能按時完成開發，及時交付使用。(3)軟件工程原則：抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗證性。結構化分析方法1、需求分析方法有：1)結構化需求分析方法；2)面向對象的分析方法。從需求分析建立的模型的特性來分：靜態分析和動態分析。

2、結構化分析方法是結構化程序設計理論在軟件需求分析階段的應用。

結構化分析方法的實質：著眼于數據流，自頂向下，逐層分解，建立系統的處理流程，以數據流圖和數據字典為主要工具，建立系統的邏輯模型。

結構化分析的常用工具：1)數據流圖(DFD)；2)數據字典(DD)；3)判定樹；4)判定表。

數據流圖的基本圖形元素：加工(轉換)：輸入數據經加工變換產生輸出。

數據流：沿箭頭方向傳送數據的通道，一般在旁邊標注數據流名。

存儲文件(數據源)：表示處理過程中存放各種數據的文件。

源，潭：表示系統和環境的接口，屬系統之外的實體。(1)數據流圖（DFD）是分析員與用戶之間極好的通信工具。(2)數據字典（DD）是對數據流圖中所有元素的定義的集合，是結構化分析的核心。*：數據字典的作用是對數據流圖中出現的被命名的圖形元素的確切解釋。數據字典中有4種類型的條目：數據流、數據項、數據存儲和加工。3、軟件需求規格說明書是需求分析階段的最后成果，是軟件開發的重要文檔之一。它的特點是具有正確性、無歧義性、完整性、可驗證性、一致性、可理解性、可修改性和可追蹤性。結構化設計方法1、軟件設計的基礎軟件設計的基本目標是用比較抽象概括的方式確定目標系統如何完成預定的任務，軟件設計是確定系統的物理模型。

軟件設計是開發階段最重要的步驟，是將需求準確地轉化為完整的軟件產品或系統的唯一途徑。

從技術觀點來看，軟件設計包括軟件結構設計、數據設計、接口設計、過程設計。

從工程角度來看，軟件設計分兩步完成，即概要設計和詳細設計。

概要設計又稱結構設計，將軟件需求轉化為軟件體系結構，確定系統級接口、全局數據結構或數據庫模式。

詳細設計：確定每個模塊的實現算法和局部數據結構，用適當方法表示算法和數據結構的細節。軟件設計的一般過程：軟件設計是一個迭代的過程；先進行高層次的結構設計；后進行低層次的過程設計；穿插進行數據設計和接口設計。

軟件設計的基本原理包括：抽象、模塊化、信息隱蔽和模塊獨立性。*：模塊分解的主要指導思想是信息隱蔽和模塊獨立性。

模塊的耦合性和內聚性是衡量軟件的模塊獨立性的兩個定性指標。

內聚性：是一個模塊內部各個元素間彼此結合的緊密程度的度量。

*：按內聚性由弱到強排列，內聚可以分為以下幾種：偶然內聚、邏輯內聚、時間內聚、過程內聚、通信內聚、順序內聚及功能內聚。

耦合性：是模塊間互相連接的緊密程度的度量。

*：按耦合性由高到低排列，耦合可以分為以下幾種：內容耦合、公共耦合、外部耦合、控制耦合、標記耦合、數據耦合以及非直接耦合。一個設計良好的軟件系統應具有高內聚、低耦合的特征。

在結構化程序設計中，模塊劃分的原則是：模塊內具有高內聚度，模塊間具有低耦合度。

2、總體設計(概要設計)和詳細設計

(1)總體設計(概要設計)

軟件概要設計的基本任務是：1)設計軟件系統結構；2)數據結構及數據庫設計；3)編寫概要設計文檔；4)概要設計文檔評審。

常用的軟件結構設計工具是結構圖，也稱程序結構圖。程序結構圖的基本圖符：

模塊用一個矩形表示，箭頭表示模塊間的調用關系。在結構圖中還可以用帶注釋的箭頭表示模塊調用過程中來回傳遞的信息。還可用帶實心圓的箭頭表示傳遞的是控制信息，空心圓箭心表示傳遞的是數據信息。結構圖的基本形式：基本形式、順序形式、重復形式、選擇形式。

結構圖有四種模塊類型：傳入模塊、傳出模塊、變換模塊和協調模塊。

典型的數據流類型有兩種：變換型和事務型。

變換型系統結構圖由輸入、中心變換、輸出三部分組成。

(2)詳細設計

詳細設計是為軟件結構圖中的每一個模塊確定實現算法和局部數據結構，用某種選定的表達工具表示算法和數據結構的細節。

常用的過程設計(即詳細設計)工具有以下幾種：

1、圖形工具：程序流程圖、N-S(方盒圖)、PAD(問題分析圖)和HIPO(層次圖+輸入/處理/輸出圖)。程序流程圖中主要元素：1）方框：表示一個處理步驟2）菱形框：表示一個邏輯條件3）箭頭：表示控制流向

2、表格工具：判定表。

3、語言工具：PDL(偽碼)軟件測試1、軟件測試定義：使用人工或自動手段來運行或測定某個系統的過程，其目的在于檢驗它是否滿足規定的需求或是弄清預期結果與實際結果之間的差別。

軟件測試的目的：盡可能地多發現程序中的錯誤，不能也不可能證明程序沒有錯誤。軟件測試的關鍵是設計測試用例，一個好的測試用例能找到迄今為止尚未發現的錯誤。

2、軟件測試方法：靜態測試和動態測試。

靜態測試：包括代碼檢查、靜態結構分析、代碼質量度量。不實際運行軟件，主要通過人工進行。

動態測試：是基于計算機的測試，主要包括白盒測試方法和黑盒測試方法。

(1)白盒測試

白盒測試方法也稱為結構測試或邏輯驅動測試。它是根據軟件產品的內部工作過程，檢查內部成分，以確認每種內部操作符合設計規格要求。

白盒測試的基本原則：保證所測模塊中每一獨立路徑至少執行一次；保證所測模塊所有判斷的每一分支至少執行一次；保證所測模塊每一循環都在邊界條件和一般條件下至少各執行一次；驗證所有內部數據結構的有效性。

*：白盒測試法的測試用例是根據程序的內部邏輯來設計的，主要用軟件的單元測試，主要方法有邏輯覆蓋、基本路徑測試等。

A、邏輯覆蓋。邏輯覆蓋泛指一系列以程序內部的邏輯結構為基礎的測試用例設計技術。通常程序中的邏輯表示有判斷、分支、條件等幾種表示方法。

語句覆蓋：選擇足夠的測試用例，使得程序中每一個語句至少都能被執行一次。

路徑覆蓋：執行足夠的測試用例，使程序中所有的可能的路徑都至少經歷一次。

判定覆蓋：使設計的測試用例保證程序中每個判斷的每個取值分支(T或F)至少經歷一次。

條件覆蓋：設計的測試用例保證程序中每個判斷的每個條件的可能取值至少執行一次。

判斷-條件覆蓋：設計足夠的測試用例，使判斷中每個條件的所有可能取值至少執行一次，同時每個判斷的所有可能取值分支至少執行一次。

*：邏輯覆蓋的強度依次是：語句覆蓋<路徑覆蓋<判定覆蓋<條件覆蓋<判斷-條件覆蓋。

B、基本路徑測試。其思想和步驟是，根據軟件過程性描述中的控制流程確定程序的環路復雜性度量，用此度量定義基本路徑集合，并由此導出一組測試用例，對每一條獨立執行路徑進行測試。

(2)黑盒測試

黑盒測試方法也稱為功能測試或數據驅動測試。黑盒測試是對軟件已經實現的功能是否滿足需求進行測試和驗證。

黑盒測試主要診斷功能不對或遺漏、接口錯誤、數據結構或外部數據庫訪問錯誤、性能錯誤、初始化和終止條件錯誤。

黑盒測試不關心程序內部的邏輯，只是根據程序的功能說明來設計測試用例，主要方法有等價類劃分法、邊界值分析法、錯誤推測法等，主要用軟件的確認測試。

3、軟件測試過程一般按4個步驟進行：單元測試、集成測試、確認測試和系統測試程序的調試程序調試的任務是診斷和改正程序中的錯誤，主要在開發階段進行，調試程序應該由編制源程序的程序員來完成。程序調試的基本步驟:（1）錯誤定位;（2）修改設計和代碼，以排除錯誤;（3）進行回歸測試，防止引進新的錯誤。軟件的調試后要進行回歸測試，防止引進新的錯誤。軟件調試可分為靜態調試和動態調試。靜態調試主要是指通過人的思維來分析源程序代碼和排錯，是主要的調試手段，而動態調試是輔助靜態調試。對軟件主要的調試方法可以采用：(1)強行排錯法。(2)回溯法。(3)原因排除法。(本章應考點撥：本章在筆試中一般占8分左右，約3道選擇題，1道填空題，是公共基礎部分比較重要的一章。從出題的深度來看，本章主要考察對基本概念的識記，有少量對基本原理的理解，沒有實際運用，因此考生在復習本章時，重點應放在基本概念的記憶和基本原理的理解上。)第4章數據庫設計基礎數據庫的基本概念1、數據、數據庫、數據管理系統（1）數據：實際上就是描述事物的符號記錄。數據的特點：有一定的結構，有型與值之分，如整型、實型、字符型等。（2）數據庫（DB）：是數據的集合，具有統一的結構形式并存放于統一的存儲介質內，是多種應用數據的集成，并可被各個應用程序所共享。（3）數據庫管理系統（DBMS）：一種系統軟件，負責數據庫中的數據組織、數據操縱、數據維護、控制及保護和數據服務等，是數據庫的核心。數據庫管理系統功能：

（1）數據模式定義：即為數據庫構建其數據框架；

（2）數據存取的物理構建：為數據模式的物理存取與構建提供有效的存取方法與手段；

（3）數據操縱：為用戶使用數據庫的數據提供方便，如查詢、插入、修改、刪除等以及簡單的算術運算及統計；

（4）數據的完整性、安生性定義與檢查；

（5）數據庫的并發控制與故障恢復；

（6）數據的服務：如拷貝、轉存、重組、性能監測、分析等。為完成數據庫管理系統的功能，數據庫管理系統提供相應的數據語言：數據定義語言、數據操縱語言、數據控制語言。數據語言按其使用方式具有兩種結構形式：交互式命令(又稱自含型或自主型語言)宿主型語言（一般可嵌入某些宿主語言中）。數據定義語言：負責數據的模式定義與數據的物理存取構建；數據操縱語言：負責數據的操縱，如查詢與增、刪、改等；數據控制語言：負責數據完整性、安全性的定義與檢查以及并發控制、故障恢復等。數據庫技術的根本目標是解決數據的共享問題。數據庫系統的發展和基本特點1、數據庫系統的發展

數據庫管理發展至今已經歷了三個階段：人工管理階段、文件系統階段和數據庫系統階段。2、數據庫系統的基本特點(1)數據的高集成性。(2)數據的高共享性與低冗余性。(3)數據獨立性：(4)數據統一管理與控制

數據獨立性一般分為物理獨立性與邏輯獨立性兩級。

物理獨立性：物理獨立性即是數據的物理結構(包括存儲結構，存取方式等)的改變，如存儲設備的更換、物理存儲的更換、存取方式改變等都不影響數據庫的邏輯結構，從而不致引起應用程序的變化。

邏輯獨立性：數據庫總體邏輯結構的改變，如修改數據模式、增加新的數據類型、改變數據間聯系等，不需要相應修改應用程序，這就是數據的邏輯獨立性。數據庫管理員：對數據庫進行規劃、設計、維護、監視等的專業管理人員。

數據庫系統：由數據庫（數據）、數據庫管理系統（軟件）、數據庫管理員（人員）、硬件平臺（硬件）、軟件平臺（軟件）五個部分構成的運行實體。

數據庫應用系統：由數據庫系統、應用軟件及應用界面三者組成。數據庫系統的內部體系結構1、數據庫系統的三級模式：1)概念模式：數據庫系統中全局數據邏輯結構的描述，是全體用戶(應用)公共數據視圖。

2)外模式：也稱子模式或用戶模式，它是用戶的數據視圖，也就是用戶所見到的數據模式，它由概念模式推導而出。

3)內模式：又稱物理模式，它給出了數據庫物理存儲結構與物理存取方法。內模式的物理性主要體現在操作系統及文件級上，它還未深入到設備級上(如磁盤及磁盤操作)。內模式對一般用戶是透明的，但它的設計直接影響數據庫的性能。內模式處于最底層，它反映了數據在計算機物理結構中的實際存儲形式，概念模式處于中間層，它反映了設計者的數據全局邏輯要求，而外模式處于最外層，它反映了用戶對數據的要求。2、數據庫系統的兩級映射：

1)概念模式/內模式的映射：實現了概念模式到內模式之間的相互轉換。當數據庫的存儲結構發生變化時，通過修改相應的概念模式/內模式的映射，使得數據庫的邏輯模式不變，其外模式不變，應用程序不用修改，從而保證數據具有很高的物理獨立性。

2)外模式/概念模式的映射：實現了外模式到概念模式之間的相互轉換。當邏輯模式發生變化時，通過修改相應的外模式/邏輯模式映射，使得用戶所使用的那部分外模式不變，從而應用程序不必修改，保證數據具有較高的邏輯獨立性。數據模型的基本概念數據模型從抽象層次上描述了數據庫系統的靜態特征、動態行為和約束條件，因此數據模型通常由數據結構、數據操作及數據約束三部分組成。數據庫管理系統所支持的數據模型分為3種：層次模型、網狀模型和關系模型。1）層次模型的基本結構是樹形結構。，具有以下特點：（1）每棵樹有且僅有一個無雙親結點，稱為根（2）樹中除根外所有結點有且僅有一個雙親。2）網狀模型是層次模型的一個特例，從圖論上看，網狀模型是一個不加任何條件限制的無向圖。3）關系模型采用二維表來表示，簡稱表，由表框架及表的元組組成。一個二維表就是一個關系。二維表中的每一個分量都是不可再分的。

在二維表中凡能唯一標識元組的最小屬性稱為鍵或碼。從所有侯選健中選取一個作為用戶使用的鍵稱主鍵。表A中的某屬性是某表B的鍵，則稱該屬性集為A的外鍵或外碼。主碼：或稱為關鍵字，表中的一個屬性或幾個屬性的組合、其值能唯一地標識表中一個元組的。主碼屬性不能取空值

關系中的數據約束：

（1）實體完整性約束：約束關系的主鍵中屬性值不能為空值；

（2）參照完全性約束：是關系之間的基本約束；

（3）用戶定義的完整性約束：它反映了具體應用中數據的語義要求。E-R模型1、E-R模型的基本概念：

1）實體：現實世界中的事物。

2）屬性：事物的特性。

3）聯系：現實世界中事物間的關系。實體集的關系有一對一、一對多、多對多的聯系。E-R模型三個基本概念之間的聯接關系：實體是概念世界中的基本單位，屬性有屬性域，每個實體可取屬性域內的值。一個實體的所有屬性值叫元組。*：E-R模型的基本成分是實體和聯系。2、E-R模型的圖示法：1）實體集：用矩形表示。2）屬性：用橢圓形表示。3）聯系：用菱形表示。4）實體集與屬性間的聯接關系：用無向線段表示。5）實體集與聯系間的聯接關系：用無向線段表示。關系模型關系模式采用二維表來表示，一個關系對應一張二維表。可以這么說，一個關系就是一個二維表，但是一個二維表不一定是一個關系。?元組：在一個二維表（一個具體關系）中，水平方向的行稱為元組。元組對應存儲文件中的一個具體記錄；?屬性：二維表中垂直方向的列稱為屬性，每一列有一個屬性名；?域：屬性的取值范圍，也就是不同元組對同一屬性的取值所限定的范圍。關系模型采用二維表來表示，二維表一般滿足下面7個性質：①二維表中元組個數是有限的——元組個數有限性；②二維表中元組均不相同——元組的唯一性；③二維表中元組的次序可以任意交換——元組的次序無關性；④二維表中元組的分量是不可分割的基本數據項——元組分量的原子性；⑤二維表中屬性名各不相同——屬性名唯一性；⑥二維表中屬性與次序無關，可任意交換——屬性的次序無關性；⑦二維表屬性的分量具有與該屬性相同的值域——分量值域的統一性。*：同一個關系模型的任兩個元組值不能完全相同。關系代數關系數據庫系統的特點之一是它建立在數據理論的基礎之上，有很多數據理論可以表示關系模型的數據操作，其中最為著名的是關系代數與關系演算。1、關系的數據結構

關系是由若干個不同的元組所組成，因此關系可視為元組的集合。n元關系是一個n元有序組的集合。

關系模型的基本運算：1)插入；2)刪除；3)修改；4)查詢(包括投影、選擇、笛卡爾積運算)。

2、關系操縱

關系模型的數據操縱即是建立在關系上的數據操縱，一般有查詢、增加、刪除和修改四種操作。

3、集合運算及選擇、投影、連接運算

(1)并(∪)：關系R和S具有相同的關系模式，R和S的并是由屬于R或屬于S的元組構成的集合。

(2)差(－)：關系R和S具有相同的關系模式，R和S的差是由屬于R但不屬于S的元組構成的集合。

(3)交(∩)：關系R和S具有相同的關系模式，R和S的交