計算機二級公共基礎知識

第一章 資料結構與演算法

1. 演算法：是指一組有窮的指令集，是解題方案的準確而完整的描述，演算法不等于程式，也不等于計算方法，
2. 演算法的基本特征：
   1）確定性，演算法中每一步驟都必須有明確定義，不允許有多義性；
   2）有窮性，演算法必須能在有限的時間內做完，即能在執行有限個步驟后終止；
   3）可行性，演算法原則上能夠精確地執行；
   4）擁有足夠的情報，
3. 演算法的組成要素：一個演算法由資料物件的運算和操作以及其控制結構這兩部分組成，
4. 演算法的基本運算和操作：算術運算，邏輯運算，關系運算，資料傳輸，
5. 演算法的基本控制結構：順序，選擇，回圈，
6. 演算法基本設計方法：列舉法、歸納法、遞推、遞回、減半遞推技術，

1. 演算法效率的度量——演算法的復雜度：時間復雜度和空間復雜度，
   1）演算法時間復雜度：指執行演算法所需要的計算作業量，通常，一個演算法所用的時間包括編譯時間和運行時間，
   2）演算法空間復雜度：指執行這個演算法所需要的記憶體空間，包括演算法程式所占的空間，輸入的初始資料所占的空間，演算法執行程序中所需的額外空間，

空間復雜度和時間復雜度并不相關，

資料：資料是客觀事物的符號表示，是能輸入到計算機中并被計算程式識別和處理的符號的總稱，如檔案，聲音，視頻等，
資料元素：資料元素是資料的基本單位，
資料物件：資料物件是性質相同的資料元素的集合，
資料結構：是指由某一資料物件中所有資料成員之間的關系組成的集合，

1. 資料結構可分為資料的邏輯結構和存盤結構，
   1.） 資料的邏輯結構是對資料元素之間的邏輯關系的描述，與資料的存盤無關，是面向問題的，是獨立于計算機的，它包括資料物件和資料物件之間的關系，
   2.）資料的存盤結構也稱為資料的物理結構，是資料在計算機中的存放的方式，是面向計算機的，它包括資料元素的存盤方式和關系的存盤方式，
2. 存盤結構和邏輯結構的關系：一種資料的邏輯結構可以表示成多種存盤結構，即資料的邏輯結構和存盤結構不一定一一對應，
3. 常見的存盤結構有：順序，鏈接，索引等，采用不同的存盤結構其資料處理的效率是不同的，

1. 線性結構的條件（一個非空資料結構) ：
   （1）有且只有一個根結點；
   （2）每一個結點最多有一個前件，也最多有一個后件，
2. 非線性結構： 不滿足線性結構條件的資料結構，
   堆疊、佇列、雙向鏈表是線性結構，
   樹、二叉樹為非線性結構，

1. 線性表是由一組資料元素構成，資料元素的位置只取決于自己的序號，元素之間的相對位置是線性的，
2. 在復雜線性表中，由若干項資料元素組成的資料元素稱為記錄；由多個記錄構成的線性表稱為檔案，
3. 非空線性表的結構特征：
   （1）有且只有一個根結點a1，它無前件；
   （2）有且只有一個終端結點an，它無后件；
   （3）除根結點與終端結點外，其他所有結點有且只有一個前件，也有且只有一個后件，
   結點個數n稱為線性表的長度，當n=0時，稱為空表，
4. 線性表的順序存盤結構具有以下兩個基本特點：
   （1）線性表中所有元素所占的存盤空間是連續的；
   （2）線性表中各資料元素在存盤空間中是按邏輯順序依次存放的，
5. 順序表的運算：查找、插入、洗掉，

1. 線性鏈表是線性表的鏈式存盤結構，資料結構中的每一個結點對應于一個存盤單元，這種存盤單元稱為存盤結點，簡稱結點，
2. 結點由兩部分組成：
   (1) 用于存盤資料元素值，稱為資料域；
   (2) 用于存放指標，稱為指標域，用于指向前一個或后一個結點，
3. 在鏈式存盤結構中，存盤資料結構的存盤空間可以不連續，
4. 各資料結點的存盤順序與資料元素之間的邏輯關系可以不一致，
5. 而資料元素之間的邏輯關系是由指標域來確定的，
6. 鏈式存盤方式既可用于表示線性結構，也可用于表示非線性結構，
7. 線性單鏈表中，HEAD稱為頭指標，HEAD=NULL（或0）稱為空表，
8. 雙向鏈表有兩個指標：左指標（Llink）指向前件結點，右指標（Rlink）指向后件結點，
9. 回圈鏈表：回圈鏈表與單鏈表的不同的是它的最后一個結點的指標域存放的事指向第一個結點的指標，而單鏈表存放的是空指標，
10. 線性鏈表的基本運算：查找、插入、洗掉，

1. 堆疊的基本概念
   堆疊是一種特殊的線性表，只允許在表的一端進行插入和洗掉的線性表；插入，洗掉的一端為堆疊頂，另一端為堆疊底；當表中沒有元素時為空堆疊，
   堆疊是一種后進先出（或先進后出Last In First Out）的線性表，堆疊具有記憶功能，堆疊的實體：火車調度，子彈夾，
