中国科学院软件研究所 一九九五年招收硕士学位研究生入学考试试题 试题名称：软件基础 一．（6分）请给出下图的邻接矩阵、邻接表、逆邻接表和十字链表。 二．（12分）编一个程序，按递增次序生成集合M的最小的100个数。M的定 义如下： （a）数1属于M； （b）如果x属于M，则y=2*x+1和z=3*x+1也属于M； （c）再没有别的数属于M。 （M={1，3，4，7，9，10……}） 三．（8分）使用对半查找程序的限制条件是什么？下列的三种对半查找程序 （Pascal语言），哪些是正确的，哪个效率高一些？假定N>0，以及下列变 量已经定义。 var i，j，k ：integer； a ：array [1..N] of T; x ：T; 程序A: i:=1; j:=N; repeat k:=(i+j) div 2 if a[k]<x then i:=k else j:=k; until (a[k]=x) ∨(i≧j) 程序B: i:=1; j:=N; repeat k:=(i+j) div 2; if x≦a[k] then j:=k-1; if a[k]≦x then i:=k+1; until i>j; 程序C: i:=1; j:=N; repeat k:=(i+j) div 2; if x<a[k] then j:=k else i:=k+1; until i≧j 四．（14分）用高级语言（C或Pascal）设计一个非递归的快速排序程序。 五．（6分）将下面的DFA化成最简DFA（注意，大写C和小写c是不同符号） 六．（7分）文法G的产生式如下： S I|R I d|Id R WpF W ε|Wd F d|Fd 令d表示任意数字，p表示十进制小数点，那么非终结符S，I，R，W 和F在程序设计语言中分别表示什么？ 该文法是LR（1）文法吗？为什么？ 七．（10分）有文法： S L.L|L L LB|B B 0|1 给此文法配上语义动作子程序（或者说为此文法写一个语法制导定义），它 输出S产生的二进制数的值。例如，输入101.101时，输出5.625。 八．（7分） 下面C语言程序中，函数printf的调用仅含一个参数。该程序输出三个 整数。试从存储分配和printf的实现来分析，为什么此程序仍有三个整 数输出。 main（）{ printf(“%d,%d,%d\n”) } 考虑下面的C程序 main（） { char *cp1，*cp2； cp1:= “12345”; cp2=“abcdefghij”; strcpy(cp1,cp2); printf(“cp1=%s\ncp2=%s\n”,cp1,cp2); } 该程序运行的结果是： cp1=abcdefghij cp2=ghij 试分析，为什么cp2所指向的串被修改了？ 九．简答题：（2分×5） 采用多道程序设计的主要优点是什么？ 什么是SPOOLing技术？ 叙述“打开（OPEN）”和“关闭（CLOSE）”文件操作的意义。 有哪些对空闲盘块的管理方案？UNIX系统采用的是什么？ 什么是死锁？对死锁问题有哪些对策？ 十．（5分）在UNIX系统中，将进程控制块（PCB）和文件控制块（FCB） 各分解为哪二个部分？为什么？ 十一．（6分）分页存储管理有效的解决了什么问题？试叙述其实现原理。 十二．（9分）多个进程共享一个文件，其中只读文件的称之为读者，其余只写 的称之为写者，读者可以同时读，但是写者只能独立地写。请 说明进程间得相互制约关系；应设置哪些信号量； 用P、V操作写出其同步算法； 修改上述的同步算法，使得它对写者优先，即一旦有写者到达，后续 的读者都必须等待，而无论是否有读者在读文件。