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

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

湖北專升本網(wǎng)獲悉，2015年黃岡師范學(xué)院普通專升本《數(shù)據(jù)結(jié)構(gòu)》考試大綱如下：

一、總體要求：

1、基本理論知識(shí)

(l)什么是數(shù)據(jù)結(jié)構(gòu)、基本概念和基本術(shù)語(yǔ)，算法的描述和算法分析。

(2)什么是線性表、在線性表上常進(jìn)行的基本操作以及這些操作分別在順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的實(shí)現(xiàn)及復(fù)雜度分析。

(3)棧和隊(duì)列的定義、表示方法和實(shí)現(xiàn)。

(4)串的定義及其基本操作。

(5)數(shù)組的定義、運(yùn)算和存儲(chǔ)、稀疏矩陣的壓縮存儲(chǔ)。

(6)樹(shù)的定義、基本術(shù)語(yǔ)和存儲(chǔ)結(jié)構(gòu)，二叉樹(shù)的定義和性質(zhì)、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及其各種操作，哈夫曼樹(shù)。

(7)圖的定義和術(shù)語(yǔ)、圖的存儲(chǔ)結(jié)構(gòu)及其各種操作。

(8)各種查找方法的算法、適用范圍及時(shí)間復(fù)雜度的分析。

(9)多種內(nèi)排算法的基本思想和算法的時(shí)間復(fù)雜度分析，不同排序方法的比較。

2、基本技能

(1)能閱讀用類C語(yǔ)言編寫(xiě)的算法。

(2)能分析算法所完成的功能、運(yùn)行結(jié)果和時(shí)間復(fù)雜度。

(3)能根據(jù)要求用類C語(yǔ)言編寫(xiě)算法。

二、考核知識(shí)點(diǎn)

1、緒論

(1)數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、物理結(jié)構(gòu)、元素、結(jié)點(diǎn)等基本概念。抽象數(shù)據(jù)類型的定義、表示和實(shí)現(xiàn)方法。

(2)算法、算法的特性、如何用類C語(yǔ)言來(lái)描述算法。

(3)算法設(shè)計(jì)的基本要求以及計(jì)算語(yǔ)句頻度和估算算法時(shí)間復(fù)雜度的方法。

2、線性表

(1)線性表的定義和操作。

(2)順序存儲(chǔ)線性表的實(shí)現(xiàn)和運(yùn)算。

(3)鏈?zhǔn)酱鎯?chǔ)線性表，帶有附加表頭結(jié)點(diǎn)和不帶附加表頭結(jié)點(diǎn)的單鏈表、循環(huán)鏈表和雙向鏈表的實(shí)現(xiàn)和查找對(duì)插入、刪除等基本操作。

3、棧和隊(duì)列

(1)棧和隊(duì)列的定義及其存儲(chǔ)結(jié)構(gòu)、循環(huán)隊(duì)列。

(2)棧和隊(duì)列的主要運(yùn)算。

(3)棧的應(yīng)用舉例，如：數(shù)制轉(zhuǎn)換、表達(dá)式求值等。

4、串

(1)串的定義、空串、空格串。

(2)串的基本操作。

(3)串的順序存儲(chǔ)結(jié)構(gòu)及在順序存儲(chǔ)結(jié)構(gòu)下基本操作的實(shí)現(xiàn)。

(4)串的模式匹配算法。

5、樹(shù)和二叉樹(shù)

(1)樹(shù)的定義和術(shù)語(yǔ)。

(2)二叉樹(shù)(完全二叉樹(shù)、滿二叉樹(shù))的定義和性質(zhì)、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)（順序表示法和二叉鏈表表示法）。

(3)二叉樹(shù)遍歷的遞歸算法。

(4)樹(shù)和森林轉(zhuǎn)換為二叉樹(shù)的方法。

6、圖

(1)圖的定義。

(2)圖的基本術(shù)語(yǔ)。

①圖及無(wú)向圖、有向圖、網(wǎng)、子圖、連通圖、強(qiáng)連通圖。

②頂點(diǎn)的度、入度、出度。

③頂點(diǎn)間路徑、路徑長(zhǎng)度、環(huán)。

(3)圖的存儲(chǔ)結(jié)構(gòu)

①鄰接矩陣

②鄰接表(含逆鄰接表)

(4)遍歷圖

①深度優(yōu)先搜索遍歷圖的算法及其時(shí)間復(fù)雜度。

②廣度優(yōu)先搜索遍歷圖的思想及其時(shí)間復(fù)雜度。

(5)生成樹(shù)

①生成樹(shù)、最小生成樹(shù)的概念。

②最小生成樹(shù)的構(gòu)造過(guò)程(Prim算法和Kruskal算法)及其時(shí)間復(fù)雜度。

(6)兩類求最短路徑問(wèn)題的解法。

8、排序

(1)排序的目的、分類和排序方法的穩(wěn)定性的定義。

(2)插入排序

①直接插入排序的算法。

②希爾排序的思想。

(3)選擇排序

①簡(jiǎn)單的選擇排序的算法。

③堆的定義、堆排序的思想。

(4)歸并排序的思想。

(5)基數(shù)排序的思想及特點(diǎn)。

(6)各種內(nèi)部排序方法的比較。

9、查找

(1)查找、關(guān)鍵字、平均查找長(zhǎng)度等概念。

(2)靜態(tài)查找表的查找算法及其效率(最壞和平均查找長(zhǎng)度)。

①順序查找

②分塊查找

(3)動(dòng)態(tài)查找表

①二叉排序樹(shù)定義、構(gòu)造過(guò)程及其查找算法和效率。

(4)哈希表

①哈希表的特點(diǎn)。

②構(gòu)造哈希函數(shù)的方法（除留余數(shù)法等）。

③處理沖突的方法。

教材：《數(shù)據(jù)結(jié)構(gòu)》（C語(yǔ)言版） 朱站立編著 西安交通大學(xué)出版社

試卷結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)部分，100分）

試卷題型比例：

選擇題 約50%

填空題 約30%

計(jì)算分析算法題 約20%