技術文章 » 計算機二級公共基礎知識

計算機二級公共基礎知識

2020-09-22 12:00:29

計算機二級公共基礎知識

2020-9-20開始記錄計算機二級考試

文章目錄

第一章 資料結構與演演算法

【考點1】演演算法的基本概念
  1. 演演算法：是指一組有窮的指令集，是解題方案的準確而完整的描述。演演算法不等於程式，也不等於計算方法。
  2. 演演算法的基本特徵：
    1）確定性，演演算法中每一步驟都必須有明確定義，不允許有多義性；
    2）有窮性，演演算法必須能在有限的時間內做完，即能在執行有限個步驟後終止；
    3）可行性，演演算法原則上能夠精確地執行；
    4）擁有足夠的情報。
  3. 演演算法的組成要素：一個演演算法由資料物件的運算和操作以及其控制結構這兩部分組成。
  4. 演演算法的基本運算和操作：算術運算，邏輯運算，關係運算，資料傳輸。
  5. 演演算法的基本控制結構：順序，選擇，迴圈。
  6. 演演算法基本設計方法：列舉法、歸納法、遞推、遞迴、減半遞推技術。
【考點2】演演算法的複雜度
  1. 演演算法效率的度量——演演算法的複雜度：時間複雜度和空間複雜度。
    1）演演算法時間複雜度：指執行演演算法所需要的計算工作量。通常，一個演演算法所用的時間包括編譯時間和執行時間。
    2）演演算法空間複雜度：指執行這個演演算法所需要的記憶體空間。包括演演算法程式所佔的空間，輸入的初始資料所佔的空間，演演算法執行過程中所需的額外空間。

空間複雜度和時間複雜度並不相關。

【考點3】資料結構的基本概念

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

【考點4】邏輯結構和儲存結構
  1. 資料結構可分為資料的邏輯結構和儲存結構。
    1.） 資料的邏輯結構是對資料元素之間的邏輯關係的描述，與資料的儲存無關，是面向問題的，是獨立於計算機的。它包括資料物件和資料物件之間的關係。
    2.）資料的儲存結構也稱為資料的物理結構，是資料在計算機中的存放的方式，是面向計算機的，它包括資料元素的儲存方式和關係的儲存方式。
  2. 儲存結構和邏輯結構的關係：一種資料的邏輯結構可以表示成多種儲存結構，即資料的邏輯結構和儲存結構不一定一一對應。
  3. 常見的儲存結構有：順序，連結，索引等。採用不同的儲存結構其資料處理的效率是不同的。
【考點5】線性結構和非線性結構
  1. 線性結構的條件（一個非空資料結構) ：
    （1）有且只有一個根結點；
    （2）每一個結點最多有一個前件，也最多有一個後件。
  2. 非線性結構： 不滿足線性結構條件的資料結構。
    棧、佇列、雙向連結串列是線性結構，
    樹、二元樹為非線性結構。
【考點6】線性表及其順序儲存結構
  1. 線性表是由一組資料元素構成，資料元素的位置只取決於自己的序號，元素之間的相對位置是線性的。
  2. 在複雜線性表中，由若干項資料元素組成的資料元素稱為記錄；由多個記錄構成的線性表稱為檔案。
  3. 非空線性表的結構特徵：
    （1）有且只有一個根結點a1，它無前件；
    （2）有且只有一個終端結點an，它無後件；
    （3）除根結點與終端結點外，其他所有結點有且只有一個前件，也有且只有一個後件。
    結點個數n稱為線性表的長度，當n=0時，稱為空表。
  4. 線性表的順序儲存結構具有以下兩個基本特點：
    （1）線性表中所有元素所佔的儲存空間是連續的；
    （2）線性表中各資料元素在儲存空間中是按邏輯順序依次存放的。
  5. 順序表的運算：查詢、插入、刪除。
