2023年二級(jí)C語言基礎(chǔ)知識(shí)要點(diǎn)

下面分為四個(gè)部分進(jìn)行組織。文中標(biāo)注了三個(gè)星號(hào)的，表達(dá)非常重要，基本每次考試都是必

考；標(biāo)注了兩個(gè)星號(hào)或一個(gè)星號(hào)的，表達(dá)也較重要，很容易考到。出現(xiàn)在【】括號(hào)中的內(nèi)容,

表達(dá)要很精確的背下來的，

第一部分算法與數(shù)據(jù)結(jié)構(gòu)（歷年比例41%））

1、算法

?問題解決方案的對(duì)的而完整的描述稱為【算法】。算法分析的目的是，分析算法的效率

以求改善。算法的基本特性是【可行性】、【擬定性】、【有窮性】和擁有足夠情報(bào)。

?算法的有窮性是指：算法程序的運(yùn)營時(shí)間是有限的。

?算法的復(fù)雜度是衡晟算法好壞的度量，分為【時(shí)間復(fù)雜度】和【空間復(fù)雜度】。

★★時(shí)間復(fù)雜度是指執(zhí)行算法所需要的【計(jì)算工作量】；算法的空間復(fù)雜度是指算法執(zhí)行

過程中所需的【存儲(chǔ)空間】。

?算法時(shí)間復(fù)雜度或空間復(fù)雜度中的一項(xiàng)的值，沒有辦法推出另一項(xiàng)的值。

2、數(shù)據(jù)結(jié)構(gòu)

?數(shù)據(jù)結(jié)構(gòu)分為【邏輯結(jié)構(gòu)】和【存儲(chǔ)結(jié)構(gòu)】。線性結(jié)構(gòu)和非線性結(jié)構(gòu)屬于邏輯結(jié)構(gòu)；順

序、鏈?zhǔn)?、索引屬于存?chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）。循環(huán)隊(duì)列屬于【存儲(chǔ)結(jié)構(gòu)】。

★數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)又稱為物理結(jié)構(gòu)，是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式。

??個(gè)邏輯結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，且各種存儲(chǔ)結(jié)構(gòu)影響數(shù)據(jù)解決的效率。程序執(zhí)行的

效率與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)密切相關(guān)。

?數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，帶鏈的隊(duì)列屬于【線性結(jié)構(gòu)】。

?線性表的存儲(chǔ)結(jié)構(gòu)重要分為順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)一定是

連續(xù)的，鏈?zhǔn)酱鎯?chǔ)的存儲(chǔ)空間不一定是連續(xù)的。

?有序線性表既可以采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

?隊(duì)列是一種特殊的線性表，循環(huán)隊(duì)列按照【先進(jìn)先出】原則組織數(shù)據(jù)。循環(huán)隊(duì)列是隊(duì)列

的【順序】存儲(chǔ)結(jié)構(gòu)。

?數(shù)據(jù)的獨(dú)立性分為【物理獨(dú)立】性和【邏輯獨(dú)立性】。當(dāng)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)改變時(shí)，其邏

輯結(jié)構(gòu)可以不變，因此，基于邏輯結(jié)構(gòu)的應(yīng)用程序可以不用修改，稱為【物理獨(dú)立性】。

3、棧和隊(duì)列

★★棧是一種特殊的線性表，是只能在一端進(jìn)行插入和刪除的線性表，特點(diǎn)是FILO(FirstIn

LastOut)o

★★棧是【先進(jìn)后出】的線性表；棧具有記憶作用；花棧的插入與刪除操作中，不需要改

變【棧底指針】。假定讓元素1、2、3、A、B依次入棧，則出棧的順序是：B、A、3、2、

lo

?棧與隊(duì)列都是線性結(jié)構(gòu)，樹是非線性結(jié)構(gòu)。支持子程序調(diào)用的數(shù)據(jù)結(jié)構(gòu)是【棧】。

