2021山東大學(xué)849軟件工程專業(yè)基礎(chǔ)綜合研究生考試大綱 正文

849-軟件工程專業(yè)基礎(chǔ)綜合
 
操作系統(tǒng)
一、考查目標(biāo)
操作系統(tǒng)是軟件工程專業(yè)的一門核心專業(yè)基礎(chǔ)課程，具有較強(qiáng)的理論性和實(shí)踐性。該課程的考試內(nèi)容包括引論、進(jìn)程管理、內(nèi)存管理、存儲(chǔ)管理（包括文件系統(tǒng)與輸入/輸出系統(tǒng)）、保護(hù)與安全五部分的相關(guān)概念、設(shè)計(jì)原理和實(shí)現(xiàn)方法。考試的具體要求包括：
1. 了解操作系統(tǒng)在計(jì)算機(jī)系統(tǒng)中的作用、地位、發(fā)展和特點(diǎn)。
2. 理解操作系統(tǒng)的基本概念、主要功能、主要組成部分，掌握操作系統(tǒng)各個(gè)組成部分的設(shè)計(jì)方法和實(shí)現(xiàn)技術(shù)。
3. 能夠運(yùn)用所學(xué)的操作系統(tǒng)原理、方法和技術(shù)對(duì)相關(guān)問(wèn)題進(jìn)行分析和解決。
 
二、考試的內(nèi)容
1．導(dǎo)論
1）操作系統(tǒng)的概念
2）計(jì)算機(jī)系統(tǒng)的操作、存儲(chǔ)結(jié)構(gòu)、輸入輸出結(jié)構(gòu)和計(jì)算機(jī)系統(tǒng)的體系結(jié)構(gòu)。
3）操作系統(tǒng)的結(jié)構(gòu)組成、操作系統(tǒng)的操作及各部分的功能、高速緩沖存儲(chǔ)器CACHE
4）操作系統(tǒng)的分類和運(yùn)行環(huán)境
2．操作系統(tǒng)結(jié)構(gòu)
1）操作系統(tǒng)提供的服務(wù)類型
2）操作系統(tǒng)的用戶接口類型
3）系統(tǒng)調(diào)用及類型
4）操作系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)方法
5）操作系統(tǒng)的結(jié)構(gòu)分類及優(yōu)缺點(diǎn)
6）虛擬機(jī)的基本概念和原理
3．進(jìn)程
1）進(jìn)程的概念、組織、控制和狀態(tài)轉(zhuǎn)換
2）進(jìn)程調(diào)度的基本概念
3）進(jìn)程的操作，包括進(jìn)程的生成、終止等
4）進(jìn)程通信
4．線程
1）線程的概念與動(dòng)機(jī)
2）多線程模型
5．CPU調(diào)度
1）調(diào)度的基本概念
2）調(diào)度的時(shí)機(jī)、切換和過(guò)程
3）調(diào)度的基本準(zhǔn)則
4）典型調(diào)度方法：先來(lái)先服務(wù)調(diào)度算法、最短作業(yè)優(yōu)先調(diào)度算法、優(yōu)先級(jí)調(diào)度算法、時(shí)間片輪轉(zhuǎn)調(diào)度算法、多級(jí)隊(duì)列調(diào)度算法、多級(jí)反饋隊(duì)列調(diào)度算法
5）線程調(diào)度
6）調(diào)度算法的性能評(píng)估
6．進(jìn)程同步
1）進(jìn)程同步的基本概念
2）臨界區(qū)訪問(wèn)的原則及實(shí)現(xiàn)臨界區(qū)互斥的基本方法：軟件實(shí)現(xiàn)方法和硬件實(shí)現(xiàn)方法
3）信號(hào)量概念與基本機(jī)制
4）經(jīng)典同步問(wèn)題：生產(chǎn)者－消費(fèi)者問(wèn)題、讀者－寫(xiě)者問(wèn)題、哲學(xué)家就餐問(wèn)題和理發(fā)師問(wèn)題。
5）管程的基本概念、原理和實(shí)現(xiàn)
7．死鎖
1）死鎖的概念及條件
2）死鎖的處理策略
3）死鎖的預(yù)防及實(shí)現(xiàn)方法
4）死鎖的避免：系統(tǒng)安全狀態(tài)、資源分配圖算法、銀行家算法
5）死鎖的檢測(cè)方法和解除
8．主存
1）內(nèi)存管理的基本概念：程序的裝入與鏈接、邏輯地址與物理地址、內(nèi)存保護(hù)
2）交換技術(shù)
3）內(nèi)存的分配管理方法：連續(xù)分配管理方法、分頁(yè)管理方法、分段管理方法、段頁(yè)式管理方法。
9．虛擬內(nèi)存
1）虛擬內(nèi)存的基本概念
2）請(qǐng)求分頁(yè)管理方法
3）頁(yè)面置換算法：先進(jìn)先出置換算法、最佳置換算法、最近最少使用置換算法、近似最近最少使用置換算法
4）幀的分配策略
5）抖動(dòng)現(xiàn)象的原因及解決方法
6）內(nèi)核內(nèi)存的分配方法
7）虛擬內(nèi)存中需要考慮的其他問(wèn)題：預(yù)調(diào)頁(yè)、頁(yè)大小的影響、TLB的搜索能力、逆向頁(yè)表等
10．文件系統(tǒng)接口
1）文件的基本概念
2）文件的結(jié)構(gòu)：順序文件、索引文件等
3）文件的訪問(wèn)方法
4）目錄結(jié)構(gòu)：文件的存儲(chǔ)結(jié)構(gòu)、單級(jí)目錄結(jié)構(gòu)、兩級(jí)目錄結(jié)構(gòu)、樹(shù)形目錄結(jié)構(gòu)、無(wú)環(huán)圖目錄結(jié)構(gòu)、通用圖目錄結(jié)構(gòu)
5）文件共享
11．文件系統(tǒng)實(shí)現(xiàn)
1）文件系統(tǒng)的結(jié)構(gòu)
2）文件系統(tǒng)的實(shí)現(xiàn)
3）目錄的實(shí)現(xiàn)
4）文件的磁盤(pán)空間分配方法：連續(xù)、鏈?zhǔn)健⑺饕?br /> 5）空閑空間的管理
12．大容量存儲(chǔ)
1）磁盤(pán)的結(jié)構(gòu)
2）磁盤(pán)的調(diào)度方法：先到先服務(wù)調(diào)度算法、最短尋道時(shí)間調(diào)度算法、SCAN調(diào)度算法、C-SCAN調(diào)度算法、LOOK調(diào)度算法、C-LOOK調(diào)度算法
3）磁盤(pán)管理：格式化、引導(dǎo)塊、壞塊的處理
4）RAID結(jié)構(gòu)
13．輸入/輸出系統(tǒng)
1）輸入/輸出硬件
2）輸入/輸出訪問(wèn)控制方式
3）輸入/輸出應(yīng)用接口
4）內(nèi)核輸入/輸出子系統(tǒng)：輸入/輸出調(diào)度、緩存、緩沖、假脫機(jī)與設(shè)備預(yù)留、錯(cuò)誤處理、輸入/輸出保護(hù)、內(nèi)核數(shù)據(jù)結(jié)構(gòu)
5）輸入/輸出從請(qǐng)求到硬件操作的轉(zhuǎn)換過(guò)程
14．保護(hù)
1）保護(hù)的目標(biāo)與原則
2）保護(hù)域
3）訪問(wèn)矩陣及實(shí)現(xiàn)方法：全局表、訪問(wèn)列表、能力表
15．安全
1）系統(tǒng)中存在的安全問(wèn)題以及安全措施的級(jí)別
2）程序的威脅：木馬、后門、邏輯炸彈、棧與緩沖溢出、病毒
3）系統(tǒng)與網(wǎng)絡(luò)威脅：蠕蟲(chóng)、端口掃描、DoS
 
