中科院计算机所试题.pdf

该【中科院计算机所试题 】是由【小屁孩】上传分享，文档一共【20】页，该文档可以免费在线阅读，需要了解更多关于【中科院计算机所试题 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:..中科院计算机所试题中科院计算所2003年考研试题第一部分编译(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*func(){return(a);}编译报告:第6行warning:patiblepointertype(2)typedefintA[10][20]Aa;A*func(){return(}无类型方面错误(3)typedefintA[10][20]typedefintB[20]Aa;B*func(){return(a);}无类型方面错误(4)typedefintA[10][20]Aa;func(){Printf(“%d,%d,%d/n,a,a+1,}main(){1/20:..func();}结果:134518112,134518192,134518912第二部分操作系统(40’)、操作系统内核有强内核和微内核,unix是前者,windowsNT是后者,简介微内核比强内核的优点。(4?)(强内核:弱内核:各自优缺点:)2、若只有进程控制,其独立性表现在?引入线程后,独立性有何改变?(4?)3、请求调页存储系统确定页面大小的标准(4?)六、,在m个同类资源,n个进程共享它,每次进程只能获得或释放至多一个资源,问会不会发生死锁,若:(1)、设每个进程所需资源数为ri1rlink=restore(5)+k,rpos+1,n-1-k);Returnptr;}postorder(TNODE*ptr){if(ptr=NULL)return;postorder(ptr->llink);postorder(ptr->rlink);printf(“%c”,ptr->info);}四.(10分)已知有如下定义的静态链表:ponent=RecordData:elemtp;Next:0..maxsizeEndVARSTALIST:array[0..maxsize]ponent;以及三个指针:aV指向头结点,p指向当前结点,pre指向的前驱结点,现要求静态链表中next域中的内容,使得该静态链表有双向链表功能,从当前结点P既能往后查找,也能往前查找(1)定义next中的内容。(用老的next中的值表示):(2)如何得到当前结点p的前驱(pre)的前驱,给出计算式;3)如何得到p的后继,给出计算式;五、(5分)试求有n个叶结点的非满的完全二叉树的高度;六、(15分)试以逆邻接表为存储结构,通过每次删除出度为要顶点及其入边来写一拓扑排序算法,要求输出的顶点序列是拓扑有序序列。七、(15分)设A[1¨100]是一个记录构成的数组,B[1..100]是一个整数组,其值介于1至100之间,现要求按B[1··100]的内容调整A中记录的次序,比如当B[1]=ll时,则要求将A[1]的内容调整到A[11]中去。规定可使用的附加空间为o(1).八、(15分)在用除余法作为散列函数、线性探测解决冲突的散列表中,写一删除关键字的算法,要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不致于断裂。2/20:..中科院计算机技术研究所1999年硕士生入学试题数据结构与程序设计一、选择题.(20分,每空2分)。(1).前序线索树(2).中序线索树(3).,其叶结点个数为n,则非叶结点的个数为___.(1)n-1(2)|_n/m_|-1(3)上取整(n-1)/(m-1)4)[上取整n/(m-1)]-1(5)[上取整(n+1)/(m+1)]-(哈夫曼树),最优查找树均为平均查找路径长度wihi最小的树,其中对最优二叉树,n表示___,对最优查找树,n表示____;构造这两种树均为——。(1)结点数(2)叶结点数(3)非叶结点数(4)度为2的结点数(5)需要一张N个关键字的有序表(6)需要对N个关键字进行动态插入(7)需要N个关键字的查找概率表(8)不需要任何前提。;(2)只有根结点的二叉树(3)根结点无左孩子的二叉树(4)根结点无右孩子的二叉树(5)所有结点只有左子数的二叉树(6)+树是一棵_____,其结点中关键字最多为___个,(2)M路平衡索引树(3)M路TRIE树(4)M路键树(5)M-1(6)M(7)M+1(8)上取整(M/2)-1(9)上取整(M/2)(10)上取整(M/2)+1二、填空题(10分,每空1分),..-树的查找路径长度不会大于________.,,(设根的层数为一)的完全二叉树至少有______个结点,至多有_____个结点,、问答题(10分,每题5分),,其他顶点入度为一的有向图却不一定是一棵有向树。请举例说明之。,那么如果增加一个元素为K(n+1),请用文字简要说明你如何在log2(n)的时间内将其重新调整为一个堆?阅读下述程序,指出程序输出。(10分)voidg(int**);main(){intline[100],i;int*p=line;for(i=0;iS(S),S->ε/*空产生式*/试写出一个语法制导定义,:..五.(10分)已知某语言L={a^(m)b^(n)|n>m>=0}.试写出产生该语言的两个文法G1和G2,其中G1是LR(1)文法,G2是非LR(1)(每空一分,共20分),____和____。,系统向用户提供的用于创建新进程的系统调用是____________;用于建立无名管道的系统调用是______________;,引起进程调度的原因有_________,____________,,首次适应算法倾向于优先利用内存中__部分的空闲分区,,__________,,对文件主删除了共享文件后造成的指针悬空问题,.(8分)在消息传递通信方式下,?(将接收到的数据存入S)为例,说明当接收进程执行到标号为L2的语句时,采用这三种同步方式,X的值可能各是多少?发送进程P:接收进程Q:M=10;L1:sendMtoQ;L1:receiveSfromP;L2:M=20;L2:X:=S+1;gotoL1;八.(8分)一系统具有150个存储单元,在T0时刻按下表所示分配给3个进程:进程MaximumdemandCurrentallocationP17025P26040P36045对下列请求应用银行家算法分析判定是否是安全的:,最大需求60个存储单元,,最大需求50个存储单元,,请说明原因。九、(14分),起始页号(块号),,:(1)5499;(2)2221;4/20:..虚页号状态位访问位修改位物理块号01104111172000---310024000---51010解释:访问位---当某页被访问时,.(1)后缀式:ABCD-*+ECD-N**/+(2)四元式三元式(1)(-,C,D,t1)(1)(-,C,D)(2)(*,B,t1,t2)(2)(*,B,(1))(3)(+,A,t2,t3)(3)(+,A,(2))(4)(-,C,D)(4)(-,C,D,t4)(5)(**,(4),N)(5)(**,t4,N,t5)(6)(/,E,t5,t6)(6)(/,E,(5))(7)(+,t3,t6,t7)(7)(+,(3),(6))四.(5分)为符号S引入综合属性h,语法制导定义如下:产生式语义规则S->S1(S2):=++1S->:=0S'->Sprint()/*输出其配对括号数*/五.(10分)G1:LR(1)文法G2:非LR(1),非二义性文法S->A,BS->aSb|BA->aAb|εB->Bb|bB->Bb|,,初始化处理机状态信息,初始化处理机控制信息;,提高程序执行的并发度;;正在执行的进程执行了sleep系统调用;正在执行的进程执行了exit系统调用;,,控制器控制表,通道控制表,,:算法设计题目要求写注解,,若只设头指针,则出队列和入队的时间复杂度分别是______和______;若只设尾指针,=((),()),则DEAD(L)是_______;TAIL(L)是__________;L长度是________;;至多有____个结点;H和结点总数N之间的关系是____,.,,若在某结点中插入一个新关键字而引起该结点分裂,则此结点中原有的关键字的个数是____,若是某结点中删除一个关键字而导致结点合并,:..,(20分,每题2分)(A)问题的规模(B)待处理数据的初态(C).(B)和(A),此说法__(A)正确(B).,若用线性探测法把这K个关键字存入散列表中,至少要进行多少次探测(A)K-1次(B).K次(C).K+1次(D).K(K+1)/(nLOG2N)的时间内完成对数的排序,且要求排序是稳定的,则可选则的排序方法是(A)快速排序(B)堆排序(C)归并排序(D)(B)索引文件(C),主对角线以下的元素均为另零,则该图的拓扑有序__(A)序列存在(B),其最少的比较次数是__(A)N(B)2N-1(C)2N(D)N-,哪一种满足性质:从任一结点出发到跟的路径上所经过的结点序列按其关键字有序______(A).二叉排序树(B)哈夫曼树(C)AVL树(D),每个组包含K个元素,且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的各元素和小于后一组内的所有元素,若采用基于比较的排序,其时间下界应为_(a)o(klog2k)(b)o(klog2n)(c)o(nlog2k)(d)o(log2n),最优二叉树一定是完全二叉树,该说法__(a)正确(b)^是T的叶子,Y^是X^^.KEY是T中大于X^.^.,前N个元素A[1..N]递减有序,后N个元素A[N+1…2N]递减有序,且2N是2的整数次幂,既K=LG(2N)/[1..8]=[90,85,10,30,65,80,100]满足上述要求,这里N=4,K=3,,并要求:(1)给出FOR循环中每次执行PERFECTSHUFFLE(A,N)和COMPAREEXCHANGE(A,N)的结果.(2)解释DEMO的时间复杂度.(3)(vara;arraytype;n:integer){I:=1;J:=1;WHILEIa[j+1]thena[j]a[j+1];//交换A[J]和A[J+1]J:=J+2}}PROCEDUREDEMO(VARA:ARRAYTYPE;N:INTEGER){//A的长度为2N,K=LG(2N)/LG2为整数FORJ:=1TOLG(2N)/LG2DO{Perfectshuffle(a,n);Compareexchange(a,n);}}6/20:..五.(1).设二叉排序中关键字由1至1000的整数构成,现要检索关键字为363的结点,下述关键字序列中哪些可能是二叉排序树上搜索到的序列,哪些不可能是二叉排序数上搜索到的序列?2,252,401,398,330,344,397,363924,220,911,244,898,258,362,363925,202,911,240,912,245,3632,399,387,219,266,382,381,278,363(2).通过对(1)的分析,写一个算法判定的关键字序列(假定关键字各不相同),,不同之处在于使用栈代替BFS中的队列,入、出队列的操作改为入、出栈的操作。即当一个顶点的所有邻结点被搜索之后,下一个搜索出发点应该是最近入栈(栈顶)的顶点。用邻接表做存贮结构,写一个D__搜索算法。用D__搜索方法的访问次序和相应的生成树,当从某顶点出发搜索它的邻接点,请按邻接点序号递增序搜索,以使答案唯一。中科院计算所1998年编译原理和操作系统一.(10分)某操作系统下合法的文件名为device:,其中第一部分(device:)和第三部分(.extension)可缺省,若device,name和extension都是字母串,长度不限,但至少为1,.(10分)下面的二义文法描述命题演算公式,->SandS|SorS|notS|p|q|(S)三.(10分)把表达式-(a+b)*(c+d)+(a+b+c).(10分)由于文法二义引起的LR(1)分析动作冲突,可以根据消除二义的规则而得到LR(1)分析表,(1)文法引起的LR(1)分析动作的冲突,是否也可以根据什么规则来消除LR(1)分析动作的冲突而得到LR(1)分析表,并且根据此表识别相应语言的句子?若可以,你是否可以给出这样的规则?五.(10分)(1)改成1的话,(){staticinti=5;if(i=0){return(1);}else{i=i-1;return((i+abs(1))*fact());}}main(){}(每小题2分,共10分)1)线程2)管程3)管道4)I/O重定向5)动态地址重定位线程:是进程内的调度,也称为轻权进程7/20:..(,共10分),使得操作系统更加安全可靠地工作,实际操作系统中区分程序执行的两种不同的运行状态是核心态,:______________,,一个程序的页面走向为1,2,1,4,3,2,3,5,1,2,1,,则采用FIFO,LRU和LFU页面置换算法时,访向过程中的缺页次数分别为___,,实现了_______与_______的并行;________与_________的并行;,还要为他分配设备控制器,(共10分);与一般中断相比,主要的区别是什么??与一般的地址索引结构相比有什么优点?付出的代价是什么?(共10分)遵循同步机制的四条准则,写出用锁机制实现的解决读者--:同步机制的四条准则是:有空则进,让权等待,有限等待,十.(10分)简述UNIX系统V中块设备数据缓冲池的管理技术,(共25分)1.(10分)为正规式(a|b)*a(a|b)构造一个确定的有限自动机。2.(15分)试画出如下中间代码序列的程序流图,并求出:①各结点的必经结点集合D(n);②流图中的回边与循环。J:=0;L1:I:=0;IfI0if(k>0){a(k)--;r(k)++;}}else{a[k+1]=(6);r[k+1]=r[k]-a[k+1];k++;}}while(k>0);}inttest_data[]={3,4,5};main(){inti;for(i=0;i8/20:..func(i,j,f,e)shorti,j;floatf1,e1;{shorti1,j1;floatf1,e1;i1=i;j1=j;f1=f;e1=e;printf(“Addressesofi,j,f,e=%d,%d,%d,%dn”,printf(“Addressesn”,printf(“Sizeofshort,int,long,float,doublen”,sizeof(short),sizeof(int),sizeof(long),sizeof(float),sizeof(double));}main(){shorti,j;floatf,e;i=j=1;f=e=;func(i,j,f,e);}运行结果:Addressesofi,j,f,e=-268438178,-268438174,-268438172,-268438164;Addressesofi1,j1,f1,e1=-268438250,-268438252,-268438256,-268438260;Sizeofshort,int,long,float,double=2,4,4,4,8七.(5分)在UNIX系统中,对换区的功能是什么?UNIX系统V是如何对对换区进行管理的?八.(5分)UNIX系统V为进程之间的通信提供了哪些工具?各用于什么场合?九.(5分)操作系统中的文件共享有几种形式?它们是如何实现的?各有什么特点?十.(5分)Dijkstra(1965)提出的银行家算法的主要思想是什么?它能够用来解决实际中的死锁问题吗?为什么?十一.(10分)有五个批处理的作业(A,B,C,D,E)几乎同时到达一个计算中心,估计的运行时间分别为2,4,6,8,10分钟,它们的优先数分别为1,2,3,4,5(1为最低优先级)。对下面的每种调度算法,分别计算作业的平均周转时间。①最高优先级优先;②时间片轮转(时间片为2分钟);③FIFO(作业到达的顺序为C,D,B,E,A);④短作业优先。:9/20:..S→aB→aaBB→aabB→aabbS→aabbaB→aabbab;S→aB→aaBB→aabSB→aabbAB→aabbaB→aabbab;SaBS|bAS|aB|bABaBB|bAbAA|:Sleep/Wakeup:核心态进程的同步;软中断信号机制(signal/kill):同一用户进程间的通讯(小数据量);基于文件系统的pipe机制:进程间大数据量的通讯;共享存储器、信号量集和消息传递机制。。共享时间短;采用目录表项之间的链接。即使一个用户目录中的表项直接指向另一个目录中的表项。长久共享。采用基本文件目录和符号文件目录的组织方式,便于用户文件的共享。,其每个非终端结点的平衡因子均为1,则该树共有__个终端结点.(2分),至少应有__个结点.(2分),最多有__个结点.(2分),决定出8位运动员之间的名次顺序排列,至少需编排__场次的比赛.(考虑最坏)(2分)(Tail([Head(S),Head(Tail(Tail(S))]))广义表满足上式,.[[a,b],b,a]b.[[b,a],[a],[b]]c.[[a],[a,b],[b]]d.[b,[a],[a,b]]e.[[a],[b],[b,a]]f.[[b],[b,a],[a]](其中,方括号表示广义表,圆括号表示函数,Head()表示取广义表的头部)(210/20:..分),___对查找指定结点在该次序下的后继效果较差.(2分).(2分),__算法最适合于求边稀疏的网的最小生成树(2分),在对无向图的边进行操作时(如删除一条边),,;;-(1).在文件局部有序或文件长度较小的情况下,最优内部排序的方法是_A__.(2).快速排序在最坏的情况下,时间复杂度是_B__,_C__的性能差;(3)就平均时间而言,.:(1)直接插入排序(2)起泡排序(3)简单选择排序;B.:(1)O(nlog(n))(2)O(n^2)(n^3)C.:(1)堆排序(2)起泡排序(3).:(1)堆排序(2)快速排序(3),判别是等腰三角形,等边三角形,,至少应对该程序的输入数据考虑_A_个等价类,(1)3;(2)5;(3)7;(4)12;(5)15;(6)18;(7)21;(8)25;(9)33;(10)40;:(共四分),,,,将出现多少个空指针域?(x,y:integer):integer;beginify=1thencalc:=xelsecalc:=calc(x,y-1)+xend;a,b均为正整数,则calc(a,b)=___.(1).a*(b-1)(2).a*b(3)a+b(4)a+(a,b);11/20:..c:=*a+b;ifc=0thena:=1elsea:=++;保证该程序段运行不出错的必要条件是:___(1).b>0;(2).a>0andb>0;(3).b!=0;(4).b!=0andc!=0;:,对错误编号说明理由:程序段1:(8分)Label1:constmax=50;typeday={Mon,Tue,Wed,Thu,Fri,Sat,Sun};vardate:day;N:integer;begina:N:=N-ord('0');b:fordate:=MontoSundoN:=ord((date))-1c:forn:=1to10dobegin......1:语句;end;......goto1;......:.(8分)Programtype(input,output);varR:real;Procedureprint(varx:integer,y:real);varz:real;Proceduresum(x:integer;y:real);vark:real;beginz:=x+y;k:=3*z;x:=x+y;end;{sum}beginsum(x,y);writeln(x,y,z,k);end;{print}begin12/20:..readln(R);print(15,R);print(R,R)end.{mainprogam},填空使之成为一个完整的程序:该程