中国科学院软件研究所 一九九五年招收硕士学位研究生入学考试试题答案 试题名称：软件基础 一． 1．邻接矩阵： 2．邻接表 1 1 0 1 0 0 0 2 0 0 1 3 1 0 0 0 4 3．逆邻接表 4.十字链表 1 2 3 4 二．解决该问题的一个C语言程序如下： main（） { int M[100]； int yi，zi，j，y，z； M[0]=1； j=1； y=3； yi=0； z=4; zi=0； for(j=1；j<100;j++） { if (y<z) { M[j]=y; yi++; y=2*M[yi]+1; } else if (y==z) { M[j]=y; yi++; zi++; y=2*M[yi]+1; z=3*M[zi]+1;} else { /* (y>z) */ M[j]=z; zi++; z=3*M[zi]+1;} } for (j=0;j<100;j++) printf(“%d ”,M[j]); } ?三．1．对半查找程序只适用于以向量（数组）做存储结构的有序表。 2．程序A和B正确，C错误。 程序B的效率更高一些。 四．快速排序的非递归程序用PASCAL语言描述如下，要排序的元素n个。 type index = 0..n； type item = record key ： integer； 其它项； end //----------------------procedure START----------------------------------- procedure quicksort const m = 12； /* 栈大小 */ var i，j，l，r ：index； x，w ：item； s ：0..m； stock ：array [1..m] of record l , r : index end; a : array [1..n] of item; begin s:=1; stack[2].l:=1; stack[1].r:=n; repeat l:=stack[s].l; r:=stack[s].r; s:=s-1; repeat i:=1; j:=r; x:=a[(l+r) div 2]; repeat while a[i].key < x.key do i:=i+1; while x.key < a[j].key do j:=j-1; if i<=j then begin w:=a[i]; a[i]:=a[j]; a[j]:=w; i:=i+1; j:=j-1; end until i>j; if i<r then begin s:=s+1; stack[s].l:=i; stack[s].r:=r end r:=j until l>=r until s=0 end {quicksort} 五． 六．1．S：无符号数， I：无符号整数， R：无符号实数， W：无符号实数的小数点前面部分，F：无符号实数的小数点后面部分。 2．当第一个终结符是d时，不知应把d归约成I呢，还是空归约成W。 七． S’ S print(S.val) S L1.L2 S.val:=L1.val+L2.val/2 S L S.val:=L.val L L1B L.val:=L1.val*2 + B.val； L.length:=L1.length + 1 L B L.val:=B.val L.length:=2 B 1 B.val:=1 B 0 B.val:=0 八．1．（简单回答） 根据C的存储分配特点，被调用过程总能知道第一个实参的位置，printf 的实现是从第一个参数分析还有几个参数。 2．执行前常数区是 cp1 cp2 ↓ ↓ 12345\0abcdefghij\0 strcpy执行后，该区域变成了： abcdefghij\0fghij\0 ↑ ↑ cp1 cp2 九．1．多道程序设计通过将用户的CPU请求和I/O请求重叠起来的办法，提高 了CPU的使用效率。 2．它使用直接存取的大容量磁盘作为缓冲，将一个可共享的磁盘空间，改 造成若干台输入设备和输出设备，并使得I/O设备与CPU并行操作。 3．OPEN：告诉系统所指定的文件将变成活跃，其文件说明（或文件目录） 复制到内存中； CLOSE：告诉系统，用户不再使用指定的文件，其文件说明不需保存在 内存中 4.空闲文件目录，空闲盘块链，位示图，成组链接法。 5．死锁是指在系统中，有二个后多个进程无限期的等待永远不会发生的条 件的一种系统状态。 对待死锁的对策有：死锁的预防、避免、死锁的检测和解除。 十． prec结构，含常用信息，常驻内存； PCB( user结构，含进程运行时所用信息，可调入/调出内存。 目的：节省内存空间。 名号 ： 含文件名及编号i； FCB( 小结点： 对应i的其它文件控制信息。 目的： 加快检索速度，便于文件的共享。 十一．1．解决了存储器零头（碎片）问题。 2．实现要点： a．存储器等分为块，称之为存储块（页架），是分配的单位，其大 小为 。 b．作业地址空间分页，页与块的大小相等。 c．页表、作业在物理空间上不要求连续存放，存放页表表目，建立 页与块的对应关系。 d．地址变换机构，动态地实现逻辑地址到物理地址的映射。 十二．a．读者之间同时读；读者与写者之间互斥进行；写者之间互斥进行。 设置 mutex1：各读者进程使用计数器rc时的互斥信号量； mutex2：写者之间、写者与读者之间互斥使用文件所用的互斥 信号量。 b．用类Pascal语言描述算法如下： begin mutex1：=1； mutex2：=1； rc：=0； cobegin ┇ reader: begin P(mutex1); rc:=rc+1; if rc=1 then P(mutex2); V(mutex1); Reading the file: P(mutex1); rc:=rc-1; if rc=0 then V(mutex2); V(mutex1); end； ┇ writer: begin P(mutex2); Writing the file; V(mutex2); end; ┇ coend; end. c.增加一个信号量WW，用以写进程到时封锁后续的读者。相应的算法改 为： begin mutex1：=1； mutex2：=1； WW：=1； rc：=0 cobegin ┇ reader： begin P（WW）； P（mutex1）； rc：=rc+1； if rc=1 then P（mutex2）； V（mutex1）； V（WW）； Reading the file； P（mutex1）； rc：=rc-1； if rc=0 then V（mutex2）； V（mutex1）； end； writer： begin P（WW）； P（mutex2）； Writing the file； V（mutex2）； V（WW）： end； coend； end。