1、中國科學技術大學一九九一年招收碩士學位研究生入學考試試題試題名稱:編譯原理和操作系統(tǒng)編譯原理部分(50 分)一. 填空(10 分)1. Chomsky定義的四種形式語言文法是(1)_文法又稱_文法)(2)_文法又稱_文法)(3)_文法又稱_文法)(4)_文法又稱_文法)2. 程 序 設 計 語 言 的 語 法 分 析 方 法 可 分 為 兩 大 類 ,_ 和_;其中,前者采用_分析方法;后者采用_或_分析方法;3. 邏輯表達式的計算有_和_兩種方式,選擇哪種計算方式取決于_.4. 在一遍掃描的編譯程序中,我們必須采取_手段來解決轉(zhuǎn)移目標不明確的困難.5. Lex是用于_的工具;Yacc是用于_

2、的工具.6. 根據(jù)連接在文法符號上的屬性間的依賴關系 ,屬性被分為_ ,_互不相交的二大類.7. 參數(shù)傳遞方式有_ , _ , _等幾種.二. 簡答題(4 分)1. 整數(shù)和實數(shù)的算術運算是可兼容的,為什么編譯器要區(qū)分它們?2. 什么是代碼優(yōu)化?舉出至少三種用于代碼優(yōu)化的手段.三. 下列文法是否屬于 LR(1),若是,則給出分析表;若不是指出原因(分析過程中可能遇到的麻煩),并考慮能否使其成為 LR(1)文法如何做? (10 )S ASES | AS | fE Ea | EbA c | d四. 說明 Pascal 語言和 C 語言的變量定義對編譯程序?qū)崿F(xiàn)的影響.(8 分)例: Pascal的變量

3、說明: a, b, c : integer ;C 的變量說明: int a, b, c;五. Pascal 程序設計語言不允許越過父過程或函數(shù)調(diào)用其中的子過程或函數(shù)例如:procedure Aprocedure Bprocedure Cprocedure D在過程D 中不允許調(diào)用過程 B,試解釋其原因(8 分).六. 給出將二進制數(shù)直接翻譯成十六進制數(shù)的翻譯方案 .假定屬性 hex 用于存放十六進制位串,串并置采用算符.二進制數(shù)文法如下:S BS | BB 0 | 1操作系統(tǒng)部分(50 分)一.填空(每空1 分共15 分)1. 操作系統(tǒng)的基本特征是_和_.2. _是用戶和外設、外存之間的接口.

4、3. 產(chǎn)生死鎖的原因是_和_.4. 有 一 個 530 字 的 程 序 . 考 慮 如 下 訪 問 內(nèi) 存 的 邏 輯 地 址 序列 :10,11,104,107,73,526,185,245,246,309,458,364,442,247,248,434.假 定 頁 面 大 小 為 100 字 , 則 其 對 應 的 頁 面 走 向 序 列為:_.如每個進程最多可分給 300 字內(nèi)存空間,且采用 LRU 算法,則其缺頁次數(shù)為_次,其缺頁率為_.5. 段表中設“改變位”的目的是_.6. 為了_而引入多道程序設計.7. 邏輯設備是_.8. JCB 的作用是_和_,它由_建立.9. 臨界資源是_.

5、二.選擇(四擇一每題1 分共5 分)1. 軟件共享的必要性是為了( ).A. 節(jié)約內(nèi)存空間B. 縮短運行時間C. 減少內(nèi)外存對換信息量 C. A和 C2. 請求頁面存儲管理采用( ).A.動態(tài)定位,靜態(tài)分配,靜態(tài)鏈接B.動態(tài)定位,動態(tài)分配,動態(tài)鏈接C.動態(tài)定位,動態(tài)分配,靜態(tài)鏈接D.靜態(tài)定位,靜態(tài)分配,靜態(tài)鏈接3. 用戶的虛擬 CPU功能( ).A.和物理 CPU完全一樣B.可以執(zhí)行所有機器指令以及軟件“指令”C.不能執(zhí)行特權(quán)指令D.可以執(zhí)行除特權(quán)以外的機器指令以及軟件“指令”4. 虛擬存儲管理中,段(或頁)表需要( ),而快表中可以沒有它.A.中斷位C.改變位B.引用位D.B和 C5. OP

6、EN操作的目的是為了( ).A.將制定的文件記錄復制到內(nèi)存中B.將制定的 文 件 復制到內(nèi)存中C.將制定的文件說明復制到內(nèi)存中D.將制定的共享文件復制到內(nèi)存中三.判斷并改正(前4 題各1 分第5 題 6 分共10 分)1. ( ) 虛擬存儲器空間的大小由外存容量決定.2. ( ) 在生產(chǎn)速度和消費速度完全相同時 ,只要用單緩沖就可以完全并行工作.3. ( ) 進程間的同步與互斥工具也是一種通訊工具.4. ( ) 虛擬設備和物理設備一一對應.5. 設有n個環(huán)形緩沖區(qū),n和一個無窮序列 ,a , 甲進程序1列順序逐個的把信息寫入環(huán)形緩沖區(qū)中 ,而乙進程則逐個的把緩沖區(qū)信n息讀出.(1) 請敘述甲、乙二進程的相互制約關系(2) 下列用 P、V 操作表示的同步算法有何錯誤.初值 S := 0 ;S := n;21甲進程乙進程V(S )P(S )11讀出寫入P(S )V(S )22(3) 用 P、V 操作寫出正確的同步算法.四. (10 分)1. 敘述請求頁面存儲管理所需要的數(shù)據(jù)結(jié)構(gòu)、軟件支持和硬件支持.2. 敘述(或加說明畫出)執(zhí)行一條訪內(nèi)指令的過程.五. (10 分)設有四個進程P 、P 、P 、P ,有二組緩沖區(qū):1: 由 7 個緩沖區(qū)組成;234: 由 100 個緩沖區(qū)組成.、P 的功能: 不斷的往Q 中送初始信息;21P 的功能: 不斷的取Q