中国科学院软件研究所
一九九七年招收硕士学位研究生入学考试试题答案
试题名称：软件基础
是非题（1分×10）
1．√ 2．√ 3．× 4．× 5．√ 6．× 7．× 8．× 9．× 10．×
程序阅读题（共18分）
（2分×5）
① 1 ， 1 ，f（m，n-1）， n
② 9 （nine）
（2分×4）
C[i]表示数组A中值等于i的元素的个数（1≦i≦n）；
C[i]表示数组A中值小于等于i的元素的个数（1≦i≦n）；
B[1..n]有序
O（n）
注：这是一个计数排序算法。
（10分）
proc HeapInsert(var heap:HEAP; key:keystype)
{
if heap.size ≧ max
then error(“overflow”)
else
{
heap.size := heap.size + 1;
i := heap.size; //新结点作为树叶先插入i位置
while (i > 1) and (heap.keys[parents(i)] < key) do
{ //向上调整最多至根
heap.keys[i] := heap.keys[parents(i)];
i := parents(i); //相当于新结点往上调整至双亲
}//end of while
heap.keys[i] := key
} //end of if
} //end of proc
这里parents(i)是一函数，返回值为 。
此题要点如题中的提示，必须从size+1位置往上调整使其满足堆性质；
另一要点是将数组keys看作是完全二叉树的顺序存储结构，若从上往下调
整，难以保证筛下的元素恰好是数在size+1的位置。
（12分）
func Rank（T：TREE；x：↑node）：int
{ //可设x≠nil
if x↑.lchild = nil
then r := 1
else r := x↑.lchild↑.size + 1;
y :=x;
while y ≠ T do
{
//循环不变量:r表示以y为根的子树中,结点x↑的Rank值
//当y等于根T时,即为所求
if y = y↑.parents↑.rchild
then
{
//当y↑是其双亲的右子时,y↑的双亲结点的左子树中所有结点及
//y↑的双亲本身均应排在y↑的前面(指中根序列)
if y↑.parents↑.lchild = nil
then r := r + 1;
else r := r + y↑.parents↑.lchild↑.size + 1;
}
y := y↑.parents;
}//end of while
return r;
}//end of func.
此题要点：先找x↑在以x↑为根的子树中的排列序号r，因为x↑的
左子树中所有结点在中根序列中均处于x↑之前，所以有：
r：=x↑左子树的大小（size）+1；
这里加1是包括x↑本身。当x↑左子树为空时，相当于左子树size为0。
注意：x↑在以x↑为根的子树中的r值并非它在整个树T中的排列序号，
所以要从x↑上溯到其双亲，当x↑是其双亲的左子树时，r值不变；当
x↑是其双亲的右子树时，必须加上双亲结点本身及其左子树中所有结点数
作为新的r值。此过程最多上溯至根。所以执行时间不超过树的高度。
（1分×9）
①相当容量的辅存；②一定容量的主存；③地址变换机构。
抖动。
独占、共享、虚拟。
提高硬件的并行操作程度、减少对CPU的中断次数。
（共16分，第一题4分，其余二题各6分）
裸机、CPU调度和PV操作、内存管理、作业管理、设备管理、文件管理、命令管理、用户。
产生死锁的必要条件有：①独占条件（互斥条件）；②请求和保持条件；③不剥夺条件；④环路条件（循环等待条件）。
解决死锁问题常用的方法有：①死锁的检测和解除；②死锁的预防。
UNIX进程映像由PROC结构、正文段、数据段三部分组成。
PROC结构为进程控制块PCB的一部分，它含有进程最常用的信息：进程状态、进程优先级、进程特征、地址和大小信息等。
正文段内容为可重入的程序代码，可以为若干个进程共享。
数据段由用户栈区、用户数据区、系统数据区三部分组成。
（10分）
（15分）
程序的流程为下，方框表示基本块。
各结点的必经结点集合分别为：
D(n0) = {n0}
D(n1) = {n0,n1}
D(n2) = {n0,n1,n2}
D(n3) = {n0,n1,n3}
D(n4) = {n0,n1,n3,n4}
D(n5) = {n0,n1,n3,n5}
D(n6) = {n0,n1,n3,n6}
D(n7) = {n0,n1,n3,n6,n7}
回边有n6 ——→n1一条。
该回边所表示的循环为{n1,n2,n3,n4,n5,n6}。入口为n1，出口为n6。
