同济计算机考研复试：数据库+编译原理+算法

所有问题和回答仅供参考

1.数据库

1.1 引言

1.什么是数据库？
数据库是一个庞大的、集成的数据集合；它是对现实世界企业的建模，数据库包含实体与联系

2.什么是关系数据模型？
关系数据模型是一种利用表的集合来表示数据和数据间的联系的数据模型

3.数据抽象的三个层次是什么？
数据抽象的三个层次从低到高分别是物理层、逻辑层与视图层；
物理层是最低层次的抽象，描述数据实际上是怎样存储的。物理层详细描述复杂的底层数据结构
逻辑层是比物理层层次稍高的抽象，描述数据库中存储什么数据及这些数据间存在什么关系。
视图层是最高层次的抽象，只描述整个数据库的某个部分，用于与用户的交互

4.什么是数据独立性？
数据独立性包括逻辑数据独立性与物理数据独立性，逻辑数据独立性指应用程序不受数据逻辑结构变化的影响。物理数据独立性指应用程序不受数据物理存储结构变化的影响

5.什么是数据库的三级模式结构？
数据库的三级模式结构包括外模式、概念模式（模式）、内模式
外模式又称子模式或用户模式，对应于用户级。它是某个或某几个用户所看到的数据库的数据视图
概念模式又称模式或逻辑模式，对应于概念级。它是由数据库设计者构造的全局逻辑结构，是对数据库中全部数据的逻辑结构和特征的总体描述
内模式又称存储模式，对应于物理级。它是数据库中全体数据的内部表示或底层描述，它描述了数据在存储介质上的存储方式和物理结构，对应着实际存储在外存储介质上的数据库

6.数据库设计可分为哪几个阶段？
数据库设计可分为需求分析、概念结构设计、逻辑结构设计、物理结构设计、数据库实施、数据库运行与维护这几个阶段

7.为什么不用文件处理系统来存储组织信息，而是用数据库系统？
使用文件处理系统来存储组织信息的主要弊端包括：数据的冗余和不一致、数据访问困难、数据孤立、完整性问题、原子性问题、并发访问异常问题以及安全性问题。以上问题促进了数据库系统的发展，数据库系统为了解决上述问题提出了大量的概念和算法

8.SQL语句按照功能可分为哪几个部分？
SQL语句按功能可分为数据定义语言DDL、查询语言QL、数据操纵语言DML、数据控制语言DCL
数据定义语言用于定义，删除或更改数据模式。查询语言用于检索数据。数据操纵语言用于插入、删除或更新数据。数据控制语言用于控制用户对数据的访问权限

1.2 数据模型

1.在数据库发展的历史中，总共出现过哪些数据模型？
数据模型的发展大致经历了层次数据模型、网状数据模型、关系数据模型、实体-联系模型、面向对象的数据模型等过程

2.关系数据模型中的关系指的是什么？
在关系模型的术语中，关系用来指表，元组用来指行，属性指代的是表中的列

3.为什么关系数据模型是目前使用最广泛的数据模型？
关系数据模型基于集合论，具有很高的抽象级别，它建立了新的代数系统——关系代数，它可以支持非过程化的查询语言——SQL语言。

4.什么是主键？
一组属性是关系的候选键，如果任意两条不同元组在这组属性上的值都不同，或者这组属性的值确定，该元组其他属性的值被唯一确定。
若这组属性的任何一个子集没有上述特性，则可从中选取一个键作为主键，其他的则称为候选键。

5.什么是外键？
外键是一个关系中用于引用另一个关系中的元组的属性集，它是通过另一个关系的主键来引用该关系的

6.关系代数的基本操作有哪些？
选择、投影、笛卡尔乘积、集合差、集合并是关系代数的基本操作，它们是一组完备操作集合，其他关系代数的操作都可由它们派生出来

1.3 数据库设计

1.什么是1NF、2NF、3NF、4NF、5NF？
1NF指关系的每个属性都必须是原子的，2NF在1NF的基础上加上了不允许属性对主键的部分函数依赖这一项，3NF在2NF的基础上加上了不允许属性对主键的传递函数依赖这一项
4NF在3NF的基础上消除了可能存在的属性之间的多值依赖，5NF在4NF的基础上消除了可能存在的连接依赖
一般的标准是需要满足3NF

2.有哪些数据依赖关系？
属性之间存在的依赖关系有：函数依赖、多值依赖、连接依赖
函数依赖是一种最基本的数据依赖关系，它是指一个或一组属性的值可以决定其他属性的值，函数依赖是多值依赖的特例
多值依赖是指一些属性的值可以决定其他一些属性的一组值
连接依赖是指，如果可以始终通过连接多个表（每个表都具有T的属性的子集）来重新创建T，则表T受到连接依赖性的约束。

3.数据库设计采用的方法有哪几种？
数据库设计采用的方法有面向过程的方法和面向数据的方法两种类型
面向过程的方法以业务流程为中心，由于没有对数据以及数据之间的内部关系进行详细的分析，尽管完成项目需要的时间较短，但是很难确保软件质量，而且系统也很难适应未来的需求和环境变化。这种方法不适用于大型复杂系统的开发
面向数据的方法基于对数据的详细分析和数据之间的内在联系来设计数据库。它以数据为中心，而不是以业务流程为中心。它不仅可以满足当前的需求，还可以满足一些未来潜在的需求，易于适应需求和环境的变化。此方法适合在开发大型，复杂的系统时使用。

1.4 数据存储和查询

1.文件中记录的组织形式有哪几种？
有堆文件形式、哈希文件形式、索引文件形式、动态哈希文件形式等
在堆文件中，记录按照插入顺序存储，并按顺序检索。这是文件组织中最基本，最通用的形式
在哈希文件中，使用每条记录的某些属性计算一个散列函数，散列函数的结果确定了记录应放到文件的哪个块中
索引文件则在堆文件的基础上使用了B+树索引
动态哈希文件可以动态调整哈希函数的映射空间

2.查询优化可以在哪两个方面进行？
查询优化一方面在关系代数级别发生，即系统尝试找出一个与给出的表达式等价但执行起来更为高效的表达式。另一方面是为处理查询选择一个详细的策略，比如对一个操作的执行选择合适的算法，选择使用特定的索引等

1.5 事务管理

1.什么是事务？事务具有的特性是什么？每个特性的含义分别是什么？
事务是访问并可能更新各种数据项的一个程序执行单元。事务具有ACID特性：原子性（atomicity）、一致性（consistency）、隔离性（isolation）、持久性（durability）。
原子性保证事务的所有影响在数据库中要么全部反映出来，要么根本不反映；一个故障不能让数据库处于事务部分执行后的状态
一致性保证若数据库一开始是一致的，则事务（单独）执行后数据库仍处于一致状态
隔离性保证并发执行的事务相互隔离，使得每个事务感觉不到系统中其他事务的并发执行
持久性保证一旦一个事务提交后，它对数据库的改变不会丢失，即使系统可能出现故障

2.什么是两阶段封锁协议，两阶段封锁协议可以保证不会发生死锁吗？有哪些应对死锁的方式？
两阶段封锁协议要求每个事务分两个阶段提出加锁和解锁申请，这两个阶段分别是增长阶段和缩减阶段。在增长阶段，事务可以获得锁，但不能释放锁；在缩减阶段，事务可以释放锁，但不能获得新锁
两阶段封锁并不能保证不会发生死锁
处理死锁问题主要有两种方式，分别是死锁预防和死锁检测与恢复。预防死锁有两种方法：一种方法是通过对加锁请求进行排序或要求同时获得所有的锁来保证不会发生循环等待。另一种方法比较接近死锁恢复，每当等待有可能导致死锁时，进行事务回滚而不是等待加锁。死锁检测则根据等待图进行，当检测算法判定存在死锁时，需根据回滚代价选择某一个（或一些）事务进行回滚

3.什么是日志？
日志是自上次备份副本以来，数据库上所有更新的记录

4.什么是提交规则、先记后写规则？
提交规则是指在提交事务之前，必须将新值写入非易失性存储器。先记后写规则是指如果在事务提交之前将新值写入数据库，则必须在此之前先将旧值写入日志

5.当数据库中有多个事务并发执行时，有可能出现哪些问题？如何解决这些问题？
当数据库中有多个事务并发执行时，有可能出现丢失更新（写-写冲突）、脏读（写-读冲突）、不可重复的读（读-写冲突）。写-写冲突在任何时候都应该被避免，写-读和读-写冲突在通常情况下应该被避免，但它们在某些应用场合下可以存在。
最常用的并发控制机制有两阶段封锁协议和快照隔离

6.有哪些检测死锁发生的方式？在何时检测死锁是否发生？在检测出死锁发生后，如何解除死锁？
检测死锁是否发生的一种方法是：若某事务等待了指定的时间，则认为发生死锁，并中止该事务。另一种方法是利用等待图来检测死锁，若等待图中有环，则死锁发生。
检测死锁常用的方式是周期性检测，也可以在某个事务等待时进行检测
解除死锁首先需根据回滚代价选择一个事务作为牺牲者，然后回滚该事务并释放它拥有的所有资源和锁，接下来允许一个等待事务运行，最后重启被回滚的事务

7.如何使用基于时间戳的协议进行死锁避免？
每个事务都有其唯一的时间戳，若A事务请求对已经被B事务加锁的数据对象加锁，则等待-死亡方法或击伤-等待方法其中之一将被使用以避免死锁的发生
在等待-死亡方法下，若A的时间戳小于B，则A等待，否则它将被回滚并进入睡眠，之后自动地使用原来的时间戳重新运行
在击伤-等待方法下，若A的时间戳大于B，则A等待，否则它将B击伤，即事务B被回滚并进入睡眠，之后自动地使用原来的时间戳重新运行
在上述两种方法下，都只会出现单方向等待，不会出现循环等待，因此死锁被避免

2.编译原理

2.1 引论

1.从高级语言源程序到目标机器代码的全过程是怎样的？
源程序首先要经过预处理器，预处理器将存储在不同文件中的源程序聚合在一起，并把宏转换为原始语句。经过预处理后的源程序交与编译器，编译器将其编译为汇编语言程序，汇编语言程序之后被汇编器汇编为可重定位的机器代码，该机器代码经由链接器以及加载器处理后变为最终的目标机器代码

2.编译程序的工作包括哪些方面？它们具体的含义是什么？
编译程序的工作包括：词法分析、语法分析、语义分析和中间代码生成、优化以及目标代码生成
词法分析的任务是扫描源程序的字符，识别出各个单词，确定单词的类型，将识别出的单词转换成统一的机内表示（词法单元token形式）
语法分析从词法分析器输出的token序列中识别出各类短语，并构造语法分析树，语法分析树描述了句子的语法结构
语义分析的任务是收集标识符的属性信息并进行语义检查
中间代码生成的任务是对语法分析识别出的各类语法范畴，分析其含义，进行初步翻译，产生介于源代码和目标代码之间的一种代码
优化的任务是对中间代码进行加工变换，为的是在最后阶段能产生更为高效的目标代码
目标代码生成的任务是把经过优化的中间代码转化成特定机器上的低级语言代码

3.什么是终结符、什么是非终结符?
终结符是文法所定义的语言的基本符号，有时也称为token
非终结符是用来表示语法成分的符号，有时也称为语法变量

2.2 词法分析

1.什么是正则表达式？
正则表达式是对字符串操作的一种逻辑公式，就是用事先定义好的一些特定字符、及这些特定字符的组合，组成一个“规则字符串”，这个“规则字符串”用来表达对字符串的一种过滤逻辑。

2.什么是有穷自动机、确定有穷自动机、不确定有穷自动机?
有穷自动机是对一类处理系统建立的数学模型，这类系统具有一系列离散的输入输出信息和有穷数目的内部状态。系统只需要根据当前所处的状态和当前面临的输入信息就可以决定系统的后继行为。每当系统处理了当前的输入后，系统的内部状态也将发生改变
确定有穷自动机是一种特殊的有穷自动机，它的任意一个状态对于任意一个输入符号有且只有一个转换。
不确定有穷自动机是说当一个状态面对一个输入符号的时候，它所转换到的可能不只一个状态，可以是一个状态集合

3.什么是有穷自动机定义的语言？
给定输入串x，若存在一个对应于串x的从初始状态到某个终止状态的转换序列，则称串x被该有穷自动机接收
由一个有穷自动机接收的所有串构成的集合称为是该有穷自动机定义的语言

4.词法分析阶段可以检测到哪些错误类型？是如何检测的？对错误的处理过程是什么？
词法分析阶段可以检测到的错误类型有：单词拼写错误、非法字符。
词法错误检测的方法是：若当前状态与当前输入符号在转换表对应项中的信息为空，则报错，调用错误处理程序
错误处理程序将查找已扫描字符串中最后一个对应于某终态的字符，若找到，将该字符与其前面的字符识别成一个单词，然后将输入指针退回到该字符，扫描器重新回到初始状态，继续识别下一个单词。若未找到，则确定出错，采用错误恢复策略。
简单的一种错误恢复策略称为恐慌模式，它从剩余的输入中不断删除字符，直到词法分析器能够在剩余输入的开头发现一个正确的字符为止

2.3 语法分析

1.什么是上下文无关文法？
上下文无关文法就是说这个文法中所有的产生式左边只有一个非终结符

2.什么是语法分析树？
一颗语法分析树是一个推导的图形表示。在推导中出现的每一个非终结符号都在树中有一个对应结点。一个结点的子节点就是在推导中用来替换该节点对应的非终结符号的文法符号串。

3.什么是二义性文法？
若一个文法的某些终结符号串有两颗或多颗语法分析树，或者等价地说有两个或多个最左推导/最右推导，那么这个文法就称为二义性文法。在实践中的大多数情况下，我们可以对一个二义性文法进行重新设计，使它变成一个描述相同语言的无二义性文法。然而，有时使用二义性文法并应用一些技巧可以得到更加高效的语法分析器

4.什么是自顶向下和自底向上语法分析？
语法分析器通常可以按照它们的工作方式分为自顶向下的（从文法的开始符号出发，从顶部开始构造语法分析树）和自底向上的（从构成语法分析树叶子节点的终结符号串开始，从底部开始构造语法分析树）。自顶向下的语法分析器包括递归下降语法分析器和LL语法分析器，而最常见的自底向上语法分析器是LR语法分析器

5.什么是推导？什么是归约？什么是最左推导？什么是最右推导？自底向上的分析和自顶向下的分析分别采用什么推导或归约方式？
推导是从开始符号开始，通过使用产生式的右部取代左部，最终能产生语言的一个句子的过程。在最左推导中，总是选择每个句型的最左非终结符进行替换，在最右推导中，总是选择每个句型的最右非终结符进行替换
归约是推导的逆过程，即从给定的源语言的句子开始，通过规则的左部取代右部，最终达到开始符号的过程
自底向上的分析采用最左归约的方式，自顶向下的语法分析采用最左推导方式

2.4 语法制导的翻译

1.语法制导翻译指的是编译的哪几个阶段？
语法制导翻译包括语法分析、语义分析、中间代码生成三个阶段
语法制导翻译使用上下文无关文法（CFG）来引导对语言的翻译，是一种面向文法的翻译技术

2.5 中间代码生成

1.常见的中间代码形式有哪些？
四元式、三元式、逆波兰式

2.6 运行时刻环境

1.数据的存储分配策略是怎样的？
对于那些在编译时刻就可以确定大小的数据对象，可以在编译时刻就为它们分配存储空间，这样的分配策略称为静态存储分配。反之，若不能在编译时完全确定数据对象的大小，就要采用动态存储分配的策略，即在编译时仅产生各种必要的信息，而在运行时刻，再动态地分配数据对象的存储空间。动态存储分配又可分为栈式存储分配与堆式存储分配
静态和动态存储分配分别对应编译时刻和运行时刻

2.程序运行时内存的划分是怎样的？
内存分为静态代码区、静态数据区以及动态数据区。动态数据区又分为栈区、堆区以及空闲内存区

3.适合静态存储分配的语言必须满足的限制条件是什么？常用的静态存储分配方法有哪些？
适合静态存储分配的语言必须满足：数组上下界必须是常数、不允许过程的递归调用以及不允许动态建立数据实体
常用的静态存储分配方法有：顺序分配法、层次分配法。顺序分配法按照过程出现的先后顺序逐段分配存储空间，各过程的活动记录占用互不相交的存储空间。层次分配法通过对过程间的调用关系进行分析，凡属无相互调用关系的并列过程，尽量使其局部数据共享存储空间

4.什么是栈式存储分配？
有些语言使用过程、函数或方法作为用户自定义动作的单元，几乎所有针对这些语言的编译器都把它们的运行时刻存储以栈的形式进行管理，称为栈式存储分配
这种安排不仅允许活跃时段不交叠的多个过程调用之间共享空间，而且使得过程的非局部变量的相对地址总是固定的，和过程调用序列无关