時(shí)間已經(jīng)到了3月中旬，還有十天左右全國(guó)計(jì)算機(jī)等級(jí)考試（NCRE）就將拉開序幕。為了幫助各位考生在國(guó)二的考試中取得好的成績(jī)，我將持續(xù)為大家分享一些國(guó)二C語(yǔ)言（筆者考的就是C語(yǔ)言，其他的太多，時(shí)間有限，所以后期推送主要還是針對(duì)二級(jí)C語(yǔ)言）的考點(diǎn)總結(jié)已經(jīng)真題分析，希望能對(duì)各位考生有所幫助。

【考點(diǎn)1】算法的基本概念

（1）概念：算法是指一系列結(jié)局問題的清晰指令。

（2）4個(gè)基本特征：可行性，確定性，有窮性，擁有足夠的情報(bào)

（3）2個(gè)基本要素：對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作；算法的控制結(jié)構(gòu)（運(yùn)算和操作時(shí)間的順序）。

（4）設(shè)計(jì)的基本***：列舉法，歸納法，遞歸法，減半遞推技術(shù)和回溯法。

【真題舉例】

1.下列敘述中正確的是（）

A）所謂算法就是計(jì)算***

B）程序可以作為算法的一種描述***

C）算法設(shè)計(jì)只需要考慮得到計(jì)算結(jié)果

D）算法設(shè)計(jì)可以忽略算法的運(yùn)算時(shí)間

【真題解析】

由上面我們給大家講解的算法的概念可以知道，算法是一系列的解決問題的指令，并不完全等同于數(shù)學(xué)上的計(jì)算***，所以A錯(cuò)，B正確。算法的特征有窮性告訴我們算法要具有操作步驟有限，能在有限時(shí)間內(nèi)完成的特點(diǎn)。如果一個(gè)算法執(zhí)行耗費(fèi)的時(shí)間太長(zhǎng)，就算能得到結(jié)果，有什么意義呢？所以C錯(cuò)，D錯(cuò)。這些都是要綜合考慮的。一般而言看見C選項(xiàng)這種”只“限定的可以優(yōu)先考慮排除。

【考點(diǎn)2】算法的復(fù)雜度

（1）時(shí)間復(fù)雜度：執(zhí)行算法所需要的計(jì)算工作量

（2）空間復(fù)雜度：執(zhí)行算法所需要的內(nèi)存空間

【真題舉例】

下列敘述中正確的是（）

A.算法的時(shí)間復(fù)雜度與計(jì)算機(jī)的運(yùn)行速度有關(guān)

B.算法的時(shí)間復(fù)雜度與運(yùn)行算法時(shí)特定的輸入有關(guān)系

C.算法的時(shí)間復(fù)雜度與算法程序中的語(yǔ)句條數(shù)成正比

D.算法的時(shí)間復(fù)雜度與算法程序編制者的水平有關(guān)

【真題解析】

不知道大家還記得高中時(shí)候我們學(xué)生物，學(xué)化學(xué)，老師一直在強(qiáng)調(diào)的”控制變量法

“嗎，在這里我們一定要有這個(gè)想法。我們?cè)u(píng)價(jià)一個(gè)算法當(dāng)然是評(píng)價(jià)算法本身，一個(gè)好的算法給一臺(tái)幾十年前幾乎報(bào)廢了的電腦來運(yùn)行，也會(huì)很慢，電腦配置，電腦運(yùn)行速率我們要控制變量，算法的評(píng)價(jià)不應(yīng)該和電腦，編制者等等有關(guān)系，A,D排除。C選項(xiàng)很容易知道錯(cuò)誤，語(yǔ)句的數(shù)量怎么能反映他的時(shí)間復(fù)雜度呢。就好比一個(gè)矮個(gè)子和一個(gè)高個(gè)子賽跑，你就怎么能保證高個(gè)子腿長(zhǎng)就一定跑的快呢？

【考點(diǎn)3】數(shù)據(jù)結(jié)構(gòu)的基本概念

數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的***，即數(shù)據(jù)的組織形式。其中邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系。存儲(chǔ)結(jié)構(gòu)為數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式，有順序存儲(chǔ)，鏈?zhǔn)酱鎯?chǔ)。索引存儲(chǔ)和散列存儲(chǔ)4種方式。

數(shù)據(jù)結(jié)構(gòu)按各元素之間前后件關(guān)系的復(fù)雜度可劃分為以下兩種：

