资源描述
浙江工商大学 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 ） 页内最大和最小偏移量是多少 ？答案写在答题纸上 ， 写 在 试 卷 上 无 效 第 l 页 （ 其 2 页）2. (15 分） 有 M 个生产者 凹 ， P2 ， ， PM 和 K 个消费者 Cl , C2 ， ， CK ， 一 个大小为 n 的环形缓 冲区 ， 生产者把产品放入缓冲区 ， 消费者从缓冲区取产品来消费 。 请用 wai t 和 signal 原语实现生产者 和消费者的同步操作 。3. Cl5 分 设系统中物理页的数量为 1 50。 在 TO 时刻按表 I 所示分配给三个进程 Pl 、 P2 和 P3 。 系 统采用银行家算法实施死锁避免策略 。 对 下 列 内 存 请 求 ， 请 分 别 判 断 是 否 安 全 ， 如 果 是 安 全 的 ， 请 给 出 一 个可能的进程安全执行序列 ： 如 果 不 是 安 全 的 ， 请 说 明 原 因 。c 1) 进程问到达 ， 共 需 要 60 个物理页 ， 当 前 请 求 分 配 25 页 ：( 2 ） 进程 问到 达 ， 共需要 50 个物理页 ， 当前请求 分 自 己 35 页 。表 l TO 时刻系统状态进程 最大物理页需求量 己分配物理页数量Pl 70 25P2 60 40P3 60 45答案写在答题纸上 ， 写 在 试 卷 上 无 效 第 2 页 （ 共 2 页
展开阅读全文