云南省普高專升本專業(yè)課《數(shù)據(jù)結構》考試大綱

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

（一）基本理論知識

1．數(shù)據(jù)結構的基本概念和基本術語，算法的描述，算法的時間復雜度和空間復雜度分析。

2．線性表的定義，在線性表上常進行的基本操作，這些操作在順序和鏈式存儲結構下的實現(xiàn)及復雜度分析。

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

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

5．數(shù)組的定義、運算和存儲、稀疏矩陣的壓縮存儲、廣義表的定義和基本操作。

6．樹德定義、基本術語和存儲結構，二叉樹的定義和性質(zhì)、二叉樹的存儲結構及其各種操作，Huffman和Huffman編碼。

7．圖的定義和常用術語、圖的存儲結構及其遍歷操作，求最小生成樹、最短路徑的算法，拓撲排序。

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

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

（二）基本技能

1．能閱讀用類C語言編寫的算法。

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

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

二、考試形式

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

滿分：150分（單科成績）

考試時間：120分鐘。

變更，從2015年開始

考試形式：

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

滿分：150分（單科成績）。

考試時間：120分鐘。

三、試題難易程度分布

較易試題：約占50%

中等試題：約占30%

較難試題：約占20%

四、題型及題型分值分布

單選題：約占20%

多選題：約占10%

取消：填空題：約占15%

算法閱讀題：約占10%

綜合題：約占30%

程序設計題：約占15%

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

五、內(nèi)容比例

第一章 緒論：約占5%

第二章 線性表：約占10%

第三章 棧和隊列：約占15%

第四章 串：約占5%

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

第六章 樹和二叉樹：約占15%

第七章 圖：約占15%

第八章 查找：約占15%

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

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

第一章 緒論

1．了解數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)對象、數(shù)據(jù)結構、邏輯結構、物理結構、元素、結點等基本概念。2．理解抽象數(shù)據(jù)類型的定義、表示和實現(xiàn)方法。3．理解算法的定義、算法的特性，掌握加何用類C語言來描述算法。4．理解算法設計的基本要求，掌握計算語句頻度和估算算法時間復雜度的方法。

第二章 線性表

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

第三章 棧和隊列

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

第四章 串

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

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

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

第六章 樹和二叉樹

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

第七章 圖

1．了解圖的定義。2．了解圖的基本術語：圖及無向圖、有向圖、網(wǎng)、子圖、連通圖、強連通圖、頂點的度、入度、出度、頂點間路徑、路徑長度、環(huán)。3．理解圖的兩種存儲結構：鄰接矩陣和鄰接表（含逆鄰接表）。4．掌握遍歷圖的兩種方法：深度優(yōu)先搜索和廣度優(yōu)先搜索遍歷圖的算法及其時間復雜度。5．理解生成樹、最小生成樹的概念，掌握最小生成樹的構造過程（Prim的算法和Kruskal算法）及其時間復雜度。6．掌握拓撲排序的方法及最短路徑的計算。7．掌握求最短路徑問題的Dijkstra算法，了解F1oyd算法.

第八章 查找

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

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

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

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