浙江工商大学 2018 年全国硕士研究生入学考试试卷 （A ） 卷

考试科曰 ：845 计算机基础综合 总分：150 分 考试时间 ：3 小时

I 、数据结构 (75 分）

一、问答 （每小题 10 分，共 30 分〉

1. ( 10 分） 给定二叉树的两种遍历序歹 1j ，分别是： 前序遍历序列 ：D,   A ,   C,   E,   B,   H ,   F,   G ,   I ;

中序遍历序列 ：D,    C, B, E,  H ,  A , G ,  I, F;

请给出这棵二叉树的后序遍历序列 ，并简述由任意二叉树 B 的前序遍历序列和中序遍历序列求二叉树 B

的思想方法。

2. (10 分〉 已知排序码值序列 ｛19,  2,   20,   7,  23,   5,  65,   15｝ ，请写出快速排序第一趟的排序结果 （ 假 设我们选择第一个元素 19 做为基数），  并描述快速排序算法思想 。

3. (10 分） 选取哈希函数 H (k ) = C k ) MOD 11。用二次探测处理冲突 ，试在 一10 的散列地址空间中对

关键字序列 （ 22, 41, 53, 46, 30, 13, 01 ） 造哈希表 ，并求等概率情况下查找成功时的平均查找长度 。 二、算法和程序设计 （每小题 15 分，共 45  分）

1. (15 分〉 编写一算法 ，在不增加辅助空间的前提下 ，将两个递增的单链表合并为一个递增的单链表 。

2. (15 分〉 编写一算法 ，描述如何将一个中序表达式转化为后序表达式 。例如 ，输入如果是 2+3*4+5,

则输出为 234＊十肘 。

3. 05 分〉 编写一函数 in t he ight (struct tree 丰root ） ，求二叉树的高度 。假设空二叉树的高度为 O o struct  tree  定义如下：

struct tree{ int data ;

struct  tree *lef t,  *right ;

II 、操作系统 （ 75 分）

三、简答题 （每小题 6 分，共 30 分）

1. ( 6 分〉 简述操作系统主要功能 。

2. ( 6 分〉 进程状态有哪些 ？这些状态之间如何转换 ？

3. ( 6 分） 产生死锁的四个必要条件 。

4. ( 6 分） TLB ( Translat ion Lookasi de Buf f er ） 快表的作用 。

5. (6 分） 简述 SCAN 扫描算法 （ 电梯算法）。 四、综合题 （每小题 15 分，共 45 分）

1. C 15 分〉 一个采用请求式页面存储的系统 ，其物理内存为 512M 字节 ，虚拟地址空间大小为 4G 字节， 页面大小为 4K 字节 ，试问：

(1） 物理地址应设为多少位 ？

( 2 ） 主存中有多少物理页 ？

( 3 ） 虚拟地址应该设多少位 ？

( 4 ） 虚拟地址空间最多可以有多少页 ？

( 5 ） 页内最大和最小偏移量是多少 ？

2.    (15 分） 有 M 个生产者 凹，P2 ，…，PM 和 K 个消费者 Cl ,  C2 ，…，CK ，一个大小为 n 的环形缓 冲区 ，生产者把产品放入缓冲区 ，消费者从缓冲区取产品来消费 。请用 wai t 和 signal 原语实现生产者 和消费者的同步操作 。

3.   Cl5 分〉 设系统中物理页的数量为 150。在 TO 时刻按表 I 所示分配给三个进程 Pl 、P2 和 P3 。系统

采用银行家算法实施死锁避免策略 。对下列内存请求 ，请分别判断是否安全 ，如果是安全的 ，请给出一 个可能的进程安全执行序列 ：如果不是安全的 ，请说明原因 。

c 1)  进程问到达 ，共需要 60 个物理页 ，当前请求分配 25 页：

( 2 ） 进程 问到达，共需要 50 个物理页 ，当前请求分自己 35 页

考研高分咨询新祥旭罗老师

电话/微信：13701149740

咨询QQ：3219057729