中国人民公安大学2004年硕士研究生入学考试计算机软件技术基础试题

中国人民公安大学2004年硕士研究生入学考试计算机软件技术基础试题

一、名词解释和名词比较（每题5分，共30分）

1.       树

2.       虚拟存储管理

3.       管理信息系统

4.       计算机病毒

5.       比较数据与信息

6.       比较投影运算和选择运算

二、简答题（每题10分，共60分）

1.       给定一个不带头结点的线性链表（头指针为head），如何实现在一个结点p的前面插入一个结点s？要求写出具体的实现算法，描述语言采用类C语言。

2.       在一个任意二叉树中，若有n₀个叶子结点，n₂个度为2的结点，请问n₀ 和n₂之间存在什么关系？要求给出证明过程。

3.       操作系统中，产生死锁的原因和必要条件分别是什么？

4.       软件工程中，为什么采用原型法作为系统分析与设计的一个工具？实现原型的一般途径是什么？

5.       简要说明开放系统互联参考模型OSI各层协议的功能。

6.       计算机网络安全要求包括几个方面？

三、综合题（第1题25分，第2题20分，第3题15分，共60分）

1.       假设有三个分别命名为a、b、c的塔座，在塔座a上插有3个直径大小各不相同、依小到大编号为1，2，3的圆盘。现要求将塔座a上的3个圆盘移至塔座c上并且仍按同样顺序叠排。圆盘移动时必须遵守下列规则：

1）每次只能移动一个圆盘；

2）  圆盘可以插在a、b、c中的任一塔座上；

3）  任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。

下面给出了符合上述要求的实现圆盘的移动操作的类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 {

2           if (n==1)

3               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  }