山東建筑大學(xué)研究生入學(xué)考試《計(jì)算機(jī)專業(yè)綜合》科目在職研究生考試大綱如下：

　　一、數(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. 掌握單向循環(huán)鏈表、雙向循環(huán)鏈表的實(shí)現(xiàn)；

　　4. 了解靜態(tài)線性表的概念；

　　5. 了解順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的優(yōu)缺點(diǎn)及適用場(chǎng)合；

　　6. 掌握線性表的應(yīng)用，如集合的并、交、差運(yùn)算的實(shí)現(xiàn)，一元多項(xiàng)式求和等。

　　(三)棧和隊(duì)列

　　1. 理解棧和隊(duì)列的特性和它們之間的差異，掌握棧和隊(duì)列的適用場(chǎng)合;

　　2. 掌握順序棧定義及基本操作的實(shí)現(xiàn);

　　3. 掌握循環(huán)隊(duì)列定義及基本操作的實(shí)現(xiàn);

　　4. 了解優(yōu)先隊(duì)列的概念和常用操作的實(shí)現(xiàn);

　　5. 掌握棧和隊(duì)列的應(yīng)用。

　　(四)樹與二叉樹

　　1. 理解樹的基本概念;

　　2. 掌握二叉樹的定義及主要特征;

　　3. 掌握二叉樹的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu);

　　4. 掌握二叉樹的先序、中序、后序和層次遍歷及遍歷應(yīng)用;

　　5. 理解樹的存儲(chǔ)結(jié)構(gòu);

　　6. 掌握樹和森林的遍歷、樹和森林與二叉樹的轉(zhuǎn)換;

　　7. 掌握哈夫曼(Huffman)樹和哈夫曼編碼。

　　(五)圖

　　1. 理解圖的基本概念；

　　2. 掌握?qǐng)D的鄰接矩陣和鄰接表存儲(chǔ)結(jié)構(gòu)，掌握?qǐng)D的基本操作在兩種存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn);

　　3. 了解圖的多重鄰接表和十字鏈表存儲(chǔ)結(jié)構(gòu);

　　4. 掌握?qǐng)D的深度優(yōu)先遍歷和廣度優(yōu)先遍歷;

　　5. 掌握?qǐng)D的基本應(yīng)用中的最小生成樹(Prim和Kruskal)、最短路徑(Dijkstra和Floyd)、拓?fù)渑判蛩惴�及�?fù)雜性分析。

　　(六)查找

　　1. 理解查找的基本概念；

　　2. 掌握順序查找法和查找性能分析；

　　3. 掌握折半查找法和查找性能分析；

　　4. 掌握二叉排序樹的定義、構(gòu)造、插入、刪除及查找性能分析;

　　5. 理解二叉平衡樹；了解B+樹;

　　6. 掌握哈希(Hash)表的構(gòu)造、查找及查找性能分析。

　　(七)內(nèi)部排序

　　1. 理解排序的基本概念;

　　2. 了解直接插入排序、折半插入排序、簡(jiǎn)單選擇排序;

　　3. 掌握希爾排序、快速排序、堆排序、歸并排序、基數(shù)排序

　　4. 各種排序算法的比較，包括時(shí)間性能、空間性能、穩(wěn)定性等。

　　二、操作系統(tǒng)(占75分)

　　(一)操作系統(tǒng)概述

　　1. 操作系統(tǒng)的概念、特性和功能

　　2. 操作系統(tǒng)的發(fā)展與分類;

　　3. 操作系統(tǒng)中內(nèi)核態(tài)與用戶態(tài)、中斷、系統(tǒng)調(diào)用等概念

　　4. 操作系統(tǒng)的體系結(jié)構(gòu)如微內(nèi)核的概念

　　(二)進(jìn)程管理

　　(1)進(jìn)程與線程

　　1. 進(jìn)程的概念

　　2. 進(jìn)程的狀態(tài)與轉(zhuǎn)換

　　3. 進(jìn)程控制

　　4. 進(jìn)程組織

　　5. 進(jìn)程通信：共享存儲(chǔ)系統(tǒng);消息傳遞系統(tǒng);管道通信。

　　6. 線程概念與多線程模型

　　(2)處理機(jī)調(diào)度

　　1. 調(diào)度的基本概念

　　2. 調(diào)度時(shí)機(jī)、切換與過程

　　3. 調(diào)度的基本準(zhǔn)則

　　4. 調(diào)度方式

　　5. 典型調(diào)度算法：先來先服務(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)量

　　4. 管程

　　5. 經(jīng)典同步問題：生產(chǎn)者-消費(fèi)者問題;讀者-寫者問題;哲學(xué)家進(jìn)餐問題。

　　(4)死鎖

　　1. 死鎖的概念

　　2. 形成死鎖的四個(gè)必要條件

　　3. 處理死鎖的方法：死鎖預(yù)防(破壞形成死鎖的各個(gè)必要條件);死鎖避免(系統(tǒng)安全狀態(tài)：銀行家算法);死鎖檢測(cè)和解除

　　(三)內(nèi)存管理

　　(1)內(nèi)存管理基礎(chǔ)

　　1. 內(nèi)存管理概念：程序裝入與鏈接;邏輯地址與物理地址空間;內(nèi)存保護(hù)。

　　2. 交換與覆蓋

　　3. 連續(xù)分配管理方式：?jiǎn)我贿B續(xù)分配;分區(qū)分配。

　　4. 非連續(xù)分配管理方式：分頁管理方式;分段管理方式;段頁式管理方式。

　　(2)虛擬內(nèi)存管理：

　　1. 虛擬內(nèi)存基本概念

　　2. 請(qǐng)求分頁管理方式

　　3. 頁面置換算法：最佳置換算法(OPT);先進(jìn)先出置換算法(FIFO);最近最少使用置換算法(LRU);時(shí)鐘置換算法(CLOCK)。

　　4. 頁面分配策略

　　5. 抖動(dòng)：抖動(dòng)現(xiàn)象;工作集。

　　6. 請(qǐng)求分段管理方式

　　(四)輸入輸出(I/O)管理

　　(1)I/O管理概述

　　1. I/O設(shè)備及設(shè)備控制器

　　2. I/O控制方式：程序I/O、中斷驅(qū)動(dòng)I/O、直接存儲(chǔ)器訪問I/O和通道I/O

　　3. I/O軟件層次結(jié)構(gòu)：中斷處理程序、設(shè)備驅(qū)動(dòng)程序、設(shè)備獨(dú)立性軟件、用戶層I/O軟件

　　(2)設(shè)備分配

　　1. 分配中使用的數(shù)據(jù)結(jié)構(gòu)

　　2. 獨(dú)占設(shè)備的分配過程

　　3. 假脫機(jī)技術(shù)(SPOOLing)

　　(3)提高性能的高速緩存與緩沖區(qū)

　　(五)文件管理

　　(1)文件系統(tǒng)基礎(chǔ)

　　1. 文件概念

　　2. 文件邏輯結(jié)構(gòu)：順序文件;索引文件;索引順序文件。

　　3. 目錄結(jié)構(gòu)：文件控制塊和索引節(jié)點(diǎn);單級(jí)目錄結(jié)構(gòu)和兩級(jí)目錄結(jié)構(gòu);樹形目錄結(jié)構(gòu);目錄的查詢技術(shù)。

　　4. 文件共享及保護(hù)

　　(2)磁盤組織與管理

　　1. 外存的組織方式/文件的物理機(jī)構(gòu)：連續(xù)分配、鏈接分配、索引分配

　　2. 磁盤存儲(chǔ)空間管理：空閑表/鏈法、位示圖法、成組鏈接法

　　3. 磁盤調(diào)度算法：先來先服務(wù)、最短尋道、掃描算法、循環(huán)掃描等

　　三、參考書目

　　[1] 嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)(C語言版)[M]. 北京：清華大學(xué)出版社

　　[2] (美)Ellis Horowitz， Sartaj Sahni，Dinesh Mehta著， 張力等譯. 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)(C++語言版)(第2版)[M]. 北京：清華大學(xué)出版社

　　[3] 湯子瀛. 計(jì)算機(jī)操作系統(tǒng)(修訂版)[M]. 西安電子科技大學(xué)出版社，2005年1月

　　[4] 湯小丹等. 計(jì)算機(jī)操作系統(tǒng)學(xué)習(xí)指導(dǎo)與題解[M]. 西安電子科技大學(xué)出版社，2008年9月

　　[5] 操作系統(tǒng)考研輔導(dǎo)教程(計(jì)算機(jī)專業(yè)研究生入學(xué)考試全真題解)[M]. 電子科技大學(xué)出版社，2010年9月第1版