《中科院计算所历年考研真题编译原理操作系统数据结构软件基础含答案》由会员分享，可在线阅读，更多相关《中科院计算所历年考研真题编译原理操作系统数据结构软件基础含答案（8页珍藏版）》请在金锄头文库上搜索。
1、中科院计算所 2003 年考研试题第一部分编译(40一、(1/01) *0*说明是什么语言 画出DFA(IO)二、S过程调用语句/数组的赋值语句(10)过程调用语句为：id(id,id,.,id)赋值语句:id(id,.,id):=id(id,.,id)(a) 写一个LR(1)方法(产生式不大于6个)(b) 若在LR分析同时完成语义分析，中间代码生成，基于你的文法有什么困难？三、EE*E/+E/-E/unsigned-integer为上面表达式产生栈机器代码，代码执行后，表达式值留在栈上，自己设计所需栈机器指令，并写清指令含 义。(10)四、C语言中，a表示数组首址，而&a也表示数组首址，然而
2、使用时有时并不相同，请根据下面写出a与&a 类型表达式 (10)(1) tgpedef int A1020A a;A * func ( )return(a);在 linux 上用 gcc 编译报告:第 6 行 warning: return from incompatible pointer type(2) typedef int A1020A a;A *func( )return(&a); 无类型方面错误(3) typedef int A1020typedef int B20A a;B *func( )return(a);无类型方面错误(4) typedef int A1020A a;fun
3、c( )Printf(“%d,%d,%d/n,a,a+1,&a+1);main( )func( );结果： 134518112， 134518192， 134518912中科院计算机技术研究所 1999 年硕士生入学试题中科院计算所1999年编译原理与操作系统一.（15分）有表达式如下:A+B*（C-D）*N （*为幕乘）三. （5分）构造一个DFA（确定的有限自动机），使之接受含偶数个T的0,1串集.四. （5分）有文法G,其产生式如下：S-S（S）,S-8空产生式*/ 试写出一个语法制导定义,它输出配对的括号个数.五. （10分）已知某语言L=aA（m）bA（n）lnm=0.试写出产生该语
4、言的两个文法G1和G2,其中G1是LR（1）文 法,G2是非LR（1）和非二义性文法.六. 填空（每空一分,共 20 分）中科院计算所1999年编译原理与操作系统参考答案.(1)后缀式:ABCD-*+ECD-N*/+(2)四元式(1) (-,C,D,t1)(2) (*,B,t1,t2)(3) (+,A,t2,t3)(4) (-,C,D)(5) (*,(4),N)(6) (/,E,t5,t6)(7) (+,t3,t6,t7)三元式(1) (-,C,D)(2) (*,B,(1)(3) (+,A,(2)(4) (-,C,D,t4)(5) (*,t4,N,t5)(6) (/,E,(5)(7) (+,(
5、3),(6)四.（5分）为符号S引入综合属性h,语法制导定义如下：产生式语义规则S-S1（S2）S.h:=S1.h+S2.h+1S- &S.h:=0S-Sprint(S.h)/* 输出其配对括号数 */五.(10 分)G1:LR(1)文法 G2:非 LR(1),非二义性文法 S-A,BS-aSblBA-aAbl & B-BblbB-Bblb六.填空 1.并发,共享 2.初始化标识符信息,初始化处理机状态信息,初始化处理机控制信息;3.为了减少程序并发执行时所需付出的时空开销，提高程序执行的并发度;4.forkpipemknod5.正在执行的进程时间片完;正在执行的 进程执行了 sleep系统调
6、用;正在执行的进程执行了 exit系统调用;正在执行的进程在用户态运行时有优先级更 高的进程进入就绪队列 6.中低地址,高地址 7.设备控制表,控制器控制表,通道控制表,系统设备表 8.只让文件主 拥有指向该文件索引结点的指针,而共享该文件的其他用户只有该文件的路径明而不是指向索引结点的指针.中科院 98 考研题中科院计算所1998年编译原理和操作系统一. (10分)某操作系统下合法的文件名为device:name.extension ,其中第一部分(device:)和第三部分(.extension) 可缺省,若 device,name 和 extension 都是字母串,长度不限,但至少为
7、1,画出实现这种文件名的确定有限自动机.二. (10 分)下面的二义文法描述命题演算公式,为他写一个等价的非二义文法.S-S and S|S or S|not S|p|q|(S)三. (10 分)把表达式 - (a+b)*(c+d)+(a+b+c) 翻译成四元式.四. (10分)由于文法二义引起的LR(1)分析动作冲突，可以根据消除二义的规则而得到LR(1)分析表，根据此表可 以正确识别输入串是否为响应语言的句子对于非二义非LR(1)文法引起的LR(1)分析动作的冲突，是否也可以 根据什么规则来消除LR(1)分析动作的冲突而得到LR(1)分析表，并且根据此表识别相应语言的句子?若可以, 你是否
8、可以给出这样的规则?五. (10分)下面程序的结果是120.但是如果把第5行的abs(1)改成1的话,则程序结果为1. 试分析为什么会有这不同的结果.int fact()static int i=5; if(i=0) return(1); else i=i-1; return( i+abs(1)*fact(); main() printf(factor or 5=%dn，fact();中国科学院计算所1997年编译原理试题(共25分)1. (10分)为正规式(alb) *a(alb)构造一个确定的有限自动机。2(15 分) 试画出如下中间代码序列的程序流图，并求出： 各结点的必经结点集合 D(
9、n)； 流图中的回边与循环。J：=0；L1 ：I：=0；If I 8 goto L3;L2：A:=B+CB:=D*C;L3：if B = o goto L4;Write B;goto L5;L4 ：I:= I+1;If I8 goto L2L5：J:= J+1If J=3 goto L1;HALT中科院计算所1996年程序设计一、单项选择：( 20 分)二、问答题(25 分)中国科学院计算所一九九六年软件基础一（10 分）已知序列 17，31，13，11，20，35，25，8，4，11，24，40，27。请画出该序列的二叉排序树， 并分别给出下列操作后的二叉树；插入数据9；删除结点17；再删除
10、结点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 I bAB bS I aBB I bA aS I bAA I a其中非终结符B推出b比a的个数多1个的串，A则反之。说明该文法是二义的。 对上述文法略作修改,使之非二义,并产生同样的语言。略作修改的含义是：不增加非终结符。五. （1
11、0 分）某些语言允许给出名字表的一个属性表,也允许声明嵌在另一个声明里面,下面文法抽象这个 问题。Dattrlist (D)的含义是：在括号中的声明提到的所有名字有attrlist中给出的属性，而不管声明嵌套多少层。写一个翻译方案，它将每个名字的属性个数填入符号表。六. (10分)下面是一个C语言程序及其运行结果。从运行结果看函数func中四个局部变量订，j1，f1，e1 的地址间隔和它们类型的大小不一致,试分析不一致的原因。#include func(i , j , f , e ) short i , j ; float f1 , e1;short i1, j1; float f1, e1;
12、i1 = i; j1 = j; f1 = f; e1 = e;printf(“Addresses of i, j, f, e = %d, %d, %d, %dn”, &i, &j, &f, &e); printf(“Addresses of i1, j1, f1, e1 = %d, %d, %d, %dn”, &i1, &j1, &f1, &e1); printf(“Size of short, int, long, float, double = %d, %d, %d, %d, %dn” , sizeof(short), sizeof(int), sizeof(long), sizeof(f
13、loat), 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,
14、 4, 4, 4, 8中国科学院计算所一九九六年软件基础答案is2.7171*1只8MlO1C2j2C11202S11；92427212Ejrn4.句子aabbab有两种不同的推导：S 9 aB 9 aaBB 9 aabB 9 aabbS 9 aabbaB 9 aabbab；S 9 aB 9 aaBB 9 aabSB 9 aabbAB 9 aabbaB 9 aabbab；S aBS I bAS I aB I bAB aBB I bA bAA I a8. UNIX系统V提供的工具有：Sleep/Wakeup：核心态进程的同步；软中断信号机制（signal/kill）：同一用户进程间的通讯（小数据量）；基于文件系统的pipe机制：进程间大数据量的通讯； 共享存储器、信号量集和消息传递机制。9. 采用全路径名访问他人文件。共享时间短；采用目录表项之间的链接。即使一个用户目录中的表项直接指向另一个目录中的表项。长久共享 采用基本文件目录和符号文件目录的组织方式，便于用户文件的共享。中科院计算所 1994 年软件基础语言与编译部分（35分）S （L） | aL L, S | S给此文法配上语义动作子程序（或者说为此文法写一个语法制导定义），它输出配对的括号的个数，如对于句 子（a,（a,a）输出是2。三. （15分）为语言a mbn In m 0 写三个文法，
