江蘇自動化研究所碩士研究生入學考試數(shù)據(jù)結(jié)構(gòu)與程序設計考試大綱

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

　　(一)、數(shù)據(jù)結(jié)構(gòu)部分

　　1、概述

　　(1)數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)的基本概念;

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

　　2、線性表

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

　　(2)線性表的順序存儲結(jié)構(gòu)與鏈式存儲結(jié)構(gòu)(包括單鏈表、循環(huán)鏈表和雙向鏈表)的構(gòu)造原理;

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

　　3、堆棧與隊列

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

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

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

　　4、樹與二叉樹

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

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

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

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

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

　　5、圖

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

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

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

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

　　6、文件及查找

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

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

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

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

　　7、內(nèi)排序

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