科目代号：70
试题适用专业：计算机软件
一． 构造正规（a，abb）的相应DFA。（10分）
二． 已知文法：（26分）
G：Z--- Azjb
A- Zaja
1． 证明aaaabbbbababab 是文法G的句子
2． 画出 aaaabbbbababab 所对应的语法树。
3． 将文法G拓广为G'，并求出G'所非终结符的Follow.(4分)
4． 列出拓广文法G'的所有LR(0)项目。
5． 构造出拓广文法G' 的LR(0) 项目集族及GO函数。（9 分）
6． 该文法是`SLR 文法吗？若是则构造出其 SLR 分析表，否则说明不是
SLR文法的理由。（3分）
三． 将下列表达式表示成后缀式。（8分）
1． Y=((a+b+c)/(-a*d/e))/(f-k*t)
2． (A∧B∨C)∧(C∨D∧E∨F)∨G∨(P∨Q)
四． 已知语言 L(G)={a b c d |n≥1,i≥0}, 试构造出产生该语言德文法。（6分）
五． 指出以下各组概念是否有区别，有何：（区别5分）
（1） 进程，程序，作业
（2） 临界资源，共享资源
（3） 地址空间，存储空间
（4） 预防死锁，避免死锁
（5） 分时系统，实时系统，多道系统
六． 简要论述操作系统的虚拟特征。（6分）
七． 有一计算机系统利用位示图来管理磁盘文件空间。假定该磁盘组共有100
每个柱面上个柱面有20个磁道，每个盘面分成8个扇块（扇区），每个盘
快1k字节，位示图如下： （10分）
j \ I o 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
3 1 1 1 1 1 1 0 1 1 1 1 1 1 0 0 0
4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
。。。。。。
（1） 试给出位示图中的位置(i,j)与对应盘块所在的物理位置(柱面号,磁头
号,扇区号)之间的计算公式.假定柱面号,磁头号,扇区号都从1开始编号.(5分)
(2) 试说明分配和回收一盘块的过程.(5分)
八 说明CSW,CAW,CCW三个控制字在I/O控制过程中的作用.(9分)
九 请问能同时处理分时作业和批处理作业的系统设计一套进程方案.(10分)
