上海交通大学
2000年硕士生入学考试试题
试题序号：20
试题名称：编译原理及操作系统
（答案必须写在答题纸上，否则答题无效）
操作系统部分
1．请用信号量实现4*100（4人，每人100米）接力赛的同步过程（10分）
2．进程拥护态图象由共享正文段、数据段和栈段三部分组成，请指出c语言程序中下列部分通常位于哪以段中：
（1）动态局部变量
（2）静态局部变量
（3）外部变量
（4）在程序执行时用malloc函数分配到存储区
（5）函数调用时传送的参数值（10）
3．在支持线程的系统中，同一进程中的个线程是否共享一个栈，为什么？（10分）
4．在一个使用交换技术（swapping）的系统中，按地址从低到高排列的内存空洞长度时10K、4K、20K、18K、7k、9K、12K和15K。
对于下列顺序的段请求：
（1）。
1、下面哪个资源不是操作系统应该管理的？（D）A . CPU B.内存 C. 外存 D. 源程序2、下列选项中，操作系统提供给应用程序的接口是（A）。
(2010年联考原题）系统调用 B. 中断 C. 库函数 D. 原语3、计算机开机后，操作系统最终被加载到（D）。
（2013年联考原题）A. BIOSB. ROMC. EPROMD.RAM4、设有A、B、C三道程序，其执行过程分别如下：A：C11=30ms I12=40ms C13=10msB：C21=60ms I22=30ms C23=10msC：C31=20ms I32=40ms C33=20ms其中，Cij表示CPU内部计算过程，Iij表示I/O操作，三者的优先权顺序为ABC。
假设调度和启动I/O的执行时间忽略不计，同时假设每道程序请求的外设不冲突。
问：（1）单道处理系统，三道程序顺序执行完需要花费多少时间？（2）多道处理系统，三道程序同时驻留内存，执行完需要花费多少时间？5、有两个程序，程序A依次使用CPU计10s，使用设备甲计5s，使用CPU计5s，使用设备乙计10s，使用CPU计10s；程序B依次使用设备甲计10s，使用CPU计10s，使用设备乙计5s，使用CPU计5s，使用设备乙计10s。
在单道程序环境下先执行程序A再执行程序B，计算CPU的利用率是多少？在多道程序环境下，CPU利用率是多少。
答：（1）单道环境下CPU运行时间为：(10 + 5 + 10) + (10 + 5)=40s总运行时间为：40+40 = 80s所以，CPU利用率为 50%。
（2）多道环境下CPU运行时间为：40s，总运行时间为：45s所以，CPU利用率为 88.9%。
1、一个进程映像是（ C ）。
A.由协处理器执行的一个程序B.一个独立的程序+数据集C.PCB结构与程序和数据的组合D.一个独立的程序2、进程与程序的根本区别是（A ）。
A.静态和动态特点B.是不是被调入到内存C.是不是具有就绪、运行和等待三种状态D.是不是占有处理器3、操作系统是根据（ B ）来对并发执行的进程进行控制和管理的。
2011年计算机考研统考真题【1】设n是描述问题规模的非负整数，下面的程序片段的时间复杂度是（）。
x=2;while(x<n/2)x=2*x;A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)【解析】A。
容易看出，程序基本操作为x=2*x;基本操作执行的次数即为程序的时间复杂度，因此可设基本操作执行k次结束，则有：执行第1次：x=2×2=21+1=4；执行第2次：x=4×2=22+1=8；执行第3次：x=8×2=23+1=16；……执行第k次：x=2k+1。
由循环结束条件知：x<n/2，即2k+1<n/2时结束，即k<log2n-2，即k=log2n+C（为方便说明，其中C为起修正作用的常数）。
综上得：时间复杂度为O(log2n)。
【2】元素a,b,c,d,e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是（）。
A.3B.4C.5D.6【解析】B。
若要保证出栈序列以d开头，则前三个元素必连续进栈，中间不能出现出栈的情况，然后d出栈，此时栈内元素由底到顶为，a,b,c，栈外元素为e，出栈序列中元素为d。
因为a,b,c三个元素在栈内的顺序已定，由栈的先进后出原则，其在出栈序列中的相对位置必为…c…b…a…；加上d的位置已定，所以出栈待定序列必为d…c…b…a…。
显然在栈外的e可以在任何时候出栈入栈，即可以出现在以上待定序列中任何一个省略号的位置，即出栈序列可为：1:d,e,c,b,a；2:d,c,e,b,a；3:d,c,b,e,a；4:d,c,b,a,e。
【3】已知循环队列存储在一维数组A[0…n-1]中，且队列非空时front和rear分别指向队头和队尾元素。
若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是（）。
计算机操作系统考研真题计算机综合硕士真题一、选择题真题解析4某系统采用改进型CLOCK置换算法，页表项中字段A为访问位，M为修改位。
A＝0表示页最近没有被访问，A＝1表示页最近被访问过。
M＝0表示页没有被修改过，M＝1表示页被修改过。
按（A，M）所有可能的取值，将页分为四类：（0，0）、（1，0）、（0，1）和（1，1），则该算法淘汰页的次序为（）。
[2016年408统考]A．（0，0），（0，1），（1，0），（1，1）B．（0，0），（1，0），（0，1），（1，1）C．（0，0），（0，1），（1，1），（1，0）D．（0，0），（1，1），（0，1），（1，0）【答案】A ~ @【解析】使用改进型CLOCK置换算法淘汰页面时，其原理是：（1）首先扫描访问位为0，修改位为0的页；（2）若（1）中没有找到，则重新扫描，查找访问位为0，修改位为1的页，此过程中将被跳过页的访问位设为0；（3）若（2）依旧没找到，则开始重复（1）开始查找、若没有则继续（2）查找。
因此该算法首先置换（0，0）、（0，1），若都没找到，此时（1，0）、（1，1）被更改为（0，0）、（0，1）进行查找，所以最后该算法淘汰页的次序为（0，0），（0，1），（1，0），（1，1）。
45使用TSL(Test and Set Lock)指令实现进程互斥的伪代码如下所示。
do{ … whlie(TSL(&lock)); critical; section; lock=FALSE; …}while(TRUE);下列与该实现机制相关的叙述中，正确的是（）。
[2016年408统考] A．退出临界区的进程负责唤醒阻塞态进程B．等待进入临界区的进程不会主动放弃CPUC．上述伪代码满足“让权等待”的同步准则D．while(TSL(&lock))语句应在关中断状态下执行【答案】B ~ @【解析】A项，TSL指令作用的进程都是短进程，不会出现阻塞情况，退出临界区的进程不需要负责唤醒阻塞态进程；C项，TSL指令作用的进程属于忙则等待的类型，运行的进程等待资源时，进入临界区的进程并不会主动放弃CPU。
第1章引论习题集一、选择题1.操作系统是对（）进程管理的软件。
【＊，联考1.1】A. 软件B. 硬件C. 计算机资源D. 应用程序2.操作系统是提供了处理机管理、（）管理、设备管理和文件管理的软件。
【＊，★，联考1.1】A. 存储器B. 用户C. 软件D. 数据3.从用户的观点看，操作系统是（）。
【＊，联考】A. 用户与计算机之间的接口B. 控制和管理计算机资源的软件C. 合理地组织计算机工作流程的软件D. 由若干层次的程序按一定的结构组成的有机体4.以下选项中，（）不是操作系统关心的主要问题。
【＊，★，联考1.1】A. 管理计算机裸机B. 设计、提供用户程序与计算机硬件系统的界面C. 管理计算机系统资源D. 高级程序设计语言的编译器5.以下不属于操作系统管理范畴的是（）。
【＊，联考1.1】A. CPUB. 编写程序C. 主存D. 中断6.配置了操作系统的计算机是一台比原来的物理计算机功能更强的计算机，这样的一台计算机只是一台逻辑上的计算机，称为（）计算机。
【＊＊，★，联考】A. 并行B. 真实C. 虚拟D. 共享7.在操作系统中，对系统中的信息进行管理的部分通常称为（）。
【＊，联考1.1】A. 数据库系统B. 软件系统C. 文件系统D. 检索系统8.在操作系统中，并发性是指若干事件（）发生。
【＊＊，★，联考】A. 在同一时刻B. 一定在不同时刻C. 某一时间间隔内D. 依次在不同时间间隔内9.下面（）不是程序在并发系统内执行的特点。
【＊＊，联考1.1】A. 程序执行的间断性B. 相互通信的可能性C. 产生死锁的必然性D. 资源分配的动态性10.操作系统的不确定性是指（）。
【＊＊，★，联考】A. 程序运行结果的不确定性B. 程序运行次序的不确定性C. 程序多次运行时间的不确定性D. B和C11.在操作系统中，（）负责对进程的调度。
【＊，联考】A. 处理机管理B. 作业管理C. 高级调度管理D. 存储和设备管理12.以下不属于衡量操作系统性能指标的是（）。
