2017年北京师范大学986软件基础硕士研究生考试大纲

  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 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 将E-R图转化为关系模式集合的基本规则

  7.2函数依赖

  7.3关系模式的范式

  1NF、2NF、3NF、BCNF、4NF、5NF

  7.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门外系的课程，该约束应如何实现