北京师范大学2017年《软件基础》考试大纲_北师大考研论坛.pdf

北京师范大学2017年 《软件基础》考试大纲 软件基础 一、考试内容 （一）概述 1、 《软件基础》的考核内容包括 “数据结构”和 “数据库”两部分。 2、考生可以参考任何覆盖本考试大纲考核内容的教材、参考资料等进行复习。 （二）数据结构 1概述 1.1基本概念和术语 数据、数据元素、数据对象、数据结构、逻辑结构、存储结构、数据类型、抽象数据类型 1.2抽象数据类型搜索的表现与实现 1.3算法和算法分析 2线性表 2.1线性表的类型定义 2.2线性表的顺序表示和实现 2.3线性表的链式表示和实现 2.4一元多项式的表示及相加 3栈和队列 3.1栈的定义、表示与实现 3.2队列的定义、表示与实现 3.3栈和队列的基本应用 4 串 4.1串的定义、表示和实现 4.2串的基本应用 5数组和广义表 5.1数组的定义 5.2数组的顺序表现和实现 5.3矩阵的压缩存储 5.4广义表的定义 5.5广义表的储存结构 6树和二叉树 6.1树的定义和基本术语 6.2二叉树的定义、性质与存储结构 6.3遍历二叉树和线索二叉树 6.4树和森林 6.4.1树的存储结构 6.4.2森林与二叉树的转换 6.4.3树和森林的遍历 6.5赫夫曼树及其应用 6.5.1最优二叉树 （赫夫曼树） 6.5.2赫夫曼编码 7图 7.1图的定义和术语 7.2图的存储结构 7.2.1数组表示法 7.2.2邻接表 7.2.3十字链表 7.2.4邻接多重表 7.3图的遍历 7.3.1深度优先搜索 7.3.2广度优先搜索 7.4 图的连通性问题 7.4.1无向图的连通分量和生成树 7.4.2最小生成树 7.5有向无环图及其应用 7.6最短路径 8查找 8.1静态查找表 8.1.1顺序表的查找 8.1.2有序表的查找 8.1.3索引顺序表的查找 8.2哈希表 8.2.1哈希表的定义 8.2.2哈希函数的构造方法 8.2.3处理冲突的方法 8.2.4哈希表的查找及其分析 9 内部排序 9.1插入排序 9.1.1直接插入排序 9.1.2其他插入排序 9.1.3希尔排序 9.2快速排序 9.3选择排序 9.3.1简单选择排序 9.3.2树形选择排序 9.3.3堆排序 9.4多种内部排序方法的比较讨论 （三）数据库 1数据库系统简介 1.1基于文件的数据处理与数据库 1.2基本概念 数据库、数据库管理系统 （DBMS）、数据库系统、元数据、数据模型、模式 1.3 DBMS的主要功能 1.4数据库系统的三级模式结构 1.4.1外模式、概念模式、内模式 1.4.2逻辑独立性、物理独立性 1.5 DBMS的基本构件及相应的作用 2关系模型 2.1基本概念 关系、关系模式 2.2完整性约束： 实体完整性约束、参照完整性约束、用户定义的完整性约束 2.3关系代数 关系代数的八种基本操作 2.4关系演算 元组关系演算、域关系演算 2.5关系代数与关系演算的表达能力 3SQL语言 3.1使用SQL语言定义关系模式 3.2基于SQL语言完成查询、插入、更新操作 3.2.1 SQL查询的基本形式 3.2.2交、并、差操作 3.2.3嵌套查询 关联与非关联的嵌套查询、集合运算符 3.2.4聚集运算 3.2.5 NULL 涉及NULL的比较操作、外连接 3.3使用SQL语言定义视图 3.3.1可更新视图与不可更新视图 3.3.2视图的作用 3.4使用SQL语言定义完整性约束 3.4.1属性级约束 3.4.2表级约束 3.5 JDBC vs ODBC 3.6游标 3.7存储过程及存储函数 4安全性与商业规则 4.1使用SQL语言完成授权 4.2使用视图实现安全性控制 4.3使用触发器实现商业规则 5事务处理 5.1事务的基本概念 ACID特性 5.2并发性控制 5.2.1调度 串行性、冲突等价性和视图等价性 5.2.2并发控制协议：两段锁协议、多版本协议 5.2.3死锁 5.2.4多粒度加锁机制 5.3 SQL隔离层 5.4基于日志的恢复 5.4.1立即更新与延迟更新 5.4.2 WAL协议 5.4.3 REDO与UNDO操作 5.4.4检测点 5.5SQL语言对事务的支持 6数据建模 6.1实体、属性和实体集 6.2联系和联系集 6.3 E-R 图的其他特征 6.3.1主键约束 6.3.2参与性约束 6.3.3弱实体 6.3.4实体层次 6.4局部E-R 图与全局E-R 图 7逻辑设计 7.1