西北师范大学2015年普通专升本招生计算机科学与技术专业考试大纲

一、考试目的

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

二、考试内容

《数据结构》部分

(一)数据结构的概念

1、熟练掌握什么是数据结构(逻辑结构，存储结构，运算);

2、掌握算法，算法分析，算法特性;

3、理解算法与程序的差别。

(二)顺序表

1、熟练掌握线性表(向量)的定义，操作，算法;

2、熟练掌握栈的定义，操作，算法;

3、熟练掌握队列的定义，操作，算法。

(三)链表

1、熟练掌握链表的概念及其特点;

2、熟练掌握单链表的概念，存储表示，查找，输入，删除等运算和算法;

3、熟练掌握双链表的概念，存储表示，查找，输入，删除等运算和算法。

(四)排序

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

2、掌握内排序的分类;

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

(五)线性表的检索

1、熟练掌握顺序检索的概念，算法，时间复杂度;

2、熟练掌握二分检索的概念，算法，时间复杂度;

3、掌握散列法：

(1)掌握基本概念;

(2)理解散列函数的构造方法;

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

(六)树形结构

1、熟练掌握树和二叉树的概念;

2、掌握树(林)与二叉树的相互转换;

3、熟练掌握二叉树的存储表示

(1)二叉链表

(2)完全二叉树的顺序存储;

4、熟练掌握二叉树与树的周游(遍历)的概念，各种周游方法;

5、掌握二叉树遍历的算法;

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

(七)树表检索

1、掌握二叉排序树的概念，插入，删除运算;

2、掌握最佳二叉排序树的概念，建立方法，算法;

3、理解平衡二叉排序树(AVL)的概念，构造方法(如何调整。)

(八)图

1、熟练掌握图的概念和相关术语;

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

3、掌握图的遍历： 深度优先遍历，广度优先遍历;

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

5、理解拓扑排序的概念，算法思想，算法;

6、掌握最短路径的概念，构造方法，算法。

《操作系统》部分

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

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

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

3、掌握多道程序设计和虚拟处理机的基本原理;

4、了解操作系统的分类;掌握分时系统的特征。

5、了解研究操作系统的几种不同观点。

(二)用户与操作系统的接口

1、理解作业，作业步，作业流的概念;

2、掌握脱机作业控制方式，联机作业控制方式;

3、了解系统功能调用。

(三)作业管理

1、理解并掌握作业管理的基本功能;

2、理解并掌握作业控制的两种方式;

3、掌握批处理作业的几种调度算法以及作业调度和进程调度的关系;

4、掌握脱机输入输出和SPOOLING 技术;

5、了解作业控制块和作业后备队列。

(四)进程管理

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、掌握磁盘的驱动调度算法。

(八)常用操作系统

了解DOS操作系统、WINDOWS操作系统和UNIX操作系统的概念和基本命令。

三、试题难易程度

较容易题 约30%

中等难度题 约50%

较难题 约20%

四、说明

试卷满分为200分，《数据结构》和《操作系统》各100分。考试时间为180分钟。

五、参考书目

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

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