【考點1】算法的基本概念
1、算法：是指一組有窮的指令集，是解題方案的準(zhǔn)確而完整的描述。算法不等于程序，也不等于計算方法。
2、算法的基本特征：
1）確定性，算法中每一步驟都必須有明確定義，不允許有多義性；
2）有窮性，算法必須能在有限的時間內(nèi)做完，即能在執(zhí)行有限個步驟后終止；
3）可行性，算法原則上能夠精確地執(zhí)行；
4）擁有足夠的情報。
3、算法的組成要素：一個算法由數(shù)據(jù)對象的運算和操作以及其控制結(jié)構(gòu)這兩部分組成。
4、算法的基本運算和操作：算術(shù)運算，邏輯運算，關(guān)系運算，數(shù)據(jù)傳輸。
5、算法的基本控制結(jié)構(gòu)：順序，選擇，循環(huán)。
6、算法基本設(shè)計方法：列舉法、歸納法、遞推、遞歸、減半遞推技術(shù)。
【考點2】算法的復(fù)雜度
1、算法效率的度量——算法的復(fù)雜度：時間復(fù)雜度和空間復(fù)雜度。
1）算法時間復(fù)雜度：指執(zhí)行算法所需要的計算工作量。通常，一個算法所用的時間包括編譯時間和運行時間。
2）算法空間復(fù)雜度：指執(zhí)行這個算法所需要的內(nèi)存空間。包括算法程序所占的空間，輸入的初始數(shù)據(jù)所占的空間，算法執(zhí)行過程中所需的額外空間。
空間復(fù)雜度和時間復(fù)雜度并不相關(guān)。
【考點2】算法的復(fù)雜度
1、算法效率的度量——算法的復(fù)雜度：時間復(fù)雜度和空間復(fù)雜度。
1）算法時間復(fù)雜度：指執(zhí)行算法所需要的計算工作量。通常，一個算法所用的時間包括編譯時間和運行時間。
2）算法空間復(fù)雜度：指執(zhí)行這個算法所需要的內(nèi)存空間。包括算法程序所占的空間，輸入的初始數(shù)據(jù)所占的空間，算法執(zhí)行過程中所需的額外空間。
空間復(fù)雜度和時間復(fù)雜度并不相關(guān)。
【考點3】數(shù)據(jù)結(jié)構(gòu)的基本概念
數(shù)據(jù)：數(shù)據(jù)是客觀事物的符號表示，是能輸入到計算機中并被計算程序識別和處理的符號的總稱，如文檔，聲音，視頻等。
數(shù)據(jù)元素：數(shù)據(jù)元素是數(shù)據(jù)的基本單位。
數(shù)據(jù)對象：數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合。
數(shù)據(jù)結(jié)構(gòu)：是指由某一數(shù)據(jù)對象中所有數(shù)據(jù)成員之間的關(guān)系組成的集合。
【考點4】邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)
1、數(shù)據(jù)結(jié)構(gòu)可分為數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。
1）數(shù)據(jù)的邏輯結(jié)構(gòu)是對數(shù)據(jù)元素之間的邏輯關(guān)系的描述，與數(shù)據(jù)的存儲無關(guān)，是面向問題的，是獨立于計算機的。它包括數(shù)據(jù)對象和數(shù)據(jù)對象之間的關(guān)系。
2）數(shù)據(jù)的存儲結(jié)構(gòu)也稱為數(shù)據(jù)的物理結(jié)構(gòu)，是數(shù)據(jù)在計算機中的存放的方式，是面向計算機的，它包括數(shù)據(jù)元素的存儲方式和關(guān)系的存儲方式。
2、存儲結(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)。
3、常見的存儲結(jié)構(gòu)有：順序，鏈接，索引等。采用不同的存儲結(jié)構(gòu)其數(shù)據(jù)處理的效率是不同的。
【考點5】線性結(jié)構(gòu)和非線性結(jié)構(gòu)
1、線性結(jié)構(gòu)的條件（一個非空數(shù)據(jù)結(jié)構(gòu))：
（1）有且只有一個根結(jié)點；
（2）每一個結(jié)點最多有一個前件，也最多有一個后件。
2、非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。
棧、隊列、雙向鏈表是線性結(jié)構(gòu)，樹、二叉樹為非線性結(jié)構(gòu)。
【考點6】線性表及其順序存儲結(jié)構(gòu)
1、線性表是由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的序號，元素之間的相對位置是線性的。
2、在復(fù)雜線性表中，由若干項數(shù)據(jù)元素組成的數(shù)據(jù)元素稱為記錄；由多個記錄構(gòu)成的線性表稱為文件。
3、非空線性表的結(jié)構(gòu)特征：
（1）有且只有一個根結(jié)點a1，它無前件；
（2）有且只有一個終端結(jié)點an，它無后件；
（3）除根結(jié)點與終端結(jié)點外，其他所有結(jié)點有且只有一個前件，也有且只有一個后件。
結(jié)點個數(shù)n稱為線性表的長度，當(dāng)n=0時，稱為空表。
4、線性表的順序存儲結(jié)構(gòu)具有以下兩個基本特點：
（1）線性表中所有元素所占的存儲空間是連續(xù)的；
（2）線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。
元素ai的存儲地址為：ADR(ai)=ADR(a1)+(i-1)*k，ADR(a1)為第一個元素的地址，k代表每個元素占的字節(jié)數(shù)。
5、順序表的運算：查找、插入、刪除。
【考點7】線性鏈表
線性鏈表是線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)中的每一個結(jié)點對應(yīng)于一個存儲單元，這種存儲單元稱為存儲結(jié)點，簡稱結(jié)點。結(jié)點由兩部分組成：(1) 用于存儲數(shù)據(jù)元素值，稱為數(shù)據(jù)域；(2) 用于存放指針，稱為指針域，用于指向前一個或后一個結(jié)點。
在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以不連續(xù)，各數(shù)據(jù)結(jié)點的存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的。
鏈?zhǔn)酱鎯Ψ绞郊瓤捎糜诒硎揪�性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。