?棧與隊(duì)列的共同點(diǎn)是，都只允許在【端點(diǎn)處】插入和刪除元素。

?棧只能順序存儲(chǔ)的描述是錯(cuò)誤的“?？梢杂小卷樞蚝玩?zhǔn)健績煞N存儲(chǔ)方式.

★★隊(duì)列是允許在一段插入，在另一端進(jìn)行刪除的線性表，其特點(diǎn)是【先進(jìn)先出】。

?循環(huán)隊(duì)列中元素的個(gè)數(shù)是由隊(duì)頭指針和隊(duì)尾指針共同決定。循環(huán)隊(duì)列的頭指針為front,

尾指針為rear,容量為maxSize,則循環(huán)隊(duì)列中元素的個(gè)數(shù)是【(rear-front+maxSize)mod

maxSize］八

4、線性鏈表

?線性鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。用鏈表表達(dá)線性表的優(yōu)點(diǎn)是【便于插入和刪除操作，

?線性鏈表的存儲(chǔ)空間不一定連續(xù)，且各元素的存儲(chǔ)順序是任意的。

5、樹與二叉樹

?在樹結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件(繼)的個(gè)數(shù)稱為該結(jié)點(diǎn)的度，所有結(jié)點(diǎn)中最大的

度稱為樹的度。二叉樹各結(jié)點(diǎn)的度只也許取值0、1、2,不也許是其它值。換言之，知道

了度為1結(jié)點(diǎn)數(shù)量的前提下，葉子結(jié)點(diǎn)或度為2的結(jié)點(diǎn)中知道其一，就可以求出總的結(jié)點(diǎn)

數(shù)。

★★★下面關(guān)于計(jì)算結(jié)點(diǎn)數(shù)量的幾個(gè)性質(zhì)，非常重要：

(1)對(duì)任意的二叉樹，葉子結(jié)點(diǎn)的數(shù)量，比度為2的結(jié)點(diǎn)數(shù)量多一個(gè)(換言之，已知葉子結(jié)點(diǎn)的數(shù)量，減去

1則是度為2的結(jié)點(diǎn)數(shù)量；已知度為2的結(jié)點(diǎn)數(shù)量，加上1就是葉子結(jié)點(diǎn)數(shù)量)

(2)完全二叉樹假如有N個(gè)結(jié)點(diǎn)，當(dāng)N為奇數(shù)的時(shí)候，葉子結(jié)點(diǎn)數(shù)為(N+l)/2,此時(shí)二叉樹只有度為。的葉

干結(jié)點(diǎn)及度為2的結(jié)點(diǎn)，沒有度為1的結(jié)點(diǎn)；當(dāng)N為偶數(shù)的時(shí)候.葉子結(jié)點(diǎn)的數(shù)量為N/20(注意條件，必

須是完全二叉樹，當(dāng)然涉及滿二叉樹)

(3)滿二叉樹第K層上的結(jié)點(diǎn)數(shù)量為2K-A深度為K的滿二叉樹，結(jié)點(diǎn)總數(shù)為2K-1。

上述的計(jì)算公式，關(guān)鍵要可以應(yīng)用，例如，深度為7的滿二叉樹，度為2的結(jié)點(diǎn)數(shù)量是多

少？既然是滿二叉樹，葉子結(jié)點(diǎn)的數(shù)量就是第7層的結(jié)點(diǎn)數(shù)量，也就是26,可以算出葉子

結(jié)點(diǎn)為64,因此度為2的結(jié)點(diǎn)數(shù)是63(葉子結(jié)點(diǎn)數(shù)減去工)。

★★★二叉樹的前序遍歷、中序遍歷、后續(xù)遍歷：前中后三個(gè)詞是相對(duì)于根來講的，前序

是【根--＞左??＞右】，中序是【左-?＞根--＞右】，后續(xù)是【左右根］。具體操作

為：

先序遍歷(DLR):訪問根結(jié)點(diǎn)，按先序遍歷左子樹，按無序遍歷右子樹。

