资源描述
科目代 码 ： 922 科目 名称 ： 数据 结构 与操 作系 统 ( 专 业学位 ) 第 1 页 共 4 页 南 京 航 空 航 天 大学 2 0 1 7 年 硕 士 研 究生 入 学 考 试 初 试试 题 （ A 卷 ） 科目代码 : 922 科目名称 : 数据结构与操作系统 ( 专业学位 ) 满分 : 150 分 注 意 : 认 真阅 读答 题纸上 的注 意事项 ； 所有答案 必须 写在 答 题纸 上 ， 写在 本试 题纸或 草稿 纸上均无效 ； 本试题纸须随 答题 纸一起装入试题袋中 交回 ！ 数 据结 构部分 （ 7 5 分 ） 1 （ 5 分 ） 已知带权图如下所示 ， 用 Kruskal 算法产生最小生成树 ， 并 说明算法思想 。 2 （ 10 分 ） 为一个家谱管理程序设计一种数据结构 ， 以一个四代人 ， 11 个家庭成员为例 ，（ A 有 3 个孩子 A1 、 A2 、 A3 ； A1 有 2 个孩子 A 11 、 A12 ； A2 无子 ， A3 有 3 个孩子 A31 、 A32 、A33 ； A11 有 1 个孩子 A 111 ； A32 有 1 个孩子 A 321 ； 其余尚无子 ） ， 画出家谱示意图 ， 给出所设计的存储结构示意图 ， 并给出在该存储结构上输出第 k 代所有人员的算法思想 。 3. （ 10 分 ） 设有 8 个字符 （ a, b, c, d, e, f, g, h ） ， 其权值为 （ 48,15,20,12,6,61,8,10 ） ，给出进行 Huffman 编码 所用的数据结构和求解过程数据结构中数据的最后结果 。 4 （ 10 分 ） 已知输入数据序列为 (58,68,42,10,88,32,70,52,55,46 ) ， 给出建立 3 阶 B -树示意图 ， 再给出删除 55 ， 70 后的 B - 树 。 5 （ 10 分 ） 试用 Dijkstra 算法 ， 求下图中从 V1 到其余各顶点的最短路径 ， 给出实现算法所用的数据结构和求解过程中每一步的状态 。 V 2 V 4 V 5 V 6 V 1 V 37 2 5 8 6 1 0 3 1 0 V 2 V 6 V 3 V 4 V 1 V 5 2 1589 4 1 8 3 科目代 码 ： 922 科目 名称 ： 数据 结构 与操 作系 统 ( 专 业学位 ) 第 2 页 共 4 页 6 （ 10 分 ） 设 A 、 B 为 递 减 有序 （ 元素值为整型 ） 的单链表 ， 编写函 数 ， 利用原结点将它们合 并 成 一 个 递 增 有 序 的单 链 表 ， 相 同 元素 值 只保 留 一 个 结 点 。 先 给 出算 法 思 想 ， 再 写出 相应代码 。 7. （ 10 分 ） 设二叉树 T ， 用二叉链表结构存储 。 编写函数 ， 对于每个元素值为 x 的结点 ，删去以它为根的子树 ， 并释放 相 应的空间 。 要求先给出算法思想 ， 再写出相应代码 。 8. （ 10 分 ） 设有 n 个学 生成绩 （ 0 - 100 整数 ） 的顺序结构线性表 L ， 编写函数 ， 将该线性表中调整为成绩及格 （ 大于等于 60 ） 在不及格之前 ， 要求 T(n)=O(n), S(n)=O(1) 。 先给出算法思想 ， 再写出相应代码 。 操 作系 统 部分 （ 7 5 分 ） 1. 单选题 （ 10 分 ， 每题 1 分 ) （ 1 ） 在下列系统中 ， ( ) 是实时系统 。 A . 计算机激光照排系统 B. 军用反导弹系统 C. 办公自动化系统 D. 计算机辅助设计系统 （ 2 ） . 引入多道程序的目的在于 ( ) 。 A. 充分利用 CPU ， 减少 CPU 等待时间 B 提高实时响应速度 C. 有利于代码共享 ， 减少主 、 辅存信息交换量 D 解放 cpu 对外设的管理 （ 3 ） 已经获得除 ( ) 以外的所有运行所需资源的进程处于就绪状态 A. 存储器 B 打印机 C CPU D 磁盘空间 （ 4 ） 采用时间片轮转法调度是为了 ( ) 。 A. 多个终端都能得到系统的及时响应 B. 先来先服务 C. 优先级较高的进程得到及时调度 D. 需 CPU 最短的进程先做 （ 5 ） 在一段时间内只允许一个进程访问的资源 ， 称为 ( ) 。 A. 共享资源 B 临界区 C 临界资源 D 共享区 （ 6 ） . 并发性是指若干事件在 ( ) 发生 。 A 同一时刻 B 同一时间间隔内 C 不同时刻 D 不同时间间隔内 （ 7 ） 管道通信是以 ( ) 进行写入和读出 。 A 消息为单位 B 自然字符流 C 文件 D 报文 （ 8 ） 操作系统中有一组特殊的程序 它们不能被系统中断 ， 在操作系统中称为 ( ) A. 初始化程序 B 原语 C 子程序 D. 控制模块 科目代 码 ： 922 科目 名称 ： 数据 结构 与操 作系 统 ( 专 业学位 ) 第 3 页 共 4 页 （ 9 ） . 在分段管理中 ( ) 。 A 以段为单位分配 ， 每段是一个连续存储区 B 段与段之间必定不连续 C 段与段之间必定连续 D 每段是等长的 （ 10 ） . 通道是一种 ( ) 。 A.I O 端口 B 数据通道 C I O 专用处理机 D 软件工具 2. 简答 题 （ 20 分 ， 每题 4 分 ） （ 1 ） . 系统型线程和用户型线程有何区别 ？ （ 2 ） . 多级反馈队列调度算法是如何工作的 ？ （ 3 ） . 分段式系统和分页式系统有何区别 ？ （ 4 ） . 引入缓冲的目的是什么 ， 有哪些常见的缓冲模式 ？ （ 5 ） . SPOOLING 技术如何实现 ， 在操作系统中起何作用 ？ 3 . （ 9 分 ） 设有三道作业 ， 它们的提交时间及执行时间由下表给出 : 作业号 提交时间 执行时间 1 8.5 2.0 2 9.2 1.6 3 9.4 0.5 （ 1 ） 周转时间和带权周转时间的区别是什么 ， 为何引入带权周转时间 ？（ 2 分 ） （ 2 ） 试计算在单道程序环境下 ， 采用先来先服务调度算法和最短作业优先调度算法时的平均周转时间 。 （ 7 分 ） 4 . （ 9 分 ） 某系统有 A 、 B 、 C 、 D 四类资源可供五个进程 P1 、 P2 、 P3 、 P4 、 P5 共享 。 系统共有这四类资源为 :A 类 3 个 、 B 类 14 个 、 C 类 12 个 、 D 类 12 个 。 进程对资源的需求和分配情况如下 ： 已占有资源 最大需求数 进程 A B C D A B C D P1 0 0 1 2 0 0 1 2 P2 1 0 0 0 1 7 5 0 P3 1 3 5 4 2 3 5 6 P4 0 6 3 2 0 6 5 2 P5 0 0 1 4 0 6 5 6 科目代 码 ： 922 科目 名称 ： 数据 结构 与操 作系 统 ( 专 业学位 ) 第 4 页 共 4 页 （ 1 ） 现在系统是否处于安全状态 ？（ 4 分 ） （ 2 ） 如果进程 P2 提出需要 A 类资源 0 个 、 B 类资源 4 个 、 C 类资源 2 个和 D 类资源 0 个 ，系统能否去满足它的请求 ？（ 5 分 ） 5 . （ 9 分 ） 某分页系统 ， 每个页面长为 1KB ， 某时刻该用户进程的页表如下 ： 页号 物理块号 是否在快表中 0 8 是 1 7 是 2 4 否 3 1 0 否 4 5 否 5 3 是 6 2 是 （ 1 ） 请写出分页系统的地址转换过程 （ 3 分 ） （ 2 ） 计算两个逻辑地址 ： 0AC5H 、 1AC5H 对应的物理地址 （ 16 进制表示 ） 。 （ 3 分 ） （ 3 ） 已知主存的一次存取为 2us ， 对于快表的查询时间可以忽略 ， 则访问上述两个逻辑地址分别耗费多少时间 ？（ 3 分 ） 6 . （ 9 分 ） 在某请求 分页管理系统中 ， 作业 执行时一次访问如下页面 ： 1 ， 4 ， 3 ， 1 ， 2 ， 5 ，1 ， 4 ， 2 ， 1 ， 4 ， 5 ， 若分配给该作业的主存块数为 3. （ 1 ） 页面置换算法在虚拟存储管理中的重要性 。 （ 2 分 ） （ 2 ） FIF O, LRU 算法各适用于什么场合 （ 3 分 ） （ 3 ） 计算 FIFO ， LRU ， 页面置换算法 ， 试求出缺页中断次数 。 （ 4 分 ） 7 . （ 9 分 ） 一家四口人 ， 儿子喜欢吃苹果 ， 由父亲负责购买 , 女儿喜欢吃橘子 ， 由母亲负责 购 买 。 父 亲 和母 亲 购买 水 果 后 放 到 家中 的 抽屉 里 ， 儿 子 和 女儿 从 抽屉 里 取 出 水 果 。 假 设抽屉只能容纳 20 个水果 ， 同时只能一人开关 , 用纪录型信号量同步父母子女四个进程 。
展开阅读全文