第一部分：考試說明

　　考試范圍：數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫系統(tǒng)基礎(chǔ)。
　　考試形式與試卷結(jié)構(gòu)：
　　（一）?答卷形式：閉卷，筆試；所列題目均為必答題。
　?。ǘ?答題時間：180分鐘。
　?。ㄈ?各部分考察比例：
　　1） 數(shù)據(jù)結(jié)構(gòu)部分：40%
　　2） 數(shù)據(jù)庫部分：60%
　　（四）?題型比例
　　填空題：約30%
　　簡答或程序分析題：約30%
　　程序、算法設(shè)計或綜述性題目：40%

第二部分：考察要點

　　

A. 數(shù)據(jù)結(jié)構(gòu)部分
　　一、?基本概念：
　　1.?? 熟悉數(shù)據(jù)、數(shù)據(jù)元素等名詞術(shù)語的基本概念。了解抽象數(shù)據(jù)類型的定義、表示和實現(xiàn)方法，熟悉類C語言的書寫規(guī)范。
　　2.?了解計算語句頻度和估算時間算法復(fù)雜度的方法
　　二、?線性表、棧、隊列
　　1.? 理解線性表的邏輯結(jié)構(gòu)，掌握線性表在順序存儲及鏈表結(jié)構(gòu)結(jié)構(gòu)上實現(xiàn)基本操作的算法。
　　2.?掌握棧和隊列這兩種抽象數(shù)據(jù)類型的特點，并能在相應(yīng)的應(yīng)用問題中正確選用它們。
　　3.?掌握棧類型的兩種實現(xiàn)方法，即兩種存儲結(jié)構(gòu)表示時的基本操作實現(xiàn)算法。
　　4.?了解遞歸算法執(zhí)行過程中棧的狀態(tài)變化過程。
　　5.?了解遞歸算法到非遞歸算法的機械轉(zhuǎn)化過程。
　　三、?串
　　1.?掌握串的七種基本操作的定義，并能利用這些基本操作實現(xiàn)串的其他各種操作的方法。
　　2.?了解串的定長順序存儲結(jié)構(gòu)上實現(xiàn)串的各種操作的方法。
　　3.?了解串的堆存儲結(jié)構(gòu)以及在其上實現(xiàn)串操作的基本方法。
　　4.?了解串匹配的KMP算法。
　　5.?了解串操作的應(yīng)用方法和特點。
　　四、?數(shù)組與廣義表
　　1.?了解數(shù)組的兩種存儲表示方法，并掌握數(shù)組在以行為主的
　　2.?了解特殊矩陣進(jìn)行壓縮存儲時的下標(biāo)變換公式。
　　3.?了解稀疏矩陣的兩種壓縮存儲方法的特點和適用范圍。
　　4.?了解廣義表的結(jié)構(gòu)特點及其存儲表示方法。
　　五、?樹和二叉樹
　　1．? 熟練掌握二叉樹的結(jié)構(gòu)特性，了解相應(yīng)的證明方法。
　　2．? 熟悉二叉樹的各種存儲結(jié)構(gòu)的特點及適用范圍。
　　3．? 熟悉遍歷二叉樹的基本概念、性質(zhì)與實現(xiàn)方法。
　　4．? 了解樹的存儲結(jié)構(gòu)及其特點，理解樹和森林與二叉樹的轉(zhuǎn)換方法。
　　5．? 熟悉最優(yōu)二叉樹和哈夫曼編碼。
　　六、?圖
　　1.?理解圖的各種存儲結(jié)構(gòu)及其構(gòu)造算法。
　　2.?掌握圖的兩種搜索路徑的遍歷：遍歷的邏輯定義、深度優(yōu)先搜索的兩種形式（遞歸和非遞歸）和廣度優(yōu)先搜索的算法。
　　七、?查找與排序
　　1.?掌握順序表和有序表的查找方法。
　　2.?了解靜態(tài)查找樹的構(gòu)造方法和查找算法，理解靜態(tài)查找樹和折半查找的關(guān)系。
　　3.?掌握二叉排序樹的構(gòu)造和查找方法。
　　4.?了解二叉平衡樹的維護(hù)平衡方法。
　　5.?了解哈希表的構(gòu)造方法，理解哈希表與其他結(jié)構(gòu)的表的實質(zhì)性的差別。
　　6.?了解描述查找過程的判定樹的構(gòu)造方法，以及按定義計算各種查找方法在等概率情況下查找成功時的平均查找長度。
　　7.?理解排序的定義和各種排序方法的特點。
　　8.?了解各種方法的排序過程及其依據(jù)的原則。
　　9.?了解各種排序方法的時間復(fù)雜度的分析方法。
　　10.?了解“表排序”和“地址排序”的過程及其適用場合。
　　11.?理解外部排序的兩個階段和第二階段——歸并的過程。
　　12.?了解外部排序過程中所需進(jìn)行外存讀/寫次數(shù)計算方法。