2014年黃岡師范學(xué)院專升本《數(shù)據(jù)結(jié)構(gòu)》考試大綱

黃岡師范學(xué)院
2014年專升本《數(shù)據(jù)結(jié)構(gòu)》考試大綱

一、總體要求：
1、基本理論知識
(l)什么是數(shù)據(jù)結(jié)構(gòu)、基本概念和基本術(shù)語，算法的描述和算法分析。
(2)什么是線性表、在線性表上常進(jìn)行的基本操作以及這些操作分別在順序存儲和鏈?zhǔn)酱鎯Y(jié)構(gòu)下的實現(xiàn)及復(fù)雜度分析。
(3)棧和隊列的定義、表示方法和實現(xiàn)。
(4)串的定義及其基本操作。
(5)數(shù)組的定義、運(yùn)算和存儲、稀疏矩陣的壓縮存儲。
(6)樹的定義、基本術(shù)語和存儲結(jié)構(gòu)，二叉樹的定義和性質(zhì)、二叉樹的存儲結(jié)構(gòu)及其各種操作，哈夫曼樹。
(7)圖的定義和術(shù)語、圖的存儲結(jié)構(gòu)及其各種操作。
(8)各種查找方法的算法、適用范圍及時間復(fù)雜度的分析。
(9)多種內(nèi)排算法的基本思想和算法的時間復(fù)雜度分析，不同排序方法的比較。
2、基本技能
(1)能閱讀用類C語言編寫的算法。
(2)能分析算法所完成的功能、運(yùn)行結(jié)果和時間復(fù)雜度。
(3)能根據(jù)要求用類C語言編寫算法。
二、考核知識點
1、緒論
(1)數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、物理結(jié)構(gòu)、元素、結(jié)點等基本概念。抽象數(shù)據(jù)類型的定義、表示和實現(xiàn)方法。
(2)算法、算法的特性、如何用類C語言來描述算法。
(3)算法設(shè)計的基本要求以及計算語句頻度和估算算法時間復(fù)雜度的方法。
2、線性表
(1)線性表的定義和操作。
(2)順序存儲線性表的實現(xiàn)和運(yùn)算。
(3)鏈?zhǔn)酱鎯€性表，帶有附加表頭結(jié)點和不帶附加表頭結(jié)點的單鏈表、循環(huán)鏈表和雙向鏈表的實現(xiàn)和查找對插入、刪除等基本操作。
3、棧和隊列
(1)棧和隊列的定義及其存儲結(jié)構(gòu)、循環(huán)隊列。
(2)棧和隊列的主要運(yùn)算。
(3)棧的應(yīng)用舉例，如：數(shù)制轉(zhuǎn)換、表達(dá)式求值等。
4、串
(1)串的定義、空串、空格串。
(2)串的基本操作。
(3)串的順序存儲結(jié)構(gòu)及在順序存儲結(jié)構(gòu)下基本操作的實現(xiàn)。
(4)串的模式匹配算法。
5、樹和二叉樹
(1)樹的定義和術(shù)語。
(2)二叉樹(完全二叉樹、滿二叉樹)的定義和性質(zhì)、二叉樹的存儲結(jié)構(gòu)（順序表示法和二叉鏈表表示法）。
(3)二叉樹遍歷的遞歸算法。
(4)樹和森林轉(zhuǎn)換為二叉樹的方法。
6、圖
(1)圖的定義。
(2)圖的基本術(shù)語。
①圖及無向圖、有向圖、網(wǎng)、子圖、連通圖、強(qiáng)連通圖。
②頂點的度、入度、出度。
③頂點間路徑、路徑長度、環(huán)。
(3)圖的存儲結(jié)構(gòu)
①鄰接矩陣
②鄰接表(含逆鄰接表)
(4)遍歷圖
①深度優(yōu)先搜索遍歷圖的算法及其時間復(fù)雜度。
②廣度優(yōu)先搜索遍歷圖的思想及其時間復(fù)雜度。
(5)生成樹
①生成樹、最小生成樹的概念。
②最小生成樹的構(gòu)造過程(Prim算法和Kruskal算法)及其時間復(fù)雜度。
(6)兩類求最短路徑問題的解法。
8、排序
(1)排序的目的、分類和排序方法的穩(wěn)定性的定義。
(2)插入排序
①直接插入排序的算法。
②希爾排序的思想。
(3)選擇排序
①簡單的選擇排序的算法。
③堆的定義、堆排序的思想。
(4)歸并排序的思想。
(5)基數(shù)排序的思想及特點。
(6)各種內(nèi)部排序方法的比較。
9、查找
(1)查找、關(guān)鍵字、平均查找長度等概念。
(2)靜態(tài)查找表的查找算法及其效率(最壞和平均查找長度)。
①順序查找
②分塊查找
(3)動態(tài)查找表
①二叉排序樹定義、構(gòu)造過程及其查找算法和效率。
(4)哈希表
①哈希表的特點。
②構(gòu)造哈希函數(shù)的方法（除留余數(shù)法等）。
③處理沖突的方法。 教材：《數(shù)據(jù)結(jié)構(gòu)》（C語言版） 朱站立編著 西安交通大學(xué)出版社
試卷結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)部分，100分）
試卷題型比例：
選擇題 約50%
填空題 約30%
計算分析算法題 約20%