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

操作系统试卷 1 10 月 15 下午 操作系统 计算机体系结构 操作系统部分 试题 1 选择题 共 8 题 32 分 1 很简单的没记 2 如果用银行家算法解决死锁问题 某系统一共有 150M 内存 现有 3 个进程 内存需 要及已经分配情况如下 进程名需要内存已分配 P1 7045 P2 6040 P36015 现再来一个进程 需要内存 60M 问分配给它最多多少才能保证死锁发生 3 关于下面这段算法 能不能让 P0 和 P1 两个进程 假设仅有这两个进程可以进入该临 界区 互斥进入临界区及会不会发生 饥饿 enter loop if turn 1 turn I if turn I loop turn 1 leave turn 0 4 关于缺页率和页面置换算法 哪个页面置换算法缺页率最低 最优置换算法 先进先出算法 最近最久未使用算法 second chance 5 某系统允许 5000 个用户同事访问 怎么设置只能让 4990 个用户同时访问 Develist 文 件 通过设置用户属性来实现 通过设置文件属性来实现 两个一起 两个都不行 6 哲学家进餐问题 怎样改进才能避免死锁发生 do wait chockstick i wait chockstick i 1 5 eat signal chockstick i signal chockstick i 1 5 while 1 a 每个人先拿左边再拿右边筷子 b 最多只允许 4 个哲学家同时拿起筷子 但允许 5 个 同时思考 c 拿筷子前先看左边的哲学家 如果他在思考才可以拿起筷子 d 把人数由 5 改 成 4 7 通用操作系统可以用什么语言编写 汇编 高级语言 一部分汇编一部分高级 8 操作系统的作用 操作系统试卷 2 试题 2 计算平均 cpu 时间 进程名到达就绪队列时间 秒 执行时间 秒 P10 08 P20 44 P31 01 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 cpi ic isa cpi 流水线 3 a i i b i a i c i a i b i 这个计算 以下哪种结构的计算机可以把结构利用的最好 堆栈结构 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 DF0 0 R1 F0 Men R1 0 ADD DF4 F0 F2 F4 F0 F2 S DF4 0 R1 Men R1 0 F4 DADDUIR1R1 8 R1 R1 8 BENR1 R2 LOOP ifR1 R2 LOOP 使循环内竞争最少 写出优化后代码 试题 3 遵循写时无效 cache 一致性监听协议 动作有 总线写 总线读 本地写 本地读 状态有 共享 独占 无效 1 画出本地 cpu 请求时的状态转换图 2 填表 计算机体系结构 2 Cpu 动作总线动作CpuA 的 cacheCpuB 的 cache内存地址 x 内容 0 CpuA 读 xMiss for x CpuB 读 x CpuA 写 2 到 x CpuB 读 x 计算理论基础 1 最难的一门 大部分是证明设计题 1 正则语言和上下文无关语言的证明 12 分 L1 和 L2 是正则语言 L1 L2 uv u L1 v L2 u v 证明 L1 L2 是上下文无关语言 如果 L1 是正则语言 L2 是上下文无关语言 用反例证明 L1 L2 是上下文无关语 言 2 上下文无关文法和下推自动机 14 分 字符串 a b c a b c 上标皆为整数 给出一个上下文无关文法 设计一个下推自动机 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 x2 xn 判断是否有 P n P 为素数 使得 Xpp x1 x2 xp 1 xp 1 xn 给出算法 描述就行了 估计计算时间 说明属于 P 类 X 面向对象和图形学 人工智能 多媒体之一 1 绝大部分为概念共 6 题 面向对象 共六题 1 简述 8 分 2 交互图及其表示法 8 分 3 比较分析 顺序制图和合作制图 过程抽象和数据抽象 4 服务的详细说明方法 5 说明 OOA 过程 6 例举两种 OOA 或者 OOD 方法 并描述其思想 图形学 1 给出两点坐标 写直线 DDA 算法 2 给多个点 计算多边形面积的算法 3 以某点为参考的变化 缩放 变换矩阵 4 phong 光照模型并解释参数含义 5 三维坐标系变换成屏幕坐标系需要经历那些坐标系统 及变换 人工智能 共三题 第一题写一个什么边框的概念 第二题是一个什么抵消 题目是这样 的 王是总经理 陈是销售部门经理 赵是销售部门职员 李是后勤部门经理 总经理是 部门经理的上司