【考點7】線性連結串列
  1. 線性連結串列是線性表的鏈式儲存結構，資料結構中的每一個結點對應於一個儲存單元，這種儲存單元稱為儲存結點，簡稱結點。
  2. 結點由兩部分組成：
    (1) 用於儲存資料元素值，稱為資料域；
    (2) 用於存放指標，稱為指標域，用於指向前一個或後一個結點。
  3. 在鏈式儲存結構中，儲存資料結構的儲存空間可以不連續，
  4. 各資料結點的儲存順序與資料元素之間的邏輯關係可以不一致，
  5. 而資料元素之間的邏輯關係是由指標域來確定的。
  6. 鏈式儲存方式既可用於表示線性結構，也可用於表示非線性結構。
  7. 線性單連結串列中，HEAD稱為頭指標，HEAD=NULL（或0）稱為空表。
  8. 雙向連結串列有兩個指標：左指標（Llink）指向前件結點，右指標（Rlink）指向後件結點。
  9. 迴圈連結串列：迴圈連結串列與單連結串列的不同的是它的最後一個結點的指標域存放的事指向第一個結點的指標，而單連結串列存放的是空指標。
  10. 線性連結串列的基本運算：查詢、插入、刪除。
【考點8】棧
  1. 棧的基本概念
    棧是一種特殊的線性表，只允許在表的一端進行插入和刪除的線性表；插入，刪除的一端為棧頂，另一端為棧底；當表中沒有元素時為空棧。
    棧是一種後進先出（或先進後出Last In First Out）的線性表。棧具有記憶功能。棧的範例：火車排程，子彈夾。
  2. 棧的儲存結構
    1）順序儲存結構：用一組地址連續的儲存單元即一維陣列來儲存；
    2）鏈式儲存：用線性連結串列來儲存；
  3. 棧的基本運算
    (1) 入棧運算，在棧頂位置插入元素； Push()
    (2) 退棧運算，刪除元素(取出棧頂元素並賦給一個指定的變數)； Pop()
    (3) 讀棧頂元素，將棧頂元素賦給一個指定的變數，此時指標無變化。 Peek()
【考點9】佇列
  1. 佇列的基本概念
    佇列是一種特殊的線性表，只允許在表的一端插入，在另一端刪除，
    允許插入的一端是隊尾（rear），允許刪除的一端為隊頭（front）；
    當表中沒有元素是空佇列；佇列是一種先進先出的線性表。(FIFO)
  2. 佇列的儲存結構
    1)順序儲存：一維陣列。
    2)鏈式儲存：線性連結串列。
  3. 佇列的運算:
    (1) 入隊運算：從隊尾插入一個元素；
    (2) 退隊運算：從隊頭刪除一個元素。
  4. 佇列的順序儲存結構一般採用迴圈佇列的形式。迴圈佇列s=0表示佇列為空；s=1且front=rear表示隊滿。
  5. 計算迴圈佇列的元素個數：「尾指標減頭指標」，若為負數，再加其容量即可。front-rear
【考點10】樹的基本概念
  1. 樹是一種非線性結構，是n個結點的有限集。當n=0 時為空樹，n>0時為非空樹。
  2. 結點的度：結點所擁有的子樹的個數。
  3. 葉子結點：度為0的結點。
  4. 分支結點：除葉子結點以外的結點。
  5. 結點的層次：根結點在第一層，同一層上左右結點的子結點在下一層。
  6. 樹的深度：所處層次最大的那個結點的層次。
  7. 樹的度：樹中所有結點的度的最大值。
【考點11】二元樹及其基本性質
  1. 二元樹的概念
    二元樹是一種特殊的樹形結構，每個結點最多隻有兩棵子樹，且有左右之分不能互換，因此，二元樹有五種不同的形態。
  2. 二元樹的性質
    1 性質1 在二元樹的第k層上，最多有2(k-1)(k≥1）個結點。
    2 .性質2 深度為m的二元樹最多有2m-1個結點。
    3 .性質3 在任意一棵二元樹中，度為0的結點（葉子結點）總是比度為2的結點多一個。
    4 .性質4 具有n個結點的二元樹，其深度不小於[log2n]+1,其中[log2n]表示為log2n的整數部分。
【考點12】滿二元樹與完全二元樹
  1. 滿二元樹：除最後一層外，每一層上的所有結點都有兩個子結點。在滿二元樹中，每一層上的結點數都達到最大值，即在滿二元樹的第k層上有2(k-1)個結點，且深度為m的滿二元樹有2m－1個結點。
  2. 完全二元樹是指這樣的二元樹：除最後一層外，每一層上的結點數均達到最大值；在最後一層上只缺少右邊的若干結點。
  3. 滿二元樹是完全二元樹，而完全二元樹一般不是滿二元樹。
【考點13】完全二元樹的性質

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

【考點14】二元樹的遍歷

  1. 前序遍歷：先存取根結點、然後遍歷左子樹，最後遍歷右子樹；

  2. 中序遍歷：先遍歷左子樹、然後存取根結點，最後遍歷右子樹；

  3. 後序遍歷：先遍歷左子樹、然後遍歷右子樹，最後存取根結點；

【考點15】順序查詢
  1. 順序查詢是從表的一端開始，依次掃描表中的各個元素，並與所要查詢的數進行比較。
  2. 在下列兩種情況下也只能採用順序查詢：
    （1）如果線性表為無序表，則不管是順序儲存結構還是鏈式儲存結構，只能用順序查詢。
    （2）即使是有序線性表，如果採用鏈式儲存結構，也只能用順序查詢。
【考點16】二分查詢
  1. 二分查詢的條件：
    1)用順序儲存結構
    2)線性表是有序表。
  2. 對於長度為n的有序線性表，在最壞情況下，二分法查詢只需比較log2n次，而順序查詢需要比較n次。
