一、考试目的

　　西北师范大学专升本招生《计算机科学与技术专业》专业综合课包括两部分内容：数据结构和操作系统。考试目的是检查学生是否牢固掌握《数据结构》和《操作系统》两门课程相关知识的一次水平测定，全面考核普通高校计算机专科(含高职)应届毕业生对专业核心课程《数据结构》和《操作系统》的掌握程度，要求学生比较系统地理解数据结构和操作系统的基本概念和基本理论。

　　二、考试内容

　　数据结构部分

　　(一)数据结构的概念

　　1. 什么是数据结构(逻辑结构，存储结构，运算);

　　2. 算法，算法分析，算法特性;

　　3.算法与程序的差别。

　　(二)线性表

　　1.线性表(向量)的定义，操作，算法;

　　2.顺序表的概念，存储表示，查找，插入，删除等运算和算法;

　　3.链表的概念及其特点;

　　4.单链表的概念，存储表示，查找，插入，删除等运算和算法;

　　5.双链表的概念，存储表示，查找，插入，删除等运算和算法。

　　(三)栈和队列

　　1.栈的定义，顺序、链式表示与实现，算法;

　　2.队列的定义，顺序、链式表示与实现，算法。

　　(四)树和二叉树

　　1.树和二叉树的概念;

　　2.树(林)与二叉树的相互转换;

　　3.二叉树的存储表示(1)二叉链表(2)完全二叉树的顺序存储;

　　4.二叉树与树的遍历的概念，各种遍历方法;

　　5.二叉树遍历的算法;

　　6.二叉树中其他算法(结点统计，高度计算，左右子树交换等)。

　　(五)图

　　1.图的概念和相关术语;

　　2.图的存储表示方法：邻接矩阵，邻接表，邻接多重表;

　　3.图的遍历： 深度优先遍历，广度优先遍历;

　　4.最小生成树的概念，构造方法，算法;

　　5.拓扑排序的概念，算法思想，算法;

　　6.最短路径的概念，构造方法，算法。

　　(六)查找

　　1.顺序查找的概念，算法，时间复杂度;

　　2.折半查找的概念，算法，时间复杂度;

　　3.二叉排序树的概念，插入，删除运算;

　　5.平衡二叉排序树(AVL)的概念，构造方法(如何调整。)

　　6.哈希法：(1)基本概念;

　　(2)哈希函数的构造方法;

　　(3)冲突的处理：拉链法，开地址法，算法。

　　(七)内排序

　　1.排序的概念，内排序和外排序，排序算法的稳定性;

　　2.内排序的分类;

　　3.各种排序的基本思想，例子，算法，稳定性，时空复杂度。

　　操作系统部分

　　(一)操作系统的基本概念

　　1. 理解操作系统的定义、特征以及设置操作系统的目的;

　　2. 了解操作系统在计算机系统中的地位、操作系统的形成和发展;

　　3. 掌握多道程序设计的思想、特点和优点;

　　4. 了解操作系统的分类;理解批处理、分时和实时系统的特征;

　　5. 理解操作系统的功能;

　　6. 理解操作系统为用户提供的接口;

　　7. 掌握系统调用的概念、过程及其与一般的过程调用的区别;

　　8. 了解操作系统内核的概念和分类。

　　(二)进程管理和处理器管理

　　1. 理解并掌握程序的并发执行和资源共享;

　　2. 掌握程序并发执行的特性;

　　3. 掌握进程的概念、特征和状态转换;

　　4. 了解进程控制及进程控制原语;

　　5. 熟练掌握常用的调度算法;

　　6. 熟练掌握作业、进程和程序之间的区别和联系;

　　7. 理解并掌握进程间的同步与互斥;

　　8. 理解信号量及P，V操作，并能利用信号量机制实现进程间的同步与互斥;

　　9. 理解并熟练掌握利用信号量机制实现的生产者——消费者问题;

　　10.了解高级通讯原语(消息缓冲方式，信箱方式);

　　11. 理解并掌握死锁的概念、起因及产生死锁的必要条件;

　　12. 了解处理死锁的四种对策(预防策略，避免策略，检测和解除);

　　13.了解单项资源的银行家算法和多种资源的银行家算法;

　　(三)存储管理

　　1. 理解并掌握存储管理的基本概念功能及物理地址和逻辑地址之间的关系;

　　2. 了解早期计算机系统中主要采用的单一连续分配，分区分配，覆盖和交换的存储管理方案;

　　3. 理解并掌握页式、段式和段页式虚拟存储管理的基本原理和地址转换关系;

　　4. 理解并熟练掌握各种页面置换算法(FIFO，LRU，LRU近似算法)。

　　(四)文件管理系统

　　1. 理解文件和文件系统的概念;

　　2. 了解文件的基本类型及文件系统的基本功能;

　　3. 理解文件的逻辑结构(记录式文件，流式文件);

　　4. 理解文件的物理结构(连续结构，串连结构，索引文件);

　　5. 掌握文件的存取方法(顺序存取法，直接存取法，按键存取法);

　　6. 理解文件结构，文件存储设备和存取法的关系;

　　7.掌握简单的文件目录、二级目录和多级目录;

　　8. 掌握文件存储空间管理的各种办法;

　　9. 掌握文件存取控制的各种方法;

　　10. 了解文件系统和用户间的接口。

　　(五)设备管理

　　1. 了解I/O设备类型及设备管理的设计目标;

　　2.了解设备管理的基本功能;

　　3. 掌握I/O控制的几种方式;

　　4. 掌握通道功能及类型;

　　5. 了解通道命令和通道程序;

　　6. 了解顺序存取存储设备和直接存取存储设备;

　　7. 掌握磁盘的驱动调度算法。

　　(六)常用操作系统

　　了解WINDOWS操作系统和UNIX操作系统的概念和基本特点。

　　三、试卷结构

　　选择题 约20/%

　　填空题 约10/%

　　判断题 约10/%

　　简答题约40/%

　　算法设计题选择题 约20/% (针对数据结构)

　　计算或应用题约20/% (针对操作系统)

　　四、试题难易度

　　较容易题 约30%

　　中等难度题 约50%

　　较难题约20%

　　五、说明

　　试卷满分为200分，《数据结构》和《操作系统》各100分，考试时间为180分钟，试卷长度为A4纸6-8版。

　　六、参考书目

　　1、严蔚敏、吴伟民　数据结构(C语言版)　清华大学出版社　2011年05月

　　2、汤子瀛等《计算机操作系统》 西安电子科技大学出版社， 2006年12月，修订版