云南省普高專(zhuān)升本專(zhuān)業(yè)課《數(shù)據(jù)結(jié)構(gòu)》考試大綱

一、考試內(nèi)容概述

（一）基本理論知識(shí)

1．?dāng)?shù)據(jù)結(jié)構(gòu)的基本概念和基本術(shù)語(yǔ)，算法的描述，算法的時(shí)間復(fù)雜度和空間復(fù)雜度分析。

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

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

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

5．?dāng)?shù)組的定義、運(yùn)算和存儲(chǔ)、稀疏矩陣的壓縮存儲(chǔ)、廣義表的定義和基本操作。

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

7．圖的定義和常用術(shù)語(yǔ)、圖的存儲(chǔ)結(jié)構(gòu)及其遍歷操作，求最小生成樹(shù)、最短路徑的算法，拓?fù)渑判颉?/p>

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

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

（二）基本技能

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

2．能分析算法所實(shí)現(xiàn)的功能、運(yùn)行結(jié)果和時(shí)間、空間復(fù)雜度。

3．能根據(jù)要求用類(lèi)C語(yǔ)言編寫(xiě)一些經(jīng)典、常用算法。

二、考試形式

考試采用閉卷、答卷的考試方式。

滿(mǎn)分：150分（單科成績(jī)）

考試時(shí)間：120分鐘。

變更，從2015年開(kāi)始

考試形式：

考試采用局域網(wǎng)計(jì)算機(jī)化考試（機(jī)考）。

滿(mǎn)分：150分（單科成績(jī)）。

考試時(shí)間：120分鐘。

三、試題難易程度分布

較易試題：約占50%

中等試題：約占30%

較難試題：約占20%

四、題型及題型分值分布

單選題：約占20%

多選題：約占10%

取消：填空題：約占15%

算法閱讀題：約占10%

綜合題：約占30%

程序設(shè)計(jì)題：約占15%

變更：從2015年開(kāi)始，考試采用局域網(wǎng)計(jì)算機(jī)化考試（機(jī)考），取消填空題，分值將在要考的題型中作適當(dāng)調(diào)整，可參考?xì)v年真題

五、內(nèi)容比例

第一章 緒論：約占5%

第二章 線(xiàn)性表：約占10%

第三章 棧和隊(duì)列：約占15%

第四章 串：約占5%

第五章 數(shù)組和廣義表：約占5%

第六章 樹(shù)和二叉樹(shù)：約占15%

第七章 圖：約占15%

第八章 查找：約占15%

第九章 內(nèi)部排序：約占15%

考試內(nèi)容及要求

第一章 緒論

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)等基本概念。2．理解抽象數(shù)據(jù)類(lèi)型的定義、表示和實(shí)現(xiàn)方法。3．理解算法的定義、算法的特性，掌握加何用類(lèi)C語(yǔ)言來(lái)描述算法。4．理解算法設(shè)計(jì)的基本要求，掌握計(jì)算語(yǔ)句頻度和估算算法時(shí)間復(fù)雜度的方法。

第二章 線(xiàn)性表

1．了解線(xiàn)性表的定義和操作。2．掌握順序存儲(chǔ)線(xiàn)性表的實(shí)現(xiàn)和常用運(yùn)算：結(jié)點(diǎn)的插入、刪除等，并掌握其效率分析方法。3．掌握鏈?zhǔn)酱鎯?chǔ)線(xiàn)性表，帶表頭結(jié)點(diǎn)和不帶表頭結(jié)點(diǎn)的單鏈表的結(jié)點(diǎn)插入、刪除操作，建立單鏈表的方法。4．理解循環(huán)鏈表和雙向鏈表的實(shí)現(xiàn)方法，了解其插入，刪除等基本操作。

第三章 棧和隊(duì)列