2. 堆疊的存盤結構
   1）順序存盤結構：用一組地址連續的存盤單元即一維陣列來存盤；
   2）鏈式存盤：用線性鏈表來存盤；
3. 堆疊的基本運算
   (1) 入堆疊運算，在堆疊頂位置插入元素； Push()
   (2) 退堆疊運算，洗掉元素(取出堆疊頂元素并賦給一個指定的變數)； Pop()
   (3) 讀堆疊頂元素，將堆疊頂元素賦給一個指定的變數，此時指標無變化， Peek()

1. 佇列的基本概念
   佇列是一種特殊的線性表，只允許在表的一端插入，在另一端洗掉，
   允許插入的一端是隊尾（rear），允許洗掉的一端為隊頭（front）；
   當表中沒有元素是空佇列；佇列是一種先進先出的線性表，(FIFO)
2. 佇列的存盤結構
   1)順序存盤：一維陣列，
   2)鏈式存盤：線性鏈表，
3. 佇列的運算:
   (1) 入隊運算：從隊尾插入一個元素；
   (2) 退隊運算：從隊頭洗掉一個元素，
4. 佇列的順序存盤結構一般采用回圈佇列的形式，回圈佇列s=0表示佇列為空；s=1且front=rear表示隊滿，
5. 計算回圈佇列的元素個數：“尾指標減頭指標”，若為負數，再加其容量即可，front-rear

1. 樹是一種非線性結構，是n個結點的有限集，當n=0 時為空樹，n>0時為非空樹，
2. 結點的度：結點所擁有的子樹的個數，
3. 葉子結點：度為0的結點，
4. 分支結點：除葉子結點以外的結點，
5. 結點的層次：根結點在第一層，同一層上左右結點的子結點在下一層，
6. 樹的深度：所處層次最大的那個結點的層次，
7. 樹的度：樹中所有結點的度的最大值，

1. 二叉樹的概念
   二叉樹是一種特殊的樹形結構，每個結點最多只有兩棵子樹，且有左右之分不能互換，因此，二叉樹有五種不同的形態，
2. 二叉樹的性質
   1 性質1 在二叉樹的第k層上，最多有2^(k-1)(k≥1）個結點，
   2 .性質2 深度為m的二叉樹最多有2^m-1個結點，
   3 .性質3 在任意一棵二叉樹中，度為0的結點（葉子結點）總是比度為2的結點多一個，
   4 .性質4 具有n個結點的二叉樹，其深度不小于[log2ⁿ]+1,其中[log2ⁿ]表示為log2n的整數部分，

1. 滿二叉樹：除最后一層外，每一層上的所有結點都有兩個子結點，在滿二叉樹中，每一層上的結點數都達到最大值，即在滿二叉樹的第k層上有2^(k-1)個結點，且深度為m的滿二叉樹有2^m－1個結點，
2. 完全二叉樹是指這樣的二叉樹：除最后一層外，每一層上的結點數均達到最大值；在最后一層上只缺少右邊的若干結點，
3. 滿二叉樹是完全二叉樹，而完全二叉樹一般不是滿二叉樹，

性質1 具有n個結點的完全二叉樹的深度為[log2n]+1，
性質2 完全二叉樹中度為1的結點數為0或1，

1. 前序遍歷：先訪問根結點、然后遍歷左子樹，最后遍歷右子樹；

2. 中序遍歷：先遍歷左子樹、然后訪問根結點，最后遍歷右子樹；

3. 后序遍歷：先遍歷左子樹、然后遍歷右子樹，最后訪問根結點；

1. 順序查找是從表的一端開始，依次掃描表中的各個元素，并與所要查找的數進行比較，
2. 在下列兩種情況下也只能采用順序查找：
   （1）如果線性表為無序表，則不管是順序存盤結構還是鏈式存盤結構，只能用順序查找，
   （2）即使是有序線性表，如果采用鏈式存盤結構，也只能用順序查找，

1. 二分查找的條件：
   1)用順序存盤結構
   2)線性表是有序表，
2. 對于長度為n的有序線性表，在最壞情況下，二分法查找只需比較log2ⁿ次，而順序查找需要比較n次，

1. 交換排序
   （1）冒泡排序法，在最壞的情況下，冒泡排序需要比較次數為n(n－1)/2，
   （2）快速排序法 ，在最壞的情況下，快速排序需要比較次數為n(n－1)/2，
2. 插入類排序法：
   （1）簡單插入排序法，最壞情況需要n(n-1)/2次比較；
   （2）希爾排序法，最壞情況需要O(n^1.5)次比較，（大寫O是演算法復雜度的表示方法）
3. 選擇類排序法：
   （1）簡單選擇排序法，最壞情況需要n(n-1)/2次比較；
   （2）堆排序法，最壞情況需要O(nlog2ⁿ)次比較，
   相比以上幾種(除希爾排序法外)，堆排序法的時間復雜度最小，

