線性表(4/20/2011- 4/30/2011)

·         線性表的概念？

·         順序表的概念？如何表示？插入/刪除元素如何實現(xiàn)？平均移動多少元素？

·         鏈表的概念？如何表示？插入刪除操作如何實現(xiàn)？

·         順序表和鏈表分別用什么優(yōu)缺點/各適用于什么情況？

·         鏈表的變形：循環(huán)鏈表，雙向鏈表（插入刪除操作的實現(xiàn)）。

·         什么是棧？順序棧如何表示？Push和Pop操作如何實現(xiàn)？有哪些基本應用（進制數(shù)的轉(zhuǎn)換、括號匹配、行編輯程序）？是如何應用的？

·         什么是隊列？了解雙端隊列、輸入受限隊列、輸出受限隊列。

·         隊列的鏈式表示方法，隊列的基本操作的(帶頭結(jié)點)實現(xiàn)，初始化、入隊操作，出隊操作的實現(xiàn)，注意出隊操作時最后一個節(jié)點出隊時的處理。

·         循環(huán)隊列的表示方法，基本操作的實現(xiàn)。循環(huán)隊列實現(xiàn)時與普通的本書中之前提到的順序表，順序棧有何不同（或者說實現(xiàn)起來最需要注意的問題是什么）？

串

·         略。

數(shù)組(4/30/2011-5/3/2011)

·         多維數(shù)組如何表示？n維數(shù)組第i維的元素個數(shù)為Bi,則數(shù)組一共有多少個元素？當采用行主虛存儲時，A[j1,j2,…,jn]與元素A[0,0,…,0]之間的關(guān)系？第i維的數(shù)值增加一跨越多少個元素(Ci)？Ci和Ci-1有何關(guān)系？

·         對稱矩陣指的是什么樣的矩陣（圖）？對稱矩陣的元素A[i,j]（1<=i<=n, 1<=j<=n）的位置如何計算？

·         什么是上三角矩陣？

·         什么是稀疏矩陣？了解稀疏矩陣的兩種表示方式：三元組順序表、行邏輯表。

·         什么是矩陣轉(zhuǎn)置？矩陣相乘？掌握普通的矩陣相乘的算法的過程。簡單了解行行邏輯連接表表示的矩陣的乘法運算。

·         理解三元組順序表示的稀疏矩陣轉(zhuǎn)置的兩種方法的思想。

·         什么是十字鏈表？理解為什么十字鏈表表示的矩陣比順序表示的矩陣更適合進行矩陣的加減運算。簡單了解十字鏈表的表示方法及創(chuàng)建過程。

·         廣義表的相關(guān)概念。原子、子表、表頭、表尾（重要）、表的長度（遞歸表的長度是2）、深度。理解任何一個廣義表的表頭何以是原子也可以是列表，而表尾一定是列表。

·         理解為什么廣義表通常用鏈式結(jié)構(gòu)表示。知道廣義表的兩種表示結(jié)構(gòu)，理解為什么。

·         理解為什么不適合用線性表表示多元多項式。理解教材中給出的求廣義表深度的算法及復制廣義表遞歸算法出發(fā)的不同。

樹和二叉樹（5/3/2011-5/4/2011）

·         樹的相關(guān)概念。節(jié)點的度，樹的度，數(shù)的深度。

·         二叉樹的定義。由二叉樹的定義推導出的二叉樹的相關(guān)性質(zhì)。層數(shù)i與第i層的節(jié)點的最大數(shù)目之間的關(guān)系，進而導出k層的二叉樹的最大節(jié)點數(shù)。葉子節(jié)點與度數(shù)為2的節(jié)點之間的數(shù)目關(guān)系。

·         知道什么樣的樹是完全二叉樹。完全二叉樹的層數(shù)k與節(jié)點數(shù)目n的關(guān)系。

·         二叉樹的先序遍歷、中序遍歷、后序遍歷。

·         樹的順序表示（這里指的是按照滿二叉樹的方式進行編號）較鏈式表示有何缺點？

·         為什么要有線索二叉樹？表示線索二叉樹的結(jié)構(gòu)該如何設計？中序線索二叉樹中葉子節(jié)點的前驅(qū)和后繼。后續(xù)線索二叉樹的后繼。

·         簡單了解將一棵二叉樹中序線索化的算法。

·         樹的表示結(jié)構(gòu)：雙親表示法有何優(yōu)點？有何缺點？孩子表示法中節(jié)點的設計有哪兩種方法？孩子表示法的結(jié)構(gòu)（順序存儲所有節(jié)點）？

·         知道孩子兄弟表示法。能夠把樹轉(zhuǎn)換成二叉樹，樹在使用二叉樹表示時結(jié)構(gòu)唯一嗎？

·         樹的兩種遍歷方式先根遍歷（先序）、后根遍歷（中序）。想想為什么樹的遍歷方式比二叉樹的遍歷方式少？理解兩種遍歷方式的過程，能夠根據(jù)圖給出正確的遍歷順序。

·         關(guān)系的自反、對稱和傳遞。等價關(guān)系的定義。什么是等價類？

