中科院计算机技术研究所1998年硕士生入学考试试题

1998年招收攻读硕士学位研究生入学统一考试试题科目名称：植物学（一）名词解释无限维管束同源器官颈卵器心皮聚合果无融合生殖核型胚乳花程式孢蒴内始式：（二）、蕨类植物比苔藓植物在那些方面更能适应陆生环境。

（三）、试比较裸子植物与被子植物的主要异同点。

（四）、何谓木材的三切面？它们的概念怎样？以双子叶禾本植物为例，写出三切面的特征。

（五）、以水稻为例，叙述禾本科植物花序及花的详细组成。

（六）、试述被子植物由小孢子母细胞发育为花粉粒的全过程。

（七）、写出图中数字所指花序类型和胎座类型的名称。

……（图略）1999年招收攻读硕士学位研究生入学统一考试试题科目名称：植物学一、名词解释有丝分裂次生结构形成层侵填体花程式和花图解真核生物颈卵器世代交替孢子和种子 C3和C4植物二、试举例说明高等植物根的变态及其主要功能。

三、何谓光合作用，简述提高光合作用的几种途径。

四、试比较单子叶植物与双子叶植物茎的特点。

五、试比较裸子植物与被子植物的生活史2000年招收攻读硕士学位研究生入学统一考试试题科目名称：植物学一、名词解释管胞；凯氏带；居间生长；合轴分枝；孢子、合子与种子；平行进化；景天酸代谢；双名法；石松类植物；单性结实二、简述植物细胞中各类细胞器的形态特征与主要特征与主要功能。

三、何谓次生生长？分别以根和茎为例简要说明之。

四、试说明苔藓植物的主要进化特征。

五、白果（银杏）和苹果两种“果”的用法各指什么，试分辨之。

六、请写出下列植物拉丁文的中文属名及所在的科betula eucalyptus ficus ginkgo mangnolia populus quercus rhododendron salix ulmus2001年招收攻读硕士学位研究生入学统一考试试题科目名称：植物学一名词解释细胞器减数分裂心皮管胞有限花序子实体世代交替地衣楔叶植物通道细胞二、植物有那些主要的组织，简要说明它们的功能。

三、简述茎尖的结构及其进一把发育形成的结构或组织。

中科院计算机技术研究所1994年硕士生入学试题程序设计一、下面关于程序设计风格的叙述，那些是正确的？那些是错误的？（10分）1、编写程序是，应使用括号以改善表达式的清晰度。

2、应当尽可能对程序代码进行优化。

3、在程序设计中，不要进行浮点数相等的比较。

4、应尽可能多的输出中间结果。

5、不要使用数据类型来对数据值进行防范。

6、要用计数方法而不是用文件结束符来控制输入的结束。

7、使用有意义的标识符。

8、结构化程序设计语言中没有GOTO语句。

9、一般而言，语言的级别越高，用它编出的程序越短。

10、PASCAL是一种自由格式的弱类型语言。

二、填空：（10分）1、FORTRAN程序中，变量的作用域以______为单位，PASCAL程序的作用域遵守_____规则。

2、赋值语句A：=A+1左边的A代表_________ 含义，右边的A代表_________含义。

3、高级程序设计语言的语句分为_________ 和____________ 二种。

4、在查找算法中，顺序查找的平均查找长度ASL为________；折半查找的ASL为___________；而二叉排存树查找记录时，最坏下的情况ASL为__________；在二叉平衡排存树上插入一个结点后,最坏情况需要_______次旋转才能保持平衡。

三、选择填空：（10分）1、存贮稀疏图的数据结构常有的是。

[1]邻接矩阵[2]三元组[3]邻接表[4]十字链表2、内部排序多个关键字的文件，最坏情况下最快的排列方法是_____,相应的时间复杂度为______,该算法是的稳定性__________.[1]快速排序[2]插入排序[3]归并排序[4]简单选择排序[5]O(nlog2(n)) [6]O(n^2) [7]O(n^2log2(n)) [8]O(n) [9]稳定[10]不稳定3、倒排文件包含若干个倒排表，倒排表的内容是_____________.[1]一个关键字值和关键字的记录地址；[2]一个属性值和该属性的一个记录地址；[3]一个属性值和该属性的全部属性地址；[4]多个关键字值和它们对应的某个记录的地址。

