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)、存儲結(jié)構(gòu)及基本操作的實現(xiàn)，能夠?qū)λ惴ㄟM(jìn)行基本的時間復(fù)雜度與空間復(fù)雜度的分析；
3.能應(yīng)用數(shù)據(jù)結(jié)構(gòu)基本原理和方法進(jìn)行問題的分析與求解，具備采用計算機(jī)程序設(shè)計語言實現(xiàn)算法的能力。
二、考試內(nèi)容
一、基本概念
    （一）數(shù)據(jù)結(jié)構(gòu)的基本概念
    （二）算法的基本概念
    （三）算法分析的基本方法
二、線性結(jié)構(gòu)
　　（一）線性表、棧和隊列的基本概念
　　（二）線性表、棧和隊列的順序存儲結(jié)構(gòu)
　　（三）線性表、棧和隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)
　?。ㄋ模┚€性表、棧和隊列的應(yīng)用
三、樹與二叉樹
　　（一）樹的定義、表示和基本術(shù)語
　?。ǘ┒鏄?br /> 　　   1.二叉樹的定義及其主要性質(zhì)
　　   2.二叉樹的存儲結(jié)構(gòu)
　　   3.二叉樹的遍歷
　（三）樹與二叉樹的應(yīng)用
　  　1.二叉搜索樹
　　  2.堆結(jié)構(gòu)
　  　3.哈夫曼（Huffman）樹和哈夫曼編碼
      4.集合及其運算
四、圖
　?。ㄒ唬﹫D的基本概念
　?。ǘ﹫D的存儲結(jié)構(gòu)
　　    1.鄰接矩陣
　　    2.鄰接表
　?。ㄈ﹫D的遍歷
　　    1.深度優(yōu)先搜索
　　    2.廣度優(yōu)先搜索
　　（四）圖的基本應(yīng)用
　　    1.最?。ù鷥r）生成樹
　　    2.最短路徑
　　    3.拓?fù)渑判?br />         4.關(guān)鍵路徑計算
五、動態(tài)查找
　?。ㄒ唬┢胶舛鏄?AVL樹)
　?。ǘ┥⒘校℉ash）表
　　（三）查找算法的分析及應(yīng)用
六、排序
　　（一）插入排序
　?。ǘ┙粨Q排序
　?。ㄈ┻x擇排序
　　（四）歸并排序
　　（五）基數(shù)排序
　?。└鞣N內(nèi)部排序算法的比較和應(yīng)用
三、試卷結(jié)構(gòu)（題型分值）
1. 本科目滿分為150分，考試時間為180分鐘。
2.題型結(jié)構(gòu)
（1）選擇題： 30分
（2）填空題:  20分
（3）應(yīng)用題： 55分
（4）算法分析與設(shè)計題：45分
四、參考書目
《數(shù)據(jù)結(jié)構(gòu)（第2版）》：陳越主編，高等教育出版社，2016年
《計算機(jī)算法設(shè)計與分析（第5版）》王曉東編著,電子工業(yè)出版社,2018年
 

青島大學(xué)

本文來源：http://m.zgxindalu.cn/qdu/cankaoshumu_380553.html