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

　　一、命題范圍及考查的知識(shí)點(diǎn)

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

　　1、概述

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

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

　　2、線(xiàn)性表

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

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

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

　　3、堆棧與隊(duì)列

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

　　(2)堆棧與隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的構(gòu)造原理;

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

　　4、樹(shù)與二叉樹(shù)

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

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

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

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

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

　　5、圖

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

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

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

　　(4)最小生成樹(shù)及最短路徑的特點(diǎn)、求解過(guò)程，拓?fù)渑判蚣捌淠康摹?/P>

　　6、文件及查找

　　(1)順序查找法、折半查找法以及查找過(guò)程對(duì)應(yīng)的“判定樹(shù)”的構(gòu)造;

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

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

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

　　7、內(nèi)排序

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