中科院計(jì)算所歷年考研真題編譯原理操作系統(tǒng)數(shù)據(jù)結(jié)構(gòu)軟件基礎(chǔ)含答案

1、中科院計(jì)算所2003年考研試題第一部分編譯(40)一、(1/01) *0*說明是什么語(yǔ)言畫出DFA (10)二、Sf過程調(diào)用語(yǔ)句/數(shù)組的賦彳1語(yǔ)句(10)過程調(diào)用語(yǔ)句為：id(id,id, ,id)賦值語(yǔ)句：id(id, ,id):=id(id, ,id)(a)寫一個(gè)LR (1)方法(產(chǎn)生式不大于6個(gè))(b)若在LR分析同時(shí)完成語(yǔ)義分析，中間代碼生成，基于你的文法有什么困難？三、E*E/+E/ -E/unsigned-integer為上面表達(dá)式產(chǎn)生棧機(jī)器代碼，代碼執(zhí)行后，表達(dá)式值留在棧上，自己設(shè)計(jì)所需棧機(jī)器指令，并寫清指令含義。(10)四、C語(yǔ)言中，a表示數(shù)組首址，而&a也表示數(shù)組首址，然而使

2、用時(shí)有時(shí)并不相同，請(qǐng)根據(jù)下面寫出a與&a類型表達(dá)式(10)(1) tgpedef int A1020A a;A * func ()return(a);在 linux 上用 gcc 編譯報(bào)告：第 6 行 warning: return from incompatible pointer type(2) typedef int A1020A a;A *func() return(&a);無(wú)類型方面錯(cuò)誤(3) typedef int A1020 typedef int B20 A a;B *func() return(a);無(wú)類型方面錯(cuò)誤(4) typedef int A1020A a; func(

3、) Printf( d,%d,%d/n,a,a+1,&a+1);main()func();結(jié)果：134518112, 134518192, 134518912中科院計(jì)算機(jī)技術(shù)研究所1999年碩士生入學(xué)試題中科院計(jì)算所1999年編譯原理與操作系統(tǒng)一.(15分)有表達(dá)式如下：A+B*(C-D)*N (*為哥乘)(1)給出該表達(dá)式的逆波蘭式表示(后綴式)；(2)給出上述表達(dá)式的四元式和三元式序列.三.(5分)構(gòu)造一個(gè)DFA(確定的有限自動(dòng)機(jī)，使之接受含偶數(shù)個(gè)1的0,1串集.四.(5分)有文法G,其產(chǎn)生式如下：S-S(S),S- S /空產(chǎn)生式*/試寫出一個(gè)語(yǔ)法制導(dǎo)定義，它輸出配對(duì)的括號(hào)個(gè)數(shù).五.(1

4、0分)已知某語(yǔ)言 L=aA(m)bA(n)|nm=0.試寫出產(chǎn)生該語(yǔ)言的兩個(gè)文法G1和G2,其中G1是LR(1)文法,G2是非LR(1)和非二義性文法.六.填空(每空一分，共20分)中科院計(jì)算所1999年編譯原理與操作系統(tǒng)參考答案(2)四元式 (1)(-,C,D,t1) (2)(*,B,t1,t2) (+,A,t2,t3) (4)(-,C,D) (*,(4),N) (6)(/,E,t5,t6) (7)(+,t3,t6,t7)四.(5分)為符號(hào)一.(1)后綴式：ABCD-*+ECD-N*/+二兀式(1)(-，C,D)(2)(*,B,(1)(3)(+,A,(2)(4)(-,C,D,t4)(5)(*

5、,t4,N,t5)(6)(/,E,(5)(+,(3),(6)S-S1(S2)S.h:=S1.h+S2.h+1S- S引入綜合屬性h,語(yǔ)法制導(dǎo)定義如下：產(chǎn)生式語(yǔ)義規(guī)則S.h:=0S-Sprint(S.h)/* 輸出其配對(duì)括號(hào)數(shù) */五.(10 分)G1:LR(1)文法 G2:非 LR(1),非二義性文法 S-A,BS-aSb|BA-aAb| B-Bb|bB-Bb|b六.填空1.并發(fā)，共享2.初始化標(biāo)識(shí)符信息，初始化處理機(jī)狀態(tài)信息，初始化處理機(jī)控制信息；3.為了減少程序并發(fā) 執(zhí)行時(shí)所需付出的時(shí)空開銷，提高程序執(zhí)行的并發(fā)度;4.forkpipemknod5.正在執(zhí)行的進(jìn)程時(shí)間片完；正在執(zhí)行的 進(jìn)程執(zhí)

6、行了 sleep系統(tǒng)調(diào)用；正在執(zhí)行的進(jìn)程執(zhí)行了 exit系統(tǒng)調(diào)用；正在執(zhí)行的進(jìn)程在用戶態(tài)運(yùn)行時(shí)有優(yōu)先級(jí)更高的進(jìn)程進(jìn)入就緒隊(duì)列 6.中低地址，高地址7.設(shè)備控制表，控制器控制表，通道控制表，系統(tǒng)設(shè)備表8.只讓文件主 擁有指向該文件索引結(jié)點(diǎn)的指針，而共享該文件的其他用戶只有該文件的路徑明而不是指向索引結(jié)點(diǎn)的指針.中科院98考研題中科院計(jì)算所1998年編譯原理和操作系統(tǒng)1 .(10分)某操作系統(tǒng)下合法的文件名為device:name.extension，其中第一部分(device:)和第三部分(.extension)可缺省，若device,name和extension都是字母串，長(zhǎng)度不限，但至少為1

7、,畫出實(shí)現(xiàn)這種文件名的確定有限自動(dòng)機(jī).2 .(10分)下面的二義文法描述命題演算公式，為他寫一個(gè)等價(jià)的非二義文法 .S-S and S|S or S|not S|p|q|(S)3 .(10分)把表達(dá)式-(a+b)*(c+d)+(a+b+c) 翻譯成四元式.4 .(10分)由于文法二義引起的 LR(1)分析動(dòng)作沖突，可以根據(jù)消除二義的規(guī)則而得到LR(1)分析表，根據(jù)此表可以正確識(shí)別輸入串是否為響應(yīng)語(yǔ)言的句子.對(duì)于非二義非LR(1)文法引起的LR(1)分析動(dòng)作的沖突，是否也可以根據(jù)什么規(guī)則來(lái)消除LR(1)分析動(dòng)作的沖突而得到LR(1)分析表，并且根據(jù)此表識(shí)別相應(yīng)語(yǔ)言的句子？若可以，你是否可以給出這

8、樣的規(guī)則 ？5 .(10分)下面程序的結(jié)果是120.但是如果把第5行的abs(1)改成1的話,則程序結(jié)果為1.試分析為什么會(huì)有這不同的結(jié)果.int fact() static int i=5;if(i=0) return(1); else i=i-1; return( i+abs(1)*fact(); main()printf(factor or 5=%dn,fact(); 中國(guó)科學(xué)院計(jì)算所1997年編譯原理試題(共 25分)1. (10分)為正規(guī)式(a|b) *a(a|b)構(gòu)造一個(gè)確定的有限自動(dòng)機(jī)。2. (15分)試畫出如下中間代碼序列的程序流圖，并求出： 各結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)集合D (n);

9、流圖中的回邊與循環(huán)。J: =0 ;L1 : I: =0;If I 8 goto L3;L2 : A:=B+CB:=D*C;L3 : if B = o goto L4;Write B;goto L5;L4 : I:= I+1;If I8 goto L2L5 : J:= J+1If J=3 goto L1;HALT中科院計(jì)算所1996年程序設(shè)計(jì)一、單項(xiàng)選擇：(20分)二、問答題(25分)中國(guó)科學(xué)院計(jì)算所一九九六年軟件基礎(chǔ)一.(10分)已知序列17, 31, 13 , 11 , 20, 35, 25 , 8, 4, 11, 24, 40, 27。請(qǐng)畫出該序列的二叉排序樹， 并分別給出下列操作后的二叉

10、樹； 插入數(shù)據(jù)9;刪除結(jié)點(diǎn)17;再刪除結(jié)點(diǎn)13。二.(15分)請(qǐng)編寫一個(gè)程序，生成如下序列的前n項(xiàng)。1， 2, 1 , 2, 3, 2, 1, 2, 3, 4, 3, 2, 1, 2, 3, 4, 5, 4, 3, 2, 1,2,三.(15分)已知平面上(直角坐標(biāo)系)的 n個(gè)點(diǎn)，請(qǐng)編一個(gè)函數(shù)，求同一條直線所能通過的最多點(diǎn)數(shù)。 四.(10分)下面的文法產(chǎn)生 a的個(gè)數(shù)和b的個(gè)數(shù)相同的非空 a, b串。S aB | bAB bS | aBB | bA aS | bAA | a其中非終結(jié)符B推出b比a的個(gè)數(shù)多1個(gè)的串，A則反之。說明該文法是二義的。 對(duì)上述文法略作修改，使之非二義，并產(chǎn)生同樣的語(yǔ)言。略

11、作修改的含義是：不增加非終結(jié)符。 五.(10分)某些語(yǔ)言允許給出名字表的一個(gè)屬性表，也允許聲明嵌在另一個(gè)聲明里面，下面文法抽象這個(gè) 問題。Da attrlist namelist | attrlist ( D)namelist id , namelist | idattrlist a A , attrlist | AA d decimal | fixed | float | realD attrlist (D)的含義是：在括號(hào)中的聲明提到的所有名字有attrlist中給出的屬性，而不管聲明嵌套多少層。寫一個(gè)翻譯方案，它將每個(gè)名字的屬性個(gè)數(shù)填入符號(hào)表。六.(10分)下面是一個(gè) C語(yǔ)言程序及其運(yùn)行

12、結(jié)果。從運(yùn)行結(jié)果看函數(shù)func中四個(gè)局部變量i1 , j1 , f1 , e1的地址間隔和它們類型的大小不一致，試分析不一致的原因。#include func(i , j , f , e )short i , j ; float f1 , e1;short i1, j1; float f1, e1;i1 = i; j1 = j; f1 = f; e1 = e;printf( Addresses of i, j, f, e = %d, %d, %d, %dn ”, &i, &j, &f, &e);printf( Addresses of i1, j1, f1, e1 = %d, %d, %d,

13、%dn ”, &i1, &j1, &f1, &e1);printf( Size of short, int, long, float, double = %d, %d, %d, %d, %dn ”, sizeof(short), sizeof(int), sizeof(long), sizeof(float), sizeof(double); main() short i, j; float f, e;i = j = 1; f = e = 1.0;func(i , j , f , e);運(yùn)行結(jié)果：Addresses of i, j, f, e = -268438178, -268438174,

14、 -268438172, -268438164;Addresses of i1, j1, f1, e1 = -268438250, -268438252, -268438256, -268438260;Size of short , int , long , float , double = 2, 4, 4, 4, 8中國(guó)科學(xué)院計(jì)算所一九九六年軟件基礎(chǔ)答案SaBaaBBaabBaabbS aabbaB aabbab;SaBaaBBaabSBaabbAB aabbaB aabbab;S aBS | bAS | aB | bAB aBB | bA bAA | a8 . UNIX系統(tǒng)V提供的工具有：

15、Sleep/Wakeup：核心態(tài)進(jìn)程的同步；軟中斷信號(hào)機(jī)制（signal/kill ）:同一用戶進(jìn)程間的通訊（小數(shù)據(jù)量）基于文件系統(tǒng)的pipe機(jī)制：進(jìn)程間大數(shù)據(jù)量的通訊; 共享存儲(chǔ)器、信號(hào)量集和消息傳遞機(jī)制。9 .采用全路徑名訪問他人文件。共享時(shí)間短；采用目錄表項(xiàng)之間的鏈接。即使一個(gè)用戶目錄中的表項(xiàng)直接指向另一個(gè)目錄中的表項(xiàng)。長(zhǎng)久共享。 采用基本文件目錄和符號(hào)文件目錄的組織方式，便于用戶文件的共享。中科院計(jì)算所1994年軟件基礎(chǔ)語(yǔ)言與編譯部分 （35分）一.（7分）把下面不確定的有限自動(dòng)機(jī)化為確定的有限自動(dòng)機(jī)。二.（8分）有文法：S （ L） | aL L , S | S如對(duì)于句LR（1）且非

16、給此文法配上語(yǔ)義動(dòng)作子程序（或者說為此文法寫一個(gè)語(yǔ)法制導(dǎo)定義），它輸出配對(duì)的括號(hào)的個(gè)數(shù)，子（a,（a,a）輸出是2。3 .（15分）為語(yǔ)言a m b n |n m 0 寫三個(gè)文法，它們分別是二義文法，LR（1）文法和非二義的文法。不必證明所寫文法的正確性，但每個(gè)文法的產(chǎn)生式不能超過4個(gè)。4 .（5分）右邊是一個(gè) FORTRAN 7猥序。CALL SUB按語(yǔ)言的語(yǔ)義，程序的輸出結(jié)果是什么？CALL SUB在靜態(tài)存儲(chǔ)分配情況下，實(shí)際的輸出結(jié)END果是什么？?jī)烧呤欠裼袇^(qū)別？說明理由。SUBROUTINE SUBDATA I/10/WRITE(*, *) II=100END中國(guó)科學(xué)院軟件所一九九四年軟

17、件基礎(chǔ)答案語(yǔ)言與編譯部分：.拓廣文法，加入新開始符號(hào)S和產(chǎn)生式SS*S print(S.num)S(L)Srflum:=L.num+1SaSrnum:=0LL1,S-Lnum:=L1.num+S.numLSLflum:=S.num,必須有S 一至b型的產(chǎn)生式，以保證 b的個(gè)數(shù)不少于 a的個(gè)數(shù)。還要有 S 9b 或S bS 型的產(chǎn)生式，以保證b的個(gè)數(shù)多余 二義文法：a的個(gè)數(shù)。句子前綴中的a和后綴中的b的配對(duì)方式不同導(dǎo)致不同性質(zhì)的文法。S aSb|Sb|b LR (1)文法:S非LR (1)且非二義文法：S aSb|SSSb|bb前 看S SibS b，aS，b| 符號(hào)，不知后面還有多少個(gè) bo因

18、此不能確定是做 S到S的歸約呢，還是移進(jìn) b再做S b到S的歸約。四.按FORTRAN7的語(yǔ)義，子程序 SUB的第一次執(zhí)行輸出10,第二次輸出的值不確定。FORTRA傳言的實(shí)現(xiàn)一般都采用靜態(tài)存儲(chǔ)分配，變量和存儲(chǔ)單元的結(jié)合(binding )是靜態(tài)決定的，在程序運(yùn)行期間不會(huì)改變，因此SUB的兩次執(zhí)行的輸出分別是 10, 100。中國(guó)科學(xué)院計(jì)算所一九九三年軟件基礎(chǔ)1 .填空(1分X 20)1 .編譯過程中，比較常見的中間語(yǔ)言有2 .簡(jiǎn)答(5分X 6)|a|2.給出下列自動(dòng)機(jī)所描述的語(yǔ)言：構(gòu)造一文法產(chǎn)生任意長(zhǎng)的a, b串，使得|a|三|b|三2|a|。其中:表示a字符的個(gè)數(shù)；“|b|表示b字符的個(gè)數(shù)

19、。六.（10分）請(qǐng)按語(yǔ)法制導(dǎo)的定義，將后綴表達(dá)式翻譯成中綴表達(dá)式。注意，不允許出現(xiàn)冗余括號(hào)，后綴表 達(dá)式的文法如下：E EE+E EE*E id中國(guó)科學(xué)院計(jì)算所一九九三年軟件基礎(chǔ)答案一.填空1 .逆波蘭表示、二元式、三元式、四元式。二.簡(jiǎn)答2 . 10 1 0B bb|b六. SEE E1E2+E E1E2*S aSBS | BsaS | print （E.code） E.code:= E1.code II +II E2.code; E.op= + if E1.op= + aE2iop= +then E.code:= II Encode II *（E2.codell ）;else if E1.op= +then E.code:= II Encode II ）*E2.code;else if E2.op= +then E.code:= E1.code II *（E2.codell ）;else E.code:= E1.code II *E2.code;E.op:= * ; E.code:=id.lexeme;E.code:= $）;中國(guó)科學(xué)院計(jì)算所一九九二年軟件基礎(chǔ)一.填空（每空 1分）4.根據(jù)聯(lián)接在文法符號(hào)上的屬性之間的依賴關(guān)系，可把屬性分為 和 兩大類。二.簡(jiǎn)答8. （5分）有一