第二章 程式設計基礎

1. 形成良好的程式設計風格需注意：
   1、源程式檔案化；
   2、資料說明的方法；
   3、陳述句的結構；
   4、輸入和輸出，
   
   【考點2】結構化程式設計方法的四條原則
   

1、自頂向下； 2、逐步求精； 3、模塊化； 4、限制使用goto陳述句，

1. 順序結構：是最基本、最普通的結構形式，按照程式中的陳述句行的先后順序逐條執行，
2. 選擇結構：又稱為分支結構，它包括簡單選擇和多分支選擇結構，
3. 回圈結構：根據給定的條件，判斷是否要重復執行某一相同的或類似的程式段，
4. 回圈結構對應兩類回圈陳述句：先判斷后執行的回圈體稱為當型回圈結構；先執行回圈體后判斷的稱為直到型回圈結構，

1. 面向物件的程式設計以物件為核心，強調物件的抽象性，封裝性，繼承性和多型性，
2. 面向物件方法的優點
   （1）人類習慣的思維方法一致； （2）穩定性好； （3）可重用性好；
   （4）易于開發大型軟體產品； （5）可維護性好，

1. 物件（object）：面向物件方法中最基本的概念，可以用來表示客觀世界中的任何物體，物件是物體的抽象，
2. 物件的基本特點：
   （1）標識惟一性； （2）分類性； （3）多型性； （4）封裝性； （5）模塊獨立性好，

1. 屬性：即物件所包含的資訊，它在設計物件時確定，一般只能通過執行物件的操作來改變，

2. 類：是具有相似屬性與操作的一組物件，類是關于物件性質的描述，類是物件的抽象，物件是其對應類的一個實體，
   
   【考點7】訊息及其組成
   

3. 訊息：是一個實體與另一個實體之間傳遞的資訊，物件間的通信靠訊息傳遞，
   它請求物件執行某一處理或回答某一要求的資訊，它統一了資料流和控制流，

4. 訊息的組成包括：
   (1)接收訊息的物件的名稱；（2）訊息識別符號，也稱訊息名； （3）零個或多個引數，

1. 繼承：是使用已有的類定義作為基礎建立新類的定義技術，廣義指能夠直接獲得已有的性質和特征，而不必重復定義他們，
2. 繼承具有傳遞性，一個類實際上繼承了它上層的全部基類的特性，
3. 繼承分單繼承和多重繼承，單繼承指一個類只允許有一個父類，即類等級為樹形結構；多重繼承指一個類允許有多個父類，
4. 多型性：是指同樣的訊息被不同的物件接受時可導致完全不同的行動的現象，

第三章 軟體工程基礎

1. 軟體指的是計算機系統中與硬體相互依存的另一部分，包括程式、資料和相關檔案的完整集合，

2. 軟體的特點：
   1）軟體是一種邏輯物體，具有抽象性；
   2）軟體的生產與硬體不同，它沒有明顯的制作程序；
   3）軟體在運行、使用期間不存在磨損、老化問題；
   4）軟體的開發、運行對計算機系統具有依賴性，受計算機系統的限制，這導致了軟體移植的問題；
   5）軟體復雜性高，成本昂貴；
   6）軟體開發涉及諸多的社會因素，

3. 根據應用目標的不同，軟體可分應用軟體、系統軟體和支撐軟體（或工具軟體），
   1）應用軟體 ，為解決特定領域的應用而開發的軟體，如辦公自動化軟體
   2）系統軟體 ，計算機管理自身資源，提高計算機使用效率并為計算機用戶提供各種服務的軟體，如作業系統 ，
   3）支撐軟體（或工具軟體），支撐軟體是介于兩者之間，協助用戶開發軟體的工具性軟體，

1. 軟體生命周期是指軟體產品從提出、實作、使用維護到停止使用退役的整個程序，
   可分為軟體定義，軟體開發及軟體維護3個階段，
2. 軟體生命周期中，能夠準確確定軟體系統必須做什么和必須具備哪些功能的階段是：需求分析，

1. 軟體危機泛指在計算機軟體的開發和維護程序中遇到的一系列嚴重的問題，集中表現在成本，質量，生產效率等幾個方面，
2. 所謂軟體工程是指采用工程的概念、原理、技術和方法指導軟體的開發與維護，是建立并使用完善的工程化原則，以較經濟的手段獲得，能在實際機器上有效運行的可靠軟體的一系列方法；軟體工程的主要思想強調在軟體開發程序中需要應用工程化原則，軟體工程的核心思想是把軟體當作一個工程產品來處理，
3. 軟體工程包括3個要素：方法，工具和程序
   1. 方法是完成軟體工程專案的技術手段
   2. 工具支持軟體的開發、管理、檔案生成
   3. 程序支持軟體開發的各個環節的控制、管理

1. 軟體工程程序是把軟體轉化為輸出的一組彼此相關的資源活動，包含4種基本活動：
   （1）P(plan)——軟體規格說明； （2）D(do)——軟體開發；
   （3）C(check)——軟體確認； （4）A(action)——軟體演進，

