北京科技大學

北京科技大學數(shù)據(jù)結(jié)構(gòu)考試大綱

第1 章 緒論

考試內(nèi)容：

數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計中的作用;數(shù)據(jù)結(jié)構(gòu)的主要內(nèi)容;數(shù)據(jù)結(jié)構(gòu)的基本概念;算法及算法分析。

考試要求：

1. 理解數(shù)據(jù)結(jié)構(gòu)的基本概念;算法設(shè)計;掌握算法的時間和空間復(fù)雜度。

2. 掌握數(shù)據(jù)結(jié)構(gòu)的定義;算法的描述方法。

第2章 線性表

考試內(nèi)容：

線性表的邏輯結(jié)構(gòu);線性表的順序存儲結(jié)構(gòu)及實現(xiàn);線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn);順序表和鏈表的比較。

考試要求：

1. 掌握線性表的概念;線性表的順序存儲結(jié)構(gòu)、鏈式存儲結(jié)構(gòu)及其常用算法。

2. 掌握線性表的邏輯結(jié)構(gòu);線性表的存儲結(jié)構(gòu)及操作的實現(xiàn);鏈式存儲結(jié)構(gòu)及其常用算法;雙向循環(huán)鏈表。

第3章 棧和隊列

考試內(nèi)容：

棧的定義，表示及實現(xiàn);表達式求值;棧與遞歸過程;隊列的定義、表示及實現(xiàn).

考試要求：

1. 理解堆棧和隊列的概念;遞歸的定義;循環(huán)隊列和鏈隊列的基本運算。

2. 掌握遞歸的編程實現(xiàn);循環(huán)隊列和鏈隊列的基本運算。

第4章 字符串和多維數(shù)組

考試內(nèi)容：

字符串;多維數(shù)組;矩陣的壓縮存儲

考試要求：

1. 了解串的邏輯結(jié)構(gòu)，存儲結(jié)構(gòu)。

2.掌握串定義和存儲方法;串的操作。

第5章 樹和二叉樹

考試內(nèi)容

樹的邏輯結(jié)構(gòu);樹的存儲結(jié)構(gòu);二叉樹的邏輯結(jié)構(gòu);二叉樹的存儲結(jié)構(gòu)及實現(xiàn); 二叉樹遍歷的非遞歸算法;樹、森林與二叉樹的轉(zhuǎn)換。

考試要求：

1.了解樹的基本概念;

2.理解二叉樹的性質(zhì)和存儲結(jié)構(gòu);掌握遍歷、構(gòu)造二叉樹和線索二叉樹;

3.理解樹的存儲結(jié)構(gòu)和遍歷;掌握集合的一種表示方法;

4.掌握哈夫曼樹及其應(yīng)用;

第6章 圖

考試內(nèi)容：

圖的邏輯結(jié)構(gòu);圖的存儲結(jié)構(gòu)及實現(xiàn);最小生成樹;最短路徑;有向無環(huán)圖及其應(yīng)用。

考試要求：

1.理解圖的基本概念;圖的存儲結(jié)構(gòu);

2.掌握圖的遍歷及應(yīng)用{最小生成樹，最短路徑等};拓撲排序和關(guān)鍵路徑。

第7章 查找技術(shù)

考試內(nèi)容

查找的基本概念、查找算法的性能;線性表的查找技術(shù);樹表的查找技術(shù);散列表的查找技術(shù)

考試要求

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

2.掌握二叉排序樹的構(gòu)造方法和二叉平衡樹的建立方法

3.掌握哈希表的構(gòu)造方法，哈希表在查找不成功時的平均查找長度的計算方法

第8章 排序技術(shù)

考試內(nèi)容：

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

考試要求：

1.掌握各類排序的原理和特征;

2. 掌握排序的各種算法實現(xiàn)和應(yīng)用