中科院计算技术研究所考研科目
中科院计算技术研究所(InstituteofComputingTechnology,ChineseAcademyofSciences，简称ICT) 是国内一所重要的计算机科学研究机构，其研究领域涵盖了计算机体系结构、操作系统、编译优化、并行与分布式系统、软件工程、网络与信息安全等多个方向。

如果你希望考取ICT的研究生，以下是ICT考研科目的相关信息：
1. 计算机组成原理
计算机组成原理是ICT考研中重要的一科，主要考察考生对计算机硬件基本原理的掌握，包括计算机的基本组成和工作原理、数字逻辑、存储器、指令系统和CPU等。

2. 数据结构与算法分析
数据结构与算法分析是ICT考研中的另一门重要科目，主要考察考生的算法设计和实现能力，包括各种数据结构的表示和操作、算法分析和评估。

3. 操作系统
操作系统是ICT考研中的一门重要科目，主要考察考生对操作系统的理解和应用能力，包括操作系统的基本概念、进程管理、内存管理、文件系统和输入/输出等。

4. 计算机网络
计算机网络是ICT考研中的一门重要科目，主要考察考生对网络体系结构、传输协议、网络管理和安全等方面的掌握，包括
TCP/IP协议、路由选择、网络安全等。

5. 面向对象程序设计
面向对象程序设计是ICT考研中的一门重要科目，主要考察考生对面向对象编程的理解和应用能力，包括类、对象、继承、多态、封装等概念和应用。

以上是ICT考研的主要科目，考生可以根据自己的兴趣和强项进行选择，同时还需熟练掌握英语，因为考试中的部分试题可能是英文的。

希望考生可以在备考过程中认真复习，取得好成绩！。

计算机专业基础综合计算机组成原理（计算机系统概述）历年真题试卷汇编1(总分：70.00，做题时间：90分钟)一、单项选择题(总题数：29，分数：58.00)1.电了计算机问世至今，新型机器不断推陈出新，但不管怎么更新，依然具有“存储程序”的特点，最早提出这种概念的是____。

【上海交通大学1999年】（分数：2.00）A.巴贝奇B.冯.诺依曼√C.帕斯卡D.贝尔解析：解析：考查计算机发展历程。

2.对有关数据加以分类、统计、分析，这属于计算机在——方面的应用。

（分数：2.00）A.数值计算B.辅助设计C.数据处理√D.实时控制解析：解析：考查计算机的发展及应用。

3.冯.诺依曼型计算机的最根本特征是____。

【中科院计算所2001年】（分数：2.00）A.以运算器为中心B.采用存储程序原理√C.存储器按地址访问D.数据以二进制编码，并采用二进制运算解析：解析：考查冯.诺依曼型计算机基本概念。

冯.诺依曼型计算机的最根本特征是采用存储程序原理，基本工作方式是控制流驱动方式，工作方式的基本特点是按地址访问并顺序执行指令。

4.冯.诺依曼型计算机的基本工作方式是____。

【中科院计算所1998年】（分数：2.00）A.控制流驱动方式√B.多指令流多数据流方式C.微程序控制方式D.数据流驱动方式解析：解析：考查冯.诺依曼型计算机基本概念。

解析同上。

5.计算机系统采用层次化结构组成系统，从最上层的最终用户到最底层的计算机硬件，其层次化构成为____。

（分数：2.00）A.高级语言机器一操作系统机器一汇编语言机器一机器语言机器一微指令系统B.高级语言机器一汇编语言机器一机器语言机器一操作系统机器一微指令系统C.高级语言机器一汇编语言机器一操作系统机器一机器语言机器一微指令系统√D.高级语言机器一汇编语言机器一操作系统机器一微指令系统一机器语言机器解析：解析：考查计算机系统层次化结构。

6.计算机系统是由____组成的。

中科院计算机技术研究所1998年硕士生入学试题离散数学1.（10分）证明：若（A-B）U（B-A）=C，则A包含于（B-C）U（C-B）的充要条件是A交B交C=空。

2.（12分）找出只有6个元素的所有不同构的群。

3.（14分）R1和R2为X上的两个关系，且R1*R2=Ix（恒同关系）（1）若X为有限集合，证明：存在X上双射F1和F2，使得F1*F2=Ix且aR1b〈==〉b=F1（a），cR2d〈==〉d=F2（c）。

（2）若X为无限集合，举例说明（1）的结论不成立。