【考點17】排序
  1. 交換排序
    （1）氣泡排序法，在最壞的情況下，氣泡排序需要比較次數為n(n－1)/2。
    （2）快速排序法 ，在最壞的情況下，快速排序需要比較次數為n(n－1)/2。
  2. 插入類排序法：
    （1）簡單插入排序法，最壞情況需要n(n-1)/2次比較；
    （2）希爾排序法，最壞情況需要O(n1.5)次比較。（大寫O是演演算法複雜度的表示方法）
  3. 選擇類排序法：
    （1）簡單選擇排序法，最壞情況需要n(n-1)/2次比較；
    （2）堆排序法，最壞情況需要O(nlog2n)次比較。
    相比以上幾種(除希爾排序法外)，堆排序法的時間複雜度最小。

第二章 程式設計基礎

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

    【考點2】結構化程式設計方法的四條原則

1、自頂向下； 2、逐步求精； 3、模組化； 4、限制使用goto語句。

【考點3】結構化程式的基本結構
  1. 順序結構：是最基本、最普通的結構形式，按照程式中的語句行的先後順序逐條執行。
  2. 選擇結構：又稱為分支結構，它包括簡單選擇和多分支選擇結構。
  3. 迴圈結構：根據給定的條件，判斷是否要重複執行某一相同的或類似的程式段。
  4. 迴圈結構對應兩類迴圈語句：先判斷後執行的迴圈體稱為當型迴圈結構；先執行迴圈體後判斷的稱為直到型迴圈結構。
【考點4】物件導向的程式設計及物件導向方法的優點
  1. 物件導向的程式設計以物件為核心，強調物件的抽象性，封裝性，繼承性和多型性。
  2. 物件導向方法的優點
    （1）人類習慣的思維方法一致； （2）穩定性好； （3）可重用性好；
    （4）易於開發大型軟體產品； （5）可維護性好。
【考點5】物件及其特點
  1. 物件（object）：物件導向方法中最基本的概念，可以用來表示客觀世界中的任何實體，物件是實體的抽象。
  2. 物件的基本特點：
    （1）標識惟一性； （2）分類性； （3）多型性； （4）封裝性； （5）模組獨立性好。
【考點6】屬性，類和範例

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

  2. 類：是具有相似屬性與操作的一組物件。類是關於物件性質的描述。類是物件的抽象，物件是其對應類的一個範例。

    【考點7】訊息及其組成

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

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

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

第三章 軟體工程基礎

【考點1】軟體定義與軟體特點

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

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

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

【考點2】軟體的生命週期
  1. 軟體生命週期是指軟體產品從提出、實現、使用維護到停止使用退役的整個過程。
    可分為軟體定義，軟體開發及軟體維護3個階段。
  2. 軟體生命週期中，能夠準確確定軟體系統必須做什麼和必須具備哪些功能的階段是：需求分析。
【考點3】軟體危機和軟體工程的概念
  1. 軟體危機泛指在計算機軟體的開發和維護過程中遇到的一系列嚴重的問題，集中表現在成本，品質。生產效率等幾個方面。
  2. 所謂軟體工程是指採用工程的概念、原理、技術和方法指導軟體的開發與維護。是建立並使用完善的工程化原則，以較經濟的手段獲得，能在實際機器上有效執行的可靠軟體的一系列方法；軟體工程的主要思想強調在軟體開發過程中需要應用工程化原則。軟體工程的核心思想是把軟體當作一個工程產品來處理。
  3. 軟體工程包括3個要素：方法，工具和過程
    1. 方法是完成軟體工程專案的技術手段
    2. 工具支援軟體的開發、管理、檔案生成
    3. 過程支援軟體開發的各個環節的控制、管理
