【導語】

879-數據結構考試大綱

一、緒論

考試內容

數據結構在程序設計中的作用；數據結構的主要內容；數據結構的基本概念；算法及算法分析。

考試要求

1、理解數據結構的基本概念；算法設計；掌握算法的時間和空間復雜度。

2、掌握數據結構的定義；算法的描述方法。

二、線性表

考試內容

線性表的邏輯結構；線性表的順序存儲結構及實現；線性表的鏈接存儲結構及實現；順序表和鏈表的比較。

考試要求

1、掌握線性表的概念；線性表的順序存儲結構、鏈式存儲結構及其常用算法。

2、掌握線性表的邏輯結構；線性表的存儲結構及操作的實現；鏈式存儲結構及其常用算法；雙向循環鏈表。

三、棧和隊列

考試內容

棧的定義，表示及實現；表達式求值；棧與遞歸過程；隊列的定義、表示及實現。

考試要求

1、理解堆棧和隊列的概念；遞歸的定義；循環隊列和鏈隊列的基本運算。

2、掌握遞歸的編程實現；循環隊列和鏈隊列的基本運算。

四、字符串和多維數組

考試內容

字符串；多維數組；矩陣的壓縮存儲

考試要求

1、了解串的邏輯結構，存儲結構。

2、掌握串定義和存儲方法；串的操作。

五、樹和二叉樹

考試內容

樹的邏輯結構；樹的存儲結構；二叉樹的邏輯結構；二叉樹的存儲結構及實現；二叉樹遍歷的非遞歸算法；樹、森林與二叉樹的轉換。

考試要求

1、了解樹的基本概念。

2、理解二叉樹的性質和存儲結構；掌握遍歷、構造二叉樹和線索二叉樹。

3、理解樹的存儲結構和遍歷；掌握集合的一種表示方法。

4、掌握哈夫曼樹及其應用。

六、圖

考試內容

圖的邏輯結構；圖的存儲結構及實現；最小生成樹；最短路徑；有向無環圖及其應用。

考試要求

1、理解圖的基本概念；圖的存儲結構。

2、掌握圖的遍歷及應用{最小生成樹，最短路徑等}；拓撲排序和關鍵路徑。

七、查找技術

考試內容

查找的基本概念、查找算法的性能；線性表的查找技術；樹表的查找技術；散列表的查找技術。

考試要求

1、掌握順序查找、折半查找和索引查找的方法。

2、掌握二叉排序樹的構造方法和二叉平衡樹的建立方法。

3、掌握哈希表的構造方法，哈希表在查找不成功時的平均查找長度的計算方法

八、排序技術

考試內容

排序的基本概念、排序算法的性能；插入排序；交換排序；選擇排序；歸并排序；分配排序；各種排序方法的比較。

考試要求：

1、掌握各類排序的原理和特征。

2、掌握排序的各種算法實現和應用。