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

一、考試目的與要求

《數(shù)據(jù)結構》是人工智能、軟件工程、信息管理與信息系統(tǒng)等本科專業(yè)學生開設的學科必修課程，是電子信息類專業(yè)碩士研究生入學考試的科目之一。

考試目的：《數(shù)據(jù)結構》是計算機程序設計的重要理論技術基礎，是電子信息類的核心課程�？荚嚵η蠓从畴娮有畔�專業(yè)碩士學位的特點，科學、公平、準確、規(guī)范地測評考生的基本素質和綜合能力，選拔具有進一步深造的基本素質和培養(yǎng)潛力的學生，培養(yǎng)能解決理論問題與實際問題的高層次、應用型、復合型的專業(yè)人才。

考試要求：要求學生能系統(tǒng)掌握《數(shù)據(jù)結構》的基本概念、基本原理和方法，能夠運用所學的基本原理和基本方法分析、判斷和解決有關理論問題和實際問題。

二、參考書目

《數(shù)據(jù)結構》(第二版)，何欽銘，徐鏡春，魏寶剛，楊棖著，陳越編，高等教育出版社，2016年。

三、考試形式和試卷結構

1、試卷滿分及考試時間

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

2、答題方式

答題方式為閉卷、筆試。試卷由試題、答題紙組成，題目的答案必須寫在答題紙上。考生不得攜帶具有存儲功能的計算器。

3、試卷結構

內容包括基本概念、復雜度計算、線性表、堆棧、隊列、樹、散列查找、圖、排序等內容。

(1)選擇題(30分)

(2)程序閱讀題(20分)

(3)填空題(30分)

(4)簡答題(40分)

(5)算法設計題(30分)

四、考試內容

(一)基本概念與復雜度計算

1. 理解數(shù)據(jù)結構的基本概念;掌握數(shù)據(jù)的邏輯結構、存儲結構及其差異，以及算法各種基本操作的實現(xiàn)。

2. 掌握基本的數(shù)據(jù)處理原理和方法的基礎上，能夠對算法進行設計與分析。

3. 掌握算法的時間復雜性和空間復雜性，能選擇合適的算法進行問題求解。

(二)線性表

1. 理解線性表的定義和線性表的順序、鏈式存儲結構。

2. 熟練掌握線性表的插入、刪除等運算的算法。

3. 熟悉線性表算法設計。

(三)棧和隊列

1.理解棧的定義、順序、鏈式存儲、進出棧運算及雙棧操作。

2. 熟練掌握棧在非遞歸和遞歸算法中的應用。

3. 隊列的定義、順序、鏈式存儲、入隊和出隊運算。

4.熟練掌握棧和隊列的基本操作算法和應用。

(四)樹

1.熟悉樹的概念和樹的各種表示、二叉樹的定義、性質、存儲結構和生成算法。

2. 熟悉一般樹的存儲結構、樹和森林之間的相互轉換及樹與森林遍歷。

3. 熟練掌握二叉樹的遍歷運算。

4. 理解二叉排序樹的定義、查找、插入、刪除和生成算法。

5.熟練掌握哈夫曼樹的定義和生成過程、哈夫曼編碼。

6. 理解平衡二叉樹的建樹、查找、插入和刪除。

7. 理解大頂堆、小頂堆。

(五)圖

1.理解圖的定義和基本術語、圖的存儲結構，主要指鄰接矩陣和鄰接表。

2. 熟練掌握圖的深度和廣度優(yōu)先搜索遍歷、產生圖的最小生成樹的普利姆算法和克魯斯卡爾算法。

3. 熟練掌握最短路徑的狄克斯特拉算法和佛洛伊德算法。

4. 理解拓撲排序的概念及算法、關鍵路徑的概念及算法。

5. 理解最小生成樹和最短路的生活應用。

(六)查找

1.理解查找的有關概念、順序查找和二分查找、索引查找和分塊查找，散列的概念。

2. 掌握構造散列函數(shù)，處理沖突的方法，散列表的插入和查找算法。

3. 了解B樹的定義及查找、插入和刪除關鍵字的過程。

4. 理解查找在不同數(shù)據(jù)環(huán)境下的應用。

(七)排序

1.理解外部排序。

2.熟練掌握直接插入排序、希爾排序、直接選擇排序、堆排序、冒泡排序、快速排序、歸并排序和基數(shù)排序。

3. 理解各類排序的穩(wěn)定性和時間復雜度。

4. 理解內部排序算法的應用。