2021西安石油大學(xué)808數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)研究生考試大綱 正文

 西安石油大學(xué)2021年碩士研究生招生考試
 （808）數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)  考試大綱
 
一、考察目標(biāo)
“數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)”入學(xué)考試是為招收計(jì)算機(jī)科學(xué)與技術(shù)類(lèi)碩士生而實(shí)施的選拔性考試，主要涉及數(shù)據(jù)結(jié)構(gòu)、C/C++程序設(shè)計(jì)課程的內(nèi)容。主要包括三大常用數(shù)據(jù)結(jié)構(gòu)的邏輯、物理表示與基本操作算法實(shí)現(xiàn)部分的知識(shí)，各種結(jié)構(gòu)的經(jīng)典應(yīng)用和問(wèn)題求解?？忌鷳?yīng)掌握各種數(shù)據(jù)結(jié)構(gòu)及其操作，具備一定的算法設(shè)計(jì)與分析能力，能夠根據(jù)實(shí)際問(wèn)題選擇合適的數(shù)據(jù)結(jié)構(gòu)并設(shè)計(jì)算法實(shí)現(xiàn)。要求考生具有較全面的數(shù)據(jù)結(jié)構(gòu)表示與實(shí)現(xiàn)的基礎(chǔ)知識(shí)；具有較高的分析問(wèn)題和解決問(wèn)題的能力；具有較強(qiáng)的綜合知識(shí)運(yùn)用能力。
二、考試主要內(nèi)容
1．緒論
1.1 數(shù)據(jù)結(jié)構(gòu)的基本概念；
1.2 抽象數(shù)據(jù)類(lèi)型；
1.3 算法和算法的時(shí)間復(fù)雜度。
2. 線性表
2.1 線性表概述；
2.2 線性表的順序表示和實(shí)現(xiàn)；
2.3 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)；
2.4 靜態(tài)鏈表；
2.5 線性表的基本運(yùn)算。
3. 堆棧和隊(duì)列
3.1 堆棧；
3.2 堆棧應(yīng)用；
3.3 隊(duì)列；
3.4 優(yōu)先級(jí)隊(duì)列。
4. 串
4.1 串概述；
4.2 串的存儲(chǔ)結(jié)構(gòu)；
4.3 串基本操作的實(shí)現(xiàn)算法；
4.4 串的模式匹配算法-BF和KMP算法。
5. 數(shù)組
5.1 數(shù)組概述；
5.2 動(dòng)態(tài)數(shù)組；
5.3 特殊矩陣的壓縮存儲(chǔ)；
5.4 稀疏矩陣的壓縮存儲(chǔ)。
6. 遞歸算法
6.1 遞歸的概念；
6.2 遞歸算法的執(zhí)行過(guò)程；
6.3 遞歸算法的設(shè)計(jì)方法；
6.4 遞歸過(guò)程和運(yùn)行時(shí)棧；
6.5 遞歸算法的時(shí)間效率分析。
7. 樹(shù)和二叉樹(shù)
7.1 樹(shù)；
7.2 二叉樹(shù)；
7.3 二叉樹(shù)的設(shè)計(jì)和實(shí)現(xiàn)；
7.4 二叉樹(shù)遍歷；
7.5 線索二叉樹(shù)；
7.6 哈夫曼樹(shù)；
7.7 等價(jià)問(wèn)題；
7.8 樹(shù)與二叉樹(shù)的轉(zhuǎn)換；
7.9 樹(shù)的遍歷。
8. 圖
8.1 圖概述；
8.2 圖的存儲(chǔ)結(jié)構(gòu)；
8.3 圖的實(shí)現(xiàn)；
8.4 圖的遍歷；
8.5 最小生成樹(shù)；
8.6 最短路徑；
8.7 拓?fù)渑判颍?br /> 8.8 關(guān)鍵路徑。
9. 排序
9.1 排序的基本概念；
9.2 插入排序；
9.3 選擇排序；
9.4 交換排序；
9.5 歸并排序；
9.6 基數(shù)排序；
9.7 排序算法性能比較。
10. 查找
10.1 查找的基本概念；
10.2 靜態(tài)查找；  
10.3 動(dòng)態(tài)查找；
10.4 哈希查找；
三、考試形式及試卷結(jié)構(gòu)
考試形式為閉卷筆試?？荚嚂r(shí)間為3小時(shí)。
試卷結(jié)構(gòu)：
單項(xiàng)選擇題（20%）
填空題（13%）
簡(jiǎn)答題（20%）
算法理解與設(shè)計(jì)題（47%）
 
 
 

西安石油大學(xué)

本文來(lái)源：http://m.zhangjiajieline.cn/xasydx/cksm_387115.html