江蘇自動化研究所碩士研究生入學考試數據結構與程序設計考試大綱

　　一、命題范圍及考查的知識點

　　(一)、數據結構部分

　　1、概述

　　(1)數據的邏輯結構與存儲結構的基本概念;

　　(2)算法的定義、基本性質以及算法分析的基本概念，包括采用大形式表示時間或空間復雜度。

　　2、線性表

　　(1)線性關系、線性表的定義，線性表的基本操作;

　　(2)線性表的順序存儲結構與鏈式存儲結構(包括單鏈表、循環鏈表和雙向鏈表)的構造原理;

　　(3)在以上兩種存儲結構的基礎上對線性表實施的基本操作，包括順序表的插入和刪除、鏈表的建立、插入和刪除、檢索等操作對應的算法設計(含遞歸算法的設計)。

　　3、堆棧與隊列

　　(1)堆棧與隊列(含循環隊列)的基本概念、基本操作;

　　(2)堆棧與隊列的順序存儲結構與鏈式存儲結構的構造原理;

　　(3)在不同存儲結構的基礎上對堆棧與隊列實施插入與刪除等基本操作。

　　4、樹與二叉樹

　　(1)樹與二叉樹的基本概念，基本特征、名詞術語;

　　(2)完全二叉樹、滿二叉樹的概念、二叉樹的基本性質;

　　(3)二叉樹的順序存儲結構與二叉鏈表存儲結構的構造原理、二叉樹的前序遍歷、中序遍歷、后序遍歷和按層次遍歷算法(重點為非遞歸算法)以及利用遍歷解決有關二叉樹的其它操作;

　　(4)線索二叉樹的基本概念以及構造原理;

　　(5)二叉排序樹的基本概念、建立(插入)和查找，在二叉排序樹中查找結點的平均查找長度ASL。

　　5、圖

　　(1)圖的基本概念、名詞術語;

　　(2)鄰接矩陣存儲方法和鄰接表存儲方法的基本構造原理與特點;

　　(3)圖的深度優先搜索和廣度優先搜索的過程，圖的遍歷的基本作用;

　　(4)最小生成樹及最短路徑的特點、求解過程，拓撲排序及其目的。

　　6、文件及查找

　　(1)順序查找法、折半查找法以及查找過程對應的“判定樹”的構造;

　　(2)索引文件的基本概念;

　　(3)B-樹與B+樹的構造以及構造上異同，B-樹的插入和查找;

　　(4)散列文件的特點，散列函數和散列沖突的概念，處理散列沖突的方法以及散列文件的查找。

　　7、內排序

　　插入排序、選擇排序、泡排序、快速排序、堆積排序(大頂堆積)和二路歸并排序法等排序方法的排序原理、規律和特點。