華北電力大學（北京）

華北電力大學2020年碩士生入學考試初試科目考試大綱

考試科目編號：844

考試科目名稱：數據結構

一、考試的總體要求

掌握常用數據結構的邏輯結構、存儲結構和基本操作，靈活運用所學的數據結構解決實際問題。

二、考試的內容

1. 基本概念和術語;

2. 常用數據結構及算法：

(1)線性表：線性表的特點;順序表、鏈表的數據類型描述和基本操作的實現。

(2)棧與隊列：棧和隊列的特點;順序棧、鏈棧、循環隊列和鏈隊列的數據類型描述和基本操作的實現。

(3)二叉樹與樹：二叉樹和樹的特點;二叉樹與樹、森林的轉換;二叉鏈表、孩子兄弟鏈表和雙親孩子鏈表的數據類型描述和基本操作的實現。

(4)圖：圖的特點;鄰接矩陣和鄰接表的數據類型描述和基本操作的實現。

3. 數據處理技術：

(1)查找：靜態查找(順序查找(帶崗哨)、折半查找);動態查找(二叉排序樹的查找、插入和刪除，二叉平衡樹和哈希表的查找);查找算法的性能分析(ASL)。

(2)內排序：插入類排序(直接插入排序、折半插入排序、希爾排序)、交換類排序(冒泡排序、快速排序)、選擇類排序(簡單選擇排序、堆排序)、歸并類排序(二路歸并排序);排序算法的復雜度分析。

4. 基本應用：

(1) 線性表的應用

(2) 棧的應用

(3) 隊列的應用

(4) 二叉樹和樹的應用

(5) 圖的應用

(6) 查找的應用

(7) 排序的應用

三、考試的題型

單選題、填空題(概念及算法)、算法設計題、算法應用題。

四、參考書目

1. 林碧英主編，新編數據結構及算法教程，清華大學出版社.