ᠥᠪᠥᠷ ᠮᠣᠩᠭᠤᠯ ᠤᠨ ᠶᠡᠭᠡ ᠰᠤᠷᠭᠠᠭᠤᠯᠢ ᠶᠢᠨ 2007 ᠣᠨ ᠤ ᠠᠰᠫᠢᠷᠠᠨᠲ ᠡᠯᠰᠡᠬᠦ ᠰᠢᠯᠭᠠᠯᠲᠠ -- ᠺᠣᠮᠫᠢᠦ᠋ᠲ᠋ᠧᠷ ᠮᠡᠷᠭᠡᠵᠢᠯ .docx

ᠥᠪᠥ ᠷ ᠮᠣᠩᠭ ᠣᠯ ᠤᠨ ᠶᠡᠬᠡ ᠰᠤ ᠷᠭᠠᠭᠤᠯ ᠢ ᠶᠢᠨ 20 07 ᠣᠨ ᠤ ᠠᠰᠫ ᠢᠷᠠᠨᠲ ᠡᠯᠰᠡ ᠬᠦ ᠰᠢᠯᠭᠠᠯᠲ ᠠ ᠬᠢᠴᠢ ᠶᠡᠯ ᠲᠥᠷᠥᠯ ᠦᠨ ᠲᠥᠯ ᠥᠭᠡᠯ ᠡᠬᠦ ᠨᠣᠮᠧᠷ ᠵᠢᠴ ᠢ ᠨᠡᠷᠡᠢᠳᠦᠯ ᠄ 419 ︽ ᠳ᠋ᠠᠢᠲ᠋ᠠ ᠶᠢᠨ ᠪᠦ ᠲᠦᠴ ᠡ᠂ ᠠᠵᠢᠯᠯᠠᠭᠤᠯ ᠬᠤ ᠰ ᠢᠰᠲ᠋ᠧᠮ᠂ ᠺᠣᠮᠫᠢ ᠦ᠋ᠲ᠋ᠧᠷ ᠮᠠᠰ ᠢᠨ ᠤ ᠪᠦᠷᠢᠯ ᠳᠦᠯ ᠦᠨ ᠣᠨᠣᠯ ︾ ᠲᠣᠬᠢᠷᠠᠯ ᠴᠠᠬᠤ ᠲᠤ ᠰᠬᠠᠢ ᠮᠡᠷᠭ ᠡᠵᠢᠯ᠄  ᠺᠣᠮ ᠫᠢᠦ᠋ᠲ᠋ ᠧᠷ ᠤᠨ ᠰᠢ ᠨᠵᠢᠯᠡᠬ ᠦ ᠤᠬᠠᠭᠠᠨ ᠵᠢᠴ ᠢ ᠮᠡ ᠷᠭᠡᠵᠢᠯ  ᠵᠥᠭᠡᠯ ᠡᠨ ᠲᠣ ᠨᠣᠭ ᠤᠨ ᠢᠨᠵᠧᠨᠧᠷ ᠢᠩ ***大学招收 2007 年硕士研究生初试自命题试题 科目代码及名称： 419 综合（ 数据结构与操作系统 ，计算 机组成原理） 在此试题纸上答题无效 !须使用报考点提供的答题纸答题 ! 本科目考试卷面满分为 150 分，考试时长 3 小时。 算法与 数据结构部分 （ 75） 一 . 简答 (10 分，每个要点 2 分 ) 1. 什么是数据的逻辑结构 ?什么是数据的存储结构 ? 2. 算法的可终止性、确定性是指 ? 3. 什么是抽象数据类型 ? 二 . 简要回答下列问题 (35 分，每小题 5 分 ) (1)完成下列折半查找算法 int binarySearch(int key){ int 1 =0; int r=n-1; while (__________){ int m=(l+r)/2, if (list[m]. keykey) __________ ; else __________; ｝ // while return __________; }///~ (2)请将图 .1 的二 叉 树进行中序线索化，画出线索。 (3)请给出图 2 的 3 个拓扑序列 (4)对序列 12， 35， 20， 56， 45， 11， 8， 13， 24 进行冒泡排序，请给出每冒泡一 次后的序 列状态。 (5)将 23， 45， 43， 12， 67， 54， 22， 87 依次插入初始为空的二 叉 查找树，给出最终的二叉 査找树。删除 45，简述删除过程，给出删除 45 后的二 叉 查找树。 (6)请用 Kruscal(克鲁斯卡尔 )算法求图 .3 最小生成树。给出最小生成树及边的选中顺序。 (7)请将图 .4 中的森林转换为二叉树。 三 . 算法设计 (30 分，每小题 10 分 ) 说明 :可使用 (类 ) Pascal、 (类 )C、 (类 )C++或 (类 )Java 语言。 请标明你使用的语言， 算法中的主 要数据结构要说明用途。 简要说明算法思想 ， 算法中要有必要的注释 ， 参数 ， 变量做必要的 注释 ， 以增加可读性 。 (1)用数组 tree[]顺序存储完全二叉树，有 n 个结点，设计一个递归算法，前序遍历 该二叉树。 (2)一个带表头结点的单链表 La，设计一个算法将该链表拆为两个带表头结点的单链 表 La 和 Lb， Lb 是原 La 中的第 2 个、第 4 个、……结点组成。 (3)设一幅地图有 n 个区域 (例如，省 )。用不多于 4 种颜色对这些区域进行着色，任 两相邻的区域着不同颜色。设计相关的数据结构和算法，以一种着色方案 (即哪一个区域 着什么颜色 )为输入，判定该着色方案是否满足着色要求，若满足输出 true，否则输出 false。简单分析你的算法的时间开销。 操作系统部分 (75 分 ) 一 、 判断下列各语句是否正确，若不正确请改正 (共 12 分，每小题 2 分 ) 1)并发性是指若干个事件在不同时刻发生。 2)若进程 A 和进程 B 在临界区上互斥，则当 A 位于其临界区内时，不能打断它的执 行 3) Linux 是与 Uniⅸ兼容的操作系统，它不仅仅是只能运行在 PC 机上。 4)段页式存储管理的段表表目中至少要包括段号、段的内存始址和段长。 5)中断是用户程序转换到操作系统程序的驱动源。 6)对文件进行检索时，检索的起始点必须是根目录 二 、 简答题 (共 28 分，每小题 4 分 ) 1)什么是多道程序设计 ?系统中引入多道程序设计技术后带来哪些好处 ? 2)什么是死锁 ?处理死锁的策略有哪些？ 3)在支持线程的系统中，若使用用户级线程，是每个线程一个堆栈还是每个进程 一 个堆栈 ? 请给予解释。 4)以下工作是在 4 个 I/O 软件层的哪一层完成的 ? a)维护一个最近使用块的缓存 b)向设备寄存器写命令 5)文件有哪几种逻辑结构 ?有哪几种物理结构 ? 6)当某个用户登录一台计算机时，操作系统通常要识别用户，这一过程称为用户验证。请问 目前常用的用户验证方式有哪些 ? 7)可变分区存储管理系统中，若一个进程归还一个内存分区后，空闲分区的个数会发生什么 变化 ? 三 、 计算题 (共 27 分，要求给出计算过程 ) 1)(6 分 )设一多道程序系统 中有 5 个进程 A 到 E，它们几乎同时到达就绪队列。 估计它们的运行时间分别为 10， 6， 2， 4， 8ms，其优先级分别为 3， 5， 2， 1， 4， 其中 5 为最高优先级。对于下列调度算法，计算其平均进程周转时间，可忽略进程 切换的开销。 a)时间片轮转法 (假设每个进程公平共享 CPU 时间 ) b)非抢占式的优先级调度 c)非抢占式的最短进程优先 2)(6 分 )一个计算机有 4 个页桢，其装入时间、上次访问时间和每个页面的 R 位 和 M 位如下所示 (时间以时钟滴答为单位 ): a)NRU 算法将置换哪个页面 ? b)LRU 算法将置换哪个页面 ? c)第二次机会算法将置换哪个页面 ? 3)(6 分 )假定一磁盘有 100 个柱面，编号为 0～ 99，在完成了磁道 25 处的请求后， 当前正在磁道 43 处进行请求服务。磁盘请求的柱面按 38， 6， 40， 2,20,22,10 的次序到 达，寻道时每移动一个柱面需要 10ms，计算以下算法的总寻道时间 。 a)最短寻道优先 b)电梯算法 4)(5 分 )一个系统有 4 个进程和 5 类可分配资源，当前分配和最大需求如下 ： 若保持该状态是安全状态， x 的最小值是多少 ? 5)(4 分 )UNX 系统在节点中使用了 13 个地址项来表示文件的物理地址，其中前 10 项为直接 地址，第 11 项为一次间接地址，第 12 项为二次间接地址，第 13 项为三次间接地址。如果 磁盘块地址需用 4B 表示，磁盘块大小为 4KB，那么可能的最大文件有多大 ？ 四 、 算法描述题 (共 8 分 ) 桌上有一空盘，允许存放一只水果。爸爸可向盘中放苹果，也可向盘中放橘子， 儿子专等吃盘中的橘子，女儿专等吃盘中的苹果。規定当盘空时一次只能放一只 水果供吃者取用，请用 down、 up(或 wait、 signal)操作实现爸爸、儿子、女儿 三个并发进程的同步