2022年天津理工大学计算机科学与工程学院硕士研究生考试科目数据结构与操作系统大纲 正文

一、考试方式
考试采用笔试形式，考试时间为180分钟，试卷满分为150分。

二、试卷结构与分数比重
数据结构占80分，题型及分配比例：选择题（25%）、综合应用题（75%）。
操作系统占70分，题型及分配比例：填空题（20%）、选择题（20%）、简述题（20%）、算法实现与综合分析习题（40%）。

 三、考查的知识范围
《数据结构与操作系统》入学考试总分150分，包括两部分内容：其中数据结构考试主要涉及线性结构、树、图、查找和排序中的典型数据结构和算法，要能够针对具体问题进行分析，选择正确的逻辑结构、设计合理的存储结构、提出解决问题的方法或算法，并能对所选方法和算法的正确性、复杂性进行分析，占80分；操作系统考试主要涉及基本概念、原理和功能，理解操作系统的整体运行过程， 掌握操作系统进程、内存、文件和I/O管理的策略、算法、机制以及相互关系，能够运用所学的操作系统原理、方法与技术分析问题和解决问题，并能利用C语言描述相关算法，占70分。

数据结构部分
一、绪论
1． 数据结构相关基本概念
2． 逻辑结构和物理结构
3． 算法效率的度量（O－表示法）
二、线性表、栈和队列（以下各点要求掌握算法的程序实现）
1． 顺序表的表示和基本操作的实现算法
2． 单链表、循环链表、双向链表的表示和基本操作的实现算法
3． 栈的表示和基本操作的实现算法
4． 循环队列、链队列的表示和基本操作的实现算法
三、数组、递归
1． 数组的存储方式
2． 特殊矩阵的压缩存储
3． 递归思想的特点
4． 递归算法和递归函数
四、树和二叉树
1． 树的定义和基本术语
2． 二叉树的定义、性质，二叉链表存储结构
3． 完全二叉树的性质
4． 二叉树的深度优先（先序、中序、后序）和广度优先（层序）遍历算法和程序实现
5． 树的存储结构
6． 树、森林与二叉树的转换
7． 哈夫曼树的定义、性质、构造方法、哈夫曼树的应用
五、图
1． 图的定义和术语
2． 图的邻接矩阵、邻接表存储结构
3． 图的深度优先搜索、广度优先搜索及其算法实现
4． 生成树的定义，图的最小生成树定义与构造方法（不要求算法实现）
5． 拓扑排序
6． 单源最短路径问题的求解
六、查找
1． 平均搜索长度（ASL）的定义
2． 顺序表的查找算法、程序实现和ASL分析
3． 二分查找法的算法描述、程序实现和ASL分析
4． 索引顺序表的查找（分块查找）方法和和ASL分析
5． 二叉排序树的定义、插入、删除操作
6． 平衡二叉树的定义、构造（掌握4种旋转方法），计算等概率下查找成功的ASL和查找不成功的ASL
7． B-树的定义、插入与删除操作
8． 散列表的概念，几种常用散列函数的构造方法
9． 散列表处理冲突的方法（线性探查法、二次探查法、再散列法、链地址法），计算等概率下查找成功的ASL和查找不成功的ASL
10．散列表负载因子（装填因子）α的定义
七、排序（以下每种排序算法要求掌握排序过程和程序实现）
1． 直接插入排序、希尔排序
2． 冒泡排序、快速排序
3． 简单选择排序、堆排序
4． 归并排序
5． 基数排序（箱排序）
6． 以上各种排序算法的时间复杂度分析，各自的特征及其比较

操作系统部分
一、操作系统概述
1.操作系统的概念、特征、功能和作用
2.操作系统的发展与分类
3.操作系统体系结构
二、进程管理
1.进程与线程
(1)进程概念
(2)进程的状态与转换
(3)进程控制
(4)进程同步
(5)进程通信
共享存储系统；消息传递系统；管道通信。
(6)线程概念与线程实现方式
2.处理机调度
(1)调度的基本概念
(2)调度时机、切换与过程
(3)调度的基本准则
(4)调度方式
(5)典型调度算法
先来先服务调度算法；短作业(短进程、短线程)优先调度算法；时间片轮转调度算法；优先级调度算法；
高响应比优先调度算法；多级反馈队列调度算法。
3.同步与互斥
(1)进程同步的基本概念
(2)实现临界区互斥的基本方法
软件实现方法；硬件实现方法。
(3)信号量机制
(4)管程机制
(5)经典同步问题
生产者-消费者问题；读者-写者问题；哲学家进餐问题；睡眠理发师问题。
4.死锁
(1)死锁的概念
(2)死锁处理策略
(3)死锁预防
(4)死锁避免
系统安全状态；银行家算法。
(5)死锁检测和解除
三、存储器管理
1.存储器管理概念
(1)存储器的层次结构
(2)程序的装入和链接
绝对装入方式；可重定位装入方式；动态运行时装入方式。
静态链接方式；装入时动态链接方式；运行时动态链接方式。
(3)交换技术
(4)连续分配存储管理方式
单一连续分配；固定分区分配；动态分区分配(基于顺序搜索的动态分区分配算法、基于索引的动态分区分配算法)；动态可重定位分区分配。
(5)非连续分配管理方式
分页管理方式；分段管理方式；段页式管理方式。
  2.虚拟内存管理
(1)虚拟存储器基本概念
(2)请求分页存储管理方式
(3)页面置换算法
最佳置换算法OPT；先进先出置换算法FIFO；最近最久未使用置换算法LRU；最少使用置换算法LFU；时钟置换算法CLOCK；页面缓冲算法PBA。
(4)页面分配策略
(5)抖动与工作集
(6)请求分段存储管理方式
四、输入输出(I/O)管理
1.I/O管理概述
(1)I/O系统的功能
(2)I/O软件层次结构
(3)I/O系统接口
(4)I/O控制方式
(5)设备控制器
(6)设备驱动程序
(7)设备无关性
2.I/O核心子系统
(1)缓冲区管理
(2)设备分配与回收
(3)假脱机技术(SPOOLing)
3.磁盘存储器的性能和调度
(1)磁盘性能与结构
(2)磁盘调度算法
先来先付服务FCFSl；最短寻道时间优先DDTF；扫描算法SCAN (电梯调度算法)；循环扫描算法CSCAN；NStepSCAN和FSCAN调度算法。
五、文件管理
1.文件系统基础
(1)文件概念
(2)文件的逻辑结构（顺序文件、索引文件、索引顺序文件）
(3)文件目录
文件控制块和索引节点；单级目录结构和两级目录结构；树形目录结构。
(4)文件共享
(5)文件保护
2.磁盘存储器的管理
(1)外存组织方式
连续组织方式；链接组织方式（FAT技术、NTFS技术）；索引组织方式。
(2)文件存储空间的管理
空闲表法；空闲链表法；位示图法；成组链接法。
(3)提高磁盘I/O速度的方法
(4)磁盘可靠性技术
(5)数据一致性控制

四、参考书目
 《数据结构》 机械工业出版社 2008年     戴敏
《计算机操作系统》(第四版)，汤小丹等编著, 西安电子科技大学出版社。

天津理工大学

本文来源：http://www.okaoyan.com/tianjinligongdaxue/cankaoshumu_461230.html