全國計算機二級c語言(完整復習資料)

1、1計算機二級計算機二級C復習資料復習資料公共基礎知識資料公共基礎知識資料第一章第一章數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法【考點考點1】算法的基本概念算法的基本概念算法：是指一組有窮的指令集，是解題方案的準確而完整的描述。算法不等于程序，也不等于計算方法。算法的基本特征：確定性確定性，算法中每一步驟都必須有明確定義，不允許有多義性；有窮性有窮性，算法必須能在有限的時間內(nèi)做完，即能在執(zhí)行有限個步驟后終止；可行性可行性，算法原則上能夠精確地執(zhí)行；擁有

2、足夠的情報。算法的組成要素：一個算法由數(shù)據(jù)對象的運算和操作以及其控制結構這兩部分組成。算法的基本運算和操作：算術運算，邏輯運算，關系運算，數(shù)據(jù)傳輸。算法的基本控制結構：順序，選擇，循環(huán)。算法基本設計方法：列舉法、歸納法、遞推、遞歸、減半遞推技術?！究键c考點2】算法的復雜度算法的復雜度算法效率的度量——算法的復雜度：時間復雜度和空間復雜度。算法時間復雜度：指執(zhí)行算法所需要的計算工作量指執(zhí)行算法所需要的計算工作量。通常，一個算法所用的時間包

3、括編譯編譯時間和運行時間。時間和運行時間。算法空間復雜度：指執(zhí)行這個算法所需要的內(nèi)存空間指執(zhí)行這個算法所需要的內(nèi)存空間。包括算法程序所占的空間，輸入的初始數(shù)據(jù)所占的空間，算法執(zhí)行過程中所需的額外空間。初始數(shù)據(jù)所占的空間，算法執(zhí)行過程中所需的額外空間?？臻g復雜度和時間復雜度并不相關。并不相關?！究键c考點3】數(shù)據(jù)結構的基本概念數(shù)據(jù)結構的基本概念數(shù)據(jù)：數(shù)據(jù)是客觀事物的符號表示，是能輸入到計算機中并被計算程序識別和處理的符號的總稱，如文檔，聲音

4、，視頻等。數(shù)據(jù)元素：數(shù)據(jù)元素是數(shù)據(jù)的基本單位。數(shù)據(jù)對象：數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合。數(shù)據(jù)結構：是指由某一數(shù)據(jù)對象中所有數(shù)據(jù)成員之間的關系組成的集合。【考點考點4】邏輯結構和存儲結構邏輯結構和存儲結構數(shù)據(jù)結構可分為數(shù)據(jù)的邏輯結構和存儲結構。數(shù)據(jù)的邏輯結構是對數(shù)據(jù)元素之間的邏輯關系的描述，與數(shù)據(jù)的存儲無關，是面向問題的，是獨立于計算機的。它包括數(shù)據(jù)對象和數(shù)據(jù)對象之間的關系。數(shù)據(jù)的存儲結構也稱為數(shù)據(jù)的物理結構物理結構，是數(shù)據(jù)在計算機中

5、的存放的方式，是面向計算機的，它包括數(shù)據(jù)元素的存儲方式和關系的存儲方式存儲方式和關系的存儲方式。數(shù)據(jù)結構和邏輯結構的關系：一種數(shù)據(jù)的邏輯結構可以表示成多種存儲結構即數(shù)據(jù)的邏輯結構和存儲結構不一定一一對應。常見的存儲結構有：順序，鏈接，索引等。采用不同的存儲結構其數(shù)據(jù)處理的效率是不同的?！究键c考點5】線性結構和非線性結構線性結構和非線性結構3線性鏈表的基本運算：查找、插入、刪除。【考點考點8】棧1、棧的基本概念棧是一種特殊的線性表，只允許

6、在表的一端進行插入和刪除的線性表；插入，刪除的一端為棧頂，另一端為棧底；當表中沒有元素時為空棧。棧是一種后進先出（或先進后出LastInFirstOut）的線性表。棧具有記憶功能。棧的實例：火車調(diào)度，子彈夾。2、棧的存儲結構順序存儲結構：用一組地址連續(xù)的存儲單元即一維數(shù)組來存儲；鏈式存儲：用線性鏈表來存儲；3、棧的基本運算(1)入棧運算，在棧頂位置插入元素；(2)退棧運算，刪除元素(取出棧頂元素并賦給一個指定的變量)；(3)讀棧頂元素，

7、將棧頂元素賦給一個指定的變量，此時指針無變化。【考點考點9】隊列隊列1.隊列的基本概念隊列是一種特殊的線性表，只允許在表的一端插入，在另一端刪除，允許插入的一端是隊尾（rear），允許刪除的一端為隊頭（front）；當表中沒有元素是空隊列；隊列是一種先進先出的線性表。(FIFO)2、隊列的存儲結構順序存儲：一維數(shù)組。鏈式存儲：線性鏈表。3、隊列的運算:(1)入隊運算：從隊尾插入一個元素；(2)退隊運算：從隊頭刪除一個元素。隊列的順序存儲

8、結構一般采用循環(huán)隊列的形式。循環(huán)隊列s=0表示隊列為空；s=1且front=rear表示隊滿。計算循環(huán)隊列的元素個數(shù)：“尾指針減頭指針”，若為負數(shù)，再加其容量即可?！究键c考點10】樹的基本概念樹的基本概念樹是一種非線性結構，是n個結點的有限集。當n=0時為空樹，n0時為非空樹。結點的度：結點所擁有的子樹的個數(shù)。葉子結點：度為0的結點。分支結點：除葉子結點以外的結點。結點的層次：根結點在第一層，同一層上左右結點的子結點在下一層。樹的深度：

9、所處層次最大的那個結點的層次。樹的度：樹中所有結點的度的最大值?！究键c考點11】二叉樹及其基本性質(zhì)二叉樹及其基本性質(zhì)1、二叉樹的概念二叉樹是一種特殊的樹形結構，每個結點最多只有兩棵子樹，且有左右之分不能互換，因此，二叉樹有五種不同的形態(tài)，見教材12頁。2、二叉樹的性質(zhì)性質(zhì)1在二叉樹的第k層上，最多有2k1(k≥1）個結點。性質(zhì)2深度為m的二叉樹最多有2m1個結點。性質(zhì)3在任意一棵二叉樹中，度為0的結點（葉子結點）總是比度為2的結點多一個