中国科学院软件研究所
一九九七年招收硕士学位研究生入学考试试题
试题名称：软件基础
第一部分：数据结构和程序设计
是非题（正确填√，错误填×）（1分×10）
（ ）1．稀疏矩阵压缩存储后，必会失去随机存取功能。
（ ）2．完全二叉树的某结点若无左孩子，则它必是叶结点。
（ ）3．由一棵二叉树的前序序列和后序序列可以唯一确定它。
（ ）4．在n个结点的无向图中,若边数>n-1，则该图必是连通图。
（ ）5．若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑
有序序列必定存在。
（ ）6．用向量和单链表表示的有序表均可使用折半查找方法来提高查找速
度。
（ ）7．在任意一棵非空二叉排序树，删除某结点后又将其插入，则所得二
叉排序树与删除前原二叉排序树相同。
（ ）8．若一个广义表的表头为空表，则此广义表亦为空表。
（ ）9．二叉树是度数为二的有序树。
（ ）10．对磁带机而言，ISAM是一种方便的文件组织方法。
程序阅读题（共18分）
设m，n均为自然数，m可表示为一些不超过n的自然数之和，f(m,n)为这种表示方式的数目。例f(5,3)=5，有5种表示方式：3+2，3+1+1，2+2+1，2+1+1+1，1+1+1+1+1。
①以下是该函数的程序段，请将未完成部分填入，使之完整。
int f(m,n)
int m,n;
{
if (m==1)
return ;
if (n==1) {
return ;
}
if (m<n) {
return f(m,m);
}
if (m==n) {
return 1+ ;
}
return f(m,n-1)+f(m-n, );
}
②执行程序，f(6,4)= ;
设输入为整数数组A[1..n]，其中1≦A[i] ≦k（1≦i≦n）；输出数组为B[1..n]；C[1..k]是临时工作空间；阅读下述算法后，回答下列问题：
Proc Demo(A,B,k) {
⑴ for i:=1 to k do C[i]:=0;
⑵ for j:=1 to n do C[A[j]]:=C[A[j]]+1;
⑶ for i:=2 to k do C[i]:=C[i]+C[i-1];
⑷ for j:=n downto 1 do {
⑸ B[C[A[j]]]:=A[j];
⑹ C[A[j]]:=C[A[j]]-1;
}
}
当标号⑵行的循环执行完后，C[i]（1≦i≦n）的值有何意义？
当标号⑶行的循环执行完后，C[i]（1≦i≦n）的值有何意义？
算法执行后，B的内容有何特点？
当k=O(n)时，算法的时间复杂度是多少？
（10分）设大根堆（即堆顶元素最大）的存储结构为：
type HEAP=record
keys：array[1..max] of keystype; /*存放堆元素的空间*/
size : int ; /*当前堆中已有的元素个数*/
end;
写一算法HeapInsert(var heap:HEAP;key:keystype)将关键字key插入到堆heap中且不破坏堆性质。（提示：先将key插入到数组的size+1位置上，然后自底向上调整）。
（12分）设二叉排序树的存储结构为：
type TREE=↑node；
node = record
key ：keytype；
size ：int；
lchild，rchild，parents：TREE；
end；
一个结点x↑的size域的值是以该结点为根的子树中结点的总数（包括x ↑
本身）。例如，下图中x所指结点的size值为4。设树高为h，试写一时间
为O(h)的算法Rank（T：TREE；x：↑node）返回x所指结点在二叉排序树
T的中序序列里的排列序号，即：
求x结点是根为T的二叉排序树中
第几个最小元素。例如，下图x所
指结点是树T中第11个最小元素。
（提示：你可利用size值和双亲
指针parents）。
第二部分：操作系统和编译技术
填空题（1分×9）
实现虚拟存储器，应有以下几种物质基础来支持：①
② ③ 。
页面淘汰算法选得不好会引起 现象。
从资源管理的角度看，I/O设备分为 设备、 设备和 设备三类。
引入缓冲的原因在于： 和 。
简答题（共16分）
一个分层结构操作系统有下列部分组成：裸机、用户、CPU调度和PV操作、文件管理、作业管理、内存管理、设备管理、命令管理等。试按层次结构的原则从内到外将各部分重新排列。
产生死锁的必要条件是什么？解决死锁问题常用哪几种措施？
UNIX进程映像由哪几部分组成？简述各部分的内容。
（10分）为正规式 构造一个确定的有限自动机。
（15分）试画出如下中间代码序列的程序流图，并求出：
各结点的必经结点集合D（n）；
流图中的回边与循环。
J:=0;
L1: I:=0;
if I<8 goto L3;
L2: A:=B+C;
B:=D*C;
L3: if B=0 goto L4;
write B;
goto L5;
L4: I:=I+1;
if I<8 goto L2;
L5: J:=J+1;
if J<=3 goto L1;
HALT
