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

一、考試目的與要求

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

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

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

二、參考書目

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

三、考試形式和試卷結(jié)構(gòu)

1、試卷滿分及考試時間

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

2、答題方式

答題方式為閉卷、筆試。試卷由試題、答題紙組成，題目的答案必須寫在答題紙上?？忌坏脭y帶具有存儲功能的計算器。

3、試卷結(jié)構(gòu)

內(nèi)容包括基本概念、復(fù)雜度計算、線性表、堆棧、隊列、樹、散列查找、圖、排序等內(nèi)容。題型包括選擇題、填空題、簡答題、算法設(shè)計題等。

四、考試內(nèi)容

（一）基本概念與復(fù)雜度計算

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

2.掌握基本的數(shù)據(jù)處理原理和方法的基礎(chǔ)上，能夠?qū)λ惴ㄟM行設(shè)計與分析。

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

（二）線性表

1.理解線性表的定義和線性表的順序、鏈式存儲結(jié)構(gòu)。

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

3.熟悉線性表算法設(shè)計。

（三）棧和隊列

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

2.熟練掌握棧在非遞歸和遞歸算法中的應(yīng)用。

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

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

（四）樹

1．熟悉樹的概念和樹的各種表示、二叉樹的定義、性質(zhì)、存儲結(jié)構(gòu)和生成算法。

2.熟悉一般樹的存儲結(jié)構(gòu)、樹和森林之間的相互轉(zhuǎn)換及樹與森林遍歷。

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

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

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

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

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

（五）圖

1．理解圖的定義和基本術(shù)語、圖的存儲結(jié)構(gòu)，主要指鄰接矩陣和鄰接表。

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

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

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

5.理解最小生成樹和最短路的生活應(yīng)用。

（六）查找

1．理解查找的有關(guān)概念、順序查找和二分查找、索引查找和分塊查找，散列的概念。

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

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

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

（七）排序

1.理解外部排序。

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

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

4.理解內(nèi)部排序算法的應(yīng)用。