《 數據結構 》科目考試大綱
一、考試的基本要求
《數據結構》課程是計算機科學與技術專業(yè)的必修專業(yè)基礎課。這門課程的主要特點是實踐性很強,不僅要學習基本理論知識,更要注重實踐能力,通過實踐驗證算法的正確性,掌握和鞏固所學理論知識。設立本門課程的目的是通過學習，使學生學會分析研究數據結構的特性，以便為應用涉及的數據選擇適當的邏輯結構、存儲結構及相應的算法，并初步了解對算法的時間分析和空間分析技術。另一方面，通過對本課程算法設計和實踐的訓練，還應培養(yǎng)學生的數據抽象能力和程序設計的能力，為后續(xù)課程，特別是軟件開發(fā)設計課程打下堅實的知識基礎。
二、考試的范圍和內容
考核知識點一：數據結構與算法的概述
本章目的是介紹數據結構中常用的基本概念和術語以及學習數據結構的意義。本章要了解數據的抽象類型定義。理解算法在實際問題中的應用。重點掌握各種基本概念和術語、算法描述和分析的方法
考核要求：
識記：運算的概念、存儲結構和運算實現、算法分析
掌握：數據、數據元素、數據項、數據類型、數據結構、抽象數據類型
應用：算法及其描述
考核知識點二：線性表
本章的目的是介紹線性表的邏輯結構和各種存儲表示方法，以及定義在邏輯結構上的各種基本運算及其在存儲結構上如何實現這些基本運算。要求在熟悉這些內容的基礎上，能夠針對具體應用問題的要求和性質，選擇合適的存儲結構設計出相應的有效算法，解決與線性表相關的實際問題。
考核要求：
識記：線性結構的概念、線性表的概念
掌握：線性表的鏈式存儲結構、順序表與鏈表的比較
應用：線性表的順序存儲結構，插入、刪除和定位運算在單鏈表上的實現
考核知識點三：棧和隊列
本章的目的是介紹棧和隊列的邏輯結構定義及在兩種存儲結構上如何實現棧和隊列的基本運算。要求在掌握棧和隊列的特點的基礎上，懂得在什么樣的情況下使用?；蜿犃?。
考核要求：
識記：棧的定義、隊列的定義
掌握：棧的順序實現、棧的鏈接實現、隊列的順序實現
應用：循環(huán)隊的組織方法及在其上進行人隊、出隊運算的方法和隊滿、隊空的條件。
考核知識點四：串
本章的目的是介紹串的邏輯結構、存儲結構及其串上的基本運算。本章重點是掌握串的基本概念和三種表示方法。
考核要求：
識記：串的定義
掌握：串的定長順序實現
考核知識點五：數組與廣義表
本章的目的是介紹多維數組的邏輯結構特征及其存儲方式，特殊矩陣和稀疏矩陣的壓縮存儲方法及廣義表的概念，要求熟悉這些內容。
考核要求：
識記：數組元素地址的計算、廣義表的特點和結構
掌握：特殊矩陣的壓縮存儲
考核知識點六：樹和二叉樹
本章的目的是介紹二叉樹的定義、性質、存儲結構、遍歷、線索化，樹的定義、存儲結構、遍歷、樹和森林的轉換及赫夫曼樹及其赫夫曼編碼等內容。
考核要求：
識記：樹形結構的基本概念和術語、樹和森林、二叉樹的定義、二叉樹的順序存儲結構
掌握：二叉樹的鏈式存儲結構、哈夫曼樹的概念、構造哈夫曼樹的方法
應用：二叉樹的遍歷
考核知識點七：圖
本章的目的是介紹圖的基本概念、兩種常用的存儲結構、兩種遍歷方法以及圖的應用算法。本章重點是掌握圖的兩種存儲結構上實現的遍歷算法。難點是圖的應用算法：最小生成樹，求最短路徑以及拓撲排序。只要求掌握這些算法的基本思想及時間性能。
考核要求：
識記：樹形結構的基本概念和術語、樹和森林
掌握：圖的遍歷，拓撲排序、關鍵路徑、圖的概念、圖的存儲結構最小生成樹
應用：Prime算法、迪杰斯特拉方法的基本思想
考核知識點八： 查找
本章的目的是介紹線性表、樹和哈希表的查找方法、算法實現以及各種查找方法的時間性能(平均查找長度)分析。重點掌握順序查找、折半查找、二叉排序樹和哈希表查找的基本思想和算法實現。難點是二叉排序樹上的刪除算法。
考核要求：
識記：查找表的基本概念
掌握：靜態(tài)查找表的實現、二叉排序樹的查找算法及其基本思想
應用：哈希表、在開散列表上實現查找、插入和刪除運算的思想和算法
考核知識點九： 排序
本章的目的是介紹五類內部排序方法的基本思想、排序過程、算法實現、時間和空間性能的分析以及各種排序方法的比較和選擇。重點掌握快速排序、堆排序、歸并排序和基數排序的基本思想和排序過程。難點是這四類排序算法的實現。
考核要求：
識記：排序的基本概念、歸并排序
掌握：堆的定義、堆的調整方法和“篩選”過程，建堆的方法、冒泡排序算法、直接選擇排序基本思想
應用：直接插入排序的算法和性能、折半插入排序算法、快速排序的算法和性能
三、考試題型和分値結構
總分值為100分。要求考試題型必須在五種及以上，難度適中，考試主要為以下幾種題型。其中客觀題包括單項選擇題、填空題、判斷題，分值約占50%，主觀題包括簡答題，綜合應用題，分值約占50%。具體題型分布如下：
1、單項選擇題
2、填空題
3、判斷題
4、簡答題
5、綜合應用題
四、考試形式
筆試(閉卷)。
五、考試時間
90分鐘
六、主要參考書目
1、李春葆.《數據結構教程》(第五版)，北京：清華大學出版社，2017年7月。
2、李春堡.《數據結構教程(第五版)學習指導》，北京：清華大學出版社，2017年7月。
3、李春堡.《數據結構習題》，北京：清華大學出版社，2017年7月。
4、王海艷.《數據結構(C語言)》，北京：人名郵電出版社，2017年7月。
