一、考試科目：數(shù)據(jù)結構
二、適用專業(yè)：計算機應用技術
三、參考書目
(1) 數(shù)據(jù)結構（C語言版），嚴蔚敏 吳偉民主編，2007，清華大學出版社。
四、考查目標
(1) 理解數(shù)據(jù)結構的基本概念；掌握數(shù)據(jù)的邏輯結構、存儲結構及其差異以及各種基本操作的實現(xiàn)；能夠選擇合適的數(shù)據(jù)結構和方法進行問題求解。
(2) 能夠對算法進行設計與分析。
(3) 了解常用面向對象的編程語言特點和編程規(guī)范
(4) 熟練應用C程序語言編寫和實現(xiàn)簡單應用程序（如數(shù)據(jù)結構算法等）
(5) 了解數(shù)據(jù)結構算法與計算機程序設計的關系，具有綜合運用所學知識分析和解決問題的能力。
五、考查范圍
（一）數(shù)據(jù)結構考查范圍
1、數(shù)據(jù)結構基本概念及簡單的算法分析
(1) 什么是數(shù)據(jù)結構。
(2) 抽象數(shù)據(jù)類型及面向對象概念：數(shù)據(jù)類型；數(shù)據(jù)抽象與抽象數(shù)據(jù)類型；面向對象的概念；用于描述數(shù)據(jù)結構的語言。
(3) 數(shù)據(jù)結構的抽象層次。
(4) 算法定義。
(5) 性能分析與度量：算法的性能標準；算法的后期測試；算法的事前估計；空間復雜度度量；時間復雜度度量；時間復雜度的漸進表示法；漸進的空間復雜度。
2、線性表
(1)線性表的定義和基本操作。
(2)線性表的實現(xiàn)：線性表的順序存儲結構；線性表的鏈式存儲結構。
(3)線性表的應用。
3、棧和隊列
(1) 棧：棧的抽象數(shù)據(jù)類型；棧的順序存儲表示；棧的鏈接存儲表示。
(2) 隊列 ：隊列的抽象數(shù)據(jù)類型；隊列的順序存儲表示；隊列的鏈接存儲表示。
(3) 遞歸過程與遞歸工作棧；棧的遞歸實現(xiàn)；棧和隊列的應用。
(4) 優(yōu)先級隊列：優(yōu)先級隊列的定義；優(yōu)先級隊列的存儲表示。
4、串
(1) 字符串的抽象數(shù)據(jù)類型；串的存儲表示；字符串操作的實現(xiàn)；字符串的模式匹配。
(2) 串的應用。
5、數(shù)組和廣義表
(1)數(shù)組的定義和初始化；數(shù)組的順序存儲方式。
(2)順序表：順序表的定義和特點；順序表的類定義；順序表的查找、插入和刪除；使用順序表的事例。
(3)矩陣的壓縮存儲。
(4)廣義表：廣義表的概念；廣義表的表示及操作；廣義表存儲結構的實現(xiàn)；廣義表的訪問算法；廣義表的遞歸算法。
6、樹和二叉樹
(1)樹的概念。
(2)二叉樹：二叉樹的定義及其主要特征；二叉樹的順序存儲結構和鏈式存儲結構；二叉樹的遍歷。
(3) 線索二叉樹的基本概念和構造。
(4) 堆；二叉排序樹；平衡二叉樹。
(5) 樹和森林：樹的存儲結構；森林與二叉樹的轉換；樹和森林的遍歷。
(6) 樹的應用：等價關系與等價類；確定等價類的鏈表方法；最優(yōu)二叉樹；哈夫曼（Huffman）樹和哈夫曼編碼；哈夫曼樹的應用。
7、圖
(1) 圖的定義及基本術語。
(2) 圖的存儲及基本操作：數(shù)組表示法；鄰接矩陣；鄰接表；十字鏈表；
(3) 圖的遍歷：深度優(yōu)先搜索；廣度優(yōu)先搜索
(4) 圖的連通性問題：無向圖的連通分量和生成樹；有向圖的強連通分量；最小生成樹。
(5) 有向無環(huán)圖應用及其復雜度分析：拓撲排序；關鍵路徑；最短路徑。
8、查找
(1) 查找的基本概念。
(2) 靜態(tài)查找表：順序表的查找；有序表的查找；靜態(tài)樹表的查找；索引順序表的查找。
(3) 動態(tài)查找表：折半查找；分塊查找；二叉排序樹查找；
(4) B_樹：B_樹的定義；B_樹的插入；B_樹的刪除
(5) 哈希表：哈希表與哈希方法；哈希函數(shù)的構造方法；哈希沖突與解決沖突的方法；哈希表的查找及其分析。
9、排序
(1) 排序的基本概念及各種排序算法比較。
(2) 插入排序：直接插入排序；對分插入排序；鏈表插入排序；希爾排序。
(3) 交換排序：起泡排序；快速排序。
(4) 選擇排序：直接選擇排序；錦標賽排序；堆排序。
(5) 歸并排序：歸并；迭代的歸并排序算法；遞歸的表歸并排序。
(6) 基數(shù)排序：多關鍵碼排序；鏈式基數(shù)排序。
(7) 內部排序算法的應用。
(8) 外排序：外排序的基本過程；k路平衡歸并；初始歸并段的生成；最佳歸并樹。
更多學歷考試信息請查看學歷考試網(wǎng)
公眾號
事業(yè)單位
當前位置：
公考類
招聘類
各類考試