2022年山東建筑大學(xué)計(jì)算機(jī)專業(yè)綜合二碩士研究生考研大綱及參考書(shū)目 正文

一、數(shù)據(jù)結(jié)構(gòu)（占75分）
（一）緒論
1. 理解數(shù)據(jù)結(jié)構(gòu)的基本概念；掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其差異；
2. 理解算法的概念、重要特性、設(shè)計(jì)要求，掌握算法的時(shí)間復(fù)雜性分析。
（二）線性表
1. 理解線性表的定義和基本操作；
2. 掌握線性表順序存儲(chǔ)及基本操作實(shí)現(xiàn)；
3. 掌握線性表鏈?zhǔn)酱鎯?chǔ)及基本操作實(shí)現(xiàn)，包括單鏈表、單向循環(huán)鏈表和雙向循環(huán)鏈表的實(shí)現(xiàn)；
4. 理解順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的優(yōu)缺點(diǎn)及適用場(chǎng)合；
5. 理解線性表的應(yīng)用，如有序表的合并，一元多項(xiàng)式求和等。
（三）棧和隊(duì)列
1. 理解棧和隊(duì)列的特性和它們之間的差異，掌握棧和隊(duì)列的適用場(chǎng)合；
2. 掌握順序棧和鏈棧定義及基本操作的實(shí)現(xiàn)；
3. 掌握循環(huán)隊(duì)列和鏈隊(duì)列定義及基本操作的實(shí)現(xiàn)；
4. 理解棧和隊(duì)列的應(yīng)用。
（四）樹(shù)與二叉樹(shù)
1. 理解樹(shù)的基本概念；
2. 掌握二叉樹(shù)的定義及主要特征；
3. 掌握二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；
4. 掌握二叉樹(shù)的先序、中序和后序遍歷遞歸算法，掌握層次遍歷算法，掌握遍歷的應(yīng)用；
5. 理解樹(shù)的存儲(chǔ)結(jié)構(gòu)；
6. 掌握樹(shù)和森林的遍歷、樹(shù)和森林與二叉樹(shù)的轉(zhuǎn)換；
7. 掌握哈夫曼（Huffman）樹(shù)和哈夫曼編碼。
（五）圖
1. 理解圖的基本概念；
2. 掌握?qǐng)D的鄰接矩陣和鄰接表存儲(chǔ)結(jié)構(gòu)，理解圖的基本操作在兩種存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)；
3. 掌握?qǐng)D的深度優(yōu)先遍歷和廣度優(yōu)先遍歷過(guò)程；
4. 掌握最小生成樹(shù)（Prim和Kruskal）、單源點(diǎn)最短路徑（Dijkstra）和拓?fù)渑判蛩惴ㄟ^(guò)程。
（六）查找
1. 理解查找的基本概念；
2. 掌握順序查找法和查找性能分析；
3. 掌握折半查找法和查找性能分析；
4. 掌握二叉排序樹(shù)的定義、構(gòu)造、插入、刪除及查找性能分析；
5. 掌握哈希（Hash）表的構(gòu)造、查找及查找性能分析。
（七）內(nèi)部排序
1. 理解排序的基本概念；
2. 了解直接插入排序、折半插入排序、簡(jiǎn)單選擇排序；
3. 掌握希爾排序、快速排序、堆排序、歸并排序、基數(shù)排序的算法思想和排序過(guò)程；
4. 理解各種排序算法的比較，包括時(shí)間性能、空間性能、穩(wěn)定性等。
二、操作系統(tǒng)（占75分）
（一）操作系統(tǒng)概述
1. 操作系統(tǒng)的概念、特性和功能，以及發(fā)展與分類；
2. 操作系統(tǒng)中內(nèi)核態(tài)與用戶態(tài)、中斷、系統(tǒng)調(diào)用等概念；
3. 系統(tǒng)結(jié)構(gòu)（微內(nèi)核與宏內(nèi)核）；
（二）進(jìn)程管理
（1）進(jìn)程與線程
1. 進(jìn)程的概念、狀態(tài)與轉(zhuǎn)換、進(jìn)程控制；
2. 進(jìn)程通信：共享存儲(chǔ)系統(tǒng)；消息傳遞系統(tǒng)；管道通信；
3. 線程概念、用戶級(jí)和內(nèi)核支持級(jí)線程的實(shí)現(xiàn)。
（2）處理機(jī)調(diào)度
1. 調(diào)度的基本概念、基本準(zhǔn)則、調(diào)度方式、調(diào)度時(shí)機(jī)；
2. 典型調(diào)度算法：先來(lái)先服務(wù)調(diào)度算法；短作業(yè)優(yōu)先調(diào)度算法；時(shí)間片輪轉(zhuǎn)調(diào)度算法；優(yōu)先級(jí)調(diào)度算法；高響應(yīng)比優(yōu)先調(diào)度算法；多級(jí)反饋隊(duì)列調(diào)度算法等。
（3）進(jìn)程同步與互斥
1. 進(jìn)程同步的基本概念；
2. 實(shí)現(xiàn)臨界區(qū)互斥的基本方法：軟件實(shí)現(xiàn)方法；硬件實(shí)現(xiàn)方法；
3. 使用信號(hào)量解決進(jìn)程間的同步與互斥問(wèn)題。
（4）死鎖
1. 死鎖的概念、形成死鎖的四個(gè)必要條件；
2. 處理死鎖的方法：死鎖預(yù)防（破壞形成死鎖的各個(gè)必要條件）；死鎖避免（系統(tǒng)安全狀態(tài)：銀行家算法）；死鎖檢測(cè)和解除。
（三）內(nèi)存管理
（1）內(nèi)存管理基礎(chǔ)
1.程序裝入與鏈接過(guò)程；邏輯地址與物理地址空間；
2. 交換與覆蓋；
3. 連續(xù)分配管理方式：固定分區(qū)和動(dòng)態(tài)分區(qū)分配算法；
4. 非連續(xù)分配管理方式：基本分頁(yè)管理方式；基本分段管理方式；段頁(yè)式管理方式。
（2）虛擬內(nèi)存管理：
1. 虛擬內(nèi)存基本概念；
2. 請(qǐng)求分頁(yè)管理方式、請(qǐng)求分段管理方式；
3. 頁(yè)面置換算法：最佳置換算法（OPT）；先進(jìn)先出置換算法（FIFO）；最近最少使用置換算法（LRU）；改進(jìn)的時(shí)鐘置換算法（CLOCK）；
4. 頁(yè)面分配策略；
5. 抖動(dòng)：抖動(dòng)現(xiàn)象；工作集。
（四）輸入輸出（I/O）管理
（1）I/O管理概述
1. I/O設(shè)備、設(shè)備控制器、通道；
2. I/O控制方式：程序I/O、中斷驅(qū)動(dòng)I/O、直接存儲(chǔ)器訪問(wèn)I/O和通道I/O
3. I/O軟件層次結(jié)構(gòu)：中斷處理程序、設(shè)備驅(qū)動(dòng)程序、設(shè)備獨(dú)立性軟件、用戶層I/O軟件，各層次軟件的任務(wù)和工作過(guò)程。
（2）設(shè)備分配
1. 分配中使用的數(shù)據(jù)結(jié)構(gòu)；
2. 獨(dú)占設(shè)備的分配過(guò)程；
3. 假脫機(jī)技術(shù)（SPOOLing）。
（3）提高性能的高速緩存與緩沖區(qū)技術(shù)
（五）文件管理
（1）文件系統(tǒng)基礎(chǔ)
1. 文件概念；
2. 文件邏輯結(jié)構(gòu)：順序文件；索引文件；索引順序文件；
3. 目錄結(jié)構(gòu)：文件控制塊和索引節(jié)點(diǎn)；單級(jí)目錄結(jié)構(gòu)和兩級(jí)目錄結(jié)構(gòu)；樹(shù)形目錄結(jié)構(gòu)；目錄的查詢技術(shù)；
4. 文件共享及保護(hù)。
（2）磁盤(pán)組織與管理
1. 外存的組織方式/文件的物理機(jī)構(gòu)：連續(xù)分配、鏈接分配、索引分配；
2. 磁盤(pán)存儲(chǔ)空間管理：空閑表/鏈法、位示圖法、成組鏈接法；
3. 磁盤(pán)調(diào)度算法：先來(lái)先服務(wù)、最短尋道、掃描及循環(huán)掃描等算法。
（六）操作系統(tǒng)接口
（1）接口類型；
（2）系統(tǒng)調(diào)用的概念、類型和實(shí)現(xiàn)；

三、參考書(shū)目
[1] 嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）[M]. 北京：清華大學(xué)出版社
[2] （美）薩尼（Sahni，S.）　著，汪詩(shī)林等譯. 數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用（C++語(yǔ)言描述）. 北京：機(jī)械工業(yè)出版社.
[3] 劉小晶、杜選主編. 數(shù)據(jù)結(jié)構(gòu)——Java語(yǔ)言描述（第2版）. 北京：清華大學(xué)出版社。
[4] 湯小丹，梁紅兵，湯子瀛等.計(jì)算機(jī)操作系統(tǒng)（第四版）[M].西安電子科技大學(xué)出版社.2014年5月第4版
[5] 湯小丹等. 計(jì)算機(jī)操作系統(tǒng)學(xué)習(xí)指導(dǎo)與題解[M]. 西安電子科技大學(xué)出版社，2008年9月
[6] 操作系統(tǒng)考研輔導(dǎo)教程(計(jì)算機(jī)專業(yè)研究生入學(xué)考試全真題解)[M]. 電子科技大學(xué)出版社，2010年9月第1版

山東建筑大學(xué)

本文來(lái)源：http://zgxindalu.cn/sdjzdx/cksm_495532.html