【考點4】軟體工程過程
  1. 軟體工程過程是把軟體轉化為輸出的一組彼此相關的資源活動，包含4種基本活動：
    （1）P(plan)——軟體規格說明； （2）D(do)——軟體開發；
    （3）C(check)——軟體確認； （4）A(action)——軟體演進。
【考點5】軟體開發技術和軟體工程管理
  1. 軟體工程的理論和技術性研究的內容主要包括軟體開發技術和軟體工程管理。
  2. 軟體開發技術包括軟體開發方法學、開發過程、開發工具和軟體工程環境，其主體內容是軟體開發方法學。
  3. 軟體開發方法包括分析方法，設計方法和程式設計方法。
  4. 軟體工程管理包括軟體管理學，軟體工程經濟學，軟體心理學等。
  5. 軟體管理學包括人員組織，進度安排，品質保證，設定管理，專案計劃等。
  6. 軟體工程經濟學是研究軟體開發中成本的估算，成本效益的方法和技術。
【考點6】軟體工程的原則

.

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

【考點7】需求分析概述
  1. 需求分析階段的工作：需求獲取，需求分析，編寫需求規格說明書，需求評審。
    需求分析方法有：
  2. 結構化需求分析方法；
    ①面向資料結構的Jackson方法（ISD）；
    ②面向資料流的結構化分析方法（SA）；
    ③面向資料結構的結構化資料系統開發方法（DSSD）；
  3. 物件導向的分析的方法（OOA）。
    從需求分析建立的模型的特性來分：靜態分析和動態分析。
【考點8】結構化方法和結構化分析方法
  1. 結構化方法包括結構化分析方法，結構化設計方法，結構化程式設計方法。
    結構化方法中，軟體功能分解屬於總體設計階段。
  2. 結構化分析方法的概念
    結構化分析方法是面向資料流自頂而下逐步求精進行需求分析的方法。
    結構化分析方法在軟體需求分析階段的應用。
  3. 結構化分析的常用工具

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

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

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

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

【考點9】軟體需求規格說明書

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

【考點10】軟體設計的基本概念
  1. 軟體設計是確定系統的物理模型。
  2. 軟體設計是開發階段最重要的步驟，是將需求準確地轉化為完整的軟體產品或系統的唯一途徑。
  3. 從技術觀點上看，軟體設計包括軟體結構設計、資料設計、介面設計、過程設計。
    （1）結構設計定義軟體系統各主要部件之間的關係；
    （2）資料設計將分析時建立的模型轉化為資料結構的定義；
    （3）介面設計是描述軟體內部、軟體和共同作業系統之間以及軟體與人之間如何通訊；
    （4）過程設計則是把系統結構部件轉換為軟體的過程性描述。
  4. 從工程管理角度來看，軟體設計分兩步完成：概要設計和詳細設計。
    （1）概要設計將軟體需求轉化為軟體體系結構、確定系統級介面、全域性資料結構或資料庫模式；
    （2）詳細設計確立每個模組的實現演演算法和區域性資料結構，用適當方法表示演演算法和資料結構的細節。
【考點11】軟體設計的基本原理
  1. 軟體設計中應該遵循的基本原理和與軟體設計有關的概念：
    1. 模組化：把程式劃分成獨立命名且可獨立存取的模組，每個模組完成一個子功能。
    2. 抽象化：抽出事物的本質特性而暫時不考慮它們的細節。
    3. 資訊隱藏和區域性化：資訊隱蔽是指在一個模組內包含的資訊（過程或資料），對於不需要這些資訊的其他模組來說是不能存取的，實現資訊隱蔽依靠物件的封裝。
    4. 模組獨立性：模組獨立性是指每個模組只完成系統要求的獨立的子功能，並且與其他模組的聯絡最少且介面簡單。模組的獨立程度是評價設計好壞的重要度量標準。
