黑龙江大学硕士研究生入学考试大纲
考试科目名称：软件基础 考试科目代码：[084]
一、考试要求
要求考生全面、系统地掌握《数据库系统原理》和《编译原理》课程的基本概念、原理、方法。能灵活运用，具有较强的分析、设计和解决问题的能力。
二、考试内容
（一）《数据库系统原理》部分
1.数据库系统概述
a）数据库、数据库管理系统、数据库系统
b）数据库系统的特点与功能
c）数据库系统的用户
d）数据抽象与数据独立性
e）数据库管理系统的结构
2.关系数据库系统
a）关系模型的基本概念
数学定义、关系模型、关系的性质
b）关系代数
关系代数的运算分类、传统的集合运算、专门的关系运算。
c）标准关系数据库查询语言SQL
数据定义语言、数据操纵语言、数据控制语言
3.数据库的安全性与完整性
a）安全性
数据库的安全性
为保证数据库的安全性需要考虑的问题
b）完整性
数据库的完整性
完整性约束的类型
4.数据库设计概述与需求分析
a）数据库设计概述
数据库的设计问题、数据库的生命周期、数据库的设计过程
b）需求分析
需求分析的任务、需求分析的目标、需求分析的步骤
5.概念数据库设计
a）概念数据库设计概述
概念数据库设计的任务、目标、步骤
b）实体联系模型
实体、实体型、属性、键、实体间联系
实体联系图
c）概念设计的方法与策略
概念设计的方法
概念设计的策略
6.逻辑数据库设计
a）逻辑数据库设计概述
逻辑数据库设计的任务、目标、步骤
b）形成初始关系数据库模式
实体的变换、属性的变换、联系的变换
c）关系数据库设计理论
初始关系数据库模式可能存在的问题
函数依赖
Armstrong公理系统
属性的闭包
关系模式的规范形式
d）关系模式规范化方法
无损连接性和函数依赖保持性
关系模式分解算法
7.物理数据库设计
a）影响物理数据库设计的因素
b）选择关系模式的存取方法
8.物理存储结构
a）数据库存储设备
磁盘存储器、磁盘缓冲处理技术、磁盘的调度策略。
b）数据的物理存储方式索引文件、B树。
9.数据库管理系统的数据字典
a）数据字典的定义、内容。
b）数据库管理系统软件模块对数据字典的存取。
10.关系代数操作的实现算法
a）查询处理的过程。
b）选择、笛卡儿积、投影操作的实现算法。
c）连接操作的实现算法。
d）集合的并、交、差的实现算法。
11.查询优化技术
a）问题的提出
使用不同的策略处理一个查询会得到不同的时间开销。所以，需要选择优化的查询处理策略，以减少查询处理时间，提高系统的处理能力。
b）启发式关系代数优化算法
关系代数等价变换规则、启发式代数优化规则、启发式代数优化算法。
12.并发控制技术
a）并发控制的重要性
数据更新丢失问题、临时值问题、错误聚集计算问题
b）事务模型
事务中的读写操作、事务的状态、事务的性质。
c）事务的调度
调度的可串行性
d）基于锁的并发控制协议
锁的概念、两阶段锁协议、三级封锁协议。
13.数据库恢复技术
a）数据库恢复的必要性
破坏事务原子性和引起系统故障的原因。
b）使用日志的数据库恢复技术
数据库系统日志、推迟更新技术、即时更新技术。
c）缓冲技术
日志缓冲技术。
d）检测点
14.其他事务处理技术
a）死锁处理
（二）《编译原理》部分
1.编译概述
a）编译器，源程序分析，编译器的各阶段；
b）编译器的伙伴，编译器各阶段的分组，编译器的构造工具。
2.文法和语言的基本知识
a）文法及语言的表示，文法和语言的定义；
b）句型的分析，句法树，短语，句柄；
c）文法的化简和改造，文法和语言的Chomsky分类。
3.词法分析与有穷自动机
a）词法分析器的作用，输入缓冲，记号的描述，记号的识别；
b）词法分析器描述语言，有穷自动机的构造，正则表达式；
c）转换关系：正则表达式和FA，正则表达式和正则文法，正则文法和FA；
d）NFA的确定化，DFA的最小化；
e）设计词法分析器的生成器，基于DFA 的模式匹配器的优化。
4.语法分析
a）语法分析器的作用，上下文无关文法，文法的编写；
b）自顶向下语法分析，文法左递归的消除，LL（1）文法，递归下降分析法，预测分析法，预测分析表的构造；
c）自底向上语法分析，简单优先分析法，算符优先分析法，算符优先矩阵，LR（0）、SLR（1）、LR（1）分析法，LR分析表；
d）语法分析器的构造，左、右结合问题，二义文法的应用，语法分析器的生成。
5.语法制导翻译技术和中间代码生成
a）语法制导定义，语义树的构造，属性文法；
b）自顶向下的翻译方法，属性的计算与传递；
c）中间语言：逆波兰式，三元式，四元式，三地址代码；
d）说明语句、赋值语句、布尔表达式、CASE语句的翻译；
e）回填技术，过程调用的翻译。
6.符号表的组织与管理
a）符号表的作用，符号表的组织方式；
b）符号表的建立和查找方式。
7.代码优化
a）优化的主要种类，基本优化技术，基本块划分，DAG的构造与应用；
b）流图中的循环分析，全局数据流分析；
c）程序流图分析，代码改进变换。
8.运行时的存储组织与管理
a）源语言问题和存储组织方式的关系；
b）静态存储分配，动态存储分配：栈式存储分配、堆式存储分配；
c）活动记录、数据区、DISPLAY表的构建和内容；
d）参数传递方式及其对程序运行结果的影响；
e）对非局部名字的访问，符号表访问。
9.目标代码生成
a）代码生成器设计中的基本问题和目标机器；
b）简单代码生成器的构造；
c）寄存器分配，临时变量的存储与释放；
d）代码生成器的自动生成技术。
10.其它编译技术
a）并行编译；
b）交叉编译。
三、试卷结构
1.考试时间：180分钟
2.试卷分值：150分
3.题型结构：
（1）填空题（10分）
（2）概念题（20分）
（3）简答题（40分）
（4）综合题（80分）
四、参考书目
1.《数据库系统原理》（第二版），李建中、王珊，电子工业出版社2005年9月
2.《编译原理》，李建中、姜守旭（译），机械工业出版社2003年9月
您现在的位置： 