986 软件基础一、考试内容（一）概述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 ODBC3.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 将 E-R 图转化为关系模式集合的基本规则7.2 函数依赖7.3 关系模式的范式1NF、2NF、3NF、BCNF、4NF、5NF7.4 关系模式的分解8 物理设计8.1 存储结构设计8.1.1 堆文件组织8.1.2 排序文件组织8.1.3 HASH 文件组织8.1.4 聚集文件组织8.1.5 为一个应用选择文件组织的基本策略8.2 索引设计8.2.1 聚集索引与非聚集索引8.2.2 稠密索引与稀疏索引8.2.3 多维索引8.2.4 B+TREE 索引8.2.5 HASH 索引8.2.6 位图索引8.2.7 选择索引的基本策略8.3 查询优化8.3.1 概念模式调优垂直分解与水平分解8.3.2 逆规范化8.3.3 查询改写二、题型介绍（一）名词解释简单说明该名词的定义。【例】候选键【例】哈希表（二）简答题不需要展开详细论述，只需列出相应的要点即可。【例】请比较关系代数、sql 语言、高级语言（如 C）三者的计算能力【例】什么是队列的“假溢出”现象？一般有哪几种处理方法？（三）编程题“数据结构”部分要求采用类 C 语言进行算法编写。【例】回文是指正读和反读均相同的字符序列，如“abba”和”abdba”均是回文，但”moon”不是回文。试写一个算法判定给定的字符串是否为回文。“数据库”部分只涉及到 SQL 编程。【例】使用 sql 语言完成下述查询（1） 学号为“1234567”的学生选修“高等数学”的成绩（2） 查找办公地址为“科技楼”的所有院系的信息（四）应用题给出一个应用场景，结合该场景回答问题【例】已知存在如下的数据需求：数据库中需要存放的学生信息包括（学号、姓名、年龄、性别、政治面貌、所在院系）；课程信息包括（课程号、课程名、学分、授课单位、开课学期、授课教师、上课地点、上课时间）；存放的教师信息包括（工作证号码、姓名、职称、所在单位）；存放的院所信息包括（编号，名称、办公地址、联系电话）在上述数据上需要执行下面的操作查找某个学生的选课记录及相应的成绩查找某个教师的开课信息查找某个教师开设的某门课程的学生的选课情况基于上述需求完成下述问题：（1） 创建 E-R 图（2） 将第 1 步的结果转化为关系模式集合（3） 如果一个学生一个学期最多只能选修 5 门外系的课程，该约束应如何实现