《计算机专业综合A》·考试大纲 山东建筑大学计算机科学与技术学院
山东建筑大学学术学位硕士研究生入学初试
《计算机专业综合A》课程考试大纲
一、数据结构(占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. 掌握希尔排序、快速排序、堆排序、归并排序、基数排序
《计算机专业综合A》·考试大纲 山东建筑大学计算机科学与技术学院
4. 各种排序算法的比较,包括时间性能、空间性能、稳定性等。
二、操作系统(占75分)
(一)操作系统概述
1. 操作系统的概念、特性和功能; 2. 操作系统的发展与分类;
3. 操作系统中内核态与用户态、中断、系统调用等概念; 4. 操作系统的体系结构如微内核的概念。
(二)进程管理
(1)进程与线程
1. 进程的概念;
2. 进程的状态与转换; 3. 进程控制; 4. 进程组织;
5. 进程通信:共享存储系统;消息传递系统;管道通信; 6. 线程概念;
7. 用户级线程与内核支持级线程。 (2)处理机调度
1. 调度的基本概念;
2. 调度时机、切换与过程; 3. 调度的基本准则; 4. 调度方式;
5. 典型调度算法:先来先服务调度算法;短作业优先调度算法;时间片轮转调度算
法;优先级调度算法;高响应比优先调度算法;多级反馈队列调度算法等。
(3)进程同步与互斥
1. 进程同步的基本概念;
2. 实现临界区互斥的基本方法:软件实现方法;硬件实现方法; 3. 使用信号量解决同步互斥问题; 4. 管程。 (4)死锁
1. 死锁的概念;
2. 形成死锁的四个必要条件;
3. 处理死锁的方法:死锁预防(破坏形成死锁的各个必要条件);死锁避免(系统
安全状态:银行家算法);死锁检测和解除。
(三)内存管理
(1)内存管理基础
1. 内存管理概念:程序装入与链接种类与过程;逻辑地址与物理地址空间; 2. 交换与覆盖;
3. 连续分配管理方式:固定分区与动态分区; 4. 非连续分配管理方式:基本分页管理方式、基本分段管理方式、段页式管理方式、
快表;
(2)虚拟内存管理:
1. 虚拟内存基本概念; 2. 请求分页管理方式;
《计算机专业综合A》·考试大纲 山东建筑大学计算机科学与技术学院
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. 设备独立性;
4. 假脱机技术(SPOOLing)。
(3)提高性能的高速缓存与缓冲区技术。 (五)文件管理
(1)文件系统基础
1. 文件概念;
2. 文件逻辑结构:顺序文件、索引文件、索引顺序文件;
3. 目录结构:文件控制块和索引节点、单级目录结构和两级目录结构、树形目录结构、目录的查询技术; 4. 文件共享及保护。 (2)磁盘组织与管理
1. 外存的组织方式/文件的物理机构:连续分配、链接分配(隐式链接与显式链接)、
索引分配(含混合索引算法);
2. 磁盘存储空间管理:空闲表/链法、位示图法、成组链接法;
3. 磁盘调度算法:先来先服务、最短寻道、扫描及循环扫描等算法。
(六)操作系统接口
(1)接口类型;
(2)系统调用的概念、类型和实现;
三、参考书目
[1] 严蔚敏,吴伟民. 数据结构(C语言版)[M]. 北京:清华大学出版社
[2] (美)萨尼(Sahni,S.) 著,汪诗林等译. 数据结构、算法与应用(C++语言描述). 北
京:机械工业出版社.
[3] 刘小晶、杜选主编. 数据结构——Java语言描述(第2版). 北京:清华大学出版社。 [4] 汤小丹,梁红兵,汤子瀛等.计算机操作系统(第四版)[M].西安电子科技大学出版社.2014
年5月第4版
[5] 汤小丹等. 计算机操作系统学习指导与题解[M]. 西安电子科技大学出版社,2008年9
月
[6] 操作系统考研辅导教程(计算机专业研究生入学考试全真题解)[M]. 电子科技大学出版
2020年山东建筑大学初试-《计算机专业综合A》考研大纲硕士研究生入学
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)