考試安排時間：2011年7月6號下午2：30地點：教一樓106持續(xù)時間：14:30~16:30梗概概述線性表棧與隊列串樹與二叉樹圖查找與排序概述數(shù)學(xué)歸納法數(shù)據(jù)結(jié)構(gòu)的定義算法的特點和設(shè)計原則算法的度量：時間復(fù)雜度和空間復(fù)雜度O(1)<O(logn)<O(n)<O(n2)<O(en)<O(2n)NP問題線性表線性表的定義線性結(jié)構(gòu)的特點線性表的順序表示線性表的鏈?zhǔn)奖硎眷o態(tài)鏈表

(不做要求)循環(huán)鏈表和雙向鏈表棧棧的概念：就是線性表，一端固定，另一端活動；：順序和鏈?zhǔn)綏５谋硎緱５膽?yīng)用：數(shù)字轉(zhuǎn)換、括號匹配、表達式求值棧與遞歸遞歸的概念：函數(shù)調(diào)用自身C語言中函數(shù)的遞歸是怎么實現(xiàn)的－棧一般而言，能支持函數(shù)的嵌套調(diào)用，就能支持遞歸；Hanoi塔問題：熟悉遞歸的實現(xiàn)過程；遞歸樹－分析和設(shè)計遞歸的強有力工具棧與遞歸怎樣設(shè)計算法的遞歸形式；遞歸與迭代的區(qū)別和聯(lián)系：遞歸可以通過迭代和棧來實現(xiàn)(定理)；什么情況下，算法的遞歸形式很容易轉(zhuǎn)化為其迭代形式；遞歸樹簡單或者有重復(fù)結(jié)構(gòu)。隊列隊列的定義：就是線性表，一端只能元素，另一端只能刪除元素；鏈隊列；循環(huán)隊列－如何判斷隊列滿或空：書上的方法，以及tag標(biāo)志位方法。串串的定義：字符的有限序列；字符在串中的序號；子串，子串在主串中的位置；串的長度什么情況下兩個串是相等的(必須兩個條件同時滿足)串串的五大基本操作：串賦值、求串長、串比較、求子串、串連接這五種操作構(gòu)成串的最小操作子集；如何用這五種操作實現(xiàn)串定位、

一個子串、和刪除一個子串的操作。串的模式匹配算法串的模式匹配就是串的定位操作；一般的算法(Naive)KMP算法如何求解next函數(shù)如何求解next函數(shù)的修正值nextval樹與二叉樹樹的定義：遞歸定義，非線性結(jié)構(gòu)根節(jié)點、孩子和雙親節(jié)點葉子、兄弟、祖先和子孫節(jié)點的度和樹的度樹的深度有序樹和無序樹森林二叉樹二叉樹的定義：樹中的節(jié)點的度都不大于2二叉樹的性質(zhì)：第i層上最多有2i-1個節(jié)點深度為k的二叉樹至多有2k－1個節(jié)點n0

=

n2+1具有n個節(jié)點的完全二叉樹深度為[log2n]+1二叉樹滿二叉樹和完全二叉樹結(jié)構(gòu)：順序鏈?zhǔn)绞褂面準(zhǔn)浇Y(jié)構(gòu)遍歷二叉樹遍歷二叉樹的三種順序：先序遍歷中序遍歷后序遍歷這里的序指

根節(jié)點的先后；算法實現(xiàn)－遞歸遍歷二叉樹表達式的三種形式：波蘭式－先序遍歷中綴表達－中序遍歷逆波蘭式－后序遍歷逆波蘭式的優(yōu)勢Huffman樹帶

的樹帶權(quán)的路徑帶權(quán)路徑的長度如何構(gòu)造Huffman樹，生成一棵帶權(quán)路徑長度最小的樹如何進行Huffman編碼，使得碼字的平均長度最短圖圖的定義頂點、弧、弧頭和弧尾有向圖和無向圖完全圖、稠密圖和稀疏圖鄰接、頂點的度，出度和入度路徑、簡單路徑、回路圖連通：圖中的任意兩個頂點之間都有路徑；連通圖和連通分量；(無向圖)強連通圖和強連通分量；(有向圖)生成樹圖的最小生成樹貪婪算法的基本思想生成Huffman樹的算法就是貪婪算法Prim算法Kruskal算法查找查找的定義：關(guān)鍵字、主關(guān)鍵字、次關(guān)鍵字對查找表經(jīng)常進行的操作：查找和檢索記錄到查找表從查找表中刪除記錄靜態(tài)查找表順序查找表算法及其性能分析有序表的查找：折半查找折半查找算法判定樹折半查找的性能分析二叉排序樹二叉排序樹的定義：動態(tài)查找表在查找的過程中動態(tài)的生成二叉排序樹生成二叉排序樹的過程就是對無序序列的排序過程如何在二叉排序樹中查找和

一條記錄如何生成一棵二叉排序樹排序排序的定義：將一個數(shù)據(jù)元素的任意序列重新排列成一個按關(guān)鍵字有序的序列；排序方法的穩(wěn)定性排序快速排序排序簡單

排序：如何實現(xiàn)－算法性能分析冒泡排序：一