中国科学院计算技术研究所 一九九六年招收硕士学位研究生入学考试试题 试题名称：软件基础 （10分）已知序列17，31，13，11，20，35，25，8，4，11，24，40，27。请画出该序列的二叉排序树，并分别给出下列操作后的二叉树； ①插入数据9； ②删除结点17； ③再删除结点13。 （15分）请编写一个程序，生成如下序列的前n项。 1，2，1，2，3，2，1，2，3，4，3，2，1，2，3，4，5，4，3，2，1, 2，…… （15分）已知平面上（直角坐标系）的n个点，请编一个函数，求同一条直线所能通过的最多点数。 （10分）下面的文法产生a的个数和b的个数相同的非空a，b串。 S aB | bA B bS | aBB | b A aS | bAA | a 其中非终结符B推出b比a的个数多1个的串，A则反之。 说明该文法是二义的。 对上述文法略作修改，使之非二义，并产生同样的语言。略作修改的含义是：不增加非终结符。 （10分）某些语言允许给出名字表的一个属性表，也允许声明嵌在另一个声明里面，下面文法抽象这个问题。 D attrlist namelist | attrlist（D） namelist id，namelist | id attrlist A，attrlist | A A decimal | fixed | float | real D attrlist（D）的含义是：在括号中的声明提到的所有名字有attrlist 中给出的属性，而不管声明嵌套多少层。写一个翻译方案，它将每个名字 的属性个数填入符号表。 （10分）下面是一个C语言程序及其运行结果。从运行结果看函数func中四个局部变量i1，j1，f1，e1的地址间隔和它们类型的大小不一致，试分析不一致的原因。 #include <stdio.h> func(i , j , f , e ) short i , j ; float f1 , e1; { short i1, j1; float f1, e1; i1 = i; j1 = j; f1 = f; e1 = e; printf(“Addresses of i, j, f, e = %d, %d, %d, %d\n”, &i, &j, &f, &e); printf(“Addresses of i1, j1, f1, e1 = %d, %d, %d, %d\n”, &i1, &j1, &f1, &e1); printf(“Size of short, int, long, float, double = %d, %d, %d, %d, %d\n” , sizeof(short), sizeof(int), sizeof(long), sizeof(float), sizeof(double)); } main() { short i, j; float f, e; i = j = 1; f = e = 1.0; func(i , j , f , e); } 运行结果: Addresses of i, j, f, e = -268438178, -268438174, -268438172, -268438164; Addresses of i1, j1, f1, e1 = -268438250, -268438252, -268438256, -268438260; Size of short , int , long , float , double = 2, 4, 4, 4, 8 （5分）在UNIX系统中，对换区的功能是什么？UNIX系统V是如何对对换区进行管理的？ （5分）UNIX系统V为进程之间的通信提供了哪些工具？各用于什么场合？ （5分）操作系统中的文件共享有几种形式？它们是如何实现的？各有什么特点？ （5分）Dijkstra（1965）提出的银行家算法的主要思想是什么？它能够用来解决实际中的死锁问题吗？为什么？ （10分）有五个批处理的作业（A，B，C，D，E）几乎同时到达一个计算中心，估计的运行时间分别为2，4，6，8，10分钟，它们的优先数分别为1，2，3，4，5（1为最低优先级）。对下面的每种调度算法，分别计算作业的平均周转时间。 ①最高优先级优先； ②时间片轮转（时间片为2分钟）； ③FIFO（作业到达的顺序为C，D，B，E，A）； ④短作业优先。