數(shù)據(jù)結(jié)構(gòu)
一、考試基本要求
要求考生系統(tǒng)地理解數(shù)據(jù)結(jié)構(gòu)的基本概念，掌握各種數(shù)據(jù)結(jié)構(gòu)的定義和實(shí)現(xiàn)算法。要求考生具有抽象思維能力，邏輯推理能力，和綜合運(yùn)用所學(xué)的知識(shí)分析問(wèn)題和解決問(wèn)題的能力。
 
二、考試范圍和主要內(nèi)容
1．預(yù)備知識(shí)
了解C++和Java基本語(yǔ)法結(jié)構(gòu)；掌握遞歸思想。
2．程序性能
了解復(fù)雜性的表示和計(jì)算方法。
掌握插入排序、選擇排序、冒泡排序、名詞排序基本思想。
3．數(shù)據(jù)描述
掌握線性表的公式化描述、鏈表描述、間接尋址等存儲(chǔ)方法，了解遍歷器的作用和實(shí)現(xiàn)方法，掌握插入、刪除、合并等運(yùn)算方法。
掌握箱子排序、基數(shù)排序
4．數(shù)組和矩陣
掌握對(duì)角矩陣、三對(duì)角矩陣、三角矩陣、對(duì)稱矩陣等特殊矩陣的特征，掌握存儲(chǔ)方法和基本運(yùn)算實(shí)現(xiàn)。
5．堆棧
掌握堆棧的基本概念、基本操作和實(shí)現(xiàn)方法。
掌握括號(hào)匹配的實(shí)現(xiàn)思想。
6．隊(duì)列 
掌握隊(duì)列的基本概念、基本操作和實(shí)現(xiàn)方法。第七章 跳表和散列
掌握散列的基本概念、基本操作和實(shí)現(xiàn)方法。
7．二叉樹(shù)
掌握二叉樹(shù)的基本概念、存儲(chǔ)方法、常用操作和特征；掌握二叉樹(shù)的前序、中序、后序、按層遍歷方法。
8．優(yōu)先隊(duì)列
掌握堆的基本概念和插入、刪除和初始化方法。
掌握堆排序思想。
掌握霍夫曼樹(shù)、霍夫曼編碼實(shí)現(xiàn)方法。
9．搜索樹(shù)
掌握二叉搜索樹(shù)(排序樹(shù))基本概念和插入、刪除、搜索的實(shí)現(xiàn)方法。
掌握m叉搜索樹(shù)和B樹(shù)基本概念以及插入、刪除、搜索的實(shí)現(xiàn)方法。
10．圖
掌握?qǐng)D基本概念。
掌握?qǐng)D的鄰接矩陣和臨界鏈表存儲(chǔ)方法；掌握?qǐng)D的深度優(yōu)先和廣度優(yōu)先遍歷算法。
了解圖的尋找路徑和尋找連通構(gòu)件方法。
了解生成樹(shù)的尋找方法。
11．貪婪算法
掌握AOV網(wǎng)的拓?fù)渑判蛩惴ā?br /> 掌握單源最短路徑Dijkstra算法。
掌握最小耗費(fèi)生成樹(shù)的概念、Prim算法和Kruskal算法。
12．分而治之算法
掌握歸并排序、快速排序?qū)崿F(xiàn)方法。

山東大學(xué)

本文來(lái)源：http://www.qiang-kai.com/shandongdaxue/cankaoshumu_379969.html