3. 关系数据库中可命名的最小数据单位是 ______ 。

4. 稀疏矩阵的三元组中，第三列存储的是稀疏矩阵中的 ______ 。

5. 按文件的性质和用途可分为 ______ 、 ______ 和库文件。

6. 从资源分配的角度可将设备分类为独占设备、共享设备和 ______ 。

7. 进程主要由程序、数据、控制块（ PCB) 三部分内容组成，其中 ______ 是进程存在的唯一标志。

8. 软件工程除了软件生命期之外，另一种应用模式是 ______ ，它有三种形态：纸上原型、工作原型、现有程序。

9. 在 FoxPro2.0 以上版本中，索引文件有两种：扩展名为 ______ 索引文件和扩展名为 ______ 的复合索引文件。

10. 设计软件测试用例的方法有两种： ______ 和 ______ 。

三、 简答题（每小题 4 分，共 24 分）

1. 解释程序和编译程序的区别是什么？

2. 简述数据结构中的内部排序和外部排序的区别。

3. 什么是临界资源和临界区？

4. 什么是文件？

5. 什么是外模式？

6. 软件测试的定义或目标是什么？

四、应用题（每小题 6 分，共 18 分）

1. 已知散列函数为 H(k)=k mod 12 ，键值序列为 25 ， 37 ， 52 ， 43 ， 84 ， 99 ， 120 ， 15 ， 26 ， 11 ， 70 ， 82 ，处理冲突方法为线性探测法，散列表长为 12 ，试画出散列表。

2. 已知一棵树如下图，请回答下列问题：

（ 1 ） 哪些是叶子结点？  

（ 2 ） 哪些是结点 f 的兄弟？  

（ 3 ） 树的深度是多少？  

（ 4 ） 树的度数是多少？

（ 5 ） 将该树转化为二叉树。

3. 设有关系 R 、 S ，求 T =

R                             S