2017年天津财经大学计算机应用技术复试实战预测五套卷
● 摘要
一、简答题
1． 试述关系模型的概念，定义并解释以下术语：关系，属性，域，元组，码，分量，关系模式
【答案】（1）关系模型由关系数据结构、关系操作集合和关系完整性约束三部分组成。在用户观点中，关系模型中数据的逻辑结构是一张二维表，由行和列组成。
（2）术语的定义和解释：
①关系：一个关系对应通常所说的一张表。
②属性：表中的一列即为一个属性。
③域：属性的取值范围。
④元组：表中的一行即为一个元组。
⑤主码：表中的某个属性组，它可以惟一确定一个元组。
⑥分量：元组中的一个属性值。
⑦关系模式：对关系的描述，一般表示为关系名（属性1，属性2，... ，属性n ）。
2． 请写出对一个文件按某个属性的排序算法（设该文件的记录是定长的），并上机实现。若要按多个属性排序，能否写出改进的算法？
【答案】（1）使用败者树实现多路归并的外部排序算法，对文件按某个属性进行排序。 参考代码：
是函数的类型，其值是函数结果状态代码，如OK 等
是布尔类型，其值是
一个用作示例的小顺序表的最大长度
第 2 页，共 25 页
设输出M 个数据换行
，全局变量
个文件指针（fp[k]为大文件指针）
败者树是完全二叉树且不含叶子，可采用顺序存储结构
从第i 个文件（第i 个归并段）读入该段当前第1个记录的关键字到外结点
将第i 个文件（第i 个归并段）中当前的记录写至输出归并段
指示新的胜者
第 3 页，共 25 页
为完全二叉树Is 的叶子结点，存有k 个关键字，沿从叶子
设置Is 中“败者”的初值
依次从
*利用败者树Is 将编号从0到k-1的k 个输入归并段中的记录归并到输出归并段。 *b[0]至b[k-l]为败者树上的k 个叶子结点，分别存放k 个输入归并段中当前记录的关键字。
分别从k 个输入归并段读人该段当前第一个记录的关键字到外结点
建败者树ls ，选得最小关键字为
指示当前最小关键字所在归并段
将编号为q 的归并段中当前（关键字为）的记录写至输出归并段
从编号为q
的输入归并段中读人下一个记录的关键字
调整败者树，选择新的最小关键字
将含最大关键字MAXKEY 的记录写至输出归并段
第 4 页，共 25 页
b[0]出发调整败者