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

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

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

（2）4個基本特征：可行性，確定性，有窮性，擁有足夠的情報

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

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

【真題舉例】

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

A）所謂算法就是計算***

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

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

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

【真題解析】

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

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

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

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

【真題舉例】

下列敘述中正確的是（）

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

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

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

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

【真題解析】

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

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

【考點(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)系。存儲結(jié)構(gòu)為數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)存儲空間中的存放形式，有順序存儲，鏈?zhǔn)酱鎯ΑＫ饕鎯蜕⒘写鎯?種方式。

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

（1）線性結(jié)構(gòu)：有且只有一個根節(jié)點(diǎn)，且每個節(jié)點(diǎn)最多有一個直接前驅(qū)和一個直接后繼的非空數(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)隊列

C.循環(huán)鏈表

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

【真題解析】

首先來解答大家對于B,D,R三個英文字母是什么意思的疑問：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連起來，最終可以形成一個開環(huán)f→a→c→e→d→b，顯然這是一個線性結(jié)構(gòu)，所以選A。

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

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

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

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

【真題舉例】

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

A.3

B.1

C.2

D.52

【真題解析】

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

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

<1>二叉樹的定義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

【真題舉例】

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

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

B.該二叉樹是滿二叉樹

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

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

【真題解析】

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

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

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