一、考試內容及要求

　　(一)了解

　　1.數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、抽象數(shù)據(jù)類型等概念。

　　2.數(shù)據(jù)結構的基本概念;數(shù)據(jù)的邏輯結構及物理結構;算法的定義及特點。

　　3.線性表的定義及特點;在線性表上常進行的基本操作。

　　4.頭指針、頭結點及首元結點的概念及它們的區(qū)別;設置頭結點的好處。

　　5.棧和隊列的定義、特點、表示方法和實現(xiàn);入棧和出棧序列的對應關系;入隊和出隊序列的對應關系。

　　6.串的定義及其相關概念。

　　7.數(shù)組的定義、運算和存儲;特殊矩陣和稀疏矩陣的壓縮存儲;廣義表的定義和相關概念。

　　8.樹的定義、基本術語和存儲結構;二叉樹的定義和性質;二叉樹的存儲結構及其各種操作的基本原理;樹和森林的相關概念;Huffman樹和Huffman編碼。

　　9.圖的定義和常用術語。

　　10.查找表、關鍵字、查找操作、靜態(tài)查找、動態(tài)查找等查找相關概念。

　　11.排序的定義及相關概念;各種常用內部排序操作的一趟排序的概念。

　　(二)掌握

　　1.數(shù)據(jù)邏輯結構的分類;邏輯結構和物理結構的區(qū)別與聯(lián)系;物理存儲結構的分類及不同存儲結構的特點。

　　2.數(shù)據(jù)結構的二元組表示;算法設計的要求;算法的時間復雜度和空間復雜度分析。

　　3.線性表的順序和鏈式存儲結構;兩種不同存儲結構下常用操作算法的實現(xiàn)及復雜度分析;順序存儲結構和鏈式存儲結構的優(yōu)缺點。

　　4.循環(huán)鏈表、雙向鏈表及雙向循環(huán)鏈表的基本操作算法實現(xiàn)及這些特殊鏈表的應用;

　　5.棧和隊列的與線性表的關系;棧和隊列的共同點與不同點;棧和隊列在順序存儲和鏈式存儲時基本操作的算法實現(xiàn);棧和隊列的應用。

　　6.串與線性表的聯(lián)系與區(qū)別;串的存儲表現(xiàn)形式;串的常用操作及串操作的特點;空串和空格串的區(qū)別。串的模式匹配及求子串的基本原理。

　　7.數(shù)組存儲的特點和數(shù)組操作的特點;一維數(shù)組和二維數(shù)組中數(shù)據(jù)元素存儲地址的計算;特殊矩陣和稀疏矩陣的壓縮存儲時，一維存儲空間地址下標和其行號列標的對應關系;廣義表的嵌套定義;求解非空廣義表的表頭和表尾;求解廣義表的長度和深度。

　　8.二叉樹的特點及性質;二叉樹的存儲結構及其特點;二叉樹遍歷的基本原理;樹和森林與二叉樹的相互轉換;樹和森林的遍歷及與其對應二叉樹遍歷的關系;構建哈夫曼樹的基本原理及哈夫曼編碼。

　　9.圖的存儲結構及其遍歷操作;求最小生成樹、關鍵路徑、最短路徑的基本方法，拓撲排序的基本原理;最小生成樹的構造過程(Prim算法和Kmskal算法)。

　　10.各種查找方法的基本查找原理;每種查找的適用范圍及平均查找長度的分析;各種查找的特點;不同查找方法查找某一特定數(shù)據(jù)元素時的具體比較次數(shù);靜態(tài)查找與動態(tài)查找的特點;二叉排序樹與平衡二叉樹的特點;哈希函數(shù)的構造方法及沖突解決辦法。

　　11.各種常用內部排序方法基本實現(xiàn)原理;各種內排序算法的基本思想和算法的時間復雜度、空間復雜度分析，不同排序方法的比較。

　　(三)應用

　　1.能閱讀用類C語言編寫的算法。

　　2.能分析算法所實現(xiàn)的功能、運行結果和時間、空間復雜度。

　　3.能應用線性表的基本操作算法解決現(xiàn)實生活中的相關問題。

　　4.能應用棧和隊列解決現(xiàn)實生活中的相關問題。

　　5.能設計算法解決現(xiàn)實生活中字符串處理的問題。

　　6.能根據(jù)實際的特殊矩陣推算其壓縮存儲一維存儲空間地址下標與其元素的行號列標之間的對應關系，能計算對應元素的實際物理地址;能求解實際非空廣義表的表頭、表尾、長度和深度。

　　7.能利用樹和二叉樹設計算法解決現(xiàn)實生活中的相關問題;能針對實際數(shù)據(jù)進行哈夫曼編碼。

　　8.能應用圖的基本操作解決現(xiàn)實生活中的相關問題。

　　9.能針對實際查找記錄，選擇合適的查找算法進行數(shù)據(jù)查找。

　　10.能針對實際待排序記錄，選擇合適的排序方法進行數(shù)據(jù)排序操作，并能分析實際采用的排序算法的時間復雜度和空間復雜度。

　　11.能綜合應用數(shù)據(jù)結構的相關知識解決實際生活中的問題。

　　二、考試形式

　　考試采用閉卷、筆答的考試方式。

　　滿分：150分(單科成績)。

　　考試時間：120分鐘。

　　三、試題難易程度分布

　　較易試題 約占50%

　　中等試題 約占30%

　　較難試題 約占20%

　　四、題型及題型分值分布

　　判斷題 約占15%

　　單選題 約占35%

　　多選題 約占10%

　　算法閱讀與算法設計題 約占20%

　　綜合題 約占20%

　　五、章節(jié)內容占比

　　第一章 緒論 約占7%

　　第二章 線性表 約占15%

　　第三章 棧和隊列 約占15%

　　第四章 串 約占5%

　　第五章 數(shù)組和廣義表 約占8%

　　第六章 樹和二叉樹 約占20%

　　第七章 圖 約占10%

　　第八章 查找 約占10%

　　第九章 內部排序 約占10%