2005年10月浙大计算机考博试题

10 月 15 下午：操作系统计算机体系结构 操作系统部分： 试题 1：选择题，共 8 题，32 分 1 很简单的没记 2.如果用银行家算法解决死锁问题，某系统一共有 150M 内存，现有 3 个进程，内存需 要及已经分配情况如下： 进程名 需要内存 已分配 P1: 70 45 P2: 60 40 P3 60 15 现再来一个进程，需要内存 60M，问分配给它最多多少才能保证死锁发生 3.关于下面这段算法，能不能让 P0 和 P1 两个进程（假设仅有这两个进程可以进入该临 界区）互斥进入临界区及会不会发生“饥饿” enter loop if turn!= -1； turnI; if turn!=I; loop; turn = -1; leave turn=0; 4.关于缺页率和页面置换算法，哪个页面置换算法缺页率最低： 最优置换算法、先进先出算法、最近最久未使用算法、second chance 5.某系统允许 5000 个用户同事访问，怎么设置只能让 4990 个用户同时访问 Develist 文 件。 通过设置用户属性来实现、通过设置文件属性来实现、两个一起、两个都不行 6.哲学家进餐问题，怎样改进才能避免死锁发生： do wait chockstick（i） wait chockstick（ i1）5） ） eat signal chockstick（i ） signal chockstick（i 1）5） ） while（1） a每个人先拿左边再拿右边筷子 b 最多只允许 4 个哲学家同时拿起筷子，但允许 5 个 同时思考 c 拿筷子前先看左边的哲学家，如果他在思考才可以拿起筷子 d 把人数由 5 改 成 4 7.通用操作系统可以用什么语言编写：汇编、高级语言、一部分汇编一部分高级 8.操作系统的作用 试题 2 计算平均 cpu 时间 进程名 到达就绪队列时间（秒） 执行时间（秒） P1 0.0 8 P2 0.4 4 P3 1.0 1 1 如果用非抢占式最短作业优先算法，平均 cpu 时间多少 2.如果先让 cpu 轮空 1 秒，在一秒的时候进行调度，平均 cpu 时间多少 试题 3 在关于 x windows 的书里，经常会看到如下的结构图，给定 linux 、shell 、jdk1.3、XXSQL，用这样的图表示 Xxx 应用程序 xxx 低级语言接口 Windows 计算机体系结构 - 1 - 计算机体系结构 试题 1，选择题，11 题，共 22 分 1. 计算机体系结构的研究对象 a 组成、b 指令集设计 c 和编译器无关 d 硬件设计、指令集设计、组成啊什么的 2. 影响 cpu 时间的 3 个参数 ic/cpiic/isacpi/流水线 3. ai=i+ bi=ai+ ci=ai+bi 这个计算， 以下哪种结构的计算机可以把结构利用的最好 堆栈结构、R-M 通用寄存器结构、load/save 结构、xx 4. Flynn。 。向量多计算机系统。 。是考名称缩写 SIMD MISD/SIMD MIMD/. 5. 记分牌动态调度读写什么的。 。也是考名称缩写 a) WAR WAW C WAR WAW b) RAW WAR 6. 软件流水线。 。 。 。指令相关性是什么属性 a) 程序属性 b 结构属性 c 编译属性 d 7. 指令潜在相关性。 。产生 stall。 。 。ILP 8. 多发射处理器 9. 基于硬件投机重构序缓冲器 10. （m,n）关联 是指 m。 。 2/n/m/2 。 。n 11. 多 cpu 结构。 。 。网络分布式， 试题 2 计算加速比：如果使用硬件，该部件占 40，提高 10 倍 如果用软件方法，两个程序分别占 60和 10，分别提高 2 倍和 20 倍 加速比分别是多少，你该用哪种方法 试题 3 软件流水线编译优化, R2=100,R1=218 LOOP: L.D F0,0(R1) ;F0-MenR1+0 ADD.D F4,F0,F2 ;F4-F0+F2 S.D F4, 0(R1) ;Men(R1+0)-F4 DADDUIR1 R1,# -8 ;R1-R1+(-8) BEN R1,R2,LOOP ;ifR1!=R2 LOOP 使循环内竞争最少，写出优化后代码， 试题 3 遵循写时无效 cache 一致性监听协议，动作有：总线写，总线读，本地写，本地读 状态有：共享，独占，无效 1） 画出本地 cpu 请求时的状态转换图 2） 填表 Cpu 动作 总线动作 CpuA 的 cache CpuB 的 cache 内存地址 x 内容 0 CpuA 读 x Miss for x CpuB 读 x CpuA 写 2 到 x CpuB 读 x 计算理论基础 - 1 - 最难的一门，大部分是证明设计题 1 正则语言和上下文无关语言的证明（12 分） L1 和 L2 是正则语言，L1 。L2 uv| uL1，vL2，|u|=|v| 证明 L1。L2 是上下文无关语言 如果 L1 是正则语言，L2 是上下文无关语言，用反例证明 L1。L2 是上下文无关语 言 2 上下文无关文法和下推自动机（14 分） 字符串 abcabc,上标皆为整数 给出一个上下文无关文法 设计一个下推自动机 3 图灵机设计（6 分） 设计一个图灵机， 2x (y 为偶数) f（x，y） 4x+1 (y 为奇数) 初始格局 x；y， xy 用二进制表示 4 判断（12 分） 一个语言有序可枚举，那么是递归语言 “M1” “M2”| 可以让图灵机 M1，M2 在空白符处停机，且 M1 比 M2 先停机, 那么是递归可枚举 5 P 类，给出算法，估算时间，并说明（6 分） x1，x 2， 。 。 。 ，x n，判断是否有 Pn， （P 为素数） ，使得 Xppx 1x 2x p-1+xp+1+xn 给出算法（描述就行了） ，估计计算时间，说明属于 P 类 绝大部分为概念共 6 题 面向对象：共六题 1. 简述，8 分 2. 交互图及其表示法 8 分 3. 比较分析：顺序制图和合作制图，过程抽象和数据抽象 4. 服务的详细说明方法 5. 说明 OOA 过程 6. 例举两种 OOA 或者 OOD 方法，并描述其思想 图形学 1. 给出两点坐标，写直线 DDA 算法 2. 给多个点，计算多边形面积的算法 3. 以某点为参考的变化（缩放）变换矩阵 4. phong 光照模型并解释参数含义 5. 三维坐标系变换成屏幕坐标系需要经历那些坐标系统，及变换 人工智能：共三题，第一题写一个什么边框的概念，第二题是一个什么抵消，题目是这样 的：王是总经理，陈是销售部门经理，赵是销售部门职员，李是后勤部门经理，总经理是 部门经理的上司，部门经理是部门职员的上司。上司要