1. 軟體工程的理論和技術性研究的內容主要包括軟體開發技術和軟體工程管理，
2. 軟體開發技術包括軟體開發方法學、開發程序、開發工具和軟體工程環境，其主體內容是軟體開發方法學，
3. 軟體開發方法包括分析方法，設計方法和程式設計方法，
4. 軟體工程管理包括軟體管理學，軟體工程經濟學，軟體心理學等，
5. 軟體管理學包括人員組織，進度安排，質量保證，配置管理，專案計劃等，
6. 軟體工程經濟學是研究軟體開發中成本的估算，成本效益的方法和技術，

.

軟體工程的原則：抽象，資訊隱蔽，模塊化，區域化，確定性，一致性，完備性，可驗證性，

1. 需求分析階段的作業：需求獲取，需求分析，撰寫需求規格說明書，需求評審，
   需求分析方法有：
2. 結構化需求分析方法；
   ①面向資料結構的Jackson方法（ISD）；
   ②面向資料流的結構化分析方法（SA）；
   ③面向資料結構的結構化資料系統開發方法（DSSD）；
3. 面向物件的分析的方法（OOA），
   從需求分析建立的模型的特性來分：靜態分析和動態分析，

1. 結構化方法包括結構化分析方法，結構化設計方法，結構化編程方法，
   結構化方法中，軟體功能分解屬于總體設計階段，
2. 結構化分析方法的概念
   結構化分析方法是面向資料流自頂而下逐步求精進行需求分析的方法，
   結構化分析方法在軟體需求分析階段的應用，
3. 結構化分析的常用工具

   1. 資料流圖（DFD-Data Flow Diagram）：是結構化分析方法中用于系統邏輯模型的一種工具，它以圖形的方式描繪在系統中流動和處理的程序，
      資料流圖中四種基本的符號:
      1）箭頭：表示資料流，資料流是資料在系統中傳播的路徑，
      2）圓或橢圓：表示加工，加工又稱為資料處理，是對資料流進行某些操作或變換，
      3）雙橫：表示資料存盤（資料源），資料存盤又稱為檔案，指暫時保存的資料，它可以是資料庫檔案或任何形式的資料組織，
      4）方框：資料的源點或終點，它是軟體系統外部環境中的物體，統稱外部物體

   2. 資料字典（DD）：它是結構分析方法的核心，是用來描述系統中所用到的全部資料和檔案的檔案,作用是對DFD中出現的被命名的圖形元素進行確切解釋，
      資料字典由以下4類元素組成
      1）資料流 2）資料流分量 3）資料存盤 4）處理

   3. 判定樹（決策樹）：是一種描述加工的圖形工具，適合描述時候處理中具有多個判斷，而且每個決策與若干條件有關，

   4. 判定表：與判定樹類似，也是一種描述加工的圖形工具，如果一個加工邏輯有多個條件、多個操作，并且在不同的條件組合下執行不同的操作，那么可以使用判定表來描述，

軟體需求規格說明書（SRS，Software Requirement Specification）是需求分析階段得出的最主要的檔案，軟體需求規格說明書的特點：有正確性、無歧義性、完整性、可驗證性、一致性、可理解性、可修改性和可追蹤性，其中最重要的是無歧義性，

1. 軟體設計是確定系統的物理模型，
2. 軟體設計是開發階段最重要的步驟，是將需求準確地轉化為完整的軟體產品或系統的唯一途徑，
3. 從技術觀點上看，軟體設計包括軟體結構設計、資料設計、介面設計、程序設計，
   （1）結構設計定義軟體系統各主要部件之間的關系；
   （2）數據設計將分析時創建的模型轉化為資料結構的定義；
   （3）介面設計是描述軟體內部、軟體和協作系統之間以及軟體與人之間如何通信；
   （4）程序設計則是把系統結構部件轉換為軟體的程序性描述，
4. 從工程管理角度來看，軟體設計分兩步完成：概要設計和詳細設計，
   （1）概要設計將軟體需求轉化為軟體體系結構、確定系統級介面、全域資料結構或資料庫模式；
   （2）詳細設計確立每個模塊的實作演算法和區域資料結構，用適當方法表示演算法和資料結構的細節，

1. 軟體設計中應該遵循的基本原理和與軟體設計有關的概念：
   1. 模塊化：把程式劃分成獨立命名且可獨立訪問的模塊，每個模塊完成一個子功能，
   2. 抽象化：抽出事物的本質特性而暫時不考慮它們的細節，
   3. 資訊隱藏和區域化：資訊隱蔽是指在一個模塊內包含的資訊（程序或資料），對于不需要這些資訊的其他模塊來說是不能訪問的，實作資訊隱蔽依靠物件的封裝，
   4. 模塊獨立性：模塊獨立性是指每個模塊只完成系統要求的獨立的子功能，并且與其他模塊的聯系最少且介面簡單，模塊的獨立程度是評價設計好壞的重要度量標準，

