華北電力大學(xué)2023碩士研究生考試大綱：軟件工程專業(yè)基礎(chǔ)綜合

近日華北電力大學(xué)關(guān)于調(diào)整軟件工程碩士研究生入學(xué)考試初試科目的通知發(fā)布，我校學(xué)術(shù)型碩士軟件工程（083500）和專業(yè)型碩士軟件工程（085405）專業(yè)的入學(xué)考試業(yè)務(wù)課二采用自命題科目“軟件工程專業(yè)基礎(chǔ)綜合”，具體以學(xué)校發(fā)布的招生專業(yè)目錄相關(guān)內(nèi)容為準(zhǔn)。

《軟件工程專業(yè)基礎(chǔ)綜合》考試大綱

本門課程由數(shù)據(jù)結(jié)構(gòu)和操作系統(tǒng)兩門課程組成，兩門課程各占 75分，具體要求如下：

第一部分：數(shù)據(jù)結(jié)構(gòu)

一、考試的總體要求

掌握數(shù)據(jù)結(jié)構(gòu)的基本概念、原理和方法。掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及基本操作的實(shí)現(xiàn)，能夠?qū)λ惴ㄟM(jìn)行基本的時(shí)間復(fù)雜度和空間復(fù)雜度分析。

能夠運(yùn)用數(shù)據(jù)結(jié)構(gòu)的基本原理和方法進(jìn)行問題的分析與求解，具備采用C語言設(shè)計(jì)與實(shí)現(xiàn)算法的能力。

二、考試的內(nèi)容

1.緒論

數(shù)據(jù)結(jié)構(gòu)的基本概念，數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)。

算法的定義、特性和設(shè)計(jì)要求，算法的時(shí)間復(fù)雜度分析與空間復(fù)雜度分析。

2.線性表

線性表的定義；線性表的邏輯結(jié)構(gòu)；線性表的存儲結(jié)構(gòu)（順序存儲、鏈?zhǔn)酱鎯Γ�，兩種存儲方式的特點(diǎn)和適用場合；不同存儲方式下基本操作的實(shí)現(xiàn)；線性表的應(yīng)用。

3.棧與隊(duì)列

棧：棧的定義和基本概念；棧的邏輯結(jié)構(gòu)；棧的存儲結(jié)構(gòu)（順序存儲，鏈?zhǔn)酱鎯Γ�；不同存儲方式下基本操作的�?shí)現(xiàn)；棧的應(yīng)用。

隊(duì)列：隊(duì)列的定義和基本概念；隊(duì)列的邏輯結(jié)構(gòu)；隊(duì)列的存儲結(jié)構(gòu)（順序，鏈?zhǔn)剑�；不同存儲方式下基本操作的�?shí)現(xiàn)；隊(duì)列的應(yīng)用。

4.二叉樹與樹

二叉樹：二叉樹的定義和基本概念；二叉樹的基本性質(zhì)；二叉樹的邏輯結(jié)構(gòu)；二叉樹的存儲結(jié)構(gòu)（順序、鏈?zhǔn)剑�；不同存儲結(jié)構(gòu)上的基本操作實(shí)現(xiàn)；二叉樹的遍歷及應(yīng)用；線索二叉樹的基本概念和構(gòu)造。

樹與森林：樹（森林）的定義和基本概念；樹（森林）的邏輯結(jié)構(gòu)；樹（森林）的存儲結(jié)構(gòu)（雙親表示法，孩子鏈表表示法，雙親孩子鏈表表示法，孩子兄弟鏈表表示法）；樹（森林）的基本操作實(shí)現(xiàn)；樹（森林）的遍歷及應(yīng)用。

樹（森林）與二叉樹之間的相互轉(zhuǎn)換以及遍歷的對應(yīng)關(guān)系。

哈夫曼樹（最優(yōu)二叉樹）和哈夫曼編碼。

5.圖

圖的定義與基本概念；圖的邏輯結(jié)構(gòu)；圖的存儲結(jié)構(gòu)（鄰接矩陣、鄰接表、鄰接多重表、十字鏈表）；不同存儲結(jié)構(gòu)上的基本操作實(shí)現(xiàn)；圖的遍歷（深度優(yōu)先遍歷，廣度優(yōu)先遍歷）及應(yīng)用；圖的應(yīng)用（最小生成樹、最短路徑、AOV網(wǎng)及拓?fù)渑判颉�AOE網(wǎng)及關(guān)鍵路徑）。

6.查找

查找的基本概念與術(shù)語；靜態(tài)查找表（順序查找、折半查找、分塊查找）；動(dòng)態(tài)查找表（二叉排序樹、二叉平衡樹和 B-樹）；哈希表（哈希表的概念、常用的哈希函數(shù)、解決沖突的方法）；查找算法的分析（ASL）及應(yīng)用。

7.排序

排序的基本概念；插入類排序（直接插入排序、折半插入排序、希爾排序）、交換類排序（冒泡排序、快速排序）、選擇類排序（簡單選擇排序、堆排序）、歸并類排序（二路歸并排序）、基數(shù)排序；各種內(nèi)部排序算法的穩(wěn)定性和時(shí)間復(fù)雜度與空間復(fù)雜度分析；排序算法的應(yīng)用。

8．綜合應(yīng)用：根據(jù)實(shí)際問題，設(shè)計(jì)有效的數(shù)據(jù)結(jié)構(gòu)和算法，并進(jìn)行時(shí)間復(fù)雜度分析。

1 2