（1）線性結(jié)構(gòu)：有且只有一個(gè)根節(jié)點(diǎn)，且每個(gè)節(jié)點(diǎn)最多有一個(gè)直接前驅(qū)和一個(gè)直接后繼的非空數(shù)據(jù)結(jié)構(gòu)。

（2）非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)。

【真題舉例】

設(shè)數(shù)據(jù)結(jié)構(gòu)B=(D,R),其中D={a,b,c,d,e,f}，R={（f,a）,(d,b),(e,d),(c,e),(a,c)}，該數(shù)據(jù)結(jié)構(gòu)為（）

A.線性結(jié)構(gòu)

b.循環(huán)隊(duì)列

C.循環(huán)鏈表

D.非線性結(jié)構(gòu)

【真題解析】

首先來解答大家對(duì)于B,D,R三個(gè)英文字母是什么意思的疑問：D是數(shù)據(jù)元素的***，R反映了D中各元素之間的前后件關(guān)系，B表示數(shù)據(jù)結(jié)構(gòu)。B=（D,R）可以理解為數(shù)據(jù)結(jié)構(gòu)=（數(shù)據(jù)元素的***+各數(shù)據(jù)元素之間的前后件關(guān)系），明白了這一點(diǎn)，接下來我們來看一張示意圖。

（f,a）表示f是a的前件，a是f的后件，我們用箭頭連起來：f→a；（a,c）表示a是c的前件，我們把a(bǔ)→c連起來，最終可以形成一個(gè)開環(huán)f→a→c→e→d→b，顯然這是一個(gè)線性結(jié)構(gòu)，所以選A。

【考點(diǎn)4】循環(huán)隊(duì)列及其運(yùn)算

所謂的循環(huán)隊(duì)列就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞道第一個(gè)位置，形成邏輯上的環(huán)狀空間。

入隊(duì)運(yùn)算是指在循環(huán)隊(duì)列的對(duì)胃加入一個(gè)新元素。當(dāng)循環(huán)隊(duì)列非空（s=1）且隊(duì)尾指針等于隊(duì)頭指針時(shí)，說明循環(huán)隊(duì)列已滿，不能進(jìn)行入隊(duì)運(yùn)算，這種情況稱為“上溢”

退隊(duì)運(yùn)算是指在循環(huán)隊(duì)列的隊(duì)頭位置退出一個(gè)元素并賦給指定的變量。首先將隊(duì)頭指針進(jìn)一，然后將排頭指針指向的元素賦給指定的變量。當(dāng)循環(huán)隊(duì)列為空（s=0）時(shí)，不能進(jìn)行退隊(duì)運(yùn)算，這種情況稱為“下溢”。

【真題舉例】

