中国科学院软件研究所
一九九八年招收硕士学位研究生入学考试试题
试题名称：软件基础
第一部分：程序设计和数据结构
要求：算法设计题目要求写注解，否则扣分。写出正确的设计思想和伪代码给分。
选择合适的答案填空（1分×20）
程序的三种基本控制结构是 ， 和 。
（a）顺序 （b）转移 （c）I/O （d）选择 （e）重复 （f）递归
过程或函数的副作用是指在过程或函数体内 。
（a）．对局部量的修改 （b）．对非局部量的修改
在C语言的函数void f（）{static int I=0；……}说明中，静态变量I的作用域是 ，生命期是 ，I的初始化是在 时进行的。（第一、二个空从（a）~（c）中选择，第三个空从（d），（e）中选择）
（a）整个程序 （b）函数f（）所在的文件 （c）函数f（）内部
（d）编译 （e）程序运行
将递归程序转换成非递归程序，一般都要使用栈，但是消除 可以不使用栈。
（a）直接递归 （b）间接递归 （c）尾递归
没有提供指针类型的语言，无法构造链式结构，该说法 。
（a）正确 （b）错误
若广义表A满足head（A）=tail（A）=（），则A为 。
（a）（） （b）（（）） （c）（（），（）） （d）（（），（），（））
假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行 次探测。
（a）K-1次 （b）K次 （c）K+1次 （d）K（K+1）/2次
若要尽可能快的完成对实数数组的排序，且要求排序是稳定的，则应选
。
（a）快速排序 （b）堆排序 （c）归并排序 （d）基数排序
一个具有n个顶点的强连通图，至少有 条边，至多有 条边。
（a）n-1 （b）n （c）n（n-1） （d）n（n-1）/2
用ISAM组织文件适合于 。
（a）磁带 （b）磁盘
对外部排序的K路平衡归并，采用败者树，归并效率与K 。
（a）有关 （b）无关
若一个具有n个顶点，k条边的无向图是一个森林（n>k），则该森林中必有 棵树。
（a）k （b）n （c）n-k （d）1
已知待排序的n个元素可分为n/k个组，每个组包含k个元素，且任一组内的各元素均分别大于前一组内的所有元素并小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为 。
（a）O（nlog2n） （b）O（nlog2k） （c）O（klog2n） （d）O（klog2k）
若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是 。
（a）二叉排序树 （b）哈夫曼树 （c）堆
用dfs遍历一个无环有向图，并在dfs算法退栈返回时，打印出相应的顶点，则输出的顶点序列是 。
（a）逆拓扑有序的 （b）拓扑有序的 （c）无序的
（共15分）设A[0..k-1]是一个整数数组，各分量的初值为0，即A[i]=0（0≦i≦k-1），设n为连续调用Demo过程的次数，请回答下述问题：
给出调用次数n=4时，数组A中各分量的结果。（4分）
若 ，数组A中各分量的结果是什么？（4分）
Demo过程的功能是什么？数组A起何作用？（4分）
显然Demo过程的最坏时间是o（k），故连续调用Demo过程n次的总时间为O（kn）。但是这个界偏大，请详细分析求出一个更小的n次连续调用Demo的总时间的上界。（3分）
Procedure Demo（Var A：arraytype；k：integer）
{
i：=0；
while （i<k）and （A[i]=1）do
{
A[i]：=0；
i：=i+1；
}
if i<k then A[i]：=1；
}
（共15分）一个有向图G=（V，E）的转置是有向图 ，其中
。因此将G中所有边反向后可得 。
写一算法从给定的G求出 ，并分析算法的时间复杂度，要求使用以下
邻接表作为存储结构：
Type arcptr = ^arcnode;
arcnode = RECORD //边表结点
arjvex : 1..n; //邻接点序号
nextarc: arcptr; //指向下一个边表结点
END;
vexnode = RECORD
vexdata : vextype; //顶点信息
firstarc : arcptr; //指向边表的第1个结点
END;
adjlist = ARRAY[1..n] OF vexnode;
第二部分：操作系统和编译原理
简答题（3分×5）
操作系统的作用是什么？其主要特征是什么？
什么是系统调用？它与一般的程序过程调用有什么区别？
引起系统抖动的原因是什么？
什么是虚拟设备？如何实现虚拟设备？
UNIX系统中有哪些磁盘读写方式？
（10分）分析下面用信号量解决哲学家进餐问题的同步算法是否满足同步机制的四条准则。若不满足，说明为什么，并给出满足同步机制四条准则的同步算法。
var fork：array[0..4] of semaphore;
fork[0] := fork[1] := fork[2] := fork[3] := fork[4] := 1;
parbegin
Pi : repeat /*第i个哲学家的生活过程*/
ThinkForWhile;
P(fork[i]);
P(fork[(i+1) mod 5]);
EatForWhile;
V(fork[i]);
V(fork[(i+1) mod 5]);
until false
parend
（10分）下面的二义文法描述命题演算公式，为它写一个等价的非二义文法。
S S and S | S or S | not S | p | q | (S)
（15分）下面程序的结果是120。但是如果把第10行的abs（1）改成1的话，则程序结果是1。试分析为什么会有这样不同的结果。
int fact（）
{
static int i = 5；
if （i == 0）
{
return （1）；
}
else
{
i = i –1；
return （（i+abs（1））*fact（））； /*第10行*/
}
}
main（）
{
printf（“factor of 5 = %d\n”，fact（））；
}