1、軟件工程基本概念

★★軟件是涉及【程序】、【數(shù)據(jù)】及【相關(guān)文檔】的完整集合，軟件是一種邏輯產(chǎn)品。

軟件工程三要素涉及【方法、工具和過程】，其中【過程】支持軟件開發(fā)的各個(gè)環(huán)節(jié)的控制

和管理。

?軟件工程的核心思想：把軟件產(chǎn)品當(dāng)作是一個(gè)工程產(chǎn)品來解決，強(qiáng)調(diào)在軟件開發(fā)過程中

應(yīng)川【工程化】原則。

?從工程管理角度，軟件設(shè)計(jì)一般分為兩步完畢，它們是【概要設(shè)計(jì)】和【具體設(shè)計(jì)】。

★★軟件生命周期可分為多個(gè)階段，一般分為【定義】階段、【開發(fā)】階段和【維護(hù)】階

段，編碼和測(cè)試屬于【開發(fā)階段】。

?需求分析階段產(chǎn)生的重要文檔是【軟件需求規(guī)格說明書】。軟件需求的規(guī)格說明書應(yīng)當(dāng)

有完整性、無歧義性、對(duì)的性、可驗(yàn)證性、可修改性等特性，其中最重要的是【對(duì)的性】。

2、結(jié)構(gòu)化分析與設(shè)計(jì)

★★需求分析的分發(fā)有：【結(jié)構(gòu)化】需求分析方法，【面向?qū)ο蟆康姆治龇椒?。DFD是【需

求分析階段】可以使用的工具之-o

?結(jié)構(gòu)化分析的常用工具：數(shù)據(jù)流圖（DFD）；數(shù)據(jù)字典；鑒定樹；鑒定表。

?在結(jié)構(gòu)化分析使用數(shù)據(jù)流圖（DFD）時(shí)候,運(yùn)用【數(shù)據(jù)字曲】對(duì)其中的圖形元素進(jìn)行確切

的解釋?！緮?shù)據(jù)字典】是結(jié)構(gòu)化分析的核心。

?典型的數(shù)據(jù)流類型有兩種，【互換性】和【事務(wù)型】。

?常見的過程設(shè)計(jì)工具有：圖形工具（程序流程圖、N-S,PAD,HIPO）、表格工具（鑒定表）、

語言工具（PDL偽碼）。

?內(nèi)聚性是模塊內(nèi)部的聯(lián)系，耦合性模塊之間的互相聯(lián)系的緊密限度。

★★★追求目的是：模塊的內(nèi)聚限度要高，模塊間的耦合限度要盡量弱。即高內(nèi)聚低耦合。

★★程序流程圖中帶有箭頭的線段表達(dá)的是【控制流】?！酒叫兴倪呅巍看磔斎胼敵觯?/p>

【矩形】代表解決，菱形代表【判斷】（注意，數(shù)據(jù)流圖中的箭頭，代表【數(shù)據(jù)流】）。

?符合結(jié)構(gòu)化原則的三種基本控制結(jié)構(gòu)是：【順序結(jié)構(gòu)】，【選擇結(jié)構(gòu)】和【循環(huán)結(jié)構(gòu)】。

3、軟件測(cè)試與維護(hù)

★★軟件測(cè)試的目的是盡也許多的發(fā)現(xiàn)程序中的錯(cuò)誤，但是不涉及改正錯(cuò)誤“（軟件調(diào)試的

目的才是改正錯(cuò)誤）

★★軟件測(cè)試分為靜態(tài)測(cè)試和動(dòng)態(tài)測(cè)試，其中【靜態(tài)測(cè)試】是指不執(zhí)行程序，只對(duì)程序文

本進(jìn)行檢查。軟件的動(dòng)態(tài)則試重要涉及【黑盒測(cè)試】和【白盒測(cè)試】。

