第一部分：考試說(shuō)明

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

第二部分：考察要點(diǎn)

　　

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