【考點12】耦合性和內聚性

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

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

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

  1. 概要設計的任務：
    （1）劃分出組成系統的物理元素
    （2）設計軟體的結構
  2. 概要設計的工具：
    1. 結構圖（SC-Structure Chart）也稱程式結構圖，在結構圖中，模組用一個矩形表示，箭頭表示模組間的呼叫關係。可以用帶註釋的箭頭表示模組呼叫過程中來回傳遞的資訊。
      還可用帶實心圓的箭頭表示傳遞的是控制資訊，空心圓箭心表示傳遞的是資料。
    1. 結構圖的基本形式：基本形式、順序形式、重複形式、選擇形式。
    2. 結構圖有四種模組型別：傳入模組、傳出模組、變換模組和協調模組。
    3. 程式結構圖中的專業術語：
      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——過程設計語言（結構化的英語和偽碼）。
【考點14】軟體測試的目標和準則
  1. 軟體測試的目標：發現程式中的錯誤。
  2. 軟體測試的準則：
    （1）所有測試都是應追溯到需求。
    （2）嚴格執行測試計劃，排除測試的隨意性。
    （3）充分注意測試中的群集表現。程式中存在錯誤的概率與該程式中已發現的錯誤數成正比。
    （4）程式設計師應避免檢查自己的程式。
    （5）窮舉測試不可能。窮舉測試是把程式所有可能的執行路徑都進行檢查，即使小規模的程式的執行路徑數也相當大，不可能窮盡，說明測試只能證明程式有錯，不能證明程式中無錯。
    （6）妥善儲存測試計劃，測試用例出錯統計和最終分析報告。
【考點15】軟體測試方法 測軟體的角度分為靜態測試和動態測試，按功能分為白盒測試和黑箱測試
  1. 靜態測試和動態測試
    1. 靜態測試包括程式碼檢查、靜態結構分析、程式碼品質度量。不實際執行軟體，主要通過人工進行。
    2. 動態測試是通過執行軟體來檢驗軟體中的動態行為和執行結果的正確性。動態測試的關鍵是使用設計高效、合理的測試用例。測試用例就是為測試設計的資料，由測試輸入資料（輸入值集）和預期的輸出結果（輸出值集）兩部份組成。測試用例的設計方法一般分為兩類：黑箱測試方法和白盒測試方法。
  2. 白盒測試和黑箱測試
    1. 白盒測試
      白盒測試也稱為結構測試或邏輯測試，是把程式看成裝在一隻透明的白盒子裡，測試者完全瞭解程式的結構和處理過程。它根據程式的內部邏輯來設計測試用例，檢查程式中的邏輯通路是否都按預定的要求正確地工作。
      白盒測試的基本原則：
      （1）保證所測模組中每一獨立路徑至少執行一次。
      （2）保證所測模組所有判斷的每一分支至少執行一次。
      （3）保證所測模組每一回圈都在邊界條件和一般條件下至少各執行一次。
      （4）驗證所有內部資料結構的有效性。
      （5）按照白盒測試的基本原則，「白盒」法是窮舉路徑測試。
      白盒測試的方法：邏輯覆蓋，基本路經測試。
    2. 黑箱測試
      黑箱測試也稱功能測試或資料驅動測試，是把程式看成一隻黑盒子，測試者完全不瞭解，或不考慮程式的結構和處理過程。它根據規格說明書的功能來設計測試用例，檢查程式的功能是否符合規格說明的要求。
      黑箱測試的方法：等價劃分法，邊界值分析法，錯誤推測法。
【考點16】軟體測試的實施
  1. 軟體測試過程分4個步驟，即***單元測試***、整合測試、驗收測試***和***系統測試。
  2. 單元測試是對軟體設計的最小單位——模組進行正確性檢驗的測試，單元測試的根據是源程式和詳細設計說明書，單元測試的技術可以採用靜態分析和動態測試。
  3. 單元測試期間對模組進行的測試：模組介面，區域性資料結構，重要的執行通路，出錯處理通路，邊界條件。驅動模組相當於被測模組的主程式，它接收測試資料，並傳給所測模組，輸出實際測試結果，樁模組通常用於代替被測模組呼叫的其他模組，其作用僅做少量的資料操作，是一個模擬子程式。
  4. 整合測試是測試和組裝軟體的系統化技術，主要目的是發現與介面有關的錯誤，整合測試的依據是概要設計說明書。
    整合測試的方法：非增量方式組裝和增量方法組裝。
    增量方式包括自頂而下的增量方式，自底而上的增量方式和混合增量方式。
  5. 確認測試的任務是驗證軟體的功能和效能，確認測試的實施首先運用黑箱測試方法，對軟體進行有效性測試，即驗證被測軟體是否滿足需求規格說明確認的標準。
    檢查軟體產品是否符合需求定義的過程是：確認測試。
  6. 系統測試是通過測試確認的軟體，作為整個基於計算機系統的一個元素，與計算機硬體、外設、支撐軟體、資料和人員等其他系統元素組合在一起，在實際執行（使用）環境下對計算機系統進行一系列的整合測試和確認測試。
    系統測試的具體實施一般包括：功能測試、效能測試、操作測試、設定測試、外部介面測試、安全性測試等。
