說到全國計算機最難的基礎可謂是公共基礎知識了，公共基礎知識一直以來都是以內容多，範圍廣兒讓人聞風喪膽。下面是本站小編為大家整理的關於全國計算機等級考試二級公共基礎知識，希望大家喜歡!
1.1 演算法
演算法：是指解題方案准確而完整的描述。
演算法不等於程式，也不等計算機方法，程式的編制不可能優於演算法的設計。
演算法的基本特徵：是一組嚴謹地定義運算順序的規則，每一個規則都是有效的，是明確的，此順序將在有限的次數下終止。特徵包括：
(1)可行性;
(2)確定性，演算法中每一步驟都必須有明確定義，不充許有模稜兩可的解釋，不允許有多義性;
(3)有窮性，演算法必須能在有限的時間內做完，即能在執行有限個步驟後終止，包括合理的執行時間的含義;
(4)擁有足夠的情報。
演算法的基本要素：一是對資料物件的運算和操作;二是演算法的控制結構。
指令系統：一個計算機系統能執行的所有指令的集合。
基本運算包括：算術運算、邏輯運算、關係運算、資料傳輸。
演算法的控制結構：順序結構、選擇結構、迴圈結構。
演算法基本設計方法：列舉法、歸納法、遞推、遞迴、減鬥遞推技術、回溯法。
演算法複雜度：演算法時間複雜度和演算法空間複雜度。演算法時間複雜度是指執行演算法所需要的計算工作量。演算法空間複雜度是指執行這個演算法所需要的記憶體空間。1.2 資料結構的基本基本概念
資料結構研究的三個方面：
(1)資料集合中各資料元素之間所固有的邏輯關係，即資料的邏輯結構;
(2)在對資料進行處理時，各資料元素在計算機中的儲存關係，即資料的儲存結構;
(3)對各種資料結構進行的運算。
資料結構是指相互有關聯的資料元素的集合。資料的邏輯結構包含：
(1)表示資料元素的資訊;
(2)表示各資料元素之間的前後件關係。
資料的儲存結構有順序、連結、索引等。
線性結構條件：(1)有且只有一個根結點;(2)每一個結點最多有一個前件，也最多有一個後件。非線性結構：不滿足線性結構條件的資料結構。
1.3 線性表及其順序儲存結構
線性表是由一組資料元素構成，資料元素的位置只取決於自己的序號，元素之間的相對位置是線性的。
在複雜線性表中，由若干項資料元素組成的資料元素稱為記錄，而由多個記錄構成的線性表又稱為檔案。
非空線性表的結構特徵：
(1)且只有一個根結點a1，它無前件;
(2)有且只有一個終端結點an，它無後件;
(3)除根結點與終端結點外，其他所有結點有且只有一個前件，也有且只有一個後件。結點個數n稱為線性表的長度，當n=0時，稱為空表。
線性表的順序儲存結構具有以下兩個基本特點：(1)線性表中所有元素的所佔的儲存空間是連續的;(2)線性表中各資料元素在儲存空間中是按邏輯順序依次存放的。
ai的儲存地址為：ADR(ai)=ADR(a1)+(i-1)k,，ADR(a1)為第一個元素的地址，k代表每個元素佔的位元組數。
順序表的運算：插入、刪除。(詳見14--16頁)
1.4 棧和佇列
棧是限定在一端進行插入與刪除的線性表，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧按照“先進後出”(FILO)或“後進先出”(LIFO)組織資料，棧具有記憶作用。用top表示棧頂位置，用bottom表示棧底。
棧的基本運算：(1)插入元素稱為入棧運算;(2)刪除元素稱為退棧運算;(3)讀棧頂元素是將棧頂元素賦給一個指定的變數，此時指標無變化。
佇列是指允許在一端(隊尾)進入插入，而在另一端(隊頭)進行刪除的線性表。Rear指標指向隊尾，front指標指向隊頭。佇列是“先進行出”(FIFO)或“後進後出”(LILO)的線性表。
佇列運算包括(1)入隊運算：從隊尾插入一個元素;(2)退隊運算：從隊頭刪除一個元素。
迴圈佇列：s=0表示佇列空，s=1且front=rear表示佇列滿
1.5 線性連結串列
資料結構中的每一個結點對應於一個儲存單元，這種儲存單元稱為儲存結點，簡稱結點。
結點由兩部分組成：(1)用於儲存資料元素值，稱為資料域;(2)用於存放指標，稱為指標域，用於指向前一個或後一個結點。
在鏈式儲存結構中，儲存資料結構的儲存空間可以不連續，各資料結點的儲存順序與資料元素之間的邏輯關係可以不一致，而資料元素之間的邏輯關係是由指標域來確定的。
鏈式儲存方式即可用於表示線性結構，也可用於表示非線性結構。
線性連結串列，HEAD稱為頭指標，HEAD=NULL(或0)稱為空表，如果是兩指標：左指標(Llink)指向前件結點，右指標(Rlink)指向後件結點。
線性連結串列的基本運算：查詢、插入、刪除。
1.6 樹與二叉樹
樹是一種簡單的非線性結構，所有元素之間具有明顯的層次特性。
在樹結構中，每一個結點只有一個前件，稱為父結點，沒有前件的結點只有一個，稱為樹的根結點，簡稱樹的根。每一個結點可以有多個後件，稱為該結點的子結點。沒有後件的結點稱為葉子結點。在樹結構中，一個結點所擁有的後件的個數稱為該結點的度，所有結點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。二叉樹的特點：(1)非空二叉樹只有一個根結點;(2)每一個結點最多有兩棵子樹，且分別稱為該結點的左子樹與右子樹。二叉樹的基本性質：(1)在二叉樹的第k層上，最多有2k-1(k≥1)個結點;(2)深度為m的二叉樹最多有2m-1個結點;(3)度為0的結點(即葉子結點)總是比度為2的結點多一個;
(4)具有n個結點的二叉樹，其深度至少為[log2n]+1,其中[log2n]表示取log2n的整數部分;
(5)具有n個結點的完全二叉樹的深度為[log2n]+1;
(6)設完全二叉樹共有n個結點。如果從根結點開始，按層序(每一層從左到右)用自然數1，2，….n給結點進行編號(k=1,2….n)，有以下結論：
①若k=1，則該結點為根結點，它沒有父結點;若k>1，則該結點的父結點編號為INT(k/2);
②若2k≤n，則編號為k的結點的左子結點編號為2k;否則該結點無左子結點(也無右子結點);
③若2k+1≤n，則編號為k的結點的右子結點編號為2k+1;否則該結點無右子結點。
滿二叉樹是指除最後一層外，每一層上的所有結點有兩個子結點，則k層上有2k-1個結點深度為m的滿二叉樹有2m-1個結點。完全二叉樹是指除最後一層外，每一層上的結點數均達到最大值，在最後一層上只缺少右邊的若干結點。二叉樹儲存結構採用鏈式儲存結構，對於滿二叉樹與完全二叉樹可以按層序進行順序儲存。二叉樹的遍歷：(1)前序遍歷(DLR)，首先訪問根結點，然後遍歷左子樹，最後遍歷右子樹;(2)中序遍歷(LDR)，首先遍歷左子樹，然後訪問根結點，最後遍歷右子樹;(3)後序遍歷(LRD)首先遍歷左子樹，然後訪問遍歷右子樹，最後訪問根結點。1.7 查詢技術
順序查詢的使用情況：
(1)線性表為無序表;
(2)表採用鏈式儲存結構。
二分法查詢只適用於順序儲存的有序表，對於長度為n的有序線性表，最壞情況只需比較log2n次。
1.8 排序技術
排序是指將一個無序序列整理成按值非遞減順序排列的有序序列。
交換類排序法：(1)氣泡排序法，需要比較的次數為n(n-1)/2;(2)快速排序法。
插入類排序法：(1)簡單插入排序法，最壞情況需要n(n-1)/2次比較;(2)希爾排序法，最壞情況需要O(n1.5)次比較。
選擇類排序法：(1)簡單選擇排序法, 最壞情況需要n(n-1)/2次比較;(2)堆排序法，最壞情況需要O(nlog2n)次比較。
二級公共基礎知識：程式設計基礎2.1 程式設計設計方法和風格
如何形成良好的程式設計風格
1、源程式文件化; 2、資料說明的方法;
3、語句的結構; 4、輸入和輸出。
註釋分序言性註釋和功能性註釋，語句結構清晰第一、效率第二。
2.2 結構化程式設計
結構化程式設計方法的四條原則是：1. 自頂向下;2. 逐步求精;3.模組化;4.限制使用goto語句。
結構化程式的基本結構和特點：
(1)順序結構：一種簡單的程式設計，最基本、最常用的結構;
(2)選擇結構：又稱分支結構，包括簡單選擇和多分支選擇結構，可根據條件，判斷應該選擇哪一條分支來執行相應的語句序列;
(3)迴圈結構：可根據給定條件，判斷是否需要重複執行某一相同程式段。
2.3 面向物件的程式設計
面向物件的程式設計：以60年代末挪威奧斯陸大學和挪威計算機中心研製的SIMULA語言為標誌。
面向物件方法的優點：
(1)與人類習慣的思維方法一致;
(2)穩定性好;
(3)可重用性好;
(4)易於開發大型軟體產品;
(5)可維護性好。
物件是面向物件方法中最基本的概念，可以用來表示客觀世界中的任何實體，物件是實體的抽象。
面向物件的程式設計方法中的物件是系統中用來描述客觀事物的一個實體，是構成系統的一個基本單位，由一組表示其靜態特徵的屬性和它可執行的一組操作組成。
屬性即物件所包含的資訊，操作描述了物件執行的功能，操作也稱為方法或服務。
物件的基本特點：(1)標識惟一性;(2)分類性;(3)多型性;(4)封裝性;(5)模組獨立性好。類是指具有共同屬性、共同方法的物件的集合。所以類是物件的抽象，物件是對應類的一個例項。訊息是一個例項與另一個例項之間傳遞的資訊。訊息的組成包括(1)接收訊息的物件的名稱;(2)訊息識別符號，也稱訊息名;(3)零個或多個引數。
繼承是指能夠直接獲得已有的性質和特徵，而不必重複定義他們。繼承分單繼承和多重繼承。單繼承指一個類只允許有一個父類，多重繼承指一個類允許有多個父類。多型性是指同樣的訊息被不同的物件接受時可導致完全不同的行動的現象
二級公共基礎知識：軟體工程基礎3.1 軟體工程基本概念
計算機軟體是包括程式、資料及相關文件的完整集合。
軟體的特點包括：
(1)軟體是一種邏輯實體;
(2)軟體的生產與硬體不同，它沒有明顯的製作過程;
(3)軟體在執行、使用期間不存在磨損、老化問題;
(4)軟體的開發、執行對計算機系統具有依賴性，受計算機系統的限制，這導致了軟體移植的問題;
(5)軟體複雜性高，成本昂貴;
(6)軟體開發涉及諸多的社會因素。
軟體按功能分為應用軟體、系統軟體、支撐軟體(或工具軟體)。
軟體危機主要表現在成本、質量、生產率等問題。
軟體工程是應用於計算機軟體的定義、開發和維護的一整套方法、工具、文件、實踐標準和工序。軟體工程包括3個要素：方法、工具和過程。軟體工程過程是把軟體轉化為輸出的一組彼此相關的資源和活動，包含4種基本活動：
(1)P——軟體規格說明;
(2)D——軟體開發;
(3)C——軟體確認;
(4)A——軟體演進。
軟體週期：軟體產品從提出、實現、使用維護到停止使用退役的過程。軟體生命週期三個階段:軟體定義、軟體開發、執行維護，主要活動階段是：
(1)可行性研究與計劃制定;
(2)需求分析;
(3)軟體設計;
(4)軟體實現;
(5)軟體測試;
(6)執行和維護。
軟體工程的目標和與原則：
目標：在給定成本、進度的前提下，開發出具有有效性、可靠性、可理解性、可維護性、可重用性、可適應性、可移植性、可追蹤性和可互操作性且滿足使用者需求的產品。
基本目標：付出較低的開發成本;達到要求的軟體功能;取得較好的軟體效能;開發軟體易於移植;需要較低的費用;能按時完成開發，及時交付使用。
基本原則：抽象、資訊隱蔽、模組化、區域性化、確定性、一致性、完備性和可驗證性。軟體工程的理論和技術性研究的內容主要包括：軟體開發技術和軟體工程管理。軟體開發技術包括：軟體開發方法學、開發過程、開發工具和軟體工程環境。軟體工程管理包括：軟體管理學、軟體工程經濟學、軟體心理學等內容。軟體管理學包括人員組織、進度安排、質量保證、配置管理、專案計劃等。軟體工程原則包括抽象、資訊隱蔽、模組化、區域性化、確定性、一致性、完備性和可驗證性。
3.2 結構化分析方法
結構化方法的核心和基礎是結構化程式設計理論。需求分析方法有(1)結構化需求分析方法; (2)面向物件的分析的方法。從需求分析建立的模型的特性來分：靜態分析和動態分析。結構化分析方法的實質：著眼於資料流，自頂向下，逐層分解，建立系統的處理流程，以資料流圖和資料字典為主要工具,建立系統的邏輯模型。結構化分析的常用工具(1)資料流圖; (2)資料字典; (3)判定樹; (4)判定表。
資料流圖：描述資料處理過程的工具，是需求理解的邏輯模型的圖形表示，它直接支援系統功能建模。
資料字典：對所有與系統相關的資料元素的一個有組織的列表，以及精確的、嚴格的定義，使得使用者和系統分析員對於輸入、輸出、儲存成分和中間計算結果有共同的理解。
判定樹：從問題定義的文字描述中分清哪些是判定的條件，哪些是判定的結論，根據描述材料中的連線詞找出判定條件之間的從屬關係、並列關係、選擇關係，根據它們構造判定樹。
判定表：與判定樹相似，當資料流圖中的加工要依賴於多個邏輯條件的取值，即完成該加工的一組動作是由於某一組條件取值的組合而引發的，使用判定表描述比較適宜。
資料字典是結構化分析的核心。
軟體需求規格說明書的特點：
(1)正確性;
(2)無岐義性;
(3)完整性;
(4)可驗證性;
(5)一致性;
(6)可理解性;
(7)可追蹤性。
3.3 結構化設計方法
軟體設計的基本目標是用比較抽象概括的方式確定目標系統如何完成預定的任務，軟體設計是確定系統的物理模型。軟體設計是開發階段最重要的步驟，是將需求準確地轉化為完整的軟體產品或系統的唯一途徑。
從技術觀點來看，軟體設計包括軟體結構設計、資料設計、介面設計、過程設計。結構設計：定義軟體系統各主要部件之間的關係。
資料設計：將分析時建立的模型轉化為資料結構的定義。
介面設計：描述軟體內部、軟體和協作系統之間以及軟體與人之間如何通訊。
過程設計：把系統結構部件轉換成軟體的過程描述。
從工程管理角度來看：概要設計和詳細設計。
軟體設計的一般過程：軟體設計是一個迭代的過程;先進行高層次的結構設計;後進行低層次的過程設計;穿插進行資料設計和介面設計。
衡量軟體模組獨立性使用耦合性和內聚性兩個定性的度量標準。在程式結構中各模組的內聚性越強，則耦合性越弱。優秀軟體應高內聚，低耦合。
軟體概要設計的基本任務是：
(1)設計軟體系統結構;(2)資料結構及資料庫設計;
(3)編寫概要設計文件;(4)概要設計文件評審。
模組用一個矩形表示，箭頭表示模組間的.呼叫關係。
在結構圖中還可以用帶註釋的箭頭表示模組呼叫過程中來回傳遞的資訊。還可用帶實心圓的箭頭表示傳遞的是控制資訊，空心圓箭心表示傳遞的是資料。
結構圖的基本形式：基本形式、順序形式、重複形式、選擇形式。結構圖有四種模組型別：傳入模組、傳出模組、變換模組和協調模組。典型的資料流型別有兩種：變換型和事務型。變換型系統結構圖由輸入、中心變換、輸出三部分組成。事務型資料流的特點是：接受一項事務，根據事務處理的特點和性質，選擇分派一個適當的處理單元，然後給出結果。
詳細設計：是為軟體結構圖中的每一個模組確定實現演算法和區域性資料結構，用某種選定的表達工具表示演算法和資料結構的細節。
常見的過程設計工具有：圖形工具(程式流程圖)、表格工具(判定表)、語言工具(PDL)。
3.4 軟體測試
軟體測試定義：使用人工或自動手段來執行或測定某個系統的過程，其目的在於檢驗它是否滿足規定的需求或是弄清預期結果與實際結果之間的差別。
軟體測試的目的：發現錯誤而執行程式的過程。軟體測試方法：靜態測試和動態測試。靜態測試包括程式碼檢查、靜態結構分析、程式碼質量度量。不實際執行軟體，主要通過人工進行。
動態測試：是基本計算機的測試，主要包括白盒測試方法和黑盒測試方法。
白盒測試：在程式內部進行，主要用於完成軟體內部CAO作的驗證。主要方法有邏輯覆蓋、基本基路徑測試。
黑盒測試：主要診斷功能不對或遺漏、介面錯誤、資料結構或外部資料庫訪問錯誤、效能錯誤、初始化和終止條件錯，用於軟體確認。主要方法有等價類劃分法、邊界值分析法、錯誤推測法、因果圖等。
軟體測試過程一般按4個步驟進行：單元測試、整合測試、驗收測試(確認測試)和系統測試。
3.5 程式的除錯
程式除錯的任務是診斷和改正程式中的錯誤，主要在開發階段進行。
程式除錯的基本步驟：
(1)錯誤定位;
(2)修改設計和程式碼，以排除錯誤;
(3)進行迴歸測試，防止引進新的錯誤。
軟體除錯可分表靜態除錯和動態除錯。靜態除錯主要是指通過人的思維來分析源程式程式碼和排錯，是主要的設計手段，而動態除錯是輔助靜態除錯。主要除錯方法有：
(1)強行排錯法;
(2)回溯法;
(3)原因排除法。
二級公共基礎知識： 資料庫設計基礎4.1 資料庫系統的基本概念
資料：實際上就是描述事物的符號記錄。
資料的特點：有一定的結構，有型與值之分，如整型、實型、字元型等。而資料的值給出了符合定型的值，如整型值15。
資料庫：是資料的集合，具有統一的結構形式並存放於統一的儲存介質內，是多種應用資料的整合，並可被各個應用程式共享。
資料庫存放資料是按資料所提供的資料模式存放的，具有整合與共享的特點。
資料庫管理系統：一種系統軟體，負責資料庫中的資料組織、資料操縱、資料維護、控制及保護和資料服務等，是資料庫的核心。
資料庫管理系統功能：
(1)資料模式定義：即為資料庫構建其資料框架;
(2)資料存取的物理構建：為資料模式的物理存取與構建提供有效的存取方法與手段;
(3)資料操縱：為使用者使用資料庫的資料提供方便，如查詢、插入、修改、刪除等以及簡單的算術運算及統計;
(4)資料的完整性、安生性定義與檢查;
(5)資料庫的併發控制與故障恢復;
(6)資料的服務：如拷貝、轉存、重組、效能監測、分析等。
為完成以上六個功能，資料庫管理系統提供以下的資料語言：
(1)資料定義語言：負責資料的模式定義與資料的物理存取構建;
(2)資料操縱語言：負責資料的操縱，如查詢與增、刪、改等;
(3)資料控制語言：負責資料完整性、安全性的定義與檢查以及併發控制、故障恢復等。
資料語言按其使用方式具有兩種結構形式：互動式命令(又稱自含型或自主型語言)宿主型語言(一般可嵌入某些宿主語言中)。
資料庫管理員：對資料庫進行規劃、設計、維護、監視等的專業管理人員。
資料庫系統：由資料庫(資料)、資料庫管理系統(軟體)、資料庫管理員(人員)、硬體平臺(硬體)、軟體平臺(軟體)五個部分構成的執行實體。
資料庫應用系統：由資料庫系統、應用軟體及應用介面三者組成。
檔案系統階段：提供了簡單的資料共享與資料管理能力，但是它無法提供完整的、統一的、管理和資料共享的能力。
層次資料庫與網狀資料庫系統階段：為統一與共享資料提供了有力支撐。
關係資料庫系統階段
資料庫系統的基本特點：資料的整合性、資料的高共享性與低冗餘性、資料獨立性(物理獨立性與邏輯獨立性)、資料統一管理與控制。
資料庫系統的三級模式：
(1)概念模式：資料庫系統中全域性資料邏輯結構的描述，全體使用者公共資料檢視;
(2)外模式：也稱子模式與使用者模式。是使用者的資料檢視，也就是使用者所見到的資料模式;
(3)內模式：又稱物理模式，它給出了資料庫物理儲存結構與物理存取方法。
資料庫系統的兩級對映：(1)概念模式到內模式的對映;(2)外模式到概念模式的對映。
4.2 資料模型
資料模型的概念：是資料特徵的抽象，從抽象層次上描述了系統的靜態特徵、動態行為和約束條件，為資料庫系統的資訊表與操作提供一個抽象的框架。描述了資料結構、資料操作及資料約束。
E-R模型的基本概念(1)實體：現實世界中的事物;
(2)屬性：事物的特性;
(3)聯絡：現實世界中事物間的關係。實體集的關係有一對一、一對多、多對多的聯絡。
E-R模型三個基本概念之間的聯接關係：實體是概念世界中的基本單位，屬性有屬性域，每個實體可取屬性域內的值。一個實體的所有屬性值叫元組。E-R模型的圖示法：(1)實體集表示法; (2)屬性表法; (3)聯絡表示法。
層次模型的基本結構是樹形結構，具有以下特點：
(1)每棵樹有且僅有一個無雙親結點，稱為根;
(2)樹中除根外所有結點有且僅有一個雙親。
從圖論上看，網狀模型是一個不加任何條件限制的無向圖。
關係模型採用二維表來表示，簡稱表，由表框架及表的元組組成。一個二維表就是一個關係。
在二維表中凡能唯一標識元組的最小屬性稱為鍵或碼。從所有侯選健中選取一個作為使用者使用的鍵稱主鍵。表A中的某屬性是某表B的鍵，則稱該屬性集為A的外來鍵或外碼。
關係中的資料約束：
(1)實體完整性約束：約束關係的主鍵中屬性值不能為空值;
(2)參照完全性約束：是關係之間的基本約束;
(3)使用者定義的完整性約束：它反映了具體應用中資料的語義要求。
4.3關係代數
關係資料庫系統的特點之一是它建立在資料理論的基礎之上，有很多資料理論可以表示關係模型的資料操作，其中最為著名的是關係代數與關係演算。
關係模型的基本運算：(1)插入 (2)刪除 (3)修改 (4)查詢(包括投影、選擇、笛卡爾積運算)
4.4 資料庫設計與管理
資料庫設計是資料應用的核心。
資料庫設計的兩種方法：
(1)面向資料：以資訊需求為主，兼顧處理需求;
(2)面向過程：以處理需求為主，兼顧資訊需求。
資料庫的生命週期：需求分析階段、概念設計階段、邏輯設計階段、物理設計階段、編碼階段、測試階段、執行階段、進一步修改階段。需求分析常用結構析方法和麵向物件的方法。結構化分析(簡稱SA)方法用自頂向下、逐層分解的方式分析系統。用資料流圖表達資料和處理過程的關係。對資料庫設計來講，資料字典是進行詳細的資料收集和資料分析所獲得的主要結果。
資料字典是各類資料描述的集合，包括5個部分：資料項、資料結構、資料流(可以是資料項，也可以是資料結構)、資料儲存、處理過程。資料庫概念設計的目的是分析資料內在語義關係。設計的方法有兩種(1)集中式模式設計法(適用於小型或並不複雜的單位或部門);(2)檢視整合設計法。設計方法：E-R模型與檢視整合。檢視設計一般有三種設計次序：自頂向下、由底向上、由內向外。檢視整合的幾種衝突：命名衝突、概念衝突、域衝突、約束衝突。關係檢視設計：關係檢視的設計又稱外模式設計。
關係檢視的主要作用：
(1)提供資料邏輯獨立性;
(2)能適應使用者對資料的不同需求;
(3)有一定資料保密功能。
資料庫的物理設計主要目標是對資料內部物理結構作調整並選擇合理的存取路徑，以提高資料庫訪問速度有效利用儲存空間。一般RDBMS中留給使用者參與物理設計的內容大致有索引設計、整合簇設計和分割槽設計。
資料庫管理的內容：
(1)資料庫的建立;
(2)資料庫的調整;
(3)資料庫的重組;
(4)資料庫安全性與完整性控制;
(5)資料庫的故障恢復;
(6)資料庫監控。