1．了解棧和認(rèn)列的定義，理解各自的特點(diǎn)，掌握棧的項(xiàng)序存儲(chǔ)結(jié)構(gòu)，理解循環(huán)隊(duì)列存儲(chǔ)方法。2．掌握棧和隊(duì)列的主要運(yùn)算：入棧、出棧、入隊(duì)、出對(duì)。3．能運(yùn)用棧和對(duì)列解決一些經(jīng)典問(wèn)題，如：數(shù)制轉(zhuǎn)換、表達(dá)式求值、樹(shù)的按層次遍歷、圖的廣度優(yōu)先遍歷等。

第四章 串

1．了解串的定義、空串、空格串的概念。2．了解串的基本操作。3．了解串的順序存儲(chǔ)結(jié)構(gòu)及在順序存儲(chǔ)結(jié)構(gòu)下基本操作的實(shí)現(xiàn)。4．理解串的模式匹配算法。

第五章 數(shù)組和廣義表

1．理解數(shù)組的項(xiàng)序存儲(chǔ)結(jié)構(gòu)。2．理解二維數(shù)組的按行存儲(chǔ)和數(shù)組元素的地址計(jì)算公式。3．理解矩陣的壓縮存儲(chǔ)、特殊矩陣的表示。4．了解廣義表的定義和基本操作。

第六章 樹(shù)和二叉樹(shù)

1．了解樹(shù)的定義和基本術(shù)語(yǔ)口2．掌握二叉樹(shù)（完全二叉樹(shù)、滿(mǎn)二叉樹(shù)）的定義和性質(zhì)，理解二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)，掌握二叉樹(shù)的二叉鏈表表示法。3．掌握二叉樹(shù)遍歷的遞歸算法，理解二叉樹(shù)中序遍歷的非遞歸算法，掌握根據(jù)先序遍歷序列建立二叉樹(shù)的遞歸算法。4．了解二叉樹(shù)索化的實(shí)質(zhì)及線(xiàn)索化的過(guò)程。5．了解樹(shù)的存儲(chǔ)結(jié)構(gòu)，理解樹(shù)和森林轉(zhuǎn)換為二叉樹(shù)的方法。6．掌握樹(shù)的路徑長(zhǎng)度和樹(shù)的帶權(quán)路徑長(zhǎng)度的計(jì)算方法，Huffman樹(shù)的構(gòu)造方法和Huffman編碼。

第七章 圖

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)先搜索和廣度優(yōu)先搜索遍歷圖的算法及其時(shí)間復(fù)雜度。5．理解生成樹(shù)、最小生成樹(shù)的概念，掌握最小生成樹(shù)的構(gòu)造過(guò)程（Prim的算法和Kruskal算法）及其時(shí)間復(fù)雜度。6．掌握拓?fù)渑判虻姆椒白疃搪窂降挠?jì)算。7．掌握求最短路徑問(wèn)題的Dijkstra算法，了解F1oyd算法.

第八章 查找

1．了解查找、關(guān)鍵字、平均查找長(zhǎng)度等概念。2．靜態(tài)查找表：掌握順序查找（設(shè)哨兵）、折半查找算法及其效率（最壞和平均查找長(zhǎng)度）分析，了解分塊查找算法及其效率分析。3．動(dòng)態(tài)查找表：掌握二叉排序樹(shù)的定義、構(gòu)造過(guò)程及其查找算法和效率分析，掌握平衡二叉樹(shù)的定義和其構(gòu)造過(guò)程。4．了解哈希表的特點(diǎn)，掌握構(gòu)造哈希函數(shù)的方法（除留余數(shù)法等），掌握處理沖突的方法及效率分析。

第九章 內(nèi)部排序

1．了解排序的目的、分類(lèi)和排序方法的穩(wěn)定性的定義。2．插入排序：掌握直接插入、折半插入排序算法和希爾排序的思想。

3．快速排序：掌握起泡排序的算法和快速排序的思想。4．選擇排序：掌握簡(jiǎn)單的選擇排序的算法和堆的定義，堆排序的思想。5．理解歸并排序的思想、基數(shù)排序的思想及特點(diǎn)。6．了解各種內(nèi)部排序方法的比較。