2021華北電力大學(北京)數(shù)據(jù)結構研究生考試大綱 正文

華北電力大學2021年碩士生入學考試初試科目考試大綱
考試科目編號：844             
考試科目名稱：數(shù)據(jù)結構
一、 考試的總體要求
掌握常用數(shù)據(jù)結構的邏輯結構、存儲結構和基本操作，靈活運用所學的數(shù)據(jù)結構解決實際問題。
二、 考試的內容
(一)基本概念和術語
(二)常用數(shù)據(jù)結構及算法
1、線性表
①線性表的特點；
②順序表數(shù)據(jù)類型描述和基本操作的實現(xiàn)；
③單向鏈表的數(shù)據(jù)類型描述和基本操作的實現(xiàn)；
④單向循環(huán)鏈表、雙向循環(huán)鏈表的數(shù)據(jù)類型描述和基本操作的實現(xiàn)；
⑤線性表的應用：兩個線性表的合并、一元多項式的求和與求積。
2、棧與隊列 
①棧與隊列的特點；
②順序棧、鏈棧的數(shù)據(jù)類型描述和基本操作的實現(xiàn)；
③循環(huán)隊列、鏈隊列的數(shù)據(jù)類型描述和基本操作的實現(xiàn)；
④表達式求值的兩種方法。
3、二叉樹與樹
①二叉樹的特點和性質；
②二叉樹的順序存儲與二叉鏈表的數(shù)據(jù)類型描述和基本操作的實現(xiàn)（創(chuàng)建、查找、遞歸遍歷、非遞歸遍歷、層次遍歷）和遍歷的應用；
③二叉樹與樹、森林的轉換以及遍歷的對應關系；
④樹的存儲結構：雙親表示、孩子鏈表、雙親孩子鏈表和孩子兄弟鏈表的數(shù)據(jù)類型描述；
⑤樹的算法：創(chuàng)建、查找、插入、刪除、遍歷以及遍歷的應用；
⑥表達式二叉樹的創(chuàng)建與求值；
⑥哈夫曼樹及哈夫曼編碼。
4、圖
①圖的特點；
②鄰接矩陣、鄰接表的數(shù)據(jù)類型描述；
③圖的創(chuàng)建、圖的遍歷、最小生成樹、最短路徑、AOV網(wǎng)及拓撲排序、AOE網(wǎng)及關鍵路徑；
④圖的遍歷算法的應用。
(三)數(shù)據(jù)處理技術
1、查找
①靜態(tài)查找：順序查找（帶崗哨）、折半查找；
②動態(tài)查找：二叉排序樹和二叉平衡樹的查找、插入和刪除；
③哈希表：哈希函數(shù)、處理沖突的方法；
④查找性能分析（ASL）。
2、內排序
①插入類排序（直接插入排序、折半插入排序、希爾排序）
②交換類排序（冒泡排序、快速排序）
③選擇類排序（簡單選擇排序、堆排序）
④歸并類排序（二路歸并排序）
⑤排序算法的復雜度分析
三、考試的題型
單選題、填空題（概念及算法）、算法應用題、算法設計題。
四、參考書目
1. 林碧英主編，新編數(shù)據(jù)結構及算法教程，清華大學出版社.

華北電力大學(北京)

本文來源：http://www.zhongzhouzhikong.com/huabeidianli/cankaoshumu_411175.html