资源描述
浙江工商大学 2017 年全国硕士研究生入学考试试卷 （ A ） 卷考试科目 ： 845 计算机基础综合 总 分 ： 150 分 考 试 时 间 ： 3 小时第 I 部分 数据结构 （ 75 分 一 、 简 答 题 （每小题 7 分 ， 共 42 分）1. 有一份电文中共使用五种字符 ： a,b,c,d,e ， 它 们 的 出 现 频 率 依 次 为 15, 18, 16, 13, 110， 请画出对应的编码赫夫曼树 （ 请 按 照左子树根结点的权小于等于右子树根结点的权的次 序构造 ） ， 并求出该树的带权路径长度 。2. 已 知 一 棵 二 叉 树 的 前 序 和 中 序 序 列 ， 建 立 该 二 叉 树 ， 并 求 该 二 叉 树 的 后 序 序 列 。前序序列 ： 8, 6, 3, 1. 2, 5, 4, 9, 7中 序 序 列 ： 1, 2, 3, 4, 5, 6, 8, 7, 93. 给定表 （ 23 ， ”， 42 ， ”， 78, 95, 22, 35 ） ， 请 将 表 调 整 成 初 始 最 大 堆 。4 . 请描述克鲁斯卡尔 （ Kruskal ） 构造最小生成树算法 。5. 设 一 数 列 的 输 入 顺 序 ， 为 1234 ， 若 采 用 堆 枝 结 构 ， 试 问 通 过 入 出 挽 操 作 ， 能 否 得 到 合 法 序列 3241 ， 如 果 能 ， 则 给 出 得 到 这 个 序 列 相 应 的 push 和 pop 操 作 。6. 阅 读 下 列 程 序 ， 说 明 该 函 数 实 现 了 ， 什 么 功 能 。 若 原 单 链 表 中 数 据 结 点 的 值 按 顺 序 分 别 为1,3,6,4, 2,S ， 调 用 该 函 数 后 ， 结 点 值 有 何 变 化 ？typedef struct node int data;st俨 uct node *next ;:struct node 手 u nc(st r、 uct node *head )struct node *middle,*tail,*lead ; tail = middle = NUL L;lead = head; while ( lead )midd le = lead ;lead = lead - next ; midd le- next = tail; tail= midd le;ret u俨 n middle;二 、 程 序 设 计 共 33 分1. ( 12 分） 若以单链表作为存储结构 ， 编 写 一 算 法 ， 删 除 该 线 性 表 中 所 有 大 于 a 且小于 b 的元素 （若表中存在这样的元素） 同时释放被删除结点空间 ， 假 设 线 性 表 中 的 元 素 按 递 增 有 序 排 列 。2. ( 9 分） 设棵二叉树以二叉链表为存储结构 ， 结 点 结 构 为 !child !data jrchild 。设计一个 算法 ， 求 在 前 根 序 列 中 处 于 第 k 个 位 置 的 结 点 。3. ( 12 分） 试写一算法 ， 将 两 棵 二 叉 排 序 树 合 并 为 一 棵 二 叉 排 序 树 。 答案写在答题纸上 ， 写 在 试 卷 上 无 效 第 1 页 （ 共 2 页）第口部分 操作系统 （ 75 分 三 、 简答题 每小题 6 分 ， 共 30 分 1. 简述 引 起进程调度的原因 。2. 比较分段和分页两种内存管理机制 的不同。3. 产生死锁条件及解决方法 。4. SPOOLing 技 术 。5. 电梯调度算法。四 、 综 合 题 （ 每 小 题 15 分 ， 共 45 分）1. (15 分） 在分页存储管理系统中 ， 按 如 下 次 序 访 问 页 ： 10 6 8 7 10 6 20 10 6 8 7 20 ， 假 定 分 配 的 物 理 块 数 为 3， 试 分 别 计 算 采 用 如 下 页 面 置 换 算 法 时 的 缺 页 次 数: (1 ） 先进先出置换算法 （ FIFO); ( 2 ） 最近最久未使用算法 C LRU ） 。2. (15 分 某电信营业厅提供 1个取号机 、 2 个服务窗口和 10 个供客户等待的座位 。 客户 到达 后 ， 如有空位则取号 ， 然后等待叫 号 ： 当营业员空闲 时 ， 则叫号选取一位客户 ， 并提 供服务 。 请用 P, V C 或 wai t 、 signal ) 操作来同步上述过程 ，要 求 ： (1 ） 写出所需要的信 号量及初始值 ： （ 2 ） 用伪码写出上述过程 。3. (15 分） 某文件系统采用混合索 引 分配方式 ， 如图 2 所 示 ， 有 10 个直接块 （ 每个直接块 指向一个数据块） ， 1 个一级间接块 ， 1个二级间接块和 1个三级间接块 ， 间接块指向的是 一个索 引 块 ， 每个索引块和数据块的大小均为 512 字 节 ， 索 引 块编号大小为 4 字 节 。 曰 ： (1 ） 如 只 使用直接块 ， 文件最大为多少字节 ？ ( 2 ） 在该系统中能存储的文件最大是多少? ( 3 ） 如读取某文件第 l OM 字节的内容 ， 需要访问磁盘几次 ？答案写在答题纸上 ， 写 在 试 卷 上 无 效 第 2 页 （ 共 2 页
展开阅读全文