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

　　一、數(shù)據(jù)結(jié)構(gòu)(占75分)

　　(一)緒論

　　1. 理解數(shù)據(jù)結(jié)構(gòu)的基本概念；掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其差異；

　　2. 理解算法的概念、重要特性、設計要求，掌握算法的時間和空間復雜性分析。

　　(二)線性表

　　1. 理解線性表的定義和基本操作；

　　2. 掌握線性表順序存儲及基本操作實現(xiàn)；

　　3. 掌握單向循環(huán)鏈表、雙向循環(huán)鏈表的實現(xiàn)；

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

　　5. 了解順序存儲和鏈式存儲的優(yōu)缺點及適用場合；

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

　　(三)棧和隊列

　　1. 理解棧和隊列的特性和它們之間的差異，掌握棧和隊列的適用場合;

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

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

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

　　5. 掌握棧和隊列的應用。

　　(四)樹與二叉樹

　　1. 理解樹的基本概念;

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

　　3. 掌握二叉樹的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu);

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

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

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

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

　　(五)圖

　　1. 理解圖的基本概念；

　　2. 掌握圖的鄰接矩陣和鄰接表存儲結(jié)構(gòu)，掌握圖的基本操作在兩種存儲結(jié)構(gòu)上的實現(xiàn);

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

　　4. 掌握圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷;

　　5. 掌握圖的基本應用中的最小生成樹(Prim和Kruskal)、最短路徑(Dijkstra和Floyd)、拓撲排序算法及復雜性分析。

　　(六)查找

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

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

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

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

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

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

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

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

　　2. 了解直接插入排序、折半插入排序、簡單選擇排序;

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

　　4. 各種排序算法的比較，包括時間性能、空間性能、穩(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)核的概念

　　(二)進程管理

　　(1)進程與線程

　　1. 進程的概念

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

　　3. 進程控制

　　4. 進程組織

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

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

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

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

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

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

　　4. 調(diào)度方式

　　5. 典型調(diào)度算法：先來先服務調(diào)度算法;短作業(yè)優(yōu)先調(diào)度算法;時間片輪轉(zhuǎn)調(diào)度算法;優(yōu)先級調(diào)度算法;高響應比優(yōu)先調(diào)度算法;多級反饋隊列調(diào)度算法等。

　　(3)進程同步與互斥

　　1. 進程同步的基本概念

　　2. 實現(xiàn)臨界區(qū)互斥的基本方法：軟件實現(xiàn)方法;硬件實現(xiàn)方法。

　　3. 信號量

　　4. 管程

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

　　(4)死鎖

　　1. 死鎖的概念

　　2. 形成死鎖的四個必要條件

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

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

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

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

　　2. 交換與覆蓋

　　3. 連續(xù)分配管理方式：單一連續(xù)分配;分區(qū)分配。

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

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

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

　　2. 請求分頁管理方式

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

　　4. 頁面分配策略

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

　　6. 請求分段管理方式

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

　　(1)I/O管理概述

　　1. I/O設備及設備控制器

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

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

　　(2)設備分配

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

　　2. 獨占設備的分配過程

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

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

　　(五)文件管理

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

　　1. 文件概念

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

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

　　4. 文件共享及保護

　　(2)磁盤組織與管理

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

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

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

　　三、參考書目

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

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

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

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

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