【考點17】程式偵錯
  1. 在對程式進行了成功的測試之後將進入程式偵錯（通常稱Debug，即排錯）。

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

第四章 資料庫設計基礎

【考點1】資料庫的基本概念
  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）是資料庫系統再加上應用軟體及應用介面這三者所組成，具體包括：資料庫、資料庫管理系統、資料庫管理員、硬體平臺、軟體平臺、應用軟體、應用介面。
【考點2】資料管理的發展和基本特點

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

  1. 人工管理階段特點：
    （1）計算機系統不提供對使用者資料的管理功能
    （2）資料不能共用
    （3）不單獨儲存資料。
  2. 檔案系統階段的缺陷：
    （1）資料冗餘
    （2）不一致性
    （3）資料聯絡弱。
  3. 資料庫系統的發展階段：
    第一代的網狀、層次資料庫系統；
    第二代的關聯式資料庫系統；
    第三代的以物件導向模型為主要特徵的資料庫系統。
  4. 資料庫系統的基本特點：
    （1）資料的高整合性
    （2）資料的高共用性和低冗餘性
    （3）資料高獨立性
    （4）資料統一管理與控制。
  5. 資料獨立性是資料與程式間的互不依賴性，即資料庫中的資料獨立於應用程式而不依賴於應用程式。
  6. 資料的獨立性一般分為物理獨立性與邏輯獨立性兩種。
    （1）物理獨立性：當資料的物理結構（包括儲存結構、存取方式等）改變時，其邏輯結構，應用程式都不用改變。
    （2）邏輯獨立性：資料的邏輯結構改變了，如修改資料模式、增加新的資料型別、改變資料間聯絡等，使用者的應用程式可以不變。
【考點3】資料系統的內部結構體系
  1. 資料統系統的三級模式：
    （1）概念模式，也稱邏輯模式，是對資料庫系統中全域性資料邏輯結構的描述，是全體使用者公共資料檢視。一個資料庫只有一個概念模式。
    （2）外模式，外模式也稱子模式，它是資料庫使用者能夠看見和使用的區域性資料的邏輯結構和特徵的描述，一個概念模式可以有若干個外模式。
    （3）內模式，內模式又稱物理模式，它給出了資料庫物理儲存結構與物理存取方法。一個資料庫只有一個內模式。
    內模式處於最底層，它反映了資料在計算機物理結構中的實際儲存形式，概念模式處於中間層，它反映了設計者的資料全域性邏輯要求，而外模式處於最外層，它反映了使用者對資料的要求。
  2. 資料庫系統的兩級對映
    兩級對映保證了資料庫系統中資料的獨立性。
    （1）概念模式到內模式的對映。該對映給出了概念模式中資料的全域性邏輯結構到資料的物理儲存結構間的對應關係；
    （2）外模式到概念模式的對映。概念模式是一個全域性模式而外模式是使用者的區域性模式。一個概念模式中可以定義多個外模式，而每個外模式是概念模式的一個基本檢視。
【考點4】資料模型的基本概念

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

  1. 概念資料模型：簡稱概念模型，是一種面向客觀世界，面向使用者的模型，不涉及具體的硬體環境和平臺也與具體的軟體環境無關的模式，它是整個資料模型的基礎。
  2. 邏輯資料模型：又稱資料模型，它是一種面向資料庫的模型。分為層次模型，網狀模型，關係模型和物件導向模型，其中層次模型和網狀模型統稱為非關係模型。層次模型用樹型結構表示實體之間聯絡的模型。
  3. 物理資料模型：又稱物理模型，它是一種面向計算機物理表示的模型。
