中国科学院软件研究所
一九九八年招收硕士学位研究生入学考试试题答案
试题名称：软件基础
第一部分：程序设计和数据结构
选择合适的答案填空（1分×20）
（a），（d），（e）；
（b）；
（c），（a），（d）；
（c）；
（b）；
（b）；
（d）；
（e）；
（b），（c）；
（b）；
（b）；
（c）；
（b）；
（c）；
（a）；
除A[2] = 1外，其余各分量均为0。
A中分量均为0。
Demo的功能是二进制数的增量（加上）操作，A相当于一个二进制计数器。
n次连续调用Demo的总时间的上界应为O（n），详细分析如下：
Demo操作的时间代价正比于二进制数A中位（每个A[i]相当于二进制数的位）的翻转次数，而n次连续的Demo操作是从0开始的，因此在这n次增量操作中：A[0]共翻转n次，A[1]共翻转 次，……，A[i]共翻转 次（i ）；当i 时，位A[i]根本不翻转（因为数n的二进制表示最多有 位），所以n次增量操作发生的位翻转总次数为：
Procedure transpose（G：adjlist；var GT：adjlist）
{
for i：=1 to n do //初始化转置图GT的邻接表
{
GT[i].firstarc := nil;
GT[i].vexdata := G[i].vexdata;
}
for i :=1 to n do
{
p := G[i].firstarc;
while p≠nil do
{ //依次搜索vi的邻接点vj
j := p↑.adjvex; //<vi,vj>是G的边
new(q); // 申请一表结点
q↑.adjvex := i;
q↑.nextarc := GT[j].firstarc;
GT[j].firstarc := q; //将<vj,vi>插入到GT[j]的邻接表头上
p := p↑.nextarc; //取vi的下一邻接点
} //end of while
} // end of for
}
时间复杂度：O（n+e），这里n=|V|，e=|E|。
第二部分：操作系统和编译
操作系统的作用是：屏蔽系统的硬件特性，提供功能更强的虚拟机；管理计算机系统资源，使之得到有效利用；提供方便友好的用户接口。其主要特征是并发和共享。
系统调用是操作系统提供给用户的系统服务程序，是应用程序申请操作系统服务的接口。系统调用运行在系统态，而一般的程序过程运行在用户态；应用程序以直接转入执行的方式调用一般过程，但必须通过中断方式转入执行系统调用，而不能直接转入执行。
由于多通道程序系统中引入了过多的程序道数，使得运行进程的大部分时间都用在进行页面的换入换出，而几乎不能完成任何有效的工作。
虚拟设备是由脱机或假脱机技术实现的将独占、低速、单台的物理设备改造而成的共享、高速、多台的观念上存在的设备。
UNIX系统中有两种读磁盘的方式：一般读方式和提前读方式；三种写方式：一般写方式、异步写方式和延迟写方式。
不满足“有限等待”准则，当每个哲学家都只拿到一把叉子时，发生死锁。一种改进的算法如下：
var fork：array[0..4] of semaphore;
var matex:semaphore;
fork[0] := fork[1] := fork[2] := fork[3] := fork[4] := 1;
matex :=1;
parbegin
Pi : repeat //第i个哲学家的生活过程
ThinkForWhile;
P(matex);
P(fork[i]);
P(fork[(i+1) mod 5]);
V(matex);
EatForWhile;
V(fork[i]);
V(fork[(i+1) mod 5]);
until false
parend
E E or T | T
T and F | F
F not F | p | q | (E)
i是静态变量；
这和编译时的代码生成策略有关。对于表达式（i+abs（1））*fact（），因两个子表达式都有函数调用，因此先产生左子表达式代码，后产生右子表达式代码。当abs（1）改成1后，先产生右子表达式代码。
因此有不同的结果。
