一、考查目標(biāo)
數(shù)據(jù)結(jié)構(gòu)是計算機(jī)專業(yè)的一門綜合性基礎(chǔ)課程,是學(xué)科的核心課之一。它是在離散數(shù)學(xué)、程序設(shè)計后,以C語言為工具研究數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其數(shù)據(jù)抽象的方法。是編譯原理、操作系統(tǒng)、數(shù)據(jù)庫和面向?qū)ο蟪绦蛟O(shè)計等課程的重要基礎(chǔ)。課程目標(biāo)是使學(xué)生在學(xué)習(xí)過程中逐步了解和掌握數(shù)據(jù)抽象的方法和意義,并根據(jù)數(shù)據(jù)對象的特征,選擇合適的存儲結(jié)構(gòu)以及相應(yīng)的算法。
二、試卷結(jié)構(gòu)
1、題型結(jié)構(gòu)
選擇題40分(單選,每題2分);名詞解釋10分(每題2分);簡答題30分(每題5分);算法設(shè)計題20分(每題10分)。
2、內(nèi)容結(jié)構(gòu)
線性表(15%)、棧和隊列(5%)、串(5%)、數(shù)組與廣義表(5%)、樹和二叉樹(20%)、圖(20%)、查找(10%)、內(nèi)部排序(20%)。
三、考試內(nèi)容
1、線性表
1)理解并掌握線性表的邏輯結(jié)構(gòu)和順序存儲結(jié)構(gòu);
2)掌握線性鏈表,循環(huán)鏈表,雙向鏈表的鏈?zhǔn)酱鎯Y(jié)構(gòu)及實(shí)現(xiàn)算法;
2、棧和隊列
1)熟練掌握棧的定義、基本操作和實(shí)現(xiàn)算法;
2)掌握應(yīng)用棧來實(shí)現(xiàn)表達(dá)式求值;
3)熟練掌握隊列的定義、基本操作和實(shí)現(xiàn)算法;
4)熟練掌握鏈?zhǔn)酱鎯Y(jié)構(gòu)實(shí)現(xiàn)的鏈隊列;
5)熟練掌握順序存儲結(jié)構(gòu)實(shí)現(xiàn)的循環(huán)隊列。
3、串
1)熟練掌握串的定義、邏輯結(jié)構(gòu)及基本操作;
2)掌握串的存儲結(jié)構(gòu);
3)掌握模式匹配的定義及基本算法。
4、數(shù)組和廣義表
1)掌握數(shù)組的定義和運(yùn)算;
2)熟練掌握數(shù)組的順序存儲結(jié)構(gòu)及特殊矩陣的壓縮存儲;
3)熟練掌握十字鏈表表示的稀疏矩陣;
4)理解并掌握廣義表的定義、存儲結(jié)構(gòu)。
5、樹和二叉樹
1)熟練掌握樹的結(jié)構(gòu)定義及基本操作;
2)熟練掌握二叉樹的結(jié)構(gòu)定義及基本操作;
3)熟練掌握二叉樹的性質(zhì)及存儲結(jié)構(gòu);
4)能熟練應(yīng)用前序,中序,后序遍歷二叉樹;
5)熟練掌握樹的存儲結(jié)構(gòu),樹與二叉樹的相互轉(zhuǎn)換、森林與二叉樹的相互轉(zhuǎn)換,樹的遍歷算法;
6)掌握哈夫曼樹及其應(yīng)用。
6、圖
1)熟練掌握圖的定義和術(shù)語;
2)熟練掌握圖的鄰接矩陣表示法,鄰接表表示法;
3)熟練掌握圖的深度優(yōu)先搜索和廣度優(yōu)先搜索算法;
4)理解生成樹,最小生成樹的概念;
5)熟練掌握構(gòu)造無向圖的最小生成樹的算法;
6)熟練掌握拓?fù)渑判蚝蜆?gòu)造關(guān)鍵路徑的算法;
7)能快速求出從某個源點(diǎn)到其余各頂點(diǎn)的最短路徑。
7、查找
1)熟練掌握順序查找,折半查找,分塊查找的算法;
2)掌握二叉排序樹,平衡二叉樹;
3)了解哈希表的定義,哈希函數(shù)的構(gòu)造方法及處理沖突的方法;
8、內(nèi)部排序
1)熟練掌握直接插入排序,希爾排序及算法;
2)熟練掌握冒泡排序、快速排序及算法;
3)熟練掌握簡單選擇排序及算法;
4)了解二路歸并排序的算法。