全國計算機(jī)二級c語言(完整復(fù)習(xí)資料)

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

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

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

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

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

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

7、將棧頂元素賦給一個指定的變量，此時指針無變化?！究键c考點9】隊列隊列1.隊列的基本概念隊列是一種特殊的線性表，只允許在表的一端插入，在另一端刪除，允許插入的一端是隊尾（rear），允許刪除的一端為隊頭（front）；當(dāng)表中沒有元素是空隊列；隊列是一種先進(jìn)先出的線性表。(FIFO)2、隊列的存儲結(jié)構(gòu)順序存儲：一維數(shù)組。鏈?zhǔn)酱鎯Γ壕€性鏈表。3、隊列的運(yùn)算:(1)入隊運(yùn)算：從隊尾插入一個元素；(2)退隊運(yùn)算：從隊頭刪除一個元素。隊列的順序存儲

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

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