2019年硕士研究生入学考试自命题考试大纲

 

考试科目代码：[     ]        考试科目名称：计算机专业基础

一、试卷结构

1、试卷成绩及考试时间

本试卷满分为150分，考试时间为180分钟。

2、答题方式：闭卷、笔试

3、试卷内容结构

数据结构占75分（50%），数据库原理占75分（50%）

4、题型结构

简答题：8小题，每小题5分，共40分

论述题：6小题，每小题10分，共60分

综合应用题：2小题，每小题25分，共50分

二、考试内容与考试要求 

●考试目标：

1.深刻理解并领会数据结构的基本概念和基本理论，熟练掌握常用数据结构的逻辑结构、存储结构及其相关的操作算法；

2.具有良好的程序设计能力和基本的算法设计、分析能力；

3．理解数据库完整性对数据的正确性和相容性的具体影响。

4．理解和掌握关系数据理论在构造关系模式过程中的作用。

5．运用并发控制的理念对事务的执行方式进行合理解释。

6.准确、恰当地使用计算机专业术语，论述有据，条理清晰，符合逻辑，文字表达通顺。

●考试内容

数据结构部分

（一）数据结构绪论

1.数据、数据元素、数据项、数据结构等基本概念；

2.数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系；

3.数据的基本逻辑结构和四种常用的存储表示方法；

4.算法及算法的特点，掌握算法描述和算法分析的方法。

（二）线性表、栈和队列

1．线性表的基本逻辑结构特点、栈和队列的受限特性；

2．线性表、栈、队列在顺序存储结构下的基本运算的实现；

3．线性表、栈、队列在链式存储结构下的基本运算的实现；

4．利用线性表、栈、队列设计算法解决实际的应用问题。

（三）数组和广义表

1．数组和广义表的逻辑结构特征；

2．数组顺序存储结构下随机存储的特性及地址计算方式；

3．特殊矩阵在压缩存储时的地址计算方法；

4．稀疏矩阵压缩存储的三元组表表示方法；

（四）树和二叉树

1.树和二叉树的基本概念、掌握树的逻辑结构特征；

2.树和二叉树的性质；

3.二叉树的在链式存储结构下的基本运算实现，创建二叉树、访问节点，及遍历运算等；

4.三种遍历所得到的相应的结点访问序列；理解以遍历算法为基础，应用递归方法设计有关算法解决简单的应用问题；

5.二叉树线索化的目的及实现；

6.构造二叉树的方法；

7.哈夫曼树的含义，掌握哈夫曼算法的思想及哈夫曼树的应用。

（五）图

1.图的逻辑结构特征，理解图的常用术语；

2.邻接矩阵和邻接表这两种存储结构的特点及适用范围；

3.图的基本运算的实现及图的深度优先搜索和广度优先搜索两种遍历算法；

4.利用图的基本运算设计算法解决实际的应用问题；

5.生成树和最小生成树的概念，根据Prim和Kruskal算法构造出最小生成树；

6.单源最短路径的Dijkstra算法的基本思想，根据Dijkstra算法求解最短路径的过程；

7.关键路径的求取。

（六）查找

1.顺序查找、二分查找、分块查找的基本思想、算法实现和查找效率分析；

2.二叉查找树和B-树的定义和特点以及用途；

3.二叉查找树的插入、删除、建树和查找算法及时间性能；

4.哈希表、哈希函数、哈希地址和装填因子等有关概念；

5.解决哈希冲突的方法；

（七）内排序

1．插入类排序基本思想和典型算法实现；

2. 选择类排序基本思想和典型算法实现；

3. 交换类排序基本思想和典型算法实现；

4．归并排序的基本思想和算法实现。

数据库部分

（一）数据库完整性

1.实体完整性规则及应用时应注意的问题；

2.参照完整性规则及应用时应注意的问题。

（二）关系数据理论

1.函数依赖存在的意义、部分函数依赖和传递函数依赖对范式级别的影响；

2.各种范式（包括1NF、2NF、3NF、BCNF）的定义、低级别范式存在的缺陷；

3.特别强调候选码在该部分的作用。

（三）数据库设计

1.数据库设计过程中的概念结构到逻辑结构的转换；

2.其中强调的是“联系”在转换过程中以何种形式存在。

（四）并发控制

1.事务的定义、其特性及由此引发的各种问题；

2.事务并发时产生的问题、解决方法及不足之处。