華北電力大學2024年非全日制研究生招生考試《軟件工程專業(yè)基礎(chǔ)綜合》考試大綱

　　考試科目編號：843

　　考試科目名稱：軟件工程專業(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)及基本操作的實現(xiàn)，能夠?qū)λ惴ㄟM行基本的時間復雜度和空間復雜度分析。能夠運用數(shù)據(jù)結(jié)構(gòu)的基本原理和方法進行問題的分析與求解，具備采用 C 語言設(shè)計與實現(xiàn)算法的能力。

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

　　1.緒論

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

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

　　2.線性表

　　線性表的定義;線性表的邏輯結(jié)構(gòu);線性表的存儲結(jié)構(gòu)(順序存儲、鏈式存儲)，兩種存儲方式的特點和適用場合;不同存儲方式下基本操作的實現(xiàn);線性表的應(yīng)用。

　　3.棧與隊列

　　棧：棧的定義和基本概念;棧的邏輯結(jié)構(gòu);棧的存儲結(jié)構(gòu)(順序存儲，鏈式存儲);不同存儲方式下基本操作的實現(xiàn);棧的應(yīng)用。

　　隊列：隊列的定義和基本概念;隊列的邏輯結(jié)構(gòu);隊列的存儲結(jié)構(gòu)(順序，鏈式);不同存儲方式下基本操作的實現(xiàn);隊列的應(yīng)用。

　　4.二叉樹與樹

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

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

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

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

　　5.圖

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

　　6.查找

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

　　7.排序

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

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

　　三、考試的題型

　　選擇題、填空題(概念及算法)、算法應(yīng)用題、算法設(shè)計題。

　　四、參考書目

　　1.林碧英，石敏，焦?jié)櫤? 新編數(shù)據(jù)結(jié)構(gòu)及算法教程(第 2 版).清華大學出版社,2021.

　　2.石敏，焦?jié)櫤＃荛L玉等.數(shù)據(jù)結(jié)構(gòu)與算法慕課(www.xuetangx.com).

　　第二部分：操作系統(tǒng)

　　一、考試的總體要求

　　要求考生熟練掌握計算機操作系統(tǒng)中的基本概念、基本原理; 從資源管理角度掌握計算機操作系統(tǒng)的主要功能及設(shè)計思想;了解和掌握現(xiàn)代計算機系統(tǒng)對其各種軟硬資源的管理方法及實現(xiàn)技術(shù);了解當代計算機操作系統(tǒng)的新技術(shù)與發(fā)展趨勢。

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

　　1.掌握與操作系統(tǒng)相關(guān)的基本概念。

　　2.操作系統(tǒng)概述：

　　包括操作系統(tǒng)的概念;操作系統(tǒng)的發(fā)展過程;操作系統(tǒng)的分類;操作系統(tǒng)的特征;操作系統(tǒng)的功能;操作系統(tǒng)接口;常用操作系統(tǒng)的結(jié)構(gòu)特點。

　　3.進程管理：

　　包括進程的概念;進程控制(進程的狀態(tài)機轉(zhuǎn)換);進程同步;經(jīng)典的進程同步互斥問題;進程通信;線程的定義及實現(xiàn)。

　　4.處理機調(diào)度與死鎖：

　　包括處理機調(diào)度的概念;調(diào)度方式及算法;死鎖的概念;死鎖產(chǎn)生的原因;死鎖的處理策略。

　　5.存儲器管理：

　　包括程序的裝入和鏈接;連續(xù)分配存儲管理方式;覆蓋與交換;分頁存儲管理方式;分段存儲管理方式;段頁式存儲管理方式;虛擬存儲器的概念;局部性原理;缺頁中斷;請求分頁存儲管理方式;頁面置換算法;請求分段存儲管理方式;邏輯地址到物理地址的轉(zhuǎn)換。

　　6.設(shè)備管理：

　　包括 I/O系統(tǒng)的組成;I/O控制方式;I/O軟件層次結(jié)構(gòu);設(shè)備獨立性;緩沖管理;SPOOLing技術(shù);設(shè)備分配;設(shè)備處理(驅(qū)動)。

　　7.磁盤管理：

　　包括磁盤調(diào)度;磁盤空閑存儲空間的管理;磁盤陣列。

　　8.文件管理：

　　包括文件和文件系統(tǒng)的概念;文件控制塊 FCB;索引節(jié)點;文件邏輯結(jié)構(gòu);目錄管理;外存分配方法(文件物理結(jié)構(gòu));FAT表;文件保護。

　　三、考試的題型

　　選擇題、填空題、綜合應(yīng)用題。

　　四、參考書目

　　1.鄒鵬，操作系統(tǒng)原理與實踐，北京：高等教育出版社，2008.

　　2.湯小丹等，計算機操作系統(tǒng)，第四版.西安：西安電子科技大學出版社，2014.