北京工商大學

《數(shù)據(jù)結構》考試大綱

一、考查目標

1.掌握數(shù)據(jù)結構的基本概念、基本原理和基本方法。

2.掌握數(shù)據(jù)的邏輯結構、存儲結構及基本操作的實現(xiàn)，能夠對算法進行基本的時間復雜度與空間復雜度的分析。

3.能夠利用數(shù)據(jù)結構基本原理和方法進行問題的分析與求解，具備采用C或C++語言設計與實現(xiàn)算法的能力。

二、考試形式和試卷結構

1、試卷滿分及考試時間

本試卷滿分為150分，考試時間為180分鐘

2、答題方式

答題方式為閉卷、筆試

3、試卷題型結構

單項選擇題

判斷題

簡答題/填空題

綜合應用題

算法設計題

三、考試范圍及基本要求

(一)　緒論

【內(nèi)容】

數(shù)據(jù)結構的基本概念和術語，數(shù)據(jù)抽象，算法的描述和算法分析。

【要求】

掌握基本概念和術語，初步學會算法的分析度量。

(二)　線性表

【內(nèi)容】

線性表的邏輯結構，線性表的順序存儲結構，線性表的鏈式存儲結構，循環(huán)鏈表，雙向鏈表。線性表的應用。

【要求】

1. 了解線性表的邏輯結構特性是數(shù)據(jù)元素之間存在著線性關系，在計算機中表示這種關系的不同方法得到兩類不同的存儲結構。

2. 熟練掌握這兩類存儲結構的描述方法，以及循環(huán)鏈表、雙向鏈表的特點等。

3. 熟練掌握線性表在順序存儲結構上實現(xiàn)的基本操作：插入、刪除等算法。

(三)　棧和隊列

【內(nèi)容】

棧的定義，棧的表示和實現(xiàn)，棧的順序存儲結構，應用舉例：表達式求值(*)。

隊列的定義，隊列的順序存儲結構(和棧類似結構及循環(huán)隊列)，鏈式存儲結構�？偨Y線性表靜態(tài)及動態(tài)的特點(包括棧和隊列)，并舉例說明在實際工作中的應用。

【要求】

1. 掌握棧和隊列這兩種數(shù)據(jù)結構的特點,懂得在什么樣的問題中應該利用哪種結構。

2. 熟練掌握在順序存儲結構上實現(xiàn)棧的基本運算,特別注意棧滿和�？盏臈l件及它們的描述。

3. 熟練掌握循環(huán)隊列和鏈隊列的基本運算,特別注意隊滿和隊空的描述方法。

4. 理解遞歸算法執(zhí)行過程中棧的狀態(tài)變化過程。

(四)　樹和二叉樹

【內(nèi)容】

二叉樹的定義及基本操作，二叉樹的性質(zhì)，二叉樹的存儲結構，二叉樹的遍歷。

樹的定義及存儲結構，森林與二叉樹的轉換，樹和森林的遍歷，哈夫曼樹及其應用。

【要求】

1. 熟練掌握二叉樹的結構特性,了解相應的證明方法。

2. 了解幾種特殊形態(tài)的二叉樹。

3. 熟悉二叉樹的各種存儲結構的特點及適用范圍。

4. 遍歷二叉樹是二叉樹各種運算的基礎,不僅要熟練掌握各種序遍歷的遞歸和非遞歸算法,還要了解遍歷過程中“棧”的狀態(tài),并能靈活運用遞歸遍歷算法實現(xiàn)二叉樹的其他各種運算。

5. 樹和森林(樹的存儲結構、遍歷方法;森林與二叉樹的轉換方法)。

6. 哈夫曼樹及哈夫曼編碼。

(五)　圖

【內(nèi)容】

圖的定義和術語，圖的存儲結構，圖的遍歷，深度優(yōu)先搜索，廣度優(yōu)先搜索，應用舉例：人工智能中的問題求解(*)。

無向圖的連通分量和生成樹，最小生成樹，有向無環(huán)圖及其應用：最短路徑，拓撲排序(*)，關鍵路徑(*)。

【要求】

1. 熟悉圖的各種存儲結構及其構造算法，了解實際問題的求解效率與采用何種存儲結構和算法有密切聯(lián)系。

2. 熟練掌握圖的遍歷的邏輯定義、深度優(yōu)先搜索和廣度優(yōu)先搜索的算法。在學習中應注意圖的遍歷算法與二叉樹的遍歷算法之間的類似和差異。

3. 應用圖的遍歷算法求解各種簡單路徑問題。

4. 理解參考書中討論的各種圖的算法，掌握其主要數(shù)據(jù)結構的變化情況。

(六)　查找

【內(nèi)容】

靜態(tài)查找表，二叉排序樹和平衡二叉樹(*)，散列(Hash)表。

【要求】

1. 順序表和有序表的查找方法及其平均查找長度的計算方法。

2. 靜態(tài)查找樹的構造方法和查找算法,理解靜態(tài)查找樹和折半查找的關系。

3. 熟練掌握二叉排序樹的構造和查找方法。

4. 熟練掌握散列表的構造方法，深刻理解散列表與其它結構的表的實質(zhì)性的差別。

6. 掌握按定義計算各種查找方法在等概率情況下查找成功時的平均查找長度。

(七)　內(nèi)部排序

【內(nèi)容】

冒泡排序，插入排序，快速排序，選擇排序，堆排序，歸并排序。

【要求】

1. 了解排序的定義和各種排序方法的特點。熟悉各種方法的排序過程及其依據(jù)的原則。

2. 掌握各種排序方法的時間復雜度的分析方法。能從“關鍵字間的比較次數(shù)”分析排序算法的平均情況和最壞情況的時間性能(*)。

3. 理解排序方法“穩(wěn)定”或“不穩(wěn)定”的含義，弄清楚在什么情況下要求應用的排序方法必須是穩(wěn)定的。