西北师范大学2017年专升本计算机科学与技术专业课考试大纲

一、考试目的

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

二、考试内容

《数据结构》部分

(一)数据结构的概念

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.掌握最短路径的概念，构造方法，算法。