山東建筑大學2015考研考試大綱：計算機專業綜合

• 2025考研復試伴學班
• 2025考研復試標準班
• 2026考研英語全程班
• 26考研全科上岸規劃營「擇校▪規劃▪備考」
• 山東建筑大學2025考研專業課復習資料「真題▪筆記▪講義▪題庫」

　

一、數據結構（占75分）

（一）緒論

1.理解數據結構的基本概念；掌握數據的邏輯結構、存儲結構及其差異；

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

（二）線性表

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

2.掌握線性表順序存儲及基本操作實現；

3.掌握單向循環鏈表、雙向循環鏈表的實現；

4.了解靜態線性表的概念；

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

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

（三）棧和隊列

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

2.掌握順序棧定義及基本操作的實現；

3.掌握循環隊列定義及基本操作的實現；

4.了解優先隊列的概念和常用操作的實現；

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

（四）樹與二叉樹

1.理解樹的基本概念；

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

3.掌握二叉樹的順序存儲結構和鏈式存儲結構；

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

5.理解樹的存儲結構；

6.掌握樹和森林的遍歷、樹和森林與二叉樹的轉換；

7.掌握哈夫曼（Huffman）樹和哈夫曼編碼。

（五）圖

1.理解圖的基本概念；

2.掌握圖的鄰接矩陣和鄰接表存儲結構，掌握圖的基本操作在兩種存儲結構上的實現；

3.了解圖的多重鄰接表和十字鏈表存儲結構；

4.掌握圖的深度優先遍歷和廣度優先遍歷；

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

（六）查找

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

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

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

4.掌握二叉排序樹的定義、構造、插入、刪除及查找性能分析；

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

6.掌握哈希（Hash）表的構造、查找及查找性能分析。

（七）內部排序

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

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

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

4.各種排序算法的比較，包括時間性能、空間性能、穩定性等。

二、操作系統（占75分）

（一）操作系統概述

1.操作系統的概念、特性和功能

2.操作系統的發展與分類；

3.操作系統中內核態與用戶態、中斷、系統調用等概念

4.操作系統的體系結構如微內核的概念

（二）進程管理

（1）進程與線程

1.進程的概念

2.進程的狀態與轉換

3.進程控制

4.進程組織

5.進程通信：共享存儲系統；消息傳遞系統；管道通信。

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

（2）處理機調度

1.調度的基本概念

2.調度時機、切換與過程

3.調度的基本準則

4.調度方式

5.典型調度算法：先來先服務調度算法；短作業優先調度算法；時間片輪轉調度算法；優先級調度算法；高響應比優先調度算法；多級反饋隊列調度算法等。

（3）進程同步與互斥

1.進程同步的基本概念

2.實現臨界區互斥的基本方法：軟件實現方法；硬件實現方法。

3.信號量

4.管程

5.經典同步問題：生產者-消費者問題；讀者-寫者問題；哲學家進餐問題。

（4）死鎖

1.死鎖的概念

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

3.處理死鎖的方法：死鎖預防（破壞形成死鎖的各個必要條件）；死鎖避免（系統安全狀態：銀行家算法）；死鎖檢測和解除

（三）內存管理

（1）內存管理基礎

1.內存管理概念：程序裝入與鏈接；邏輯地址與物理地址空間；內存保護。

2.交換與覆蓋

3.連續分配管理方式：單一連續分配；分區分配。

4.非連續分配管理方式：分頁管理方式；分段管理方式；段頁式管理方式。

（2）虛擬內存管理：

1.虛擬內存基本概念

2.請求分頁管理方式

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

4.頁面分配策略

5.抖動：抖動現象；工作集。

6.請求分段管理方式

（四）輸入輸出（I/O）管理

（1）I/O管理概述

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

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

3.I/O軟件層次結構：中斷處理程序、設備驅動程序、設備獨立性軟件、用戶層I/O軟件

（2）設備分配

1.分配中使用的數據結構

2.獨占設備的分配過程

3.假脫機技術（SPOOLing）

（3）提高性能的高速緩存與緩沖區

（五）文件管理

（1）文件系統基礎

1.文件概念

2.文件邏輯結構：順序文件；索引文件；索引順序文件。

3.目錄結構：文件控制塊和索引節點；單級目錄結構和兩級目錄結構；樹形目錄結構；目錄的查詢技術。

4.文件共享及保護

（2）磁盤組織與管理

1.外存的組織方式/文件的物理機構：連續分配、鏈接分配、索引分配

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

3.磁盤調度算法：先來先服務、最短尋道、掃描算法、循環掃描等

三、參考書目

[1]嚴蔚敏，吳偉民.數據結構（C語言版）[M].北京：清華大學出版社

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

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

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

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