浙江海洋大學

《數據結構》

一、使用專業

農業工程與信息技術-農業(漁業)信息化

二、考試內容

1、線性表

1)理解并掌握線性表的邏輯結構和順序存儲結構;

2)掌握線性鏈表，循環鏈表，雙向鏈表的鏈式存儲結構及實現算法;

2、棧和隊列

1)熟練掌握棧的定義、基本操作和實現算法;

2)掌握應用棧來實現表達式求值;

3)熟練掌握隊列的定義、基本操作和實現算法;

4)熟練掌握鏈式存儲結構實現的鏈隊列;

5)熟練掌握順序存儲結構實現的循環隊列。

3、串

1)熟練掌握串的定義、邏輯結構及基本操作;

2)掌握串的存儲結構;

3)掌握模式匹配的定義及基本算法。

4、數組和廣義表

1)掌握數組的定義和運算;

2)熟練掌握數組的順序存儲結構及特殊矩陣的壓縮存儲;

3)熟練掌握十字鏈表表示的稀疏矩陣;

4)理解并掌握廣義表的定義、存儲結構。

5、樹和二叉樹

1)熟練掌握樹的結構定義及基本操作;

2)熟練掌握二叉樹的結構定義及基本操作;

3)熟練掌握二叉樹的性質及存儲結構;

4)能熟練應用前序，中序，后序遍歷二叉樹;

5)熟練掌握樹的存儲結構，樹與二叉樹的相互轉換、森林與二叉樹的相互轉換，樹的遍歷算法;

6)掌握哈夫曼樹及其應用。

6、圖

1)熟練掌握圖的定義和術語;

2)熟練掌握圖的鄰接矩陣表示法，鄰接表表示法;

3)熟練掌握圖的深度優先搜索和廣度優先搜索算法;

4)理解生成樹，最小生成樹的概念;

5)熟練掌握構造無向圖的最小生成樹的算法;

6)熟練掌握拓撲排序和構造關鍵路徑的算法;

7)能快速求出從某個源點到其余各頂點的最短路徑。

7、查找

1)熟練掌握順序查找，折半查找，分塊查找的算法;

2)掌握二叉排序樹，平衡二叉樹;

3)了解哈希表的定義，哈希函數的構造方法及處理沖突的方法;

8、內部排序

1)熟練掌握直接插入排序,希爾排序及算法;

2)熟練掌握冒泡排序、快速排序及算法;

3)熟練掌握簡單選擇排序及算法;

4)了解二路歸并排序的算法。

三、推薦書目

陳越著，《數據結構》，高等教育出版社，2016.