?黑盒測(cè)試的方法有等價(jià)類劃分法，邊界值分析法，錯(cuò)誤推測(cè)法，因果佟I；白盒測(cè)試重要

方法有邏輯覆蓋、基本途徑測(cè)試。（考試時(shí)給出一種方法的名字，你要知道屬于白盒還是黑

盒）

【白盒測(cè)試】的原則之?是保證所測(cè)模塊的每?個(gè)獨(dú)立途徑至少要執(zhí)行?次。白盒測(cè)試將程

序看做是【途徑的集合】，

?軟件測(cè)試一般按照四個(gè)環(huán)節(jié)進(jìn)行：?jiǎn)卧獪y(cè)試，集成測(cè)試，驗(yàn)收測(cè)試和系統(tǒng)測(cè)試v集成測(cè)

試應(yīng)當(dāng)在【單元測(cè)試】之后進(jìn)行。

?在模塊測(cè)試中，需要為每個(gè)被測(cè)試的模塊設(shè)計(jì)【驅(qū)動(dòng)模塊】和【承接模塊】。其中，驅(qū)

動(dòng)模塊的作用是將測(cè)試的數(shù)據(jù)傳給被測(cè)試的模塊，并顯示結(jié)果。

?【測(cè)試用例】是為某個(gè)目的而編制的一組測(cè)試輸入、執(zhí)行條件及預(yù)期結(jié)果。測(cè)試用例涉

及輸入值集和【輸出值集】。

★★診斷和改正程序中的錯(cuò)誤稱為【程序調(diào)試】（或軟件調(diào)試），通常也稱為Debug。軟件

調(diào)試可分為【靜態(tài)調(diào)試】和【動(dòng)態(tài)調(diào)試】。

?在軟件已經(jīng)交付使用之后，為了改正錯(cuò)誤或滿足新的需要而修改軟件的過程稱為【軟件

維護(hù)】。注意軟件維護(hù)不屬于軟件生命周期【開發(fā)階段】的任務(wù)。

第三部分?jǐn)?shù)據(jù)庫設(shè)計(jì)基礎(chǔ)（歷年比例24%）

1、數(shù)據(jù)庫系統(tǒng)基本概念

?數(shù)據(jù)庫設(shè)計(jì)的主線目的是要解決【數(shù)據(jù)共享問題】。在數(shù)據(jù)庫管理技術(shù)發(fā)展的三個(gè)階段

中，數(shù)據(jù)共享最佳的是【數(shù)據(jù)庫系統(tǒng)階段】。數(shù)據(jù)獨(dú)立性最高的階段是【數(shù)據(jù)庫系統(tǒng)階段】。

?數(shù)據(jù)庫系統(tǒng)與文獻(xiàn)系統(tǒng)的區(qū)別是前者具有【特定的數(shù)據(jù)模型】。

?數(shù)據(jù)庫系統(tǒng)常見的數(shù)據(jù)模型向?qū)哟文Ｐ?，網(wǎng)絡(luò)模型和【關(guān)系模型】。

★★數(shù)據(jù)庫系統(tǒng)的核心是【數(shù)據(jù)庫管理系統(tǒng)】。

?DBS涉及DB和DBMS.完整講，數(shù)據(jù)庫系統(tǒng)DBS由數(shù)據(jù)庫DB、數(shù)據(jù)庫管理系統(tǒng)DBMS、

數(shù)據(jù)庫管理員DBA、硬件平臺(tái)和軟件平臺(tái)組成。

?數(shù)據(jù)庫應(yīng)用系統(tǒng)的核心是【數(shù)據(jù)庫維護(hù)】。

?數(shù)據(jù)庫系統(tǒng)的三級(jí)模式結(jié)構(gòu)：內(nèi)模式處在最底層，它反映了數(shù)據(jù)在計(jì)算機(jī)物理結(jié)構(gòu)中的

實(shí)際存儲(chǔ)形式；概念模式處在中層，它放映了設(shè)計(jì)者的數(shù)據(jù)全局邏輯規(guī)定，與軟硬件環(huán)境無

