北京林业大学821《计算机综合》2021年考研专业课初试大纲.pdf

### 北京林业大学《计算机综合》2021年考研专业课初试大纲解析 #### 一、大纲综述 《计算机综合》是针对报考北京林业大学计算机科学与技术研究生的专业课程考试科目之一。该科目由两大部分组成：数据结构（100分）与数据库技术（50分）。为了帮助考生明确考试复习范围和要求，特制定此大纲。 #### 二、考试内容 ##### （一）数据结构部分 1. **数据结构基本概念** - **数据结构的基本概念**：了解数据、数据元素、数据结构、数据的逻辑结构、物理结构、算法等基本概念。 - **算法的时间复杂度和空间复杂度分析**：掌握如何评估算法效率的方法，能够进行基本的时间复杂度和空间复杂度分析。 2. **线性表** - **线性表的定义**：理解线性表的基本概念。 - **线性表的存储结构**：掌握线性表的顺序存储和链式存储结构，以及相关算法实现（如查找、插入和删除等）。 - **链式结构特点**：学习循环链表和双向链表的特点。 - **存储结构比较**：从时间和空间复杂度角度对比两种存储结构，并讨论其适用场合。 - **线性表的应用**：例如，通过线性表合并算法来解决问题。 3. **栈和队列** - **栈的操作**：掌握栈的定义、特点以及进栈出栈算法，理解栈满和栈空的条件。 - **栈的应用**：学会使用栈解决实际问题，如表达式求值算法，理解递归算法。 - **队列的操作**：熟悉队列的定义、特点以及进队出队算法，理解循环队列中队满及队空的条件。 4. **串和数组** - **串的定义**：了解串的基本概念。 - **串的模式匹配算法**：掌握串的古典模式匹配算法。 - **数组地址计算**：理解数组地址的计算方法。 - **特殊矩阵的压缩存储**：学习特殊矩阵的压缩存储方法。 5. **树和二叉树** - **二叉树定义与性质**：掌握二叉树的定义及其性质。 - **二叉树的存储结构**：学习二叉树的顺序存储和链式存储。 - **二叉树的操作**：掌握二叉树的创建和遍历算法（前序、中序、后序），并能利用这些算法实现其他操作（如计算结点个数、叶子结点个数、高度等）。 - **线索二叉树**：理解线索二叉树的概念及其构造方法。 - **树和森林**：了解树和森林的定义、存储结构及其与二叉树之间的转换方法。 - **哈夫曼树**：掌握哈夫曼树及哈夫曼编码的构造算法、带权路径长度的计算方法。 6. **图** - **图的定义与性质**：掌握图的基本概念及其性质。 - **图的存储结构**：学习图的邻接矩阵和邻接表两种存储结构。 - **图的遍历算法**：掌握图的深度优先搜索和广度优先搜索算法。 - **图的应用**：学会拓扑排序算法、迪杰斯特拉算法（求最短路径）、普里姆算法和克鲁斯卡尔算法（构建最小生成树）等图的基本应用。 7. **查找** - **线性表的查找**：掌握顺序查找和折半查找算法。 - **树表的查找**：学习二叉排序树的定义、创建、插入、删除和查找算法。 - **散列表的查找**：理解散列表的概念，掌握两种处理冲突的方法（开放地址法、链地址法）。 - **查找算法的分析**：对上述查找算法进行分析，了解平均查找长度ASL的计算方法及时间复杂度分析，掌握不同查找算法的适用场合。 8. **排序** - **排序的基本概念**：理解排序的基本概念。 - **插入排序**：学习直接插入排序、折半插入排序和希尔排序。 - **交换排序**：掌握冒泡排序和快速排序。 - **选择排序**：学习简单选择排序和堆排序。 - **归并排序**：掌握2-路归并排序。 - **排序算法的特点与分析**：了解各种排序方法的特点和排序过程，能够进行时间和空间复杂度的分析，理解排序方法是否稳定的含义，掌握排序算法的实现及适用场合。 ##### （二）数据库技术部分 1. **数据库系统概述** - **数据库系统概论**：了解数据、数据库、数据库管理系统、数据库系统等基本概念。 - **数据模型**：学习数据模型的组成要素、概念模型、层次模型、网状模型、关系模型、对象模型。 - **数据库系统结构**：掌握数据库系统模式的概念、三级模式结构、二级映像功能与数据独立性、数据库系统的组成。 - **数据库技术研究领域**：了解当前数据库技术的研究方向。 2. **关系数据库** - **关系模型概述**：了解关系模型的基本概念。 - **关系数据结构**：掌握关系、关系模式、关系数据库的形式化定义。 - **关系的完整性**：学习实体完整性、参照完整性、用户自定义完整性。 - **关系代数**：掌握集合运算、关系运算。 3. **关系数据库标准语言——SQL** - **SQL概述**：了解SQL的基本概念。 - **SQL数据定义**：掌握SQL的数据定义语句。 - **SQL查询**：学习单表查询、连接查询、嵌套查询、集合查询。 - **SQL数据更新**：掌握插入、修改、删除数据的方法。 - **视图**：学习创建视图、查询视图、更新视图的意义。 - **数据控制**：掌握SQL授权、收回授权。 - **嵌入式SQL**：了解嵌入式SQL的概念。 4. **关系数据库理论** - **关系模式的冗余和异常问题**：理解关系模式中存在的冗余和异常问题。 - **规范化**：学习函数依赖、码、范式、2NF、3NF、BCNF、多值依赖、4NF。 - **模式分解**：掌握模式分解的方法。 5. **数据库安全保护** - **数据库安全性控制**：学习数据库安全性控制机制。 - **数据库完整性控制**：掌握数据库完整性控制方法。 - **数据库并发控制**：理解数据库并发控制的重要性，掌握其实现方法。 - **数据恢复**：学习数据恢复技术。 6. **数据库设计** - **数据库设计概述**：了解数据库设计的基本步骤。 - **需求分析**：掌握需求分析的方法。 - **概念结构设计**：学习概念结构设计的过程。 - **逻辑结构设计**：掌握逻辑结构设计的方法。 - **数据库物理设计**：理解数据库物理设计的目的和方法。 - **数据库实施**：学习数据库实施的具体步骤。 - **数据库运行维护**：掌握数据库运行维护的基本内容。 7. **SQL Server 2000 数据库管理系统** - **Transact-SQL程序设计**：学习Transact-SQL编程中的变量、流程控制命令、其他命令、常用函数。 - **存储过程和触发器**：掌握存储过程和触发器的设计与使用方法。 以上内容为《计算机综合》考试大纲的核心知识点，考生需重点掌握这些知识点及相关技能，以便在考试中取得好成绩。