浙江財(cái)經(jīng)大學(xué)

《數(shù)據(jù)結(jié)構(gòu)》考試大綱

一、考試目的與要求

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

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

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

二、參考書目

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

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

1、試卷滿分及考試時(shí)間

本試卷滿分為150分，考試時(shí)間為180分鐘。

2、答題方式

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

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

內(nèi)容包括基本概念、復(fù)雜度計(jì)算、線性表、堆棧、隊(duì)列、樹、散列查找、圖、排序等內(nèi)容。

(1)選擇題(30分)

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

(3)填空題(30分)

(4)簡答題(40分)

(5)算法設(shè)計(jì)題(30分)

四、考試內(nèi)容

(一)基本概念與復(fù)雜度計(jì)算

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

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

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

(二)線性表

1. 理解線性表的定義和線性表的順序、鏈?zhǔn)酱鎯�結(jié)構(gòu)。

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

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

(三)棧和隊(duì)列

1.理解棧的定義、順序、鏈?zhǔn)酱鎯�、進(jìn)出棧運(yùn)算及雙棧操作。

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

3. 隊(duì)列的定義、順序、鏈?zhǔn)酱鎯Α⑷腙?duì)和出隊(duì)運(yùn)算。

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

(四)樹

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

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

3. 熟練掌握二叉樹的遍歷運(yùn)算。

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

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

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

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

(五)圖

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

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

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

4. 理解拓?fù)渑判虻母拍罴八惴ā㈥P(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)定性和時(shí)間復(fù)雜度。

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