江蘇自動(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、線性表
(1)線性關(guān)系、線性表的定義,線性表的基本操作;
(2)線性表的順序存儲(chǔ)結(jié)構(gòu)與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(包括單鏈表、循環(huán)鏈表和雙向鏈表)的構(gòu)造原理;
(3)在以上兩種存儲(chǔ)結(jié)構(gòu)的基礎(chǔ)上對(duì)線性表實(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、樹與二叉樹
(1)樹與二叉樹的基本概念,基本特征、名詞術(shù)語(yǔ);
(2)完全二叉樹、滿二叉樹的概念、二叉樹的基本性質(zhì);
(3)二叉樹的順序存儲(chǔ)結(jié)構(gòu)與二叉鏈表存儲(chǔ)結(jié)構(gòu)的構(gòu)造原理、二叉樹的前序遍歷、中序遍歷、后序遍歷和按層次遍歷算法(重點(diǎn)為非遞歸算法)以及利用遍歷解決有關(guān)二叉樹的其它操作;
(4)線索二叉樹的基本概念以及構(gòu)造原理;
(5)二叉排序樹的基本概念、建立(插入)和查找,在二叉排序樹中查找結(jié)點(diǎn)的平均查找長(zhǎng)度ASL。
5、圖
(1)圖的基本概念、名詞術(shù)語(yǔ);
(2)鄰接矩陣存儲(chǔ)方法和鄰接表存儲(chǔ)方法的基本構(gòu)造原理與特點(diǎn);
(3)圖的深度優(yōu)先搜索和廣度優(yōu)先搜索的過(guò)程,圖的遍歷的基本作用;
(4)最小生成樹及最短路徑的特點(diǎn)、求解過(guò)程,拓?fù)渑判蚣捌淠康摹?/P>
6、文件及查找
(1)順序查找法、折半查找法以及查找過(guò)程對(duì)應(yīng)的“判定樹”的構(gòu)造;
(2)索引文件的基本概念;
(3)B-樹與B+樹的構(gòu)造以及構(gòu)造上異同,B-樹的插入和查找;
(4)散列文件的特點(diǎn),散列函數(shù)和散列沖突的概念,處理散列沖突的方法以及散列文件的查找。
7、內(nèi)排序
插入排序、選擇排序、泡排序、快速排序、堆積排序(大頂堆積)和二路歸并排序法等排序方法的排序原理、規(guī)律和特點(diǎn)。
相關(guān)推薦:2011考研大綱發(fā)布匯總(已發(fā)布)