2021青島大學(xué)921數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)研究生考試大綱 正文

軟件工程專業(yè)碩士入學(xué)考試大綱
考試科目代碼及名稱：921數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)
 
一、考試要求
1.掌握數(shù)據(jù)結(jié)構(gòu)的基本概念、基本原理和基本方法；
2.掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及基本操作的實(shí)現(xiàn)，能夠?qū)λ惴ㄟM(jìn)行基本的時(shí)間復(fù)雜度與空間復(fù)雜度的分析；
3.能應(yīng)用數(shù)據(jù)結(jié)構(gòu)基本原理和方法進(jìn)行問題的分析與求解，具備采用計(jì)算機(jī)程序設(shè)計(jì)語言實(shí)現(xiàn)算法的能力。
二、考試內(nèi)容
一、基本概念
    （一）數(shù)據(jù)結(jié)構(gòu)的基本概念
    （二）算法的基本概念
    （三）算法分析的基本方法
二、線性結(jié)構(gòu)
　　（一）線性表、棧和隊(duì)列的基本概念
　?。ǘ┚€性表、棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)
　?。ㄈ┚€性表、棧和隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
　　（四）線性表、棧和隊(duì)列的應(yīng)用
三、樹與二叉樹
　　（一）樹的定義、表示和基本術(shù)語
　　（二）二叉樹
　　   1.二叉樹的定義及其主要性質(zhì)
　　   2.二叉樹的存儲(chǔ)結(jié)構(gòu)
　　   3.二叉樹的遍歷
?。ㄈ渑c二叉樹的應(yīng)用
　  　1.二叉搜索樹
　　  2.堆結(jié)構(gòu)
　  　3.哈夫曼（Huffman）樹和哈夫曼編碼
      4.集合及其運(yùn)算
四、圖
　?。ㄒ唬﹫D的基本概念
　?。ǘ﹫D的存儲(chǔ)結(jié)構(gòu)
　　    1.鄰接矩陣
　　    2.鄰接表
　?。ㄈ﹫D的遍歷
　　    1.深度優(yōu)先搜索
　　    2.廣度優(yōu)先搜索
　　（四）圖的基本應(yīng)用
　　    1.最?。ù鷥r(jià)）生成樹
　　    2.最短路徑
　　    3.拓?fù)渑判?br />         4.關(guān)鍵路徑計(jì)算
五、動(dòng)態(tài)查找
　?。ㄒ唬┢胶舛鏄?AVL樹)
　　（二）散列（Hash）表
　?。ㄈ┎檎宜惴ǖ姆治黾皯?yīng)用
六、排序
　?。ㄒ唬┎迦肱判?br /> 　?。ǘ┙粨Q排序
　?。ㄈ┻x擇排序
　?。ㄋ模w并排序
　?。ㄎ澹┗鶖?shù)排序
　　（六）各種內(nèi)部排序算法的比較和應(yīng)用
三、試卷結(jié)構(gòu)（題型分值）
1. 本科目滿分為150分，考試時(shí)間為180分鐘。
2.題型結(jié)構(gòu)
（1）選擇題： 30分
（2）填空題:  20分
（3）應(yīng)用題： 55分
（4）算法分析與設(shè)計(jì)題：45分
四、參考書目
《數(shù)據(jù)結(jié)構(gòu)（第2版）》：陳越主編，高等教育出版社，2016年
《計(jì)算機(jī)算法設(shè)計(jì)與分析（第5版）》王曉東編著,電子工業(yè)出版社,2018年
 

青島大學(xué)

本文來源：http://alternativeofficeassistance.com/qdu/cankaoshumu_380553.html