總要求：

1．熟悉信息的邏輯結(jié)構(gòu)及其基本操作并在計(jì)算機(jī)中表示和實(shí)現(xiàn)；

2．掌握各種數(shù)據(jù)結(jié)構(gòu)（線性表、堆棧與隊(duì)列、樹、圖）的特性，具有數(shù)據(jù)抽象的能力；

3．熟練掌握各種數(shù)據(jù)結(jié)構(gòu)的基本操作并能靈活應(yīng)用，掌握應(yīng)用問題的算法設(shè)計(jì)；

4．掌握主要的查找與排序的思想與算法，并初步掌握各類算法的時(shí)間分析和空間分析的技術(shù)。

內(nèi)容：

（一）緒論
1．掌握數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)類型的概念和術(shù)語(yǔ)的含義；

2．理解算法五要素的確切含義；

3．掌握算法設(shè)計(jì)的基本要求以及計(jì)算語(yǔ)句頻度和估算算法時(shí)間復(fù)雜度的方法；

（二）線性表
1．掌握線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著的線性關(guān)系；

2．熟練掌握線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的描述方法, 頭結(jié)點(diǎn), 頭指針, 和首元結(jié)點(diǎn)的區(qū)別及循環(huán)鏈表, 雙向鏈表的特點(diǎn)；

3．熟練掌握線性表在順序存儲(chǔ)結(jié)構(gòu)和各種鏈表結(jié)構(gòu)上的查找、插入和刪除的算法；

4．能夠從時(shí)間和空間復(fù)雜度的角度綜合比較兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用的場(chǎng)合。

（三）棧和隊(duì)列

1． 熟練掌握棧和隊(duì)列的結(jié)構(gòu)特性；

2． 熟練掌握棧類型在兩種存儲(chǔ)結(jié)構(gòu)表示時(shí)的基本操作實(shí)現(xiàn)方法；

3． 熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)算法；

4． 熟練掌握棧和隊(duì)列的滿和空的條件和它們的描述方法；

5． 熟悉棧和隊(duì)列的典型應(yīng)用。

（四）串

1．掌握串的結(jié)構(gòu)特性----數(shù)據(jù)元素為字符的線性表；

2．熟悉串的七種基本操作；

3．掌握串匹配的KMP算法, 熟悉next函數(shù)的定義,學(xué)會(huì)手工計(jì)算next函數(shù)值。

（五）數(shù)組

1．掌握高維數(shù)組存在一維數(shù)組中的兩種存儲(chǔ)表示方法及以行為主的存儲(chǔ)結(jié)構(gòu)中的地址計(jì)算；

2．掌握對(duì)特殊矩陣進(jìn)行壓縮存儲(chǔ)時(shí)的下標(biāo)變換公式；

3．了解稀疏矩陣的三元組壓縮存儲(chǔ)表示方法及適用范圍；

（六） 樹和二叉樹

1．熟悉樹的基本定義及其相關(guān)的術(shù)語(yǔ)的含義；

2．熟練掌握二叉樹的結(jié)構(gòu)特性，了解相應(yīng)的證明方法, 理解常見的二叉樹有關(guān)理論結(jié)論；

3．熟悉二叉樹的二叉鏈和線索二叉樹存儲(chǔ)結(jié)構(gòu)特點(diǎn)及適用范圍；

4．熟悉三種遍歷二叉樹的遞歸算法；

5．掌握二叉樹線索化的實(shí)質(zhì)及線索化的過程；

6．掌握樹和森林與二叉樹的轉(zhuǎn)換, 及其各自遍歷的對(duì)應(yīng)關(guān)系；

7．了解實(shí)現(xiàn)樹的各種操作的算法；

8． 掌握最優(yōu)樹的特性，掌握Huffman樹及其應(yīng)用。

（七） 圖

1．掌握?qǐng)D的定義和術(shù)語(yǔ)；

2．掌握?qǐng)D的兩種存儲(chǔ)結(jié)構(gòu)：數(shù)組表示法、鄰接表，了解實(shí)際問題的求解效率與采取何種存儲(chǔ)結(jié)構(gòu)和算法有密切關(guān)系；

3．掌握?qǐng)D的兩種遍歷策略；圖的遍歷和樹的遍歷之間的類似與差異；

4．熟悉圖的最小生成樹的生成方法；

5．AOE有向無環(huán)網(wǎng)的關(guān)鍵路徑, 關(guān)鍵活動(dòng)的計(jì)算思路；

6．掌握網(wǎng)絡(luò)頂點(diǎn)之間的最短距離的計(jì)算思想。

（八）查找

1. 熟練掌握順序表和有序表的查找方法；

2. 掌握查找效率的計(jì)算方法；

3. 熟練掌握二叉排序樹的構(gòu)造和查找方法；

4. 掌握平衡二叉樹的維護(hù)平衡的方法。

（九）內(nèi)部排序
1． 掌握排序的定義和各種排序方法的基本思想及其特點(diǎn)；

2． 了解各種排序方法的排序過程及其依據(jù)的原則，基于“關(guān)鍵字間的比較”進(jìn)行排序的方法；

3． 熟練掌握快速排序和堆排序等方法的實(shí)例排序過程；

4． 能夠進(jìn)行各種排序方法的時(shí)間復(fù)雜性(平均情況與最壞情況)估計(jì)或分析；

5． 一般了解排序方法“穩(wěn)定”的含義。