c語言二級公共基礎知識

今天小編為大家帶來了計算機二級考試中C語言部分的內容，下面這些都是乾貨，不管你是新生老生都值得收藏喲，看看下面的c語言二級公共基礎知識吧!

第一章 資料結構與演算法

1.1 演算法

1.演算法的基本概念

(1) 概念：演算法是指一系列解決問題的清晰指令。

(2) 4個基本特徵：可行性、確定性、有窮性、擁有足夠的情報。

(3) 兩種基本要素：對資料物件的運算和操作、演算法的控制結構(運算和操作時問的順序)。

(4) 設計的基本方法：列舉法、歸納法、遞推法、遞迴法、減半遞推技術和回溯法。

2.演算法的複雜度

(1) 演算法的時間複雜度：執行演算法所需要的計算工作量。

(2) 演算法的空間複雜度：執行演算法所需的記憶體空間。

1.2 資料結構的基本概念

資料結構指相互有關聯的資料元素的集合，即資料的組織形式。其中邏輯結構反映資料元素之間邏輯關係;儲存結構為資料的邏輯結構在計算機儲存空間中的存放形式，有順序儲存、鏈式儲存、索引儲存和雜湊儲存4種方式。

資料結構按各元素之間前後件關係的複雜度可劃分為：

(1) 線性結構：有且只有一個根節點，且每個節點最多有一個直接前驅和一個直接後繼的非空資料結構。

(2) 非線性結構：不滿足線性結構的資料結構。

1.3 線性表及其順序儲存結構

1.線性表的基本概念

線性結構又稱線性表，線性表是最簡單也是最常用的一種資料結構。

2.線性表的順序儲存結構

元素所佔的儲存空間必須連續。

元素在儲存空間的位置是按邏輯順序存放的。

3.線性表的插入運算

在第i個元素之前插入一個新元素的步驟如下：

步驟一：把原來第n個節點至第i個節點依次往後移一個元素位置。

步驟二：把新節點放在第i個位置上。

步驟三：修正線性表的節點個數。

在最壞情況下，即插入元素在第一個位置，線性表中所有元素均需要移動。

4.線性表的刪除運算

刪除第i個位置的元素的步驟如下：

步驟一：把第i個元素之後不包括第i個元素的n-i個元素依次前移一個位置;

步驟二：修正線性表的結點個數。

1.4 棧和佇列

1.棧及其基本運算

(1) 基本概念：棧是一種特殊的線性表，其插入運算與刪除運算都只在線性表的一端進行，也被稱為“先進後出”表或“後進先出”表。

棧頂：允許插入與刪除的一端。

棧底：棧頂的另一端。

空棧：棧中沒有元素的棧。

(2) 特點。

棧頂元素是最後被 插入和最早被刪除的元素。

棧底元素是最早被 插入和最後被刪除的元素。

棧有記憶作用。

在順序儲存結構下，棧的插入和刪除運算不需移動表中其他資料元素。

棧頂指標top動態反映了棧中元素的變化情況

(3) 順序儲存和運算：入棧運算、退棧運算和讀棧頂運算。

2.佇列及其基本運算

(1) 基本概念：佇列是指允許在一端進行插入，在另一端進行刪除的線性表，又稱“先進先出”的線性表。

隊尾：允許插入的一端，用尾指標指向隊尾元素。

排頭：允許刪除的一端，用頭指標指向頭元素的前一位置。

(2) 迴圈佇列及其運算。

所謂迴圈佇列，就是將佇列儲存空間的最後一個位置繞到第一個位置，形成邏輯上的環狀空間。

入隊運算是指在迴圈佇列的隊尾加入一個新元素。

當迴圈佇列非空(s=1)且隊尾指標等於隊頭指標時，說明迴圈佇列已滿，不能進行人隊運算，這種情況稱為“上溢”。

退隊運算是指在迴圈佇列的隊頭位置退出一個元素並賦給指定的變數。首先將隊頭指標進一，然後將排頭指標指向的元素賦給指定的變數。當迴圈佇列為空(s=0)時，不能進行退隊運算，這種情況稱為“下溢”。

