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

【考點1】算法的基本概念

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

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

（3）2個基本要素：對數據對象的運算和操作；算法的控制結構（運算和操作時間的順序）。

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

【真題舉例】

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

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

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

C）算法設計只需要考慮得到計算結果

D）算法設計可以忽略算法的運算時間

【真題解析】

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

【考點2】算法的復雜度

（1）時間復雜度：執行算法所需要的計算工作量

（2）空間復雜度：執行算法所需要的內存空間

【真題舉例】

下列敘述中正確的是（）

A.算法的時間復雜度與計算機的運行速度有關

B.算法的時間復雜度與運行算法時特定的輸入有關系

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

D.算法的時間復雜度與算法程序編制者的水平有關

【真題解析】

不知道大家還記得高中時候我們學生物，學化學，老師一直在強調的”控制變量法

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

【考點3】數據結構的基本概念

數據結構是指相互有關聯的數據元素的***，即數據的組織形式。其中邏輯結構反映數據元素之間的邏輯關系。存儲結構為數據的邏輯結構在計算機存儲空間中的存放形式，有順序存儲，鏈式存儲。索引存儲和散列存儲4種方式。

數據結構按各元素之間前后件關系的復雜度可劃分為以下兩種：

（1）線性結構：有且只有一個根節點，且每個節點最多有一個直接前驅和一個直接后繼的非空數據結構。

（2）非線性結構：不滿足線性結構的數據結構。

【真題舉例】

設數據結構B=(D,R),其中D={a,b,c,d,e,f}，R={（f,a）,(d,b),(e,d),(c,e),(a,c)}，該數據結構為（）

A.線性結構

b.循環隊列

C.循環鏈表

D.非線性結構

【真題解析】

首先來解答大家對于B,D,R三個英文字母是什么意思的疑問：D是數據元素的***，R反映了D中各元素之間的前后件關系，B表示數據結構。B=（D,R）可以理解為數據結構=（數據元素的***+各數據元素之間的前后件關系），明白了這一點，接下來我們來看一張示意圖。

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

【考點4】循環隊列及其運算

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

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

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

【真題舉例】

設循環隊列的存儲空間為Q(1:50），初始狀態為front=rear=50.現經過一系列入隊與退隊操作后，front=rear=1，此后又正常地插入了兩個元素。最后該隊列中的元素個數為（）

A.3

B.1

C.2

D.52

【真題解析】

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

【考點5】二叉樹的定義及基本性質

<1>二叉樹的定義

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

二叉樹具有如下兩個特點：

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

2.每個節點最多有兩顆子樹，稱為左子樹和右子樹。

<2>二叉樹的基本性質

性質1：在二叉樹的第k層上至多有2的k+1次方個節點（k≥1）

性質2：深度為m的二叉樹至多有2的m次方減1個節點。

性質3：對任何一顆二叉樹，度為0的節點總是比度為2的節點多一個

性質4：具有n個節點的二叉樹的深度至少為[log2n]+1，其中log2n表示log2n的整數部分。（注log2n是以2為底，n的對數，由于手機上暫時無法打出數學格式，所以注以文字說明，望各位讀者諒解）

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

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

（2）完全二叉樹：完全二叉樹是指這樣的二叉樹：除最后一層外，每一層上的節點數均達到最大值；在最后一層上只缺少右邊的若干節點。

<4>二叉樹的存儲結構

二叉樹通常采用鏈式存儲結構，存儲節點由數據域和指針域（左指針域和右指針域）組成，二叉樹的鏈式存儲結構也稱二叉樹鏈表，對滿二叉樹和完全二叉樹可按層次進行順序存儲。

【真題舉例】

深度為7的二叉樹共有127個結點，則下列說法中錯誤的是（）

A.該二叉樹有一個度為1的結點

B.該二叉樹是滿二叉樹

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

D.該二叉樹有64個葉子結點

【真題解析】

在樹的結構中，一個結點所擁有的后件個數稱為該結點的度，所有結點中最大的度稱為樹的度。在上面我們已經復習了滿二叉樹和完全二叉樹的概念，完全二叉樹是除最后一層外，每一層上的結點數均達到最大值，在最后一層上只缺少右邊的若干結點。滿二叉樹指除最后一層外，每一層上的所有結點都有兩個子結點的二叉樹。

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

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