設(shè)循環(huán)隊(duì)列的存儲(chǔ)空間為Q(1:50），初始狀態(tài)為front=rear=50.現(xiàn)經(jīng)過一系列入隊(duì)與退隊(duì)操作后，front=rear=1，此后又正常地插入了兩個(gè)元素。最后該隊(duì)列中的元素個(gè)數(shù)為（）

A.3

B.1

C.2

D.52

【真題解析】

從他的存儲(chǔ)空間（1:50）可以知道在初始狀態(tài)，即front=rear=50這一條件意味著循環(huán)隊(duì)列為空，按照題目說的進(jìn)行一系列操作之后末態(tài)是front=rear=1，搞了半天最后還是個(gè)空的隊(duì)列，最后呢，題目說又正常的加入了兩個(gè)元素，那么答案不就出來了，空→一系列操作→空→加兩個(gè)元素，那隊(duì)列里不就只有兩個(gè)元素了嗎，所以選C。

【考點(diǎn)5】二叉樹的定義及基本性質(zhì)

<1>二叉樹的定義

二叉樹是一種非線性結(jié)構(gòu)，是有限的節(jié)點(diǎn)***，該***為空或由一個(gè)根節(jié)點(diǎn)及兩顆互不相交的左右二叉子樹組成。可分為滿二叉樹和完全二叉樹，其中滿二叉樹一定是完全二叉樹，但完全二叉樹不一定是滿二叉樹。

二叉樹具有如下兩個(gè)特點(diǎn)：

1.二叉樹可為空，空的二叉樹無節(jié)點(diǎn)，非空二叉樹有且只有一個(gè)根節(jié)點(diǎn)

2.每個(gè)節(jié)點(diǎn)最多有兩顆子樹，稱為左子樹和右子樹。

<2>二叉樹的基本性質(zhì)

性質(zhì)1：在二叉樹的第k層上至多有2的k+1次方個(gè)節(jié)點(diǎn)（k≥1）

性質(zhì)2：深度為m的二叉樹至多有2的m次方減1個(gè)節(jié)點(diǎn)。

性質(zhì)3：對(duì)任何一顆二叉樹，度為0的節(jié)點(diǎn)總是比度為2的節(jié)點(diǎn)多一個(gè)

性質(zhì)4：具有n個(gè)節(jié)點(diǎn)的二叉樹的深度至少為[log2n]+1，其中l(wèi)og2n表示log2n的整數(shù)部分。（注log2n是以2為底，n的對(duì)數(shù)，由于手機(jī)上暫時(shí)無法打出數(shù)學(xué)格式，所以注以文字說明，望各位讀者諒解）

<3>滿二叉樹與完全二叉樹

（1）滿二叉樹：滿二叉樹是這樣的一種二叉樹：除最后一層外，每一層上的所有節(jié)點(diǎn)都有兩個(gè)字節(jié)點(diǎn)，滿二叉樹在其第i層上有2的i-1次方個(gè)節(jié)點(diǎn)

（2）完全二叉樹：完全二叉樹是指這樣的二叉樹：除最后一層外，每一層上的節(jié)點(diǎn)數(shù)均達(dá)到最大值；在最后一層上只缺少右邊的若干節(jié)點(diǎn)。

<4>二叉樹的存儲(chǔ)結(jié)構(gòu)

二叉樹通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，存儲(chǔ)節(jié)點(diǎn)由數(shù)據(jù)域和指針域（左指針域和右指針域）組成，二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也稱二叉樹鏈表，對(duì)滿二叉樹和完全二叉樹可按層次進(jìn)行順序存儲(chǔ)。

【真題舉例】

深度為7的二叉樹共有127個(gè)結(jié)點(diǎn)，則下列說法中錯(cuò)誤的是（）

A.該二叉樹有一個(gè)度為1的結(jié)點(diǎn)

B.該二叉樹是滿二叉樹

C.該二叉樹是完全二叉樹

D.該二叉樹有64個(gè)葉子結(jié)點(diǎn)

【真題解析】

在樹的結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件個(gè)數(shù)稱為該結(jié)點(diǎn)的度，所有結(jié)點(diǎn)中最大的度稱為樹的度。在上面我們已經(jīng)復(fù)習(xí)了滿二叉樹和完全二叉樹的概念，完全二叉樹是除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值，在最后一層上只缺少右邊的若干結(jié)點(diǎn)。滿二叉樹指除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)的二叉樹。

再來讀題，深度為7的二叉樹，假設(shè)前6層一共有2的6次方-1=64-1=63個(gè)結(jié)點(diǎn)，那么第7層就有127-63=64個(gè)葉子結(jié)點(diǎn)，即第7層結(jié)點(diǎn)數(shù)達(dá)到了最大值。我們?cè)倏纯瓷厦娴亩x，好像既是滿二叉樹（2的6次方計(jì)算時(shí)我們認(rèn)為除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)），又是完全二叉樹（最后一層缺少若干結(jié)點(diǎn)），那么B,C,D都對(duì)，所以錯(cuò)的就選A了。樹的度指的是一個(gè)節(jié)點(diǎn)所擁有的后件個(gè)數(shù)稱為該節(jié)點(diǎn)的度，所有節(jié)點(diǎn)最大的度稱為樹的度，顯然這個(gè)樹沒有度為1的節(jié)點(diǎn)。

由于篇幅原因，本期國(guó)二計(jì)算機(jī)公共基礎(chǔ)考點(diǎn)總結(jié)（含真題解析）就先到這里，剩下的線性鏈表，查找技術(shù)，排序技術(shù)以及堆棧相對(duì)簡(jiǎn)單，大家可以自行查閱相關(guān)資料，對(duì)照真題題庫(kù)，多多練習(xí)，這樣，公共基礎(chǔ)知識(shí)相關(guān)的10道選擇題就能很輕松的拿下了。后面還會(huì)繼續(xù)推送國(guó)二C語(yǔ)言的考點(diǎn)總結(jié)，想看的話可以加一波關(guān)注，在這里也預(yù)祝各位讀者國(guó)二考試稱為過兒，看了文章的各個(gè)都能過。