1.5 線性連結串列

在定義的連結串列中，若只含有一個指標域來存放下一個元素地址，稱這樣的連結串列為單鏈表或線性連結串列。

在鏈式儲存方式中，要求每個結點由兩部分組成：一部分用於存放資料元素值，稱為資料域;另一部分用於存放指標，稱為指標域。其中指標用於指向該結點的前一個或後一個結點(即前件或後件)。

1.6 樹和二叉樹

1.樹的基本概念

樹是簡單的非線性結構，樹中有且僅有一個沒有前驅的節點稱為“根”，其餘節點分成m個互不相交的有限集合T1，T2，…，T}mm，每個集合又是一棵樹，稱T1，T2，…，T}mm為根結點的子樹。

父節點：每一個節點只有一個前件，無前件的節點只有一個，稱為樹的根結點(簡稱樹的根)。

子節點：每～個節點可以後多個後件，無後件的節點稱為葉子節點。

樹的度：所有節點最大的度。

樹的深度：樹的最大層次。

2.二叉樹的定義及其基本性質

(1) 二叉樹的定義：二叉樹是一種非線性結構，是有限的節點集合，該集合為空(空二叉樹)或由一個根節點及兩棵互不相交的左右二叉子樹組成。可分為滿二叉樹和完全二叉樹，其中滿二叉樹一定是完全二叉樹，但完全二叉樹不一定是滿二叉樹。二叉樹具有如下兩個特點：

二叉樹可為空，空的二叉樹無節點，非空二叉樹有且只有一個根結點;

每個節點最多可有兩棵子樹，稱為左子樹和右子樹。

(2) 二叉樹的基本性質。

性質1：在二叉樹的第k層上至多有2k-1個結點(k≥1)。

性質2：深度為m的二叉樹至多有2m-1個結點。

性質3：對任何一棵二叉樹，度為0的結點(即葉子結點)總是比度為2的結點多一個。

性質4：具有n個結點的完全二叉樹的深度至少為[log2n]+1，其中[log2n]表示log2n的整數部分。

3.滿二叉樹與完全二叉樹

(1) 滿二叉樹：滿二叉樹是指這樣的一種二叉樹：除最後一層外，每一層上的所有結點都有兩個子結點。滿二叉樹在其第i層上有2i-1個結點。

從上面滿二叉樹定義可知，二叉樹的每一層上的結點數必須都達到最大，否則就不是滿二叉樹。深度為m的滿二叉樹有2m-1個結點。

(2) 完全二叉樹：完全二叉樹是指這樣的二叉樹：除最後一層外，每一層上的結點數均達到最大值;在最後一層上只缺少右邊的若干結點。

如果—棵具有n個結點的深度為k的二叉樹，它的每—個結點都與深度為k的滿二叉樹中編號為1～n的結點——對應。

3.二叉樹的儲存結構

二叉樹通常採用鏈式儲存結構，儲存節點由資料域和指標域(左指標域和右指標域)組成。二叉樹的鏈式儲存結構也稱二叉連結串列，對滿二叉樹和完全二叉樹可按層次進行順序儲存。

4.二叉樹的遍歷

二叉樹的遍歷是指不重複地訪問二叉樹中所有節點，主要指非空二叉樹，對於空二叉樹則結束返回。二叉樹的遍歷包括前序遍歷、中序遍歷和後序遍歷。

(1) 前序遍歷。

前序遍歷是指在訪問根結點、遍歷左子樹與遍歷右子樹這三者中，首先訪問根結點，然後遍歷左子樹，最後遍歷右子樹;並且，在遍歷左右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹。前序遍歷描述為：若二叉樹為空，則執行空操作;否則①訪問根結點;②前序遍歷左子樹;③前序遍歷右子樹。

(2) 中序遍歷。

中序遍歷是指在訪問根結點、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然後訪問根結點，最後遍歷右子樹;並且，在遍歷左、右子樹時，仍然先遍歷左子樹，然後訪問根結點，最後遍歷右子樹。中序遍歷描述為：若二叉樹為空，則執行空操作;否則①中序遍歷左子樹;②訪問根結點;③中序遍歷右子樹。

(3) 後序遍歷。

後序遍歷是指在訪問根結點、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然後遍歷右子樹，最後訪問根結點，並且，在遍歷左、右子樹時，仍然先遍歷左子樹，然後遍歷右子樹，最後訪問根結點。後序遍歷描述為：若二叉樹為空，則執行空操作;否則①後序遍歷左子樹;②後序遍歷右子樹;③訪問根結點。

1.7 查詢技術

(1) 順序查詢：線上性表中查詢指定的元素。

(2) 最壞情況下，最後一個元素才是要找的元素，則需要與線性表中所有元素比較，比較次數為n。

(3) 二分查詢：二分查詢也稱折半查詢，它是一種高效率的查詢方法。但二分查詢有條件限制，它要求表必須用順序儲存結構，且表中元素必須按關鍵字有序(升序或降序均可)排列。對長度為n的有序線性表，在最壞情況下，二分查詢法只需比較log2n次。

1.8 排序技術

(1) 交換類排序法。

氣泡排序：通過對待排序序列從後向前或從前向後，依次比較相鄰元素的排序碼，若發現逆序則交換，使較大的元素逐漸從前部移向後部或較小的元素逐漸從後部移向前部，直到所有元素有序為止。在最壞情況下，對長度為n的線性表排序，氣泡排序需要比較的次數為n(n-1)/2。

快速排序：是迄今為止所有內排序演算法中速度最快的一種。它的基本思想是：任取待排序序列中的某個元素作為基準(一般取第一個元素)，通過一趟排序，將待排元素分為左右兩個子序列，左子序列元索的排序碼均小於或等於基準元素的排序碼，右子序列的'排序碼則大於基準元素的排序碼，然後分別對兩個子序列繼續進行排序，直至整個序列有序。最壞情況下，即每次劃分，只得到一個序列，時間效率為O(n2)。

(2) 插人類排序法。

簡單插入排序法：把n個待排序的元素看成為一個有序表和一個無序表，開始時有序表中只包含一個元素，無序表中包含有n-1個元素，排序過程中每次從無序表中取出第一個元素，把它的排序碼依次與有序表元素的排序碼進行比較，將它插入到有序表中的適當位置，使之成為新的有序表。在最壞情況下，即初始排序序列是逆序的情況下，比較次數為n(n-1)/2，移動次數為n(n-1)/2。

希爾排序法：先將整個待排元素序列分割成若干個子序列(由相隔某個“增量”的元素組成的)分別進行直接插入排序。待整個序列中的元素基本有序(增量足夠小)時，再對全體元素進行一次直接插入排序。

(3) 選擇類排序法。

簡單選擇排序法：掃描整個線性表。從中選出最小的元素。將它交換到表的最前面;然後對剩下的子表採用同樣的方法，直到子表空為止。最壞情況下需要比較n(n-1)/2次。

堆排序的方法：首先將一個無序序列建成堆;然後將堆頂元素(序列中的最大項)與堆中最後一個元素交換(最大項應該在序列的最後)。不考慮已經換到最後的那個元素，只考慮前n-1個元素構成的子序列，將該子序列調整為堆。反覆做步驟②，直到剩下的子序列空為止。在最壞情況下，堆排序法需要比較的次數為0(nlog2n)

第二章 程式設計基礎

2.1 程式設計方法與風格

(1)設計方法：指設計、編制、除錯程式的方法和過程，主要有結構化程式設計方法、軟體工程方法和麵向物件方法。

(2)設計風格：良好的設計風格要注重源程式文件化、資料說明方法、語句的結構和輸入輸出。

2.2 結構化程式設計

1.結構化程式設計的原則

結構化程式設計強調程式設計風格和程式結構的規範化，提倡清晰的結構。。

(1)自頂向下：即先考慮總體，後考慮細節;先考慮全域性目標，後考慮區域性目標。

(2)逐步求精：對複雜問題，應設計一些子目標做過渡，逐步細化。

(3)模組化：把程式要解決的總目標分解為分目標，再進一步分解為具體的小目標，把每個小目標稱為一個模組;

(4)限制使用GOT0語句。

2.結構化程式的基本結構與特點

(1)順序結構：自始至終嚴格按照程式中語句的先後順序逐條執行，是最基本、最普遍的結構形式。

(2)選擇結構：又稱為分支結構，包括簡單選擇和多分支選擇結構。

(3)重複結構：又稱為迴圈結構，根據給定的條件，判斷是否需要重複執行某一相同的或類似的程式段。

結構化程式設計中，應注意事項：

(1)使用程式設計語言中的順序、選擇、迴圈等有限的控制結構表示程式的控制邏輯。

(2)選用的控制結構只准許有一個人口和一個出口。

(3)程式語言組成容易識別的塊，每塊只有一個入口和一個出口。

(4)複雜結構應該用巢狀的基本控制結構進行組合巢狀來實現。

(5)語言中所沒有的控制結構，應該採用前後一致的方法來模擬。

(6)儘量避免GOT0語句的使用。

2.3 面向物件的程式設計

面向物件方法的本質是主張從客觀世界固有的事物出發來構造系統，強調建立的系統能對映問題域。

物件：用來表示客觀世界中任何實體，可以是任何有明確邊界和意義的東西。

類：具有共同屬性、共同方法的物件的集合。

例項：一個具體物件就是其對應分類的一個例項。

訊息：例項間傳遞的資訊，它統一了資料流和控制流。

繼承：使用已有的類定義作為基礎建立新類的定義技術。

多型性：指物件根據所接受的資訊而作出動作，同樣的資訊被不同的物件接收時有不同行動的現象。面向物件程式設計的優點：與人類習慣的思維方法一致、穩定性好、可重用性好、易於開發大型軟體產品、可維護性好。

第三章 軟體工程基礎

3.1 軟體工程基本概念

1.軟體的定義與特點

(1)定義：軟體是指與計算機系統的操作有關的計算機程式、規程、規則，以及可能有的檔案、文件和資料。

(2)特點。

是邏輯實體，有抽象性。

生產沒有明顯的製作過程。

執行使用期間不存在磨損、老化問題。

開發、執行對計算機系統有依賴性，受計算機系統的限制，導致了軟體移植問題。

複雜性較高，成本昂貴。

開發涉及諸多社會因素。

2.軟體的分類

軟體可分應用軟體、系統軟體和支撐軟體3類。

(1)應用軟體是特定應用領域內專用的軟體。

(2)系統軟體居於計算機系統中最靠近硬體的一層，是計算機管理自身資源，提高計算機使用效率併為計算機使用者提供各種服務的軟體。

(3)支撐軟體介於系統軟體和應用軟體之間，是支援其它軟體的開發與維護的軟體。

3.軟體危機與軟體工程

軟體危機指在計算機軟體的開發和維護中遇到的一系列嚴重問題。軟體工程是應用於計算機軟體的定義、開發和維護的一整套方法、工具、文件、實踐標準和工序，包括軟體開發技術和軟體工程管理。

4.軟體生命週期

軟體產品從提出、實現、使用維護到停止使用的過程稱為軟體生命週期。

在國家標準中，軟體生命週期劃分為8個階段①軟體定義期：包括問題定義、可行性研究和需求分析3個階段。②軟體開發期：包括概要設計、詳細設計、實現和測試4個階段。③執行維護期：即執行維護階段。

5.軟體工程的原則

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

3.2 結構化分析方法

需求分析的任務是發現需求、求精、建模和定義需求的過程，可概括為：需求獲取、需求分析、編寫需求規格說明書和需求評審。

1.常用的分析方法

結構化分析方法：其實質著眼於資料流，自頂向下，逐層分解，建立系統的處理流程。

面向物件分析方法。

2.結構化分析常用工具

結構化分析常用工具包括資料流圖、數字字典(核心方法)、判斷樹和判斷表。

(1)資料流圖：即DFD圖，以圖形的方式描繪資料在系統中流動和處理的過程，它只反映系統必須完成的邏輯功能。是一種功能模型。

符號名稱作用：

箭頭代表資料流，沿箭頭方向傳送資料的通道

圓或橢圓代表加工，輸入資料經加工變換產生輸出

雙槓代表儲存檔案，表示處理過程中存放各種資料檔案

方框代表源和潭，表示系統和環境的介面

(2)資料字典：結構化分析方法的核心。資料字典是對所有與系統相關的資料元素的一個有組織的列表。以及精確的、嚴格的定義，使得使用者和系統分析員對於輸入、輸出、儲存成分和中間計算結果有共同的理解。

(3)判定樹：使用判定樹進行描述時，應先從問題定義的文字描述中分清判定的條件和判定的結論，根據描述材料中的連線詞找出判定條件之問的從屬關係、並列關係、選擇關係，根據它們構造判定樹。

(4)判定表：與判定樹相似，當資料流圖中的加工要依賴於多個邏輯條件的取值，即完成該加工的一組動作是由於某一組條件取值的組合引發的，使用判定表比較適宜。

3.軟體需求規格說明書

軟體需求規格說明書是需求分析階段的最後成果，是軟體開發的重要文件之一。

(1)軟體需求規格說明書的作用：①便於使用者、開發人員進行理解和交流;②反映出使用者問題的結構，可以作為軟體開發工作的基礎和依據;③作為確認測試和驗收的依據。

(2)軟體需求規格說明書的內容：①概述;②資料描述;③功能描述;④效能描述;⑤參考文獻;⑥附錄。

(3)軟體需求規格說明書的特點：①正確性;②無歧義性;③完整性;④可驗證性;⑤一致性;⑥可理解性;⑦可修改性;⑧可追蹤性。

3.3 結構化設計方法

1.軟體設計的基本概念和方法

軟體沒計是一個把軟體需求轉換為軟體表示的過程。

(1)基本原理：抽象、模組化、資訊隱藏、模組獨立性(度量標準：耦合性和內聚性，高耦合、低內聚)。

(2)基本思想：將軟體設計成由相對獨立、單一功能的模組組成的結構。

2.概要設計

(1)4個任務：設計軟體系統結構、資料結構及資料庫設計、編寫概要設計文件、概要設計文件評審。

(2)面向資料流的設計方法：資料流圖的資訊分為交換流和事物流，結構形式有交換型和事務型。

3.詳細設計的工具

詳細設計的工具包括：

圖形工具：程式流程圖、N-S、PAD、HIPO。

表格工具：判定表。

語言工具：PDL(偽碼)。

3.4 軟體測試

1.目的

為了發現錯誤而執行程式的過程。

2.準則

所有測試應追溯到使用者需求。

嚴格執行測試計劃，排除測試的隨意性。

充分注意測試中的群集現象。

程式設計師應避免檢查自己的程式。

窮舉測試不可能。

妥善儲存設計計劃、測試用例、出錯統計和最終分析報告。

3.軟體測試技術和方法

軟體測試的方法按是否需要執行被測軟體的角度，可分為靜態測試和動態測試，按功能分為白盒測試和黑盒測試。

(1)白盒測試：根據程式的內部邏輯設計測試用例，主要方法有邏輯覆蓋測試、基本路徑測試等。

(2)黑盒測試：根據規格說明書的功能來設計測試用例，主要診斷方法有等價劃分法、邊界值分析法、錯誤推測法、因果圖法等，主要用於軟體確認測試。

4.軟體測試的實施

軟體測試是保證軟體質量的重要手段，軟體測試是一個過程，其測試流程是該過程規定的程式，目的是使軟體測試工作系統化。

軟體測試過程分4個步驟，即單元測試、整合測試、驗收測試和系統測試。

單元測試是對軟體設計的最小單位——模組(程式單元)進行正確性檢驗測試。

單元測試的目的是發現各模組內部可能存在的各種錯誤。

單元測試的依據是詳細的設計說明書和源程式。

單元測試的技術可以採用靜態分析和動態測試。

3.5 程式的除錯

(1)任務：診斷和改正程式中的錯誤。

(2)除錯方法：強行排錯法、回溯法和原因排除法。

第四章 資料庫設計基礎

4.1 資料庫系統的基本概念

(1) 資料(Data)：描述事物的符號記錄。

(2) 資料庫(DataBase)：長期儲存在計算機內的、有組織的、可共享的資料集合。

(3) 資料庫管理系統的概念

資料庫管理系統(DataBase Management System，DBMS)是資料庫的機構，它是一種系統軟體，負責資料庫中的資料組織、資料操作、資料維護、資料控制及保護和資料服務等。為完成以上6個功能，DBMS提供了相應的資料語言;資料定義語言(負責資料的模式定義與資料的物理存取構建);資料操縱語言(負責資料的操縱);資料控制語言(負責資料完整性、安全性的定義)。資料庫管理系統是資料庫系統的核心，它位於使用者和作業系統之間，從軟體分類的角度來說，屬於系統軟體。

(4) 資料庫技術發展經歷了3個階段。

人工管理階段→檔案系統階段→資料庫系統階段

(5) 資料庫系統的特點：整合性、高共享性、低冗餘性、資料獨立性、資料統一管理與控制等。

(6) 資料庫系統的內部機構體系：三級模式(概念模式、內模式、外模式)和二級對映(外模式/概念模式的對映、概念模式/內模式的對映)構成了資料庫系統內部的抽象結構體系。

4.2 資料模型

資料模型是資料特徵的抽象，從抽象層次上描述了系統的靜態特徵、動態行為和約束條件，描述的內容有資料結構、資料操作和資料約束。有3個層次：概念資料模型、邏輯資料模型和物理資料模型。

(1) E—R模型：提供了表示實體、屬性和聯絡的方法。實體間聯絡有“一對一”、“一對多”和“多對多”。

(2) E-R模型用E-R圖來表示。

(3) 層次模型：利用樹形結構表示實體及其之問聯絡。其中節點是實體，樹枝是聯絡，從上到下是一對多關係。

(4) 網狀模型：用網狀結構表示實體及其之間聯絡。是層次模型的擴充套件。網路模型以記錄型為節點，反映現實中較為複雜的事物聯絡。

(5) 關係模型：採用二維表(由表框架和表的元組組成)來表示，可進行資料查詢、增加、刪除及修改操作。關係模型允許定義“實體完整性”、“參照完整性”和“使用者定義的完整性”三種約束。

鍵(碼)：二維表中唯一能標識元組的最小屬性集。

候選鍵(候選碼)：二維表中可能有的多個鍵。

主鍵：被選取的一個使用的鍵。

4.3 關係代數

(1) 關係代數的基本運算：投影、選擇、笛卡爾積。

(2) 關係代數的擴充運算：交、連線與自然連線、除。

4.4 資料庫設計與管理

1.資料庫設計概述

基本思想：過程迭代和逐步求精。

方法：面向資料的方法和麵向過程的方法。

設計過程：需求分析→概念設計→邏輯設計→物理設計→編碼→測試→執行→進→步修改。

2.資料庫設計的需求分析

需求收集和分析是資料庫設計的第一階段，常用結構化分析方法(自頂向下、逐層分解)和麵向物件的方法，主要工作有繪製資料流程圖、資料分析、功能分析、確定功能處理模組和資料間關係。

資料字典：包括資料項、資料結構、資料流、資料儲存和處理過程，是對系統中資料的詳盡描述。

3.資料庫的設計

(1) 資料庫的概念設計：分析資料問內在的語義關聯，以建立資料的抽象模型。

(2) 資料庫的邏輯設計：從E-R圖向關係模型轉換，邏輯模式規範化，關係檢視設計可以根據使用者需求隨時建立。實體轉換為元組，屬性轉換為關係的屬性，聯絡轉換為關係。

(3) 資料庫的物理設計：是資料在物理裝置上的儲存結構與存取方法，目的是對資料庫內部物理結構作出調整並選擇合理的存取路徑，以提高速度和儲存空間。

4.資料庫管理

資料庫管理包括資料庫的建立、資料庫的調整、資料庫的重組、資料庫的安全性與完整性控制、資料庫故障恢復和資料庫的監控。