一、考試的基本要求

《數(shù)據(jù)結(jié)構(gòu)》課程是計算機(jī)科學(xué)與技術(shù)專業(yè)的必修專業(yè)基礎(chǔ)課。這門課程的主要特點(diǎn)是實(shí)踐性很強(qiáng),不僅要學(xué)習(xí)基本理論知識,更要注重實(shí)踐能力,通過實(shí)踐驗(yàn)證算法的正確性,掌握和鞏固所學(xué)理論知識。設(shè)立本門課程的目的是通過學(xué)習(xí)，使學(xué)生學(xué)會分析研究數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)及相應(yīng)的算法，并初步了解對算法的時間分析和空間分析技術(shù)。另一方面，通過對本課程算法設(shè)計和實(shí)踐的訓(xùn)練，還應(yīng)培養(yǎng)學(xué)生的數(shù)據(jù)抽象能力和程序設(shè)計的能力，為后續(xù)課程，特別是軟件開發(fā)設(shè)計課程打下堅實(shí)的知識基礎(chǔ)。

二、考試的范圍和內(nèi)容

考核知識點(diǎn)一：數(shù)據(jù)結(jié)構(gòu)與算法的概述

本章目的是介紹數(shù)據(jù)結(jié)構(gòu)中常用的基本概念和術(shù)語以及學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義。本章要了解數(shù)據(jù)的抽象類型定義。理解算法在實(shí)際問題中的應(yīng)用。重點(diǎn)掌握各種基本概念和術(shù)語、算法描述和分析的方法

考核要求：

識記：運(yùn)算的概念、存儲結(jié)構(gòu)和運(yùn)算實(shí)現(xiàn)、算法分析

掌握：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)、抽象數(shù)據(jù)類型

應(yīng)用：算法及其描述

考核知識點(diǎn)二：線性表

本章的目的是介紹線性表的邏輯結(jié)構(gòu)和各種存儲表示方法，以及定義在邏輯結(jié)構(gòu)上的各種基本運(yùn)算及其在存儲結(jié)構(gòu)上如何實(shí)現(xiàn)這些基本運(yùn)算。要求在熟悉這些內(nèi)容的基礎(chǔ)上，能夠針對具體應(yīng)用問題的要求和性質(zhì)，選擇合適的存儲結(jié)構(gòu)設(shè)計出相應(yīng)的有效算法，解決與線性表相關(guān)的實(shí)際問題。

考核要求：

識記：線性結(jié)構(gòu)的概念、線性表的概念

掌握：線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)、順序表與鏈表的比較

應(yīng)用：線性表的順序存儲結(jié)構(gòu)，插入、刪除和定位運(yùn)算在單鏈表上的實(shí)現(xiàn)

考核知識點(diǎn)三：棧和隊列

本章的目的是介紹棧和隊列的邏輯結(jié)構(gòu)定義及在兩種存儲結(jié)構(gòu)上如何實(shí)現(xiàn)棧和隊列的基本運(yùn)算。要求在掌握棧和隊列的特點(diǎn)的基礎(chǔ)上，懂得在什么樣的情況下使用?；蜿犃?。

考核要求：

識記：棧的定義、隊列的定義

掌握：棧的順序?qū)崿F(xiàn)、棧的鏈接實(shí)現(xiàn)、隊列的順序?qū)崿F(xiàn)

應(yīng)用：循環(huán)隊的組織方法及在其上進(jìn)行人隊、出隊運(yùn)算的方法和隊滿、隊空的條件。

考核知識點(diǎn)四：串 本章的目的是介紹串的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其串上的基本運(yùn)算。

本章重點(diǎn)是掌握串的基本概念和三種表示方法。

考核要求：

識記：串的定義

掌握：串的定長順序?qū)崿F(xiàn)

考核知識點(diǎn)五：數(shù)組與廣義表

本章的目的是介紹多維數(shù)組的邏輯結(jié)構(gòu)特征及其存儲方式，特殊矩陣和稀疏矩陣的壓縮存儲方法及廣義表的概念，要求熟悉這些內(nèi)容。

考核要求：

識記：數(shù)組元素地址的計算、廣義表的特點(diǎn)和結(jié)構(gòu) 掌握：特殊矩陣的壓縮存儲

考核知識點(diǎn)六、樹和二叉樹

本章的目的是介紹二叉樹的定義、性質(zhì)、存儲結(jié)構(gòu)、遍歷、線索化，樹的定義、存儲結(jié)構(gòu)、遍歷、樹和森林的轉(zhuǎn)換及赫夫曼樹及其赫夫曼編碼等內(nèi)容。

考核要求：

識記：樹形結(jié)構(gòu)的基本概念和術(shù)語、樹和森林、二叉樹的定義、二叉樹的順序存儲結(jié)構(gòu)

掌握：二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)、哈夫曼樹的概念、構(gòu)造哈夫曼樹的方法

應(yīng)用：二叉樹的遍歷

考核知識點(diǎn)七、圖

本章的目的是介紹圖的基本概念、兩種常用的存儲結(jié)構(gòu)、兩種遍歷方法以及圖的應(yīng)用算法。本章重點(diǎn)是掌握圖的兩種存儲結(jié)構(gòu)上實(shí)現(xiàn)的遍歷算法。難點(diǎn)是圖的應(yīng)用算法：最小生成樹，求最短路徑以及拓?fù)渑判?。只要求掌握這些算法的基本思想及時間性能。

考核要求：

識記：樹形結(jié)構(gòu)的基本概念和術(shù)語、樹和森林

掌握：圖的遍歷，拓?fù)渑判?、關(guān)鍵路徑、圖的概念、圖的存儲結(jié)構(gòu)最小生成樹

應(yīng)用：Prime算法、迪杰斯特拉方法的基本思想

考核知識點(diǎn)八、 查找

本章的目的是介紹線性表、樹和哈希表的查找方法、算法實(shí)現(xiàn)以及各種查找方法的時間性能（平均查找長度）分析。重點(diǎn)掌握順序查找、折半查找、二叉排序樹和哈希表查找的基本思想和算法實(shí)現(xiàn)。難點(diǎn)是二叉排序樹上的刪除算法。

考核要求：

識記：查找表的基本概念

掌握：靜態(tài)查找表的實(shí)現(xiàn)、二叉排序樹的查找算法及其基本思想

應(yīng)用：哈希表、在開散列表上實(shí)現(xiàn)查找、插入和刪除運(yùn)算的思想和算法

考核知識點(diǎn)九、 排序

本章的目的是介紹五類內(nèi)部排序方法的基本思想、排序過程、算法實(shí)現(xiàn)、時間和空間性能的分析以及各種排序方法的比較和選擇。重點(diǎn)掌握快速排序、堆排序、歸并排序和基數(shù)排序的基本思想和排序過程。難點(diǎn)是這四類排序算法的實(shí)現(xiàn)。

考核要求：

識記：排序的基本概念、歸并排序

掌握：堆的定義、堆的調(diào)整方法和“篩選”過程，建堆的方法、冒泡排序算法、直接選擇排序基本思想

應(yīng)用：直接插入排序的算法和性能、折半插入排序算法、快速排序的算法和性能

三、考試題型和分値結(jié)構(gòu)

總分值為100分。要求考試題型必須在五種及以上，難度適中，考試主要為以下幾種題型。其中客觀題包括單項選擇題、填空題、判斷題，分值約占50%，主觀題包括簡答題，綜合應(yīng)用題，分值約占50%。具體題型分布如下：

1、單項選擇題

2、填空題

3、判斷題

4、簡答題

5、綜合應(yīng)用題

四、考試形式

筆試（閉卷）。

五、考試時間

90分鐘

六、主要參考書目

1、李春葆.《數(shù)據(jù)結(jié)構(gòu)教程》（第五版），北京：清華大學(xué)出版社，2017年7月.

2、李春堡.《數(shù)據(jù)結(jié)構(gòu)教程（第五版）學(xué)習(xí)指導(dǎo)》，北京：清華大學(xué)出版社，2017年7月.

3、李春堡.《數(shù)據(jù)結(jié)構(gòu)習(xí)題》，北京：清華大學(xué)出版社，2017年7月.

4、王海艷.《數(shù)據(jù)結(jié)構(gòu)（C語言）》，北京：人名郵電出版社，2017年7月.