山东建筑大学

　　山东建筑大学研究生入学考试《计算机专业综合》科目在职研究生考试大纲如下：

　　一、数据结构(占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版