中国人民公安大学 2004 年硕士研究生入学考试
计算机软件技术基础试题 （ 315 ）
请将所有答案标明题号，写在答题本上，试题纸上请勿答题。严禁在答题纸密封线以外留下姓名、考号等任何标记，否则该卷无效。
? 名词解释和名词比较（每题 5 分，共 30 分）
? 树
? 虚拟存储管理
? 管理信息系统
? 计算机病毒
? 比较数据与信息
? 比较投影运算和选择运算
? 简答题（每题 10 分，共 60 分）
? 给定一个不带头结点的线性链表（头指针为 head ），如何实现在一个结点 p 的前面插入一个结点 s ？要求写出具体的实现算法，描述语言采用类 C 语言。
? 在一个任意二叉树中，若有 n 0 个叶子结点， n 2 个度为 2 的结点，请问 n 0 和 n 2 之间存在什么关系？要求给出证明过程。
? 操作系统中，产生死锁的原因和必要条件分别是什么？
? 软件工程中，为什么采用原型法作为系统分析与设计的一个工具？实现原型的一般途径是什么？
? 简要说明开放系统互联参考模型 OSI 各层协议的功能。
? 计算机网络安全要求包括几个方面？
? 综合题（第 1 题 25 分，第 2 题 20 分，第 3 题 15 分，共 60 分）
? 假设有三个分别命名为 a 、 b 、 c 的塔座，在塔座 a 上插有 3 个直径大小各不相同、依小到大编号为 1 ， 2 ， 3 的圆盘。现要求将塔座 a 上的 3 个圆盘移至塔座 c 上并且仍按同样顺序叠排。圆盘移动时必须遵守下列规则：
1 ）每次只能移动一个圆盘；
? 圆盘可以插在 a 、 b 、 c 中的任一塔座上；
? 任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。
下面给出了符合上述要求的实现圆盘的移动操作的类 C 语言算法。
void hanoi (int n, char x, char y, char z)
// 注释：将塔座 x 上按直径由小到大且自上而下编号为 1 至 n 的 n 个圆盘按规则搬到塔 // 座 z 上， y 用作辅助塔。搬动操作 move(x,n,z) 定义为将编号为 n 的圆盘从 x 移到 z 。
1 {
? if (n==1)
? move(x,1,z);
4 else {
5 hanoi (n-1,x,z,y);
6 move(x,n,z);
7 hanoi (n-1,y,x,z);
8 }
9 }
请根据以上说明完成下述要求：
用图示方式给出 hanoi(3,a,b,c) 执行时，递归调用过程中栈的变化情况和塔的变化状态，并配以简单的说明。栈中存放的内容应包括：调用结束后的返回地址和调用函数的参数。返回地址用上述算法中的语句行号表示， hanoi(3,a,b,c) 执行结束后的返回地址规定为 0 。调用函数的参数指 hanoi 函数中的参数，如 hanoi(3,a,b,c) 执行时，要调用 hanoi(2, …) ，则在调用之前，要将 hanoi(3,a,b,c) 的参数 (3,a,b,c) 入栈。
2. 在一个学生学籍管理系统中，有三个实体：专业、学生和课程。假设一个专业可以有多个学生，一个学生只能属于一个专业；一个学生可以选修多门课程，一门课程可以被多个学生选修。学生的属性包括：学号（主关键字）、姓名和年龄。专业的属性包括：专业编号（主关键字）、名称。课程的属性包括课程编号（主关键字）、名称、先行课。请完成下列题目：
? 在关系数据库中如何实现上述实体间的一对多联系和多对多联系，并给出示意图。
? 假设在系统中有一个记载学生成绩的关系 REL1 ，其关系模式如下： REL1 （学号，姓名，课程编号，课程名称，课程成绩）。该关系的主关键字为“学号 + 课程号”，请问该关系模式满足第二范式吗？请给出具体说明。
3. 管理信息系统的结构是什么？构成的原则是什么？每一种构成原则的特点是什么？