·         帶權(quán)路徑與樹的帶權(quán)路徑長度。

·         重點掌握赫夫曼樹。赫夫曼樹是一顆帶權(quán)的且路徑最短的二叉樹。赫夫曼樹的構(gòu)造過程。可以使用赫夫曼樹減少判定次數(shù)，能夠從數(shù)學角度對減少的次數(shù)進行量化的分析。

·         有n個葉子節(jié)點的赫夫曼樹有2n-1個節(jié)點的推理：赫夫曼樹沒有度為1的節(jié)點，而葉子節(jié)點與度為2的節(jié)點的數(shù)目關(guān)系為n0=n2+1。節(jié)點總數(shù)N=n0+n2。

·         理解求赫夫曼編碼的算法的數(shù)據(jù)結(jié)構(gòu)為何那樣設計？函數(shù)結(jié)構(gòu)為何那樣設計？或者說如何根據(jù)算法描述設計數(shù)據(jù)結(jié)構(gòu)并設計算法？

·         能夠?qū)⒔o出的權(quán)重數(shù)值轉(zhuǎn)換為赫夫曼樹。這里需要注意的問題是出現(xiàn)葉子節(jié)點與合并的樹權(quán)重相等的情況。當對樹進行組合時，總是吧最小的值放在左子樹上，出現(xiàn)相等權(quán)重的情況，按從左到右的順序放。

·         如何把求集合的冪集問題轉(zhuǎn)換為樹的構(gòu)造問題？集合中元素的個數(shù)與樹的層數(shù)有什么關(guān)系？

·         樹的構(gòu)造與4皇后問題的轉(zhuǎn)換。

·         什么是樹的計數(shù)問題？具有3個節(jié)點的二叉樹有多少中不同的形態(tài)？

·         由中序遍歷序列和前序遍歷序列可以得到一顆唯一的二叉樹。掌握這個過程。

·         判斷一個出棧序列是否可以有一組給定的入棧序列得到。

·         二叉樹的應用總結(jié)：減少判定次數(shù)，利用最優(yōu)二叉樹進行前綴編碼，求集合的冪集。

樹的應用：解決4皇后問題，迷宮問題，最優(yōu)問題。

·         二叉搜索樹的實驗。

 圖（5/11/2011-5/17/2011）

·         <v,w>,v為弧尾，w為弧頭。

·         n個節(jié)點的無向完全圖有n(n-1)/2條邊。n個節(jié)點的有向完全圖有n(n-1)條邊。

·         在有向圖中<v,w>的鄰接關(guān)系描述為v鄰接到w。

·         基本概念頂點的度，入度，出度，路徑，路徑長度，回路，簡單路徑，簡單回路，

·         無向圖中的連通，連通圖，連通分量（極大連通子圖）

·         有向圖中的強連通，強連通分量。

·         一個連通圖的生成樹是一個極小連通子圖，該樹包含了n個節(jié)點以及n-1條邊

·         圖的鄰接矩陣表示。鄰接矩陣表示可以很容易的得知兩個頂點之間是否有鄰接關(guān)系，并且可以很容易的求得一個頂點的（出/入）度。

·         理解鄰接表表示法。能畫出示意圖，理解這種表示方式現(xiàn)對于鄰接矩陣表示的優(yōu)點（在邊的條數(shù)遠小于點的個數(shù)時節(jié)省存儲空間）。如何在這種結(jié)構(gòu)上求圖的中點的度（有向圖和無向圖）？

·         表示有向圖的十字鏈表。

·         表示無向圖的多重鏈表。解決鄰接表中的一條邊被存放兩次的問題。

·         深度優(yōu)先算法和廣度優(yōu)先算法的算法描述。

·         掌握Prim算法找最小生成樹的過程?？唆斔箍査惴ㄕ易钚∩蓸涞倪^程。

·         知道什么是關(guān)節(jié)點（割點）。了解關(guān)節(jié)點在深度優(yōu)先生成樹中的兩個特性：根節(jié)點有兩個或兩個以上的子樹時，根節(jié)點為一個關(guān)節(jié)點；當某個節(jié)點v的子樹中沒有任何節(jié)點存在指向v的祖先的回路時，該節(jié)點為關(guān)節(jié)點。

·         了解重連通圖的概念。航線、電路設計最好是重連通的。

·         連通圖與關(guān)節(jié)點的關(guān)系。不要求掌握求關(guān)節(jié)點的算法，知道可以通過深度優(yōu)先算法求得。

·         什么是有向無環(huán)圖？知道可以用有向無環(huán)圖來表示一個表達式，這表示方法在有重復項時，可以比二叉樹表示方式節(jié)省空間。

·         無向圖是否存在環(huán)路可以通過檢查深度優(yōu)先遍歷的過程中是否存在回邊來判斷。

·         在對有向圖進行深度優(yōu)先遍歷的過程中，如果在對v的子樹的SDF算法執(zhí)行完畢之前出現(xiàn)了頂點u到頂點v的回邊，則有向圖中必定存在環(huán)。

·         偏序關(guān)系是自反的，反對襯的，傳遞的。全序關(guān)系要求集合中所有的關(guān)系都是可比的。拓撲排序是由偏序關(guān)系得到的一個全序關(guān)系。