【考點5】E—R模型
  1. E-R模型的基本概念
    （1）實體：現實世界中的事物可以抽象成為實體，實體是概念世界中的基本單位，它們是客觀存在的且又能相互區別的事物。
    （2）屬性：現實世界中事物均有一些特性，這些特性可以用屬性來表示。
    （3）碼：唯一標識實體的屬性集稱為碼。
    （4）域：屬性的取值範圍稱為該屬性的域。
    （5）聯絡：在現實世界中事物間的關聯稱為聯絡。
    兩個實體集間的聯絡實際上是實體集間的函數關係，這種函數關係可以有下面幾種：一對一的聯絡、一對多或多對一聯絡、多對多。
  2. E-R模型的的圖示法
    E-R模型用E-R圖來表示，E-R圖包含了表示實體集、屬性和聯絡的方法。
    （1）實體的表示：用矩形表示實體集，在矩形內寫上該實體集的名字。
    （2）屬性的表示：用橢圓形表示屬性，在橢圓形內寫上該屬性的名稱。
    （3）聯絡的表示：用菱形表示聯絡，菱形內寫上聯絡名。
【考點6】層次模型和網狀模型

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

  1. 層次模型
    （1）有且只有一個結點沒有雙親結點，這個結點稱為根結點
    （2）根以外的其他結點有且只有一個雙親結點
  2. 網狀模型
    （1）允許一個以上的結點無雙親
    （2）一個結點可以有多於一個的雙親
【考點7】關係模型及相關概念
  1. 關係模式採用二維表來表示，由關係資料結構，關係操縱和關係完整性約束3部分組成，在關聯式資料庫中，用來表示實體間聯絡的是關係。
  2. 關係：一個關係對應一張二維表。一個關係就是一個二維表，但是一個二維表不一定是一個關係。
  3. 元組：表中的一行即為一個元組。
  4. 屬性：表中的一列即為一個屬性，給每一個屬性起一個名稱即屬性名。
  5. 分量：元組中的一個屬性值，是不可分割的基本資料項。
  6. 域：屬性的取值範圍。
  7. 在二維表中惟一標識元組的最小屬性值稱為該表的鍵或碼。二維表中可能有若干個健，它們稱為表的候選碼或候選健。從二維表的所有候選鍵選取一個作為使用者使用的鍵稱為主鍵或主碼。表A中的某屬性集是某表B的鍵，則稱該屬性值為A的外來鍵或外碼。
  8. 關係操縱：資料查詢、資料的刪除、資料插入、資料修改。
  9. 關係模型允許定義三類資料約束，它們是實體完整性約束、參照完整性約束以及使用者定義的完整性約束。其中實體完整性約束、參照完整性約束必須滿足的完整性約束條件。參照完整性約束不允許關係應用不存在的元組。實體完整性約束要求關係的主鍵中屬性值不能為空，這是資料庫完整性的最基本要求。
【考點8】關係代數
  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）通過公共域的相等值進行連線。
【考點9】資料庫設計和管理
  1. 資料庫設計中有兩種方法，面向資料的方法和程式導向的方法。
  2. 面向資料的方法是以資訊需求為主，兼顧處理需求；程式導向的方法是以處理需求為主，兼顧資訊需求。由於資料在系統中穩定性高，資料已成為系統的核心，因此面向資料的設計方法已成為主流。
  3. 資料庫設計目前一般採用生命週期法，即將整個資料庫應用系統的開發分解成目標獨立的若干階段。它們是：需求分析階段、概念設計階段、邏輯設計階段、物理設計階段。
  4. 一個低一級正規化的關係模式，通過模式分解可以轉化為若干個高一級正規化的關係模式的集合，這種過程就叫規範化。
  5. 概念結構設計是將需求分析階段得到的使用者需求抽象為資訊結構即概念模型的過程，它是整個資料庫設計的關鍵。
  6. 邏輯結構設計的任務是將E—R圖轉換成關係資料模型的過程。
  7. 資料庫的物理結構是指資料庫在物理裝置上的儲存結構和存取方法。它依賴於給定的計算機系統。
  8. 常用的存取方法：索引方法，聚簇方法和HASH方法。
  9. 資料庫管理的內容：
    （1）資料庫的建立，它是資料庫管理的核心，包括資料模式的建立和資料載入。
    （2）資料庫的重組。
    （3）資料庫安全性控制。
    （4）資料庫的完整性控制，資料庫的完整性是指資料的正確性和相容性。
    （5）資料庫的故障恢復。
    （6）資料庫監控。