4.（10分）令A分别为下列各式：（1）（（p－＞q）＜－＞（v否p并q））并（p交r交否p）（2）（p并q －＞q并r) ->(q->r)（3）p<->p交(q并否q并r)（4）(p->否q)交(r并q)（5）否p<->(p交(p并q))从下列备选答案中选择正确的答案:(1)A是重言式(2)否A是重言式(3)A和否A都不是重言式.5.(8分)求公式否((p->否q)->r)的主析取范式和主合取范式.6(12分)将命题"并非E1中的每个数都小于或等于E2中的每个数"按以下要求的形式表达出来:(1)出现全称量词,不出现存在量词;(2)出现存在量词,不出现全称量词.7.(14分)(1)写出下图的关联矩阵和邻接矩阵;(2)说明如何从关联矩阵中判断一结点为割点,一边为割边.8.(10分)若图G的着色数(或称做顶色数)x(G)=k,则G 中至少有k(k-1)/2 条边.9.(10分)证明:一连通图的任两条最长通路(也称轨)有公共交点.答案略.。

中国科学院计算技术研究所一九九八年招收硕士学位研究生入学考试试题试题名称：计算机原理及系统结构一、填空（每空1分，共30分）1、三种基本的逻辑运算是与、或和非运算，但从逻辑运算功能完备性看，仅需要单一的一种逻辑门电路就可以实现了，这种门电路是与非或或非。

2、动态MOS存储器的刷新方式通常可分为集中式和分布式两类。

3、主频为 16MHz的微处理器，平均每条指令的执行时间为两个机器周期，每个机器周期由两个时钟脉冲组成，则存储器为“零等待”时，机器运行速度为4 MIPS；若两个机器周期有一个访问存储器周期，需要插入两个时钟的等待时间，则机器运行速度为 2.67 MIPS。

4、Intel 80386处理器中主要功能部件包括、、等；该处理器的指令预取队列长度为字节。

5、计算机在存取和传送数据的过程中，常用的数据校验方法有奇偶校验、海明码校验和CRC码校验等。

6、有一字长为24位的浮点数，阶码6位用移码表示，尾数18位用补码表示，基数为2，则非规格化数所能表示的数的范围为- 263 ~ (1-2 -7)*2 63，规格化正数所能表示的数的范围为- 263 ~ (1-2 -7 )*2 63。

7、设基址寄存器的内容为2000H，变址寄存器的内容为03A0H，指令的地址码部分为3FH，当前正在执行的指令所在地址为2B00H，则在考虑基址的前提下，变址寻址方式下访存的有效地址为23DFH，相对寻址方式访存的有效地址为2B3FH。

8、从数据流和指令流的角度来分类，计算机可分为单指令流单数据流方式SISD、单指令流多数据流方式SIMD、多指令流单数据流方式MISD和多指令流单数据流方式MIMD四种类型。

9、在多级存储体系中，虚拟存储器的主要功能是解决容量与成本之间的矛盾（使计算机具有辅存的容量，接近于主存的速度和辅存的成本），Cache 的主要功能是解决速度与成本之间的矛盾（匹配主存与CPU之间的速度）。

10、输入输出系统的数据传送控制方式包括程序直接控制方式、程序中断控制方式、DMA控制方式和I/O通道控制方式等。

中国科学技术大学1998年研究生入学考试操作系统试题（共50分）1填空（每空1分，共20分）①用户与操作系统之间的接口主要分为（）和（）两类。

②在操作系统中，不确定性主要是指（）和（）。

③在UNIX系统V中，一个新建的子进程从其父进程那里继承了（），（）和（）等多种资源。

④在可变分区存储管理中，分区的保护通常采用（）和（）两种方式。

⑤逻辑设备表（LUT）的主要功能是（）和（）。

⑥在采用请求分页式存储管理的系统中，地址变换过程可能会因为（），（）和（）等原因而产生中断。

⑦在UNIX系统V中，如果一个盘块的大小为1KB，每个盘号占4个字节，那么，一个进程要访问偏移量为263168字节处的数据时，需要经过（）次间址。

⑧设备驱动程序是一种低级的系统例程，它通常分为（）和（）两个部分。

⑨ UNIX系统V在打开（open）一个文件时，需要为其分配（），（）和（）等多种资源。

2（10分）简述LRU，NRU和LFU三种页面置换算法的思想，并各给出一种可能的实现方案。

3（10分）何谓临界区？下面给出的实现两个进程互斥的算法是安全的吗？为什么？#define TRUE;#define FALSE;int flag[2];flag[0] = flag[1] = FALSE;enter-crtsec（i）int i;{while（flag[1-i]）;flag[i] = TRUE;}leave-crtsec（i）int i;{flag[i] = FALSE;}process i:/* i = 0 or i = 1 */...enter-crtsec（i）;/* 进入临界区 */IN CRTICAL SECTIONleave-crtsec（i）;/* 离开临界区 */...4（10分）要使一个系统不发生死锁，一般可采用哪些方法？简述它们的实现原理。

中国科学技术大学1998年硕士生入学考试数据结构和程序设计试题要求：算法设计题目要求写注解，否则扣分。

写出正确的设计思想和伪代码给分。

1 （15分）填空：①用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是和；若只设尾指针，则出队和入队的时间复杂度分别是和。

②设广义表L＝(（），（）) 则head(L)是；tail(L)是；L的长度是；深度是③深度为h的完全二叉树至少有个结点；至多有个结点；h和结点总数n之间的关系是。

④在n个记录的有序顺序表中进行折半查找，最大的比较次数是。

⑤在一棵m阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是。

⑥n个顶点的连通图用邻接距阵表示时，该距阵至少有个非零元素。

2 （20分）请在下列各题中选择一个正确的答案①算法的时间复杂度取决于(a)问题的规模(b)待处理数据的初态(c)(a)和(b)②消除递归不一定需要使用栈，此说法。

(a)正确(b)错误③假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探侧?(a) k-1次(b) k次(c) k+1次(d) k(k+1)/2次④若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是:(a)快速排序(b)堆排序(c)归并排序(d)直接插入排序⑤用ISAM和VSAM组织文件属于·’(a)顺序文件(b)索引文件(c)散列文件⑥若一个有向图的邻接矩阵中，主对角线以下的元素均为零，则该图的拓扑有序序列(a)存在(b)不存在⑦将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是(a)n (b)2n－1 (c)2n (d)n-1⑧下述二叉树中，哪一种满足性质：从任一节点出发到根的路径上所经过的节点序列按其关键字有序(a)二叉排序树(b)哈夫曼树(c)A VL树(d)堆⑨已知持排序的n个元素可分为n/k个组，每个组包含k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为：（a）O（nlog2n）（b）O(nlog2k) （c）O(klog2n) （d）O(klog2k)⑩在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树，该说法(a)正确(b)错误3 （10分）设二叉排序树T中各结点关键字互不相同，x^是T的叶子，y^是x^的双亲。

中国科学院软件研究所一九九八年招收硕士学位研究生入学考试试题答案
试题名称：软件基础
第一部分：程序设计和数据结构
一.选择合适的答案填空（1分×20）
1．（a ），（d ），（e ）；
2．（b ）；
3．（c ），（a ），（d ）；
4．（c ）；
5．（b ）；
6．（b ）；
7．（d ）；
8．（e ）；
9．（b ），（c ）；
10.（b ）；
11.（b ）；
12.（c ）；
13.（b ）；
14.（c ）；
15.（a ）；
二.
1．除A[2] = 1外，其余各分量均为0。

2．A 中分量均为0。

3．Demo 的功能是二进制数的增量（加上）操作，A 相当于一个二进制计数器。

4．n 次连续调用Demo 的总时间的上界应为O （n ），详细分析如下：
Demo 操作的时间代价正比于二进制数A 中位（每个A[i]相当于二进制数的位）的翻转次数，而n 次连续的Demo 操作是从0开始的，因此在这n 次增量操作中：A[0]共翻转n 次，A[1]共翻转 次，……，A[i]共翻转 次（i
）；当i 时，位A[i]根本不翻转（因为数n 的二进制表示最多有 位）
，所以n 次增量操作发生⎣⎦n 2log ≤⎣⎦i n 2/⎣⎦
2/n ⎣⎦n 2log >⎣⎦1log 2+n ⎣⎦⎣⎦
)(22/12/0log 02n O n n n i i n i i ==<∑∑∞==。

中科院计算机技术研究所1995年硕士研究生入学考试试题计算机原理一.填空(每空1分共15分)1.布尔代数有三个重要的运算法则,即_____,_____和_____.2.常用的数字逻辑电路分为两类,他们是_____电路和_____电路.3.冯.诺依曼机体系结构的思想主要之点是____概念.4.微指令由控制字段和下址字段组成,其基本的控制字段编译法由___,___,___.5.提高除法运算速度(快速除法),可采用___,___,___和___等.6.在动态MOS存储器中,采用异步刷新的方法,其优点是_____,而缺点是____.二.选择题(每题1.5分,共15分)1.用一位奇偶校验法,能检测出一位存储器错的百分比是:(1).0%(2).25%(3).50%(4).100%2.若阶码为三位,用补码表示;尾数7位,用原码表示,其中一位为符号位;以2位底.则十进制数27/64的浮点规格化数是:(1)010*******(2)010*******(3)0111110110(4)00010110113.CRAY-1是下述那种计算机?(1).阵列计算机(2)并行计算机(3)并行加流水线计算机(4)数据流计算机4.程序运行时,磁盘与主机之间数据传送是通过下列那种方式进行的?(1)中断方式(2)DMA方式(3)陷阱(4)程序直接控制5.8086读写一个以奇数地址开始的双字,最少需几个线周期?(1)1(2)2(3)3(4)46.在存储系统中,增加Cache,是为了:(1)提高主存速度(2)扩充存储系统的容量(3)提高存储系统供数率(4)方便用户编程7.在指令格式中采用扩展操作码的设计方案是为了:(1)减少指令字长度(2)增加指令字长度(3)保持指令字长度不变(4)保持指令字长度不变,而增加寻址空间8.当今设计高性能计算机的重要技术途径是:(1)提高主频(2)扩大存储容量(3)采用非冯.诺依曼结构.(4)采用并行处理9.在计算机系统中表征系统运行时间状态的部件是(1)程序计数器(2)累加计数器(3)中断计数器(4)程序状态字10.在大型机上不采用标准总线结构的主要原因是:(1)成本高(2)模块化强(3)利用率低(4)数据传输率低三.名词和术语解释(每题3分,共15分)1. MIPS和MFLOPS答：MIPS即"百万条指令/s",他是表征计算机定点处理速度的指标.MFLOPS即"百万次浮点操作/s",他是表征计算机浮点运算速度的指标,也是科学计算中的重要性能指标.2.CISC 和RISC答：CISC是传统计算机指令系统的设计策略,即为了增强功能而不断扩充指令系统的指令操作种类和增加指令操作功能,使得计算机的指令系统及其硬件控制越来越复杂.RISC采用了与CISC相反的设计方法,称为简化指令集计算机,即指令系统压缩到最基本的规模,其指令执行周期绝大多数为一拍,这样可以充分利用有限的硬件资源,有效提高了计算机系统的内在性能.3.程序中断和过程调用答：多道程序是几道程序同时驻留在内存中,按程序优先次序依次执行;当正在执行的程序被中断后转入下一程序执行.而分时方式是按时间片依次轮流执行的,当本道程序所用时间片结束时即转入下道程序运行4.多道程序设计和分时系统答：多道程序是几道程序同时驻留在内存中,按程序优先次序依次执行;当正在执行的程序被中断后转入下一程序执行.而分时方式是按时间片依次轮流执行的,当本道程序所用时间片结束时即转入下道程序运行.5.紧密耦合多机系统和松散耦合多机系统答：紧密耦合多机系统是共享存储的多处理机系统,松散耦合多机系统是分布存储的.四.综合解答题(每题5分,共20分)1.画出控制中央处理器和主存之间数据传送的连接线(含数据线和控制线),并说明读数和存储过程.2.在下表中对比INTEL286,386,486处理器的异同:特点处理器286 386 486运算功能上内总线宽度主时钟相同点3.画出在磁表面记录时,数据011001110 的NRE-1,FM,MFM(不必压缩)刷的写入电流波.4.简要说明完成一次中断处理步骤,或画出其流程(可实现中断嵌套).五.设计计算题:(共35分)1.用补码不恢复余数法求x/y=? x=0.1000 y=-0 (8分)2.设有主存M1和辅存M2构成的二级存储体系,其中和M2的读出时间分别为10^(-6) s和10^(-3)s.经实测该存储系统的平均读出时间为10^(-4)s.今欲使其减小为10^(-5) 秒,试给出两种改进设计的实现方法.(10分)3.对于表达式F=Σ(i=0 to k-1)xi*yi,在计算机中可以用硬件软件和固件分别实现.式述其实现方岸及原理示意,并就性能,成本及应用方面加以简单比较.(10分)4.设定九个任务的优先图如下:(9520.bmp)且每个任务均一拍完成.现将这组任务分配给三个处理机运行.试求出最小完成时间和处理机利用率.若将这组任务分配给两个处理机,其最小完成时间和设备利用率又是多少?(7分)参考答案一.填空1.对偶原理,置换原理,反演法则.2.组合逻辑,时序逻辑3.存储程序4.直接控制法,字段直接控制法,字段间接编译法5.跳"0"跳"1"法,迭代除法,阵列除法器,查表法6.取消了机器的死区,其控制线路极其复杂四.综合解答1.读数过程:(1)送地址(2)读(3)接收数据存数过程:(1)送地址(2)送数(3)写图(9521.bmp)2.对比286 386 486运算功能上16位定点处理器32位定点64位浮点内存线宽度16 32 64主时钟8--20M 16--33M 33-66M相同点程序指令兼容3.图(9522.bmp)4.略.五.设计计算题2.解:设主存的命中率为H,M1,M2的读出时间为TM1,TM2,则系统平均读出时间为TA=H*TM1+(1-H)*TM2欲减少TA,可考虑增大H,降低TM1及TM2(1)提高H原H=(TA-TM2)/(TM1-TM2)=0.901欲使TA=10^(-5),代入上式,得H=0.991即通过改进调度算法提高命中率H为0.991(2)减小THTM1=(TA-(1-H)TM2)/H=-0.988*10^(-6)即此方法不可能实现.(3)减少TM2TM2=(TA-HTM1)/(1-H)=10^(-4) s通过提高辅存速度(10 times)可实现TA=10^(-5)3.(1)硬件实现用流水线加法器和乘法器组成乘加宏流水线运算器: (9523.bmp)特点:性能很高,成本高,用于高性能计算机中.(2)软件实现:用循环程序实现特点:灵活通用速度不高成本较低i<- 0zi<- 0lable: 取xi乘yi加zi存Fi<- i+1判i=<n转移 goto lable停机(3)固件实现:将程序固化:特点:速度较高,不便修改,专用.4(1)三个处理机运行T1 T4 T7 T9T2 T5 T1T3 T4最小完成时间为5拍,设备利用率μ=9/15=.6(2)二个处理机运行P1 T1 T2 T4 T6 T7 T9P2 T3 T5 T8最小完成时间为6拍μ=9/12=.75。

中科院计算所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也表示数组首址，然而使用时有时并不相同，请根据下面写出a与&a 类型表达式（10’）(1) tgpedef int A[10][20]A a;A * func ( ){return(a);}在linux上用gcc编译报告:第6行warning: return from incompatible pointer type(2) typedef int A[10][20]A a;A *func( ){return(&a);}无类型方面错误(3) typedef int A[10][20]typedef int B[20]A a;B *func( ){return(a);}无类型方面错误(4) typedef int A[10][20]A a;func( ){Printf(“%d,%d,%d/n,a,a+1,&a+1);}main( ){func( );}结果：134518112，134518192，134518912中科院计算机技术研究所1999年硕士生入学试题中科院计算所1999年编译原理与操作系统一.(15分)有表达式如下:A+B*(C-D)**N (**为幂乘)(1)给出该表达式的逆波兰式表示(后缀式);(2)给出上述表达式的四元式和三元式序列.三.(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分)中科院计算所1999年编译原理与操作系统参考答案一.(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)S.h:=S1.h+S2.h+1S->εS.h:=0S'->Sprint(S.h)/*输出其配对括号数*/五.(10分)G1:LR(1)文法G2:非LR(1),非二义性文法S->A,BS->aSb|BA->aAb|εB->Bb|bB->Bb|b六.填空1.并发,共享2.初始化标识符信息,初始化处理机状态信息,初始化处理机控制信息;3.为了减少程序并发执行时所需付出的时空开销,提高程序执行的并发度;4.forkpipemknod5.正在执行的进程时间片完;正在执行的进程执行了sleep系统调用;正在执行的进程执行了exit系统调用;正在执行的进程在用户态运行时有优先级更高的进程进入就绪队列6.中低地址,高地址7.设备控制表,控制器控制表,通道控制表,系统设备表8.只让文件主拥有指向该文件索引结点的指针,而共享该文件的其他用户只有该文件的路径明而不是指向索引结点的指针.中科院98考研题中科院计算所1998年编译原理和操作系统一.(10分)某操作系统下合法的文件名为device:name.extension ，其中第一部分(device:)和第三部分(.extension)可缺省,若device,name和extension都是字母串,长度不限,但至少为1,画出实现这种文件名的确定有限自动机.二.(10分)下面的二义文法描述命题演算公式,为他写一个等价的非二义文法.S->S and S|S or S|not S|p|q|(S)三.(10分)把表达式- (a+b)*(c+d)+(a+b+c) 翻译成四元式.四.(10分)由于文法二义引起的LR(1)分析动作冲突,可以根据消除二义的规则而得到LR(1)分析表,根据此表可以正确识别输入串是否为响应语言的句子.对于非二义非LR(1)文法引起的LR(1)分析动作的冲突,是否也可以根据什么规则来消除LR(1)分析动作的冲突而得到LR(1)分析表,并且根据此表识别相应语言的句子?若可以,你是否可以给出这样的规则?五.(10分)下面程序的结果是120.但是如果把第5行的abs(1)改成1的话,则程序结果为1.试分析为什么会有这不同的结果.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=%d\n",fact());}中国科学院计算所1997年编译原理试题（共25分）1．(10分) 为正规式（a|b）*a(a|b)构造一个确定的有限自动机。

中科院计算机技术研究所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的语句时,采用这三种同步方式,X的值可能各是多少?发送进程P: 接收进程Q:M=10;L1: send M to Q; L1: receive S from P;L2: M=20; L2: X:=S+1;goto L1;八.(8分)一系统具有150个存储单元,在T0时刻按下表所示分配给3个进程:进程Maximum demand Current allocationP1 70 25P2 6040P3 6045对下列请求应用银行家算法分析判定是否是安全的:A.第4个进程P4到达,最大需求60个存储单元,当前请求分配25个单元.B.第4个进程P4到达,最大需求50个存储单元,当前请求分配35个单元.如果是安全的请给出一个可能的进程安全执行序列.如果是不安全的,请说明原因.九、(14分)设正在处理器上执行的一个进程的页表如下.页表的虚页号和物理块号是十进制数,起始页号(块号)均为0.所有的地址均是存储器字节地址,页的大小为1024字节.A.详述在设有快表的请求分页存储管理系统中,一个虚地址转换成物理内存地址的过程.B.下列虚地址对应与什么物理地址: (1)5499; (2) 2221;虚页号状态位访问位修改位物理块号0 1 10 4111 1 72000---3 1 00 24 0 00---5 1 0 1 0注释:访问位---当某页被访问时,其访问位被置为1.中科院计算机技术研究所1999年硕士生入学试题编译原理与操作系统参考答案一.(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, t4) (4)( - , C , D )(5)(**, t4, N , t5) (5)(**, (4), N)(6)( / , E , t5, t6) (6)( / ,E ,(5))(7)( +, t3, t6, t7) (7)( +,(3),(6))二.(1)(5分)输出结果: 10,X,Y 其中X,Y是随机整数值(2)(10分)从活动记录内容安排看,在运行栈中,调用者的活动记录在被调用者的下面,如图:其中参数域和可能有的返回值放在紧靠调用者活动记录的地方.这样的好处是,对调用者来说无须了解被调用者的局部数据或临时量,做到信息隐藏.另一好处是,可以处理变元个数可变的过程,如printf.从printf实现看,C语言中的printf函数,他的第一个变元指出了其余参数的性质,所以一旦printf能够确定第一个变元位置,他就能找到其余变元.C的参数是逆序计算和进栈的,这样就保证了被调用者能知道第一个变元的位置.在所给例子中,main函数调用printf时仅压入两个参数到栈中,而第一个参数中指示要显示三个整数值,但仅给出(压入栈(一个有效值).所以出现上述结果.三.(5分)四.(5分)为符号S引入综合属性h,语法制导定义如下:产生式语义规则S->S1(S2) S.h:=S1.h+S2.h+1S->εS.h:=0S'->S print(S.h)/*输出其配对括号数*/五.(10分)G1:LR(1)文法G2:非LR(1),非二义性文法S->A,B S->aSb|BA->aAb|εB->Bb|bB->Bb|b六.填空1.并发,共享2.初始化标识符信息,初始化处理机状态信息,初始化处理机控制信息;3.为了减少程序并发执行时所需付出的时空开销,提高程序执行的并发度;4.fork pipe mknod5.正在执行的进程时间片完; 正在执行的进程执行了sleep系统调用; 正在执行的进程执行了exit系统调用; 正在执行的进程在用户态运行时有优先级更高的进程进入就绪队列6.中低地址, 高地址7.设备控制表, 控制器控制表, 通道控制表, 系统设备表8.只让文件主拥有指向该文件索引结点的指针,而共享该文件的其他用户只有该文件的路径明而不是指向索引结点的指针.七.在消息传递通信方式下:A三种同步方式分别为:1.发送进程和接收进程均阻塞(即同步的发送和接收)2.发送进程不阻塞,接收进程阻塞(即阻塞的发送和接收)3.发送进程和接收进程均不阻塞(即无阻塞的发送和接收)B.同步的发送和接收方式下:X=11;阻塞的发送和接收方式下:X=11;无阻塞的发送和接收,X=11,或21,或-99.八.应用银行家算法A.安全,存在至少一个进程安全执行队列:P3,P2,P1,P4.(只要P3排第一均可)B.不安全.因为系统在满足了P4的资源请求后,已不满足安全性.九.A.在设有快表的请求分页系统中地址变换机构在进行地址变换时,(1)首先检索快表,试图找到所要访问的页.若找到,便修改页表中的访问位.对于写指令,还需将修改位置成"1",然后利用页表项中给出的物理块号和页内地址(偏移址), 形成物理地址.(2)如果在快表中未找到该页的页表项,则应再到内存中查找页表,再从找到的页表项的状态位来了解该页是否已调入内存,其结果可能是:(1)该页已调入内存,这时应将该页的页表写入快表,当快表已满时,应先调出按某种算法确定的页的页表项,然后再写入该页的页表项.然后再执行如(1)所述的地址变换过程.(2)该页尚未调入内存,便要产生缺页中断,请求操作系统从外存将所缺之页调入内存.操作系统的缺页中断机构从外存中找到所缺的页后,判断内存是否已满.若否,则从外存调入所缺的页;若是,还要先调用页面置换算法从内存中换出一页,再从外存调入所缺的页.在做页面置换时,若将被换出的页的修改位置为"1",说明已被修改过,则要将该页写回内存,然后执行(1)所述的地址变换过程.B.虚地址(虚页号,页内地址) 物理地址(物理块号,块内地址)2221=1024*2+173 (2,173) (不在内存)5499=1024*5+379 (5,379) (0,379)。

软件基础操作系统部分（30分）一、填充（每空一分，共14分）1、采用单级文件目录的主要缺点是存在_______________问题。

2、在单道程序运行环境下，常用的作业调度算法有__________、__________、和__________。

3、特权指令是只能由_________________使用的指令。

4、存储器的保护机制（硬件）有___________保护和_________保护。

5、预防死锁中的预先分配法和标准（有序）分配法，它们分别破坏了产生死锁必要条件中的__________ ___条件和_____________条件。

6、在段式虚拟存储管理中，段表设置“改变位”的目的是为了___________________________________。

7、进程有三种基本状态，即[1]______________状态，[2]___________状态，[3]___________状态。

当进程又[1]演变为[2]或[3]时，就会引起__________。

二、判断。

（每题1分，共5分）1、（）有了动态重定位机构，作业地址空间的代码就可以原封不变的装入到给定的内存中。

2、（）任一时刻，若有执行状态的进程，就一定有就绪状态的进程。

3、（）文件系统中，设置OPEN操作的目的是为了将文件复制到内存中。

4、（）临界段是不可中断的程序。

5、（）作业的提交状态进入后备状态的过程是由作业调度程序完成的。

三、（5分）分页式存储管理与分段式存储管理的主要区别是什么？四、（6分）以下是高级通讯原语SEND和RECEIVE不完整的框图。

请填充以适当的P、V操作，并说明所用信号量的意义和初值。

SEND：RECEIVE：↓↓申请一消息区（3）↓↓消息送消息区（4）↓↓（1）从消息链上摘下一消息↓↓消息区挂入消息链（5）↓↓（2）消息送接收区↓↓V（S2）释放消息区↓↓语言与编译部分（35分）一、（7分）把下面不确定的有限自动机化为确定的有限自动机。