·         拓撲算法的算法描述。算法實現(xiàn)方案一：用入度的減少來表示將邊從原圖中移除，當入度為0時，表示該點可以輸出，使用Stack記錄度為0的點，出棧則表示點從圖中移除放入的結(jié)果集中；方案二：深度優(yōu)先算法訪問順序倒序輸出各個節(jié)點。

·         拓撲序列AOV指出了活動之間的先后依賴關(guān)系。

·         AOE(Activity of Edge)活動網(wǎng)。頂點表示事件，邊表示活動，邊的權(quán)值表示活動的持續(xù)時間。只有唯一的起點和一個唯一的終點。關(guān)鍵路徑是指從起點到重點最長的路徑。活動網(wǎng)上的點i都會有一個最早開始時間e(i)以及一個最晚開始時間l(i),e(i)=l(i)的點就是關(guān)鍵活動了。

·         帶權(quán)有向圖的最短路徑。v到j的最短路徑要么是<v,j>,要么是經(jīng)過某個頂點k的路徑v->k->j

查找（5/18/2011-5/25/2011）

·         靜態(tài)查找表指只進行查詢的表。動態(tài)查找表指在查詢過程中需要進行插入和刪除操作的表。

·         理解查找方法的選擇依賴于數(shù)據(jù)的組織結(jié)構(gòu)。

·         順序查找方式查找長度的計算（只考慮查找成功的情況）。

·         掌握折半查找算法（非遞歸實現(xiàn)）。知道什么是判定樹，根據(jù)判定樹的性質(zhì)來計算折半查找的平均查找長度（假設每個元素的查找概率相等）

·         知道態(tài)查找最優(yōu)樹是用來解決不等概率查找最優(yōu)問題的。

·         理解索引表的構(gòu)建思想。將數(shù)組分塊，保證其塊間有序，為這些塊建立一張索引表。索引表的每個項紀錄了兩個值，塊內(nèi)元素的最大值和塊的起始位置。

·         二叉搜索樹刪除節(jié)點時的三種不同情況，當刪除一個有兩棵子樹的節(jié)點時的兩種處理方式的思想（重組、替代）

·         了解什么是最優(yōu)二叉樹、平衡因子。

·         什么是B-樹？（定義）B樹索引是數(shù)據(jù)庫中存取和查找文件(稱為記錄或鍵值)的一種方法。B-tree算法減少定位記錄時所經(jīng)歷的中間過程，從而加快存取速度。

·         B+ 樹通常用于數(shù)據(jù)庫和操作系統(tǒng)的文件系統(tǒng)中。B+ 樹的特點是能夠保持數(shù)據(jù)穩(wěn)定有序，其插入與修改擁有較穩(wěn)定的對數(shù)時間復雜度。B+ 樹不需要象其他自平衡二叉查找樹那樣經(jīng)常的重新平衡。

·         了解Trie。

·         哈希表的思想：希望有一種辦法能夠通過計算來減少比較的次數(shù)。哈希函數(shù)的要求：產(chǎn)生的key值在規(guī)定的范圍內(nèi)，盡可能的分散。哈希表實現(xiàn)還要考慮沖突的處理問題。

·         哈希表的沖突處理方法的比較：

?  開放地址（二次再散列）。增加了“二次聚集”問題。

?  再hash。增加了計算時間。

?  鏈地址法。

?  公共溢出區(qū)。

排序算法（5/26/2011-5/29/2011）

·         排序算法穩(wěn)定性的概念。內(nèi)部排序和外部排序的概念。

·         掌握最基本的插入排序算法（內(nèi)層的插入比較過程實際上有兩種方式，一種是從左到右，一種是從右至左，注意這里的抉擇過程，不要Take it for granted）。理解折半插入排序的思想。理解二路插入排序的插入過程，二路插入排序可以減少記錄的移動次數(shù)（在關(guān)鍵字不是已排序的情況下）?？梢允褂渺o態(tài)鏈表存儲結(jié)構(gòu)來避免移動元素，但是這僅僅是把元素的移動工作變成了指針變量的修改。希爾排序算法減少時間復雜度算法的思想：跳躍式移動元素。

·         掌握快速排序算法的實現(xiàn)思想并能夠自己寫出快速排序的代碼。

·         堆排序。堆的性質(zhì)：第n/2個元素為最后一個非葉子節(jié)點。堆排序算法的實現(xiàn)。

·         通過合并排序算法理解分治法算法設計，并與快速排序進行比較。掌握其代碼實現(xiàn)思路。多選擇：合并數(shù)組時有兩種思路，一種是以原數(shù)組為依據(jù)進行迭代，另一種是以目標數(shù)組為依據(jù)進行迭代。

·         多關(guān)鍵字排序的兩種思路（MSD、LSD）。比較兩種排序算法的的區(qū)別。理解為什么基數(shù)排序要求是穩(wěn)定的。

·         鏈式基數(shù)排序的算法過程。

·         利用二叉樹分析得出結(jié)論：基于比較的排序的最低時間下界為log2(n!)。