2024年北京航空航天大學(xué)非全日制研究生招生考試《軟件工程基礎(chǔ)綜合》考試大綱

　　一、緒論

　　包括但不限于數(shù)據(jù)結(jié)構(gòu)和算法的基本概念，主要內(nèi)容有：數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu);算法的定義、基本性質(zhì)和算法分析的基本概念，包括采用大O形式表示時(shí)間復(fù)雜度和空間復(fù)雜度。

　　二、線性表與數(shù)組

　　包括但不限于線性表與數(shù)組的概念、各種存儲(chǔ)結(jié)構(gòu)和操作，主要內(nèi)容有：線性關(guān)系、線性表的定義，線性表的基本操作;線性表的順序存儲(chǔ)結(jié)構(gòu)和操作的實(shí)現(xiàn);線性鏈表及其操作;循環(huán)鏈表及其操作;雙向鏈表及其操作;鏈表的應(yīng)用;一維數(shù)組和二維數(shù)組的存儲(chǔ);矩陣的壓縮存儲(chǔ)的基本概念;對(duì)稱矩陣、對(duì)角矩陣以及三角矩陣的壓縮存儲(chǔ)。

　　三、堆棧與隊(duì)列

　　包括但不限于堆棧與隊(duì)列的基本概念、操作和應(yīng)用，主要內(nèi)容有：堆棧與隊(duì)列的基本概念與基本操作;堆棧與隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的構(gòu)造原理;在不同存儲(chǔ)結(jié)構(gòu)的基礎(chǔ)上對(duì)堆棧與隊(duì)列實(shí)施插入與刪除等基本操作的算法設(shè)計(jì);堆棧和隊(duì)列在解決實(shí)際問題中應(yīng)用。

　　四、樹與二叉樹

　　包括但不限于樹與二叉樹的基本概念和操作，主要內(nèi)容有：樹、二叉樹、完全二叉樹與滿二叉樹的基本概念;二叉樹的順序存儲(chǔ)結(jié)構(gòu)與二叉鏈表存儲(chǔ)結(jié)構(gòu)的基本原理;二叉樹的前序遍歷、中序遍歷、后序遍歷和按層次遍歷，重點(diǎn)是二叉樹在以二叉鏈表為存儲(chǔ)結(jié)構(gòu)的遍歷算法(包括遞歸和非遞歸算法)的設(shè)計(jì)與應(yīng)用;線索二叉樹的基本概念;二叉排序樹的基本概念、建立(插入)、刪除結(jié)點(diǎn)、查找以及平均查找長(zhǎng)度(ASL)的計(jì)算;哈夫曼樹的基本概念和簡(jiǎn)單應(yīng)用。

　　五、圖

　　包括但不限于圖的基本概念和操作，主要內(nèi)容有：圖的基本概念、名詞術(shù)語;圖的鄰接矩陣存儲(chǔ)方法和鄰接表(含逆鄰接表)存儲(chǔ)方法的構(gòu)造原理及特點(diǎn);圖的深度優(yōu)先搜索與廣度優(yōu)先搜索，連通分量;最小(代價(jià))生成樹、最短路徑、AOV網(wǎng)與拓?fù)渑判颉OE網(wǎng)與關(guān)鍵路徑的基本概念和算法原理。

　　六、內(nèi)排序

　　包括但不限于內(nèi)排序的基本概念、各類算法實(shí)現(xiàn)原理和應(yīng)用，主要內(nèi)容有：排序的基本概念，各種內(nèi)排序方法的基本原理和特點(diǎn);插入排序法(含折半插入排序法);選擇排序法;泡排序法;謝爾排序法;快速排序法;堆排序法;二路歸并排序法。

　　七、遞歸分析技術(shù)

　　包括但不限于遞歸分析技術(shù)的基本概念和操作，主要內(nèi)容有：掌握遞歸算法的分析步驟和計(jì)算復(fù)雜度分析方法;了解遞歸方程的求解方法;置換法;迭代法;遞歸樹法;主方法。

　　八、動(dòng)態(tài)規(guī)劃法

　　包括但不限于動(dòng)態(tài)規(guī)劃法的基本概念和主要思想，主要內(nèi)容有：動(dòng)態(tài)規(guī)劃法的特征，包括最優(yōu)子結(jié)構(gòu)和重疊子問題;掌握裝配線調(diào)度問題、鋼條切割問題、矩陣鏈相乘問題、最長(zhǎng)相同子序列問題、最優(yōu)二叉搜索樹問題、Floyd-Warshall算法求最短路徑等問題的動(dòng)態(tài)規(guī)劃設(shè)計(jì)方法。

　　九、貪心法

　　包括但不限于貪心法的基本概念和主要思想，主要內(nèi)容有：貪心法的基本特征，包括貪婪選擇屬性;掌握活動(dòng)安排問題、背包問題、霍夫曼編碼問題、Dijkstra算法求最短路徑等問題的貪心策略設(shè)計(jì)。

　　十、字符串匹配

　　包括但不限于字符串匹配的基本概念、各類算法實(shí)現(xiàn)原理和應(yīng)用，主要內(nèi)容有：各類字符串匹配算法的基本原理、特點(diǎn)和計(jì)算復(fù)雜度分析;有限自動(dòng)機(jī)字符串匹配算法;KMP算法。

　　由于篇幅有限，無法為同學(xué)全面展示，想要了解更多，請(qǐng)點(diǎn)擊下面附件進(jìn)行下載。

　　991-軟件工程基礎(chǔ)綜合-考試大綱-2024.pdf