衡量軟體的模塊獨立性是用耦合性和內聚性兩個定性的度量標準，

1. 耦合性：是對一個軟體結構內不同模塊之間互聯程度的度量，耦合性的強弱取決于模塊間介面的復雜程度，
2. 內聚性：是一個模塊內部各個元素間彼此結合的緊密程度的度量，
   一個模塊的內聚性越強則該模塊的模塊獨立性越強，一個模塊與其他模塊的耦合性越強則該模塊的模塊獨立性越弱，
3. 在結構程式設計中，模塊劃分的原則是模塊內具有高內聚度，模塊間具有低耦合度，
   耦合和內聚的種類，
4. 耦合度由低到高：非直接耦合，資料耦合，標記耦合，控制耦合，外部耦合，公共耦合，內容耦合，
5. 內聚性由強到弱：功能內聚，順序內聚，通信內聚，程序內聚，時間內聚，邏輯內聚，偶然內聚，

結構化分析方法是面向資料流自頂而下，逐步求精進行需求分析的方法，基本思想將軟體設計成由相對獨立，單一功能的模塊組成的結構，與結構分析方法銜接使用，以資料流圖為基礎得到軟體的模塊結構，適用于變換型結構和事物型結構的目標系統，

1. 概要設計的任務：
   （1）劃分出組成系統的物理元素
   （2）設計軟體的結構
2. 概要設計的工具：
   1. 結構圖（SC-Structure Chart）也稱程式結構圖，在結構圖中，模塊用一個矩形表示，箭頭表示模塊間的呼叫關系，可以用帶注釋的箭頭表示模塊呼叫程序中來回傳遞的資訊，
      還可用帶實心圓的箭頭表示傳遞的是控制資訊，空心圓箭心表示傳遞的是資料，
   2. 結構圖的基本形式：基本形式、順序形式、重復形式、選擇形式，
   3. 結構圖有四種模塊型別：傳入模塊、傳出模塊、變換模塊和協調模塊，
   4. 程式結構圖中的專業術語：
      1. 深度 表示控制的層數
      2. 上級模塊，從屬模塊 上，下兩層模塊a和b，且有a呼叫b，則a是上級模塊，b是從屬模塊
      3. 寬度 整體控制跨度（最大模塊的層）的表示
      4. 扇入 呼叫該模塊的模塊個數
      5. 扇出 一個模塊直接呼叫的其他模塊數
      6. 原子模塊 樹中位于葉子節點的模塊
3. 面向資料流的設計方法
   任何軟體系統都可以用資料流圖表示，典型的資料流型別有兩種：變換型和事務型，
   變換型系統結構圖由輸入、中心變換、輸出三部分組成，
4. 設計的準則
   （1）提高模塊獨立性，
   （2）模塊規模適中，
   （3）深度，寬度，扇出和扇入適當，
   （4）使模塊的作用域在該模塊的控制域內，
   （5）減少模塊的介面和界面的復雜性，
   （6）設計成單入口，單出口的模塊，
   （7）設計功能可預測的模塊，
5. 詳細設計常用的設計工具（工程設計工具）：圖形工具，表格工具和語言工具，
6. 圖形工具：
   程式流程圖：箭頭表示控制流，方框表示加工步驟，菱形表示邏輯條件，
   N-S圖：有五種基本圖形，
   PAD圖：問題分析圖，有五種基本圖型，
7. 表格工具：判定表，
8. 語言工具：PDL——程序設計語言（結構化的英語和偽碼），

1. 軟體測驗的目標：發現程式中的錯誤，
2. 軟體測驗的準則：
   （1）所有測驗都是應追溯到需求，
   （2）嚴格執行測驗計劃，排除測驗的隨意性，
   （3）充分注意測驗中的群集表現，程式中存在錯誤的概率與該程式中已發現的錯誤數成正比，
   （4）程式員應避免檢查自己的程式，
   （5）窮舉測驗不可能，窮舉測驗是把程式所有可能的執行路徑都進行檢查，即使小規模的程式的執行路徑數也相當大，不可能窮盡，說明測驗只能證明程式有錯，不能證明程式中無錯，
   （6）妥善保存測驗計劃，測驗用例出錯統計和最終分析報告，

1. 靜態測驗和動態測驗
   1. 靜態測驗包括代碼檢查、靜態結構分析、代碼質量度量，不實際運行軟體，主要通過人工進行，
   2. 動態測驗是通過運行軟體來檢驗軟體中的動態行為和運行結果的正確性，動態測驗的關鍵是使用設計高效、合理的測驗用例，測驗用例就是為測驗設計的資料，由測驗輸入資料（輸入值集）和預期的輸出結果（輸出值集）兩部份組成，測驗用例的設計方法一般分為兩類：黑盒測驗方法和白盒測驗方法，
2. 白盒測驗和黑盒測驗
   1. 白盒測驗
      白盒測驗也稱為結構測驗或邏輯測驗，是把程式看成裝在一只透明的白盒子里，測驗者完全了解程式的結構和處理程序，它根據程式的內部邏輯來設計測驗用例，檢查程式中的邏輯通路是否都按預定的要求正確地作業，
      白盒測驗的基本原則：
      （1）保證所測模塊中每一獨立路徑至少執行一次，
      （2）保證所測模塊所有判斷的每一分支至少執行一次，
      （3）保證所測模塊每一回圈都在邊界條件和一般條件下至少各執行一次，
      （4）驗證所有內部資料結構的有效性，
      （5）按照白盒測驗的基本原則，“白盒”法是窮舉路徑測驗，
      白盒測驗的方法：邏輯覆寫，基本路經測驗，
   2. 黑盒測驗
      黑盒測驗也稱功能測驗或資料驅動測驗，是把程式看成一只黑盒子，測驗者完全不了解，或不考慮程式的結構和處理程序，它根據規格說明書的功能來設計測驗用例，檢查程式的功能是否符合規格說明的要求，
      黑盒測驗的方法：等價劃分法，邊界值分析法，錯誤推測法，

1. 軟體測驗程序分4個步驟，即***單元測驗***、集成測驗、驗收測驗***和***系統測驗，
2. 單元測驗是對軟體設計的最小單位——模塊進行正確性檢驗的測驗，單元測驗的根據是源程式和詳細設計說明書，單元測驗的技術可以采用靜態分析和動態測驗，
3. 單元測驗期間對模塊進行的測驗：模塊介面，區域資料結構，重要的執行通路，出錯處理通路，邊界條件，驅動模塊相當于被測模塊的主程式，它接收測驗資料，并傳給所測模塊，輸出實際測驗結果，樁模塊通常用于代替被測模塊呼叫的其他模塊，其作用僅做少量的資料操作，是一個模擬子程式，
4. 集成測驗是測驗和組裝軟體的系統化技術，主要目的是發現與介面有關的錯誤，集成測驗的依據是概要設計說明書，
   集成測驗的方法：非增量方式組裝和增量方法組裝，
   增量方式包括自頂而下的增量方式，自底而上的增量方式和混合增量方式，
5. 確認測驗的任務是驗證軟體的功能和性能，確認測驗的實施首先運用黑盒測驗方法，對軟體進行有效性測驗，即驗證被測軟體是否滿足需求規格說明確認的標準，
   檢查軟體產品是否符合需求定義的程序是：確認測驗，
6. 系統測驗是通過測驗確認的軟體，作為整個基于計算機系統的一個元素，與計算機硬體、外設、支撐軟體、資料和人員等其他系統元素組合在一起，在實際運行（使用）環境下對計算機系統進行一系列的集成測驗和確認測驗，
   系統測驗的具體實施一般包括：功能測驗、性能測驗、操作測驗、配置測驗、外部介面測驗、安全性測驗等，

1. 在對程式進行了成功的測驗之后將進入程式除錯（通常稱Debug，即排錯），
   
   程式的除錯任務是診斷和改正程式中的錯誤，
   
2. 程式除錯和軟體測驗的區別：
   （1）軟體測驗是盡可能多地發現軟體中的錯誤，而程式除錯先要發現軟體的錯誤，然后借助于一定的除錯工具去執行找出軟體錯誤的具體位置，
   （2）軟體測驗貫穿整個軟體生命期，除錯主要在開發階段，
3. 程式除錯的基本步驟：
   （1）錯誤定位，從錯誤的外部表現形式入手，研究有關部分的程式，確定程式中出錯位置，找出錯誤的內在原因；
   （2）修改設計和代碼，以排除錯誤；
   （3）進行回歸測驗，防止引進新的錯誤，
4. 軟體除錯可分為靜態除錯和動態除錯，
   靜態除錯主要是指通過人的思維來分析源程式代碼和排錯，是主要的設計手段， 而動態除錯是輔助靜態除錯的，
5. 主要的除錯方法有：
   （1）強行排錯法； （2）回溯法； （3）原因排除法，包括演繹法，歸納法和二分法，

第四章 資料庫設計基礎

1. 資料（Data）是資料庫存盤的基本物件，是描述事物的符號記錄，
2. 資料庫（DB）是長期儲存在計算機內、有組織的、可共享的大量資料的集合，它具有統一的結構形式并存放于統一的存盤介質內，是多種應用資料的集成，并可被各個應用程式所共享，所以資料庫技術的根本目標是解決資料共享問題，
3. 資料庫管理系統（DBMS）是資料庫的管理機構，負責資料庫中的資料組織、資料操縱、資料維護、控制及保護和資料服務等，資料庫管理系統是資料庫系統的核心，資料庫系統包含資料庫和資料庫管理系統，
4. 資料庫管理系統的功能：
   （1）資料模式定義：即為資料庫構建其資料框架；
   （2）資料存取的物理構建：為資料模式的物理存取與構建提供有效的存取方法與手段；
   （3）資料操縱：為用戶使用資料庫的資料提供方便，如查詢、插入、修改、洗掉等以及簡單的算術運算及統計；
   （4）資料的完整性、安全性定義與檢查；
   （5）資料庫的并發控制與故障恢復；
   （6）資料的服務：如拷貝、轉存、重組、性能監測、分析等，
5. 為完成資料庫管理系統的功能，資料庫管理系統提供相應的資料語言：
   1. 資料定義語言（DDL）：負責資料模式定義和資料物理存取構建，
   2. 資料操縱語言（DML）：負責資料的操縱，
   3. 資料控制語言（DCL）：負責資料完整性，安全性的定義與檢查以及并發控制，故障恢復等功能，
6. 資料語言按使用方式具有兩個結構形式：互動式命令語言（自含型和自主型語言）和宿主型語言，
7. 資料庫管理員（DBA）的作業：資料庫設計，資料庫維護，改善系統性能，提高系統效率，
8. 資料庫系統（DBS）是指在計算機系統中引入資料庫后的系統，一般由資料庫、資料庫管理系統、應用系統、資料庫管理員和用戶構成，
9. 資料庫應用系統（DBAS）是資料庫系統再加上應用軟體及應用界面這三者所組成，具體包括：資料庫、資料庫管理系統、資料庫管理員、硬體平臺、軟體平臺、應用軟體、應用界面，

資料管理技術的發展經歷了三個階段：人工管理階段、檔案系統階段和資料庫系統階段，資料獨立性最高的階段是資料庫系統階段，

1. 人工管理階段特點：
   （1）計算機系統不提供對用戶資料的管理功能
   （2）資料不能共享
   （3）不單獨保存資料，
2. 檔案系統階段的缺陷：
   （1）資料冗余
   （2）不一致性
   （3）資料聯系弱，
3. 資料庫系統的發展階段：
   第一代的網狀、層次資料庫系統；
   第二代的關系資料庫系統；
   第三代的以面向物件模型為主要特征的資料庫系統，
4. 資料庫系統的基本特點：
   （1）資料的高集成性
   （2）資料的高共享性和低冗余性
   （3）資料高獨立性
   （4）資料統一管理與控制，
5. 資料獨立性是資料與程式間的互不依賴性，即資料庫中的資料獨立于應用程式而不依賴于應用程式，
6. 資料的獨立性一般分為物理獨立性與邏輯獨立性兩種，
   （1）物理獨立性：當資料的物理結構（包括存盤結構、存取方式等）改變時，其邏輯結構，應用程式都不用改變，
   （2）邏輯獨立性：資料的邏輯結構改變了，如修改資料模式、增加新的資料型別、改變資料間聯系等，用戶的應用程式可以不變，

1. 資料統系統的三級模式：
   （1）概念模式，也稱邏輯模式，是對資料庫系統中全域資料邏輯結構的描述，是全體用戶公共資料視圖，一個資料庫只有一個概念模式，
   （2）外模式，外模式也稱子模式，它是資料庫用戶能夠看見和使用的區域資料的邏輯結構和特征的描述，一個概念模式可以有若干個外模式，
   （3）內模式，內模式又稱物理模式，它給出了資料庫物理存盤結構與物理存取方法，一個資料庫只有一個內模式，
   內模式處于最底層，它反映了資料在計算機物理結構中的實際存盤形式，概念模式處于中間層，它反映了設計者的資料全域邏輯要求，而外模式處于最外層，它反映了用戶對資料的要求，
2. 資料庫系統的兩級映射
   兩級映射保證了資料庫系統中資料的獨立性，
   （1）概念模式到內模式的映射，該映射給出了概念模式中資料的全域邏輯結構到資料的物理存盤結構間的對應關系；
   （2）外模式到概念模式的映射，概念模式是一個全域模式而外模式是用戶的區域模式，一個概念模式中可以定義多個外模式，而每個外模式是概念模式的一個基本視圖，

資料模型按不同的應用層次分為：

1. 概念資料模型：簡稱概念模型，是一種面向客觀世界，面向用戶的模型，不涉及具體的硬體環境和平臺也與具體的軟體環境無關的模式，它是整個資料模型的基礎，
2. 邏輯資料模型：又稱資料模型，它是一種面向資料庫的模型，分為層次模型，網狀模型，關系模型和面向物件模型，其中層次模型和網狀模型統稱為非關系模型，層次模型用樹型結構表示物體之間聯系的模型，
3. 物理資料模型：又稱物理模型，它是一種面向計算機物理表示的模型，

1. E-R模型的基本概念
   （1）物體：現實世界中的事物可以抽象成為物體，物體是概念世界中的基本單位，它們是客觀存在的且又能相互區別的事物，
   （2）屬性：現實世界中事物均有一些特性，這些特性可以用屬性來表示，
   （3）碼：唯一標識物體的屬性集稱為碼，
   （4）域：屬性的取值范圍稱為該屬性的域，
   （5）聯系：在現實世界中事物間的關聯稱為聯系，
   兩個物體集間的聯系實際上是物體集間的函式關系，這種函式關系可以有下面幾種：一對一的聯系、一對多或多對一聯系、多對多，
2. E-R模型的的圖示法
   E-R模型用E-R圖來表示，E-R圖包含了表示物體集、屬性和聯系的方法，
   （1）物體的表示：用矩形表示物體集，在矩形內寫上該物體集的名字，
   （2）屬性的表示：用橢圓形表示屬性，在橢圓形內寫上該屬性的名稱，
   （3）聯系的表示：用菱形表示聯系，菱形內寫上聯系名，

層次模型是有根的定向有序樹，是資料庫系統中最早出現的資料模型，網狀模型對應的是有向圖，

1. 層次模型
   （1）有且只有一個結點沒有雙親結點，這個結點稱為根結點
   （2）根以外的其他結點有且只有一個雙親結點
2. 網狀模型
   （1）允許一個以上的結點無雙親
   （2）一個結點可以有多于一個的雙親

1. 關系模式采用二維表來表示，由關系資料結構，關系操縱和關系完整性約束3部分組成，在關系資料庫中，用來表示物體間聯系的是關系，
2. 關系：一個關系對應一張二維表，一個關系就是一個二維表，但是一個二維表不一定是一個關系，
3. 元組：表中的一行即為一個元組，
4. 屬性：表中的一列即為一個屬性，給每一個屬性起一個名稱即屬性名，
5. 分量：元組中的一個屬性值，是不可分割的基本資料項，
6. 域：屬性的取值范圍，
7. 在二維表中惟一標識元組的最小屬性值稱為該表的鍵或碼，二維表中可能有若干個健，它們稱為表的候選碼或候選健，從二維表的所有候選鍵選取一個作為用戶使用的鍵稱為主鍵或主碼，表A中的某屬性集是某表B的鍵，則稱該屬性值為A的外鍵或外碼，
8. 關系操縱：資料查詢、資料的洗掉、資料插入、資料修改，
9. 關系模型允許定義三類資料約束，它們是物體完整性約束、參照完整性約束以及用戶定義的完整性約束，其中物體完整性約束、參照完整性約束必須滿足的完整性約束條件，參照完整性約束不允許關系應用不存在的元組，物體完整性約束要求關系的主鍵中屬性值不能為空，這是資料庫完整性的最基本要求，

1. 并：R和S的并是由屬于R或屬于S的所有元組構成的集合，
2. 差：R和S的差是由屬于R但是不屬于S的元組構成的集合
3. 笛卡爾積：設R和S的元數分別為r和s，R和S的笛卡爾積是一個（r+s）元的元組集合，每個元組的前r個分量來自R的一個元組，后s個分量來自S的一個元組，運算后得到的新表的元組數是R*S，屬性是r+s，
4. 交：屬于R又屬于S的元組構成的集合，
5. 投影：一元運算，對一個關系進行垂直切割，消去某些列，并重新按排列的順序，
6. 選擇：一元運算，根據某些條件對關系進行水平分割，即選擇符合條件的元組，
7. 除：給定關系R（X，Y）和S（Y，Z），其中X，Y，Z是屬性組，R中的Y和S中Y可以有不同的屬性名，但必須出自相同的域集，
8. 連接：也稱θ連接運算，是一種二元運算，它的操作是從兩個關系的笛卡爾積中選取屬性間滿足一定條件的元組，以合并成一個大關系，連接運算包括等值連接和不等值連接，連接運算后得到的新表的屬性是運算前表中屬性相加，即多于原來關系中屬性的個數，
9. 自然連接：自然連接滿足的條件是（1）兩關系間有公共域（2）通過公共域的相等值進行連接，

1. 資料庫設計中有兩種方法，面向資料的方法和面向程序的方法，
2. 面向資料的方法是以資訊需求為主，兼顧處理需求；面向程序的方法是以處理需求為主，兼顧資訊需求，由于資料在系統中穩定性高，資料已成為系統的核心，因此面向資料的設計方法已成為主流，
3. 資料庫設計目前一般采用生命周期法，即將整個資料庫應用系統的開發分解成目標獨立的若干階段，它們是：需求分析階段、概念設計階段、邏輯設計階段、物理設計階段，
4. 一個低一級范式的關系模式，通過模式分解可以轉化為若干個高一級范式的關系模式的集合，這種程序就叫規范化，
5. 概念結構設計是將需求分析階段得到的用戶需求抽象為資訊結構即概念模型的程序，它是整個資料庫設計的關鍵，
6. 邏輯結構設計的任務是將E—R圖轉換成關系資料模型的程序，
7. 資料庫的物理結構是指資料庫在物理設備上的存盤結構和存取方法，它依賴于給定的計算機系統，
8. 常用的存取方法：索引方法，聚簇方法和HASH方法，
9. 資料庫管理的內容：
   （1）資料庫的建立，它是資料庫管理的核心，包括資料模式的建立和資料加載，
   （2）資料庫的重組，
   （3）資料庫安全性控制，
   （4）資料庫的完整性控制，資料庫的完整性是指資料的正確性和相容性，
   （5）資料庫的故障恢復，
   （6）資料庫監控，