2020年云南省專升本《數據結構》考試大綱

一、考試內容概述

(一)基本理論知識

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

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

3．棧和隊列的定義、特點、表示方法和實現。

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

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

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

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

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

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

(二)基本技能

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

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

3．能根據要求用類C語言編寫一些經典、常用算法。

二、考試形式

滿分：150分(單科成績)。

考試時間：120分鐘。

三、試題難易程度分布

較易試題約占50％

中等試題約占30％

較難試題約占20％

四、內容比例

第一章  緒論約占5％

第二章線性表約占10％

第三章  棧和隊列約占15％

第四章  串約占5％

第五章  數組和廣義表約占5％

第六章  樹和二叉樹約占15％

 4．了解二叉樹線索化的實質及線索化的過程。

5．了解樹的存儲結構，理解樹和森林轉換為二叉樹的方法。

6．掌握樹的路徑長度和樹的帶權路徑長度的計算方法， Huffman樹的構造方法和Huffman編碼。

第七章  圖

1．了解圖的定義。

2.  了解圖的基本術語：圖及無向圖、有向圖、網、子圖、連通圖、強連通圖、頂點的度、入度、出度、頂點問路徑、路徑長度、環(huán)。

3．理解圖的兩種存儲結構：鄰接矩陣和鄰接表(含逆鄰接表)。

4．掌握遍歷圖的兩種方法：深度優(yōu)先搜索和廣度優(yōu)先搜索遍歷圖的算法及其時間復雜度。

5．理解生成樹、最小生成樹的概念，掌握最小生成樹的構造過程(Prim算法和Kmskal算法)及其時間復雜度。

6．掌握拓撲排序的方法及最短路徑的計算。

7．掌握求最短路徑問題的Dijkstra算法，了解Floyd算法。

第八章  查  找

1．了解查找、關鍵字、平均查找長度等概念。

2．靜態(tài)查找表：掌握順序查找(設哨兵)、折半查找算法及其效率(最壞和平均查找長度)分析，了解分塊查找算法及其效率分析。

3．動態(tài)查找表：掌握二叉排序樹的定義、構造過程及其查找算法和效率分析，掌握平衡二叉樹的定義和其構造過程。

4．了解哈希表的特點，掌握構造哈希函數的方法(除留余數法等)，掌握處理沖突的方法及效率分析。

第九章  內部排序

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

2．插人排序：掌握直接插入、折半插入排序算法和希爾排序的思想。

3．快速排序：掌握起泡排序的算法和快速排序的思想。

4．選擇排序：掌握簡單的選擇排序的算法和堆的定義、堆排序的思想。

5．理解歸并排序的思想、基數排序的思想及特點。

6．了解各種內部排序方法的比較。