關(guān);

外模式處在最外層，它反映了用戶對(duì)數(shù)據(jù)的規(guī)定。

?在數(shù)據(jù)庫系統(tǒng)中，用戶所見的數(shù)據(jù)模式為【外模式】。

?數(shù)據(jù)庫設(shè)計(jì)的四個(gè)階段是：需求分析、概念設(shè)計(jì)、【邏輯設(shè)計(jì)】和【物理設(shè)計(jì)】。將E-R

圖轉(zhuǎn)換成關(guān)系數(shù)據(jù)模型屬于【邏輯設(shè)計(jì)】階段。

?數(shù)據(jù)庫管理系統(tǒng)提供的數(shù)據(jù)語言：數(shù)據(jù)定義語言DDL,數(shù)據(jù)操縱語言DML,數(shù)據(jù)控制語

言DCL。SQL的全稱是StructuredQueryLanguage,中文意思是【結(jié)構(gòu)化查詢語言】。

2、數(shù)據(jù)模型

★★★實(shí)體之間的聯(lián)系用樹形結(jié)構(gòu)來表達(dá)的模型是【層次模型】。采用二維表來表達(dá)的是

【關(guān)系模型】。在關(guān)系數(shù)據(jù)庫中，把數(shù)據(jù)表達(dá)成二維表，每一個(gè)二維表稱為【關(guān)系】。

?在關(guān)系數(shù)據(jù)庫中，用來表達(dá)實(shí)體之間聯(lián)系的是【關(guān)系】。

?將E-R圖轉(zhuǎn)化為關(guān)系模式時(shí)，實(shí)體和聯(lián)系都可以表達(dá)為【關(guān)系】。

★★★擬定兩個(gè)實(shí)體之間是一對(duì)一、一對(duì)多、還是多對(duì)多的方法是：選擇實(shí)體A,看是否

有多個(gè)實(shí)體B與之相應(yīng)；選擇實(shí)體B.看是否有多個(gè)實(shí)體A與之相應(yīng)。例如在''學(xué)生學(xué)習(xí)課

程〃中的兩個(gè)實(shí)體，學(xué)生與課程，一個(gè)學(xué)生可以學(xué)習(xí)多門課程，一門課程可以被多個(gè)學(xué)生學(xué)

習(xí)，所以兩者是一種多對(duì)多的關(guān)系。

★★在E-R圖中，用來表達(dá)實(shí)體的圖形是【矩形】.用來表達(dá)【屬性】的圖形是橢圓.用

菱形來表達(dá)聯(lián)系。

★★一個(gè)關(guān)系表的行稱為【元組】（或記錄），列稱為【屬性】（或字段）。

?在二維表中，元組的【分量】不能再分為更小的數(shù)據(jù)線。

?為了建立一個(gè)關(guān)系，一方面要構(gòu)造數(shù)據(jù)的【邏輯關(guān)系】。

3、關(guān)系代數(shù)

?在交、差、投影中，不改變關(guān)系表中的屬性個(gè)數(shù)但是能減少元組個(gè)數(shù)的是【交】運(yùn)算。

★★★關(guān)系運(yùn)算的規(guī)則(下面介紹的7種運(yùn)算，考試的時(shí)候一般會(huì)考察一種，都要背)

(1)并運(yùn)算RUS：并運(yùn)算是兩個(gè)表行上的合并，反復(fù)的行只出現(xiàn)一次。

(2)交運(yùn)算RGS：交運(yùn)算是選出兩個(gè)表中的公共行。

(3)差運(yùn)算R-S：差運(yùn)算是從表R中，刪除R與S中都出現(xiàn)過的行。

(4)選擇運(yùn)算：選出二維表【部分的行】稱為選擇運(yùn)算。

(5)投影運(yùn)算：選出二維表【部分的列】稱為投影運(yùn)算。

(6)連接運(yùn)