中国科学院计算技术研究所 一九九六年招收硕士学位研究生入学考试试题答案 试题名称：软件基础 Program SEQUENCE(input , output); var i , k , l , m , n : integer ; BEGIN read(n); i := 1; write(i); IF n <> 1 THEN BEGIN k := 2; m :=1; FOR l=1 to n-1 DO BEGIN i := i + m; IF i=1 THEN BEGIN k := k + 1; m := -m; END IF i=k THEN m := -m; write(i); END END END. 算法要点：从n个点中任选两条构成一条直线，用“两点式”写出该直线方程。将其余的点代入方程，记录满足此方程的点数。这样的直线共有n（n-1）/2条，从中选出最多点数。 过程中的x[i]和y[i]分别表示第i个点的横坐标和纵坐标。 （假定前面有类型说明：type T = array [1..100] of real；） function maxpoint（var x，y：T；n：integer）：integer； var i，j，k，m，mmax：integer； begin mmax：=0； for i：=1 to n-1 do for j：=i+1 to n do begin m：=2； for k：=j+1 to n do if (x[i]-x[j])*(y[j]-y[k]) = (x[j]-x[k])*(y[i]-y[j]) then m := m + 1; if m>mmax then mmax := m end; maxpoint := mmax; end. 句子aabbab有两种不同的推导： S ( aB ( aaBB ( aabB ( aabbS ( aabbaB ( aabbab； S ( aB ( aaBB ( aabSB ( aabbAB ( aabbaB ( aabbab； S aBS | bAS | aB | bA B aBB | b A bAA | a D’ { D.num = 0} D D attrlist { namelist.num = D.num + attrlist.num} namelist D attrlist { D1.num = D.num + attrlist.num} ( D1 ) namelist id { addattr(id.entry , namelist.num) } namelist id , { namelist1.num = namelist.num } namelist1 { addattr(id.entry , namelist.num) } attrlist A attrlist1 { attrlist.num = attrlist1.num + 1} attrlist A { attrlist.num = 1} C编译是不作调用时的形参和实参一致性检查的。由于整数有short、int和long三种类型，实数有float和double两种类型，C的调用是传值的。一个整形表达式的值究竟应按short、int还是long方式传递呢。显然，这儿约定为取size最大的方式，即long方式；实数用double方式。虽然按最大size方式传递，被调用函数中形式参数（局部量）是按自己类型size取值（但要考虑边界对齐）。short型的形参是取long值4字节中的后两字节内容，float型的形参是取double值字节的前4字节。这样才出现这四个形参地址的上面结果。 “扩充”内存的一种手段。将内存中处于睡眠状态的进程暂时换到磁盘对换区，将内存区让位于就绪的进程； 管理采用的数据结构为“对换映射表”： maddr —— 可用盘区始址； misize —— 该区的可用盘块数。 采用分区分配和首次适应分配算法。释放时要进行相邻区的合并。 UNIX系统V提供的工具有： Sleep/Wakeup：核心态进程的同步； 软中断信号机制（signal/kill）：同一用户进程间的通讯（小数据量）； 基于文件系统的pipe机制：进程间大数据量的通讯； 共享存储器、信号量集和消息传递机制。 采用全路径名访问他人文件。共享时间短； 采用目录表项之间的链接。即使一个用户目录中的表项直接指向另一个目录中的表项。长久共享。 采用基本文件目录和符号文件目录的组织方式，便于用户文件的共享。 它代表解决死锁问题的一种策略。在实施资源分配之前，先计算该次分配后所产生的状态是否安全，即是否存在一种顺序，使所有进程都能执行结束。若安全，则分配；否则，拒绝分配； 该算法虽有很好的理论意义，但在实际系统中却很难使用。因为算法所假设的条件，如：进程可知申请资源的最大数目、系统中进程数目固定等，在实现环境中并不成立，所以由不成立的前提导出的结果很难说明正确的。 平均周转时间 T = 22； T = 19.2； T = 19.2； T = 14。