首页 > 专业课

试题:(中科院)2003年软件所编译和操作系统

2007年06月12日 来源:考研加油站
    第一部分 编译(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)文件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’分)
    
    1、广义表,设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张由小→大排序,每张只能看一次,低花色比高花色的值小,花色的大小均相同的保持原相对的次序,请写算法,并描述所用附加存储空间结构。 
    
招生信息