第一部分编译（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张由小→大排序，每张只能看一次，低花色比高花色的值小，花色的大小均相同的保持原相对的次序，请写算法，并描述所用附加存储空间结构。