年硕士研究生招生考试大纲北京工业大学
考试科目名称：软件工程学科专业基础考试科目代码：
一、考试要求：
软件工程学科专业基础考试大纲适用于北京工业大学信息学部软件学院（）软件工程、（）电子信息（专业学位）的硕士研究生招生考试。考试内容包含数据结构与算法和操作系统两个部分，它们是软件工程学科的重要基础理论。数据结构与算法考试内容主要包括数据结构的基本概念和术语、线性表、栈和队列、数组、串和广义表、树和二叉树、集合与字典、搜索结构、图和内部排序。要求考生对其中的基本概念有很深入的理解，掌握算法的设计及评价方法，具有综合运用所学知识分析问题和解决问题的能力。操作系统的考试内容主要包括操作系统进程、内存、文件和I/O管理的策略、算法、机制以及相互关系。要求考生掌握操作系统的基本概念、基本原理和基本功能，理解操作系统的整体运行过程。
二、考试内容：
（一）数据结构与算法部分
数据结构的基本概念和术语
（1）掌握数据结构的基本概念和术语
（2）掌握数据结构的逻辑结构、存储结构
（3）熟练掌握抽象数据类型的表示方法
（4）熟练掌握算法的时间复杂度、空间复杂度的分析方法
2.线性表
（1）掌握线性表的逻辑结构
（2）掌握线性表的顺序存储结构及插入删除、查找、遍历等操作的实现
（3）掌握线性表的链式存储结构及插入删除、查找、遍历等操作的实现
3.栈和队列
（1）掌握栈的定义、栈的抽象数据类型及存贮表示
（2）熟练掌握栈操作的实现
（3）熟练掌握递归算法
（4）掌握队列的定义、队列的抽象数据类型及存贮表示
（5）熟练掌握队列操作的实现及应用
4.数组、串和广义表
（1）理解数组的定义、存贮表示及应用
（2）理解串的定义、运算和存贮表示的特点
（3）掌握串运算的算法
（4）掌握广义表的定义、ADT、存贮表示
（5）掌握广义表的遍历算法
5.树
（1）掌握树结构的概念、术语和ADT
（2）掌握二叉树的性质和存贮表示
（3）熟练掌握二叉树遍历算法及运用
（4）掌握二叉树线索化技术
（5）掌握树和森林的存贮表示、与二叉树的转化方法及树的遍历
（6）熟练掌握树的应用（Huffman树）
6.集合与字典
（1）掌握集合的概念、术语、ADT及操作的实现
（2）掌握字典的概念、术语、ADT及操作的实现
7.搜索结构
（1）熟练掌握静态查找技术
（2）熟练掌握动态查找技术
（3）掌握B树及链树的存贮表示与查找
（4）熟练掌握哈希表技术
（5）掌握查找技术的综合分析评价方法
8.图
（1）掌握图的基本概念、术语和ADT
（2）掌握图的存贮方法
（3）熟练掌握图的DFS和BFS搜索算法及应用
（4）熟练掌握最短路径算法及应用
（5）熟练掌握拓扑排序算法及应用
9.内部排序
（1）掌握排序的概念及术语
（2）熟练掌握插入排序、冒泡排序、选择排序、快速排序、归并排序、堆排序及基数排序算法
（3）掌握排序方法的最好、最坏情况分析
（二）操作系统部分
操作系统概述
（1）操作系统的概念、特征、功能和提供的服务（2）操作系统的发展与分类（3）操作系统的运行环境1）内核态与用户态2）中断、异常3）系统调用（4）操作系统体系结构
2.进程管理
（1）进程与线程
1）进程概念2）进程的状态与转换3）进程控制4）进程组织5）进程通信：共享存储系统，消息传递系统，管道通信。6）线程概念与多线程模型
（2）处理机调度
1）调度的基本概念2）调度时机、切换与过程3）调度的基本准则4）调度方式5）典型调度算法：先来先服务调度算法，短作业（短进程、短线程）优先调度算法，时间片轮转调度算法，优先级调度算法，高响应比优先调度算法，多级反馈队列调度算法
（3）同步与互斥
1）进程同步的基本概念2）实现临界区互斥的基本方法：软件实现方法，硬件实现方法
（4）死锁
1）死锁的概念2）死锁处理策略3）死锁预防4）死锁避免：系统安全状态，银行家算法5）死锁检测和解除
3.内存管理
（1）内存管理基础
1）内存管理概念：程序装入与链接，逻辑地址与物理地址空间，内存保护2）交换与覆盖3）连续分配管理方式4）非连续分配管理方式：分页管理方式，分段管理方式，段页式管理方式
（2）虚拟内存管理
1）虚拟内存基本概念2）请求分页管理方式3）页面置换算法：最佳置换算法（OPT），先进先出置换算法（FIFO），最近最少使用置换算法（LRU），时钟置换算法（CLOCK）4）页面分配策略5）工作集6）抖动
4.文件管理
（1）文件系统基础
1）文件概念2）文件的结构：顺序文件，索引文件，索引顺序文件3）目录结构：文件控制块和索引节点，单级目录结构和两级目录结构，树形目录结构4）文件共享5）文件保护：访问类型，访问控制
（2）文件系统实现
1）文件系统层次结构2）目录实现3）文件实现
（3）磁盘组织与管理
1）磁盘的结构2）磁盘调度算法3）磁盘的管理
5.输入输出(I/O)管理
（1）I/O管理概述
1）I/O控制方式2）I/O软件层次结构
（2）I/O核心子系统
1）I/O调度概念2）高速缓存与缓冲区3）设备分配与回收4）假脱机技术(SPOOLing)
三、参考书目
1.殷人昆编著，数据结构（用面向对象方法与C++语言描述）（第2版），清华大学出版社，-09-01
2.严蔚敏等编著，数据结构（C语言版），清华大学出版社，年11月
3.AndrewS.Tanenbaum，陈向群等译，现代操作系统，机械工业出版社，ISBN-2
四历年真题：