中科院計算機技術研究所1999年碩士生入學試題 編譯原理與操作係統

中科院計算機技術研究所1999年碩士生入學試題編譯原理與操作係統

一.(15分)有表達式如下:A+B*(C-D)**N (**為冪乘)

(1)給出該表達式的逆波蘭式表示(後綴式);

(2)給出上述表達式的四元式和三元式序列.

二.(15分)有C程序如下:

main()

{

printf("%d,%d,%d\n",10);

}

(1)試著寫出上述printf語句輸出的結果;

(2)從運行環境和printf的實現分析為什麼會有這樣的輸出結果.

三.(5分)構造一個DFA(確定的有限自動機),使之接受含偶數個"1"的0,1串集.

四.(5分)有文法G,其產生式如下:

S->S(S),

S->ε/*空產生式*/

試寫出一個語法製導定義,它輸出配對的括號個數.

五.(10分)已知某語言L={a^(m)b^(n)|n>m>=0}.試寫出產生該語言的兩個文法G1和

G2,其中G1是LR(1)文法,G2是非LR(1)和非二義性文法.

六.填空(每空一分,共20分)

1.現代操作係統的兩個最基本的特征是___和___.

2.進程控製塊的初始化工作包括___,___和___.

3.在操作係統中引入線程概念的主要目的是___.

4.unix係統v中,係統向用戶提供的用於創建新進程的係統調用是___;用於建立無名

管道的係統調用是___;用於創建有名管道的係統調用是___.

5.unix係統v中,引起進程調度的原因有___,___,___和___等.

6.在分區分配算法中,首次適應算法傾向於優先利用內存中___部分的空閑分區,從

而保留了___部分的大空閑區.

7.進行設備分配時所需的數據表格主要有___,___,___和___等.

8.利用符號鏈實現文件共享時,對文件主刪除了共享文件後造成的指針懸空問題,解

決的方法是___.

七.(8分)在消息傳遞通信方式下,

A.發送進程和接收進程在通信過程中可以采用那三種同步方式?

B.試以下麵給出的發送進程和接收進程(將接收到的數據存入S)為例,說明當接收進

程執行到標號為 L2 的語句時 , 采用這）
..............................