进程
最大需求
已分配
尚需求
ABCD ABCD ABCD
剩余 ABCD
P0
0044 0032 0012 1622
P1
2750 1000 1750
P2
3 6 10 10 1 3 5 4 2 3 5 6
P3
0984 0332 0652
图 T0 时刻的资源分配图 问：（1）TO 时刻系统安全吗？ （2）如果此时进程 P2 提出请求 Request（l，2，2，2）后，系统能否将资源分配给它？
答案写在答题纸上，写在试卷上无效
第 2 页（共 2 页）
浙江工商大学 2013 年硕士研究生入学考试试卷 （A）卷
考试科目：845 计算机基础综合 总分：150 分 考试时间：3 小时
一、数据结构（共 60 分）是 12345。请画出这课二叉树。 2． (12 分)从结节点 1 开始，用 Prim 算法画出下图的最小生成树的过程。
虚页号
物理页号
0
5
1
10
2
4
3
7
问：（1）虚拟存贮器的功能是怎么实现的？
（2）逻辑地址 0A5C (H)、 1A5C (H)对应的物理地址分别为多少？(如果主存中找不到, 即为页失效)
5.（9 分）假定系统中有五个进程{P0，P1，P2，P3，P4}和三种类型的资源{A，B，C，D}，按银行家算
法中，若出现下述的资源分配情况（在 T0 时刻的资源分配情况如下图所示）：
3． (12 分)已知一个电报包含的字符为"a", "b", "c", "d" 和 "e"，它们出现的频率次数分别为{25, 9, 12, 8, 11 }。请给出字符的 Huffman 编码。
4． (12 分)已知一个整数序列 {20 17 22 12 60 32 16 15}，请画出快速排序的过程和最后的结果。 5． (12 分)请构造函数 int full(btree *bt)，判断一颗二叉树是否为满二叉树，是返回 1，否返回 0。 二、计算机组成（共 45 分） 1．(9 分)画出典型的冯·诺依曼计算机硬件系统组成框图，并简述各功能部件的作用。 2．（9 分）某机器字长为 16 位，请写出下列各种情况下它能表示的十进制数的范围（采用 1 位符号位）： （1）无符号整数；（2）用补码表示的定点整数；（3）用 5 位阶码（含 1 位阶符）、11 位尾码（含 1 位数 符）表示的规格化浮点数。 3.（9 分）已知 Cache 存取周期为 30ns，主存存取周期为 120ns，执行某段程序共访问 Cache 5000 次， 访问主存 200 次，求：（1）Cache 命中率；（2）平均内存访问时间。 4.（9 分）举例说明中断处理流程。 5．（9 分）某机器中采用 RAM 芯片 8K×8 组成 16K×8 的 RAM 区域，起始地址为 8000H。假设 RAM 芯片有 CS 和 WE 信号控制端，CPU 的地址总线为 A15—A0,数据总线 D7—D0，控制信号为 R/ W, MREQ， （1）请设计地址译码方案；（2）画出 RAM 和 CPU 连接图。 三、操作系统（共 45 分） 1.（8 分）描述进程的三个基本状态以及它们之间转换的典型原因。 2.（9 分）在单道程序环境下若有四道作业，其进入系统及所需的执行时间如下表所示：
表 1 四道作业的进入和执行时间
作业 进入时间（小时） 执行时间（小时）
1
8
2
2
8.5
0.5
3
9
0.1
4
9.5
0.2
答案写在答题纸上，写在试卷上无效
第 1 页（共 2 页）
分别按先进先出算法、短作业优先算法、响应比高者优先的调度算法调度，则其平均周转时间分别为多 少（上述三种算法均为非抢占方式）？ 3.（10 分）有一个阅览室，读者进入时必须先在一张登记表上进行登记，该表为每一座位列一表目，包 括座号和姓名，读者离开时要撤消登记信息；阅览室共有 100 个座位，当阅览室满员后，读者不得进入， 只能在室外等待。试用 P、V 操作写出上述问题的同步算法。(动作部分可用文字描述) 4.（9 分）某虚拟存贮器的用户编程空间共 32 个页面, 每页 1 KB, 主存为 16 KB. 假定某时刻用户页 表中已调入主存的页面的页号和物理块号（页架号）对照表为：