山东建筑大学2015考研考试大纲：计算机专业综合

• 2025考研英语全程班 早鸟3班
• 2025/2026半岛真人体育 课 免费体验集训营（线上/线下）
• 山东建筑大学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版