辽宁石油化工大学研究生院—计算机与通信工程学院考试大纲

　　数据结构考试大纲

　　一、 考试要求

　　1、理解数据结构的基本概念；把握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现；

　　2、把握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析；

　　3、能够选择合适的数据结构和方法进行问题求解。

　　二、 考试内容

　　1、线性表

　　（1）线性表的定义和基本操作。

　　（2）线性表的实现：①顺序存储结构；②链式存储结构；③线性表的应用。

　　2、栈、队列和数组

　　（1）栈和队列的基本概念。

　　（2）栈和队列的顺序存储结构。

　　（3）栈和队列的链式存储结构。

　　（4）栈和队列的应用。

　　（5）非凡矩阵的压缩存储。

　　3、树与二叉树

　　（1）树的概念。

　　（2）二叉树：①二叉树的定义及其主要特征；②二叉树的顺序存储结构和链式存储结构；③二叉树的遍历；④线索二叉树的基本概念和构造；⑤二叉排序树；⑥平衡二叉树。

　　（3）树、森林：①树的存储结构；②森林与二叉树的转换；③树和森林的遍历。

　　（4）树的应用：①等价类问题；②哈夫曼（Huffman）树和哈夫曼编码。

　　4、图

　　（1）图的概念。

　　（2）图的存储及基本操作：①邻接矩阵法；②邻接表法；

　　（3）图的遍历：①深度优先搜索；②广度优先搜索。

　　（4）图的基本应用及其复杂度分析：①最小（代价）生成树；②最短路径；③拓扑排序；③关键路径。

　　5、查找

　　（1）查找的基本概念。

　　（2）顺序查找法。

　　（3）折半查找法。

　　（4）B-树。

　　（5）散列（Hash）表及其查找。

　　（6）查找算法的分析及应用。

　　5、内部排序

　　（1）排序的基本概念。

　　（2）插入排序：①直接插入排序；②折半插入排序；

　　（3）气泡排序。

　　（4）简单选择排序。

　　（5）希尔排序（shell sort）。

　　（6）快速排序。

　　（7）堆排序。

　　（8）二路归并排序（merge sort）。

　　（9）基数排序。

　　（10）各种内部排序算法的比较。

　　（11）内部排序算法的应用。

　　离散数学考试大纲

　　一、 考试要求：

　　1、掌握命题逻辑和谓词逻辑的基本概念及逻辑推理；

　　2、掌握集合、关系、函数的基本概念，集合与关系的各种运算方法；

　　3、掌握图与树的基本概念及表示方法；

　　3、掌握形式语言与自动机的基本概念与基本原理。

　　二、 考试内容：

　　1、数理逻辑

　　（1）命题逻辑：①命题及其表示法；②联结词；③命题公式与翻译；④真值表与等价公式；⑤重言式与蕴含式；⑥对偶与范式；⑦推理理论；⑧数理逻辑应用。　

　　（2）谓词逻辑：①谓词的概念与表示；②命题函数与量词；③谓词公式与翻译；④变元的约束；⑤谓词演算的等价式与蕴含式；⑥前束范式；⑦谓词演算的推理理论。

　　2、集合论

　　（1）集合与关系：①集合的概念和表示法；②集合的运算；③包含排斥原理；　④序偶与笛卡尔积；⑤关系及其表示；⑥关系的性质；⑦复合关系和逆关系；⑧关系的闭包运算；⑨集合的划分和覆盖；10等价关系与等价类；11相容关系；12序关系。

　　（2）函数：①函数的概念；②逆函数和复合函数；③特征函数与模糊子集；④基数的概念；⑤可数集与不可数集；⑥基数的比较。

　　3、代数系统

　　（1）代数结构：①代数系统的引入；②运算及其性质；③半群；④群与子群；⑤阿贝尔群和循环群；⑥置换群与伯恩赛德定理；⑦陪集与拉格朗日定理；⑧同态与同构；⑨环与域。

　　（2）格和布尔代数：①格的概念；②分配格；③有补格；④布尔代数；⑤布尔表达式。

　　4、图论

　　（1）图论：①图的基本概念；②路与回路；③图的矩阵表示；④欧拉图与汉密尔顿图；⑤平面图；⑥对偶图与着色；⑦树与生成树；⑧根树及其应用。

　　5、计算机科学中的应用

　　（1）形式语言与自动机：①串和语言；②形式文法；③有限状态自动机；④有限状态机的简化；⑤有限状态机与正则语言。

　　数据库原理考试大纲

　　一、 考试要求：

　　1、理解数据库的基本概念；把握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。

　　2、把握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。

　　3、能够选择合适的数据结构和方法进行问题求解。

　　二、 考试内容：

　　1、数据库系统基础

　　（1）数 据 模 型

　　（2）数据库系统结构

　　（3）数据库系统的组成

　　2、关系理论

　　（1）关系数据结构及形式化定义

　　（2）关系操作

　　（3）关系的完整性

　　（4）关系代数

　　（5）关系演算

　　（6）关系的规范化

　　（7）模式的分解

　　3、关系数据库标准语言SQL

　　（1）数据定义

　　（2）数据查询

　　（3）数据更新

　　（4）视图

　　4、数据库安全性

　　（1）数据库安全性控制

　　（2）视图机制

　　（3）审计

　　（4）数据加密

　　5、数据库完整性

　　（1）实体完整性

　　（2）参照完整性

　　（3）用户定义的完整性

　　（4）完整性约束命名子句

　　（5）触发器

　　计算机基础及程序设计考试大纲

　　一、 考试要求：

　　1、掌握计算机系统的组成，掌握计算机中数据的表示及运算方法；

　　2、掌握操作系统的基本概念；

　　3、掌握计算机信息安全的基本概念；

　　4、掌握Windows XP、Windows2007、Word、Excel、Powerpoint的基本操作；

　　5、掌握C语言的语法结构，并能使用C语言编写简单的程序。

　　二、 考试内容：

　　1、计算机基础

　　（1）计算机系统的组成

　　（2）计算机中数据的表示方法

　　（3）二进制数的运算方法

　　（4）数制之间的转换

　　2、操作系统

　　（1）操作系统的作用

　　（2）进程及进程调度

　　3、计算机信息安全

　　（1）计算机病毒及其原理

　　（2）计算机安全常识

　　4、Windows及Office

　　（1）Windows的基本操作

　　（2）Office的基本操作

　　5、C语言程序设计

　　（1）C语言的基本语句

　　（2）C语言的控制结构

　　（3）C语言中的数组、结构、指针的定义及使用

　　（4）简单程序设计