線性表
1. 線性表的邏輯結(jié)構(gòu)定義、抽象數(shù)據(jù)類型定義。
2. 線性表的兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場(chǎng)合。
順序存儲(chǔ)：借助元素在存儲(chǔ)器中的相對(duì)位置來表示元素之間的邏輯關(guān)系。
鏈?zhǔn)酱鎯?chǔ)：借助指示元素存儲(chǔ)地址的指針來表示元素之間的邏輯關(guān)系。
順序表和鏈表的優(yōu)缺點(diǎn)比較（正好是相對(duì)的）。
3. 在線性表的兩種存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)基本操作的算法。
查找、插入、刪除、歸并、分解、就地逆置等。
注意：?jiǎn)捂湵砼c雙向鏈表、普通鏈表與循環(huán)鏈表的區(qū)別。
雙向鏈表中結(jié)點(diǎn)的特征：p=p->next->prior=p->prior->next
因此，在插入和刪除時(shí)，對(duì)單鏈表，必須要知道第i-1個(gè)結(jié)點(diǎn)
的地址，而對(duì)雙向鏈表則不必如此。
例1.已知la是不帶頭結(jié)點(diǎn)的單鏈表的頭指針，試編寫逆序
輸出表中各元素值的遞歸算法。
例2.按遞增有序輸出單鏈表中的元素值。
例3.實(shí)現(xiàn)集合的交、并、差等運(yùn)算。
堆和隊(duì)列
1. 棧的定義、特征以及抽象數(shù)據(jù)類型定義。
會(huì)靈活運(yùn)用棧的特征（后進(jìn)先出）。
例：設(shè)輸入元素為1, 2, 3, P, A，輸入次序?yàn)?23PA，元素經(jīng)過棧后到達(dá)輸出序列，當(dāng)所有元素均到達(dá)輸出序列后，有哪些序列可以作為高級(jí)語言的變量名？
2.棧的存儲(chǔ)結(jié)構(gòu)順序棧：棧滿和?？盏臈l件
鏈棧
入棧、出棧、取棧頂元素等基本操作的實(shí)現(xiàn)算法。
3.棧的應(yīng)用表達(dá)式計(jì)算：了解基本思想、棧在算法中的作用
實(shí)現(xiàn)遞歸算法
4. 隊(duì)列的定義、特征以及抽象數(shù)據(jù)類型定義。
5.隊(duì)列的存儲(chǔ)結(jié)構(gòu)（順序）循環(huán)隊(duì)列
鏈隊(duì)列
入隊(duì)、出隊(duì)、取隊(duì)頭元素等基本操作的實(shí)現(xiàn)算法。
循環(huán)隊(duì)列：入隊(duì)：Q->queue[Q->rear]＝x；
Q->rear＝(Q->rear+1)%MaxQueueSize；
出隊(duì)：*d=Q->queue[Q->front]；
Q->front＝(Q->front＋1) %MaxQueueSize；
判斷隊(duì)滿和隊(duì)空：（1）少用一個(gè)存儲(chǔ)單元；
（2）設(shè)置一個(gè)標(biāo)志位；
（3）設(shè)置一個(gè)計(jì)數(shù)器。
6. 隊(duì)列的應(yīng)用：結(jié)合后面二叉樹和圖的遍歷算法。
數(shù)組
1. 數(shù)組采用行優(yōu)先或列優(yōu)先順序存儲(chǔ)時(shí)，數(shù)組元素的
存儲(chǔ)地址的計(jì)算方法（重點(diǎn)掌握二維、三維數(shù)組）。
2. 特殊矩陣進(jìn)行壓縮存儲(chǔ)時(shí)下標(biāo)變換公式的推導(dǎo)方法。
要求掌握上三角矩陣、下三角矩陣、對(duì)稱矩陣、三對(duì)角
矩陣分別按行優(yōu)先或列優(yōu)先壓縮存儲(chǔ)時(shí)的下標(biāo)變換公式。
樹
1. 樹、二叉樹的結(jié)構(gòu)特性；二叉樹的五種基本形態(tài)。
2. 滿二叉樹和完全二叉樹的定義、特點(diǎn)；二叉樹的性質(zhì)
（五條，其中有兩條只對(duì)完全二叉樹滿足）。
1、若深度從0開始計(jì)算則第i層有2^i個(gè)結(jié)點(diǎn)
2、共有2^(i+1) -1個(gè)結(jié)點(diǎn)
3、n0=n2+1
4、完全二叉樹有n個(gè)結(jié)點(diǎn)，則他的深度為log2(n+1)-1
5、完全二叉樹：第i個(gè)結(jié)點(diǎn)的左孩子在2i+1 右孩子是2i+2
3. 二叉樹的遍歷策略及算法（遞歸和非遞歸）。由前序
和中序遍歷序列、中序和后序遍歷序列能唯一構(gòu)造出一棵二叉樹。
會(huì)靈活運(yùn)用遍歷算法求解其他問題。
例1.輸出某類結(jié)點(diǎn)的值或求某類結(jié)點(diǎn)的個(gè)數(shù)（如葉子結(jié)點(diǎn)）。
例2.判定一棵二叉樹是否為二叉排序樹（采用中序遍歷策略，判斷正在訪問的結(jié)點(diǎn)與它的前驅(qū)結(jié)點(diǎn)之間是否遞增有序）。
4. 樹的三種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)（雙親表示法、孩子表示法和孩子兄弟表示法，重點(diǎn)掌握孩子兄弟表示法）；樹、
森林與二叉樹的轉(zhuǎn)換方法。
5. 樹的遍歷方法：
先根（對(duì)應(yīng)二叉樹的前序遍歷）
后根（對(duì)應(yīng)二叉樹的中序遍歷）
森林的遍歷方法：先序和中序。
6.
Huffman樹的概念及構(gòu)造方法，哈夫曼編碼的設(shè)計(jì)。
注意：Huffman樹是擴(kuò)充二叉樹（只含度為0和度為2的結(jié)點(diǎn)）。
補(bǔ)充作業(yè)：寫出二叉樹的中序和后序遍歷的非遞歸算法。
voidNInOrder(BiTreeNode*bt)
/*中序遍歷二叉樹bt的非遞歸算法*/
{BiTreeNode*stack [MaxNode], *p;
int top;
if (bt==NULL)
return;
top=0；p=bt；
while (! (p==NULL&&top==0))
{ while (p!=NULL)
{ if (top
{stack[top]=p;
top++;
}
else {printf(“\noverflow！”);
return;
}p=p->leftChild;/*訪問左子樹*/
}/*while (p!=NULL)*/
if (top==0) return;
else { top--;
p=stack[top];
visit (p);/*訪問根結(jié)點(diǎn)*/
p=p->rightChild;/*訪問右子樹*/
}
}/*while*/
}
typedefstruct
{BiTreeNode*pt;
inttag;
} Node;
voidNPostOrder(BiTreeNode*bt)
/*后序遍歷二叉樹bt的非遞歸算法*/
{ Node stack [MaxNode],BiTreeNode*p;
inttop;
if (bt==NULL)
return;
top=0；p=bt；
while (! (p==NULL&&top==0))
{ while (p!=NULL)
{ if (top
{stack[top].pt=p;stack[top].tag=1;
top++;
}else {printf(“\noverflow！”);
return;
}
p=p->leftChild;/*訪問左子樹*/
}/*while (p!=NULL)*/
if (top==0) return;
else {if (stack[top-1].tag==1)
{ p=stack[top-1].pt;stack[top-1].tag=2;
p=p->rightChild;/*訪問右子樹*/
}
else { top--;
visit (stack[top].pt);/*訪問根結(jié)點(diǎn)*/
}
}
}/*while*/
}
圖
圖的定義、基本術(shù)語。
（如：無向完全圖、有向完全圖、路徑、回路、連通圖和連通分量、強(qiáng)連通圖和強(qiáng)連通分量、連通圖的生成樹）
無向完全圖：弧數(shù)量為Cn2 的圖，有向完全圖的弧數(shù)量為An2
連通圖 ：任意兩個(gè)結(jié)點(diǎn)能連通
連通分量：在無向圖中，極大的連通子圖成為圖的連通分量
連通圖的生成樹：一個(gè)連通圖的生成樹是一個(gè)極小連通子圖，他含有途中全部定點(diǎn)n但只有足以構(gòu)成一棵樹的n-1條邊。
注意：邊數(shù)與頂點(diǎn)數(shù)、度之間的關(guān)系：
完全圖、連通圖以及生成樹的特點(diǎn)。
判斷圖中是否存在回路的方法。?
無向圖中結(jié)點(diǎn)的度均>=2 則改圖一定存在回路
利用BFS，在遍歷過程中，為每個(gè)節(jié)點(diǎn)標(biāo)記一個(gè)深度deep，如果存在某個(gè)節(jié)點(diǎn)為v，除了其父節(jié)點(diǎn)u外，還存在與v相鄰的節(jié)點(diǎn)w使得deep[v]<=deep[w]的，那么該圖一定存在回路；
2.
圖的各種存儲(chǔ)結(jié)構(gòu)（重點(diǎn)掌握鄰接矩陣和鄰接表）的
特點(diǎn)及構(gòu)造方法。
注意：圖和網(wǎng)的區(qū)別。
3. 圖的兩種遍歷策略及遍歷算法（深度優(yōu)先和廣度優(yōu)先）。
會(huì)靈活運(yùn)用遍歷算法求解其他問題。
4. 圖的應(yīng)用
（1）生成樹的定義、類型（深度優(yōu)先和廣度優(yōu)先生成樹）；
最小生成樹的定義；
Kruskal算法和Prim算法(破圈法)求網(wǎng)的最小生成樹的方法（注意：記住算法特點(diǎn)，不要混淆）。
（2）Dijkstra算法求單源最短路徑的方法（有向網(wǎng)和無向網(wǎng)都適用）。
查找
1.靜態(tài)查找表的順序查找、折半查找方法的實(shí)現(xiàn)算法；
描述折半查找過程的二叉判定樹的構(gòu)造方法；三種方
法的比較。
2.
二叉排序樹的定義、構(gòu)造以及查找、插入的實(shí)現(xiàn)方法。
注意：二叉排序樹按中序遍歷是遞增有序序列。
3.
哈希表的定義、構(gòu)造及查找方法，重點(diǎn)掌握開放定址法和鏈地址法處理沖突時(shí)的構(gòu)造方法。
開放地址法：線性探測(cè)、平方再散列法（-1^2,1^2,-2^2,2^2....）
鏈地址法：將沖突的結(jié)點(diǎn)連接在地址上，采用鏈?zhǔn)浇Y(jié)構(gòu)
4.
根據(jù)公式計(jì)算各種查找方法在等概率情況下的平均查找長(zhǎng)度。
內(nèi)部排序
1.
排序的定義，排序方法“穩(wěn)定”或“不穩(wěn)定”的含義。
注意：希爾排序、直接選擇排序、堆排序、快速排序是不穩(wěn)定的排序算法。
2.
各種排序方法的基本思想、算法特點(diǎn)、排序過程
以及它們的時(shí)間和空間復(fù)雜度分析。
（包括基本算法及它們的改進(jìn)算法：直接插入排序、
折半插入排序、希爾排序、直接選擇排序、堆排序、
冒泡排序、快速排序、歸并排序及基數(shù)排序）
會(huì)根據(jù)實(shí)際應(yīng)用情況選擇合適的排序算法。
錯(cuò)誤題目總結(jié)
1、數(shù)據(jù)的最小單位是數(shù)據(jù)項(xiàng)
2、時(shí)間復(fù)雜度不受初始狀態(tài)影響而恒為 nlog2n 的是 堆排序。
