〈新〉计算所试题.doc

中科院计算所2003年考研试题第一部分 编译（40’） 一、（1/01）*0*说明是什么语言 画出DFA（10’） 二、S→过程调用语句/数组的赋值语句（10’） 过程调用语句为：id(id,id,…,id) 赋值语句: id(id,…,id):=id(id,…,id) (a)写一个LR（1）方法（产生式不大于6个） (b)若在LR分析同时完成语义分析，中间代码生成，基于你的文法有什么困难？ 三、E→E*E/+E/-E/unsigned-integer 为上面表达式产生栈机器代码，代码执行后，表达式值留在栈上，自己设计所需栈机器指令，并写清指令含义。(10’)四、C语言中，a表示数组首址，而a也表示数组首址，然而使用时有时并不相同，请根据下面写出a与a类型表达式 （10’） (1) tgpedef int A[10][20] A a;  A * func ( )  {  return(a);  } 在linux上用gcc编译报告:第6行warning: return from incompatible pointer type (2) typedef int A[10][20] A a;  A *func( )  {  return(a);  }  无类型方面错误 (3) typedef int A[10][20] typedef int B[20]  A a;  B *func( )  {  return(a);  }  无类型方面错误 (4) typedef int A[10][20] A a;  func( )  {  Printf(“%d,%d,%d/n,a,a+1,a+1);  }  main( )  {  func( );  }  结果：134518112，134518192，134518912 第二部分 操作系统（40’） 五. 1、操作系统内核有强内核和微内核，unix是前者，windowsNT是后者，简介微内核比强内核的优点。（4’）2、若只有进程控制，其独立性表现在？引入线程后，独立性有何改变?（4’） 3、请求调页存储系统确定页面大小的标准（4’） 六、1.死锁的证明在m个同类资源，n个进程共享它，每次进程只能获得或释放至多一个资源，问会不会发生死锁，若： (1)、设每个进程所需资源数为ri 1=ri=m (6’) 2、windows NT页面大小为4KB，采用两级页表机构，为提高 设了32K或64K的Cache，试叙述windows NT地址变换过程的页面调度策略。（10’） 3、假设有一种新磁盘技术，两者即磁盘与内存访问时间在同一数量级上，作下面哪些修改以采用更快的磁盘访问速度。（12’）（1） 进程调度（4’） （2）内存管理（4’） （3）磁盘驱动程序（4’）第三部分 数据结构（70分） 七. 选择（5×2’）八.简答（10×2’） 说明七和八题都很简单,多是考察有关树方面的小问题,第八题和填空题差不多,非常简单,故没抄下来. 九、（5×5’分） 广义表，设H表示Get head ，T表示Get Tail 从下表中分解出原子a,请给出H、T操作序列。 L=((( )),(b,c),((b,(c,a)),(c,d)),((e),d)) 2、串序列T=“abcabcabca”模式串w=“abca”用kmp算法，求next[1:10] 3、一无向图，边非负权值，问用Dijkstra最短路径算法能否给出一棵生成树？该树是否一定是最小生成树？说明理由。 4、判断向一无环图增加一边是否会使图中产生环的问题时，应选用什么样的数据结构？（一名话简单回答）在使用这种数据结构时该判断所需时间。 5、设向一棵空平衡二叉树（AVL）中插入关键字序列为[45，24，12，62，70，50，10，38]画出每插入一关键字后该树状态示意图，若在此基础上删除关键字62，给出删除后的状态图。 十、（15分）有n张扑克牌，存在由记录组成的数组A（1：n）中，每个记录有三个域，其中，N0为每张扑克初始序号，一旦给定不改变,Cor表示每张扑克花色，梅花方块红桃黑桃 ，Val表子扑克数值1..13，要将这n张由小→大排序，每张只能看一次，低花色比高花色的值小，花色的大小均相同的保持原相对的次序，请写算法，并描述所用附加存储空间结构。T1(n)=n+1000. B）T2(n)=n -1000 C）T3(n)= -1000 D）T4(n)=2n-1000 2．下述编码中哪一个不是前缀码（