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

ᠥᠪᠥ ᠷ ᠮᠣᠩᠭ ᠣᠯ ᠤᠨ ᠶᠡᠬᠡ ᠰᠤ ᠷᠭᠠᠭᠤᠯ ᠢ ᠶᠢᠨ 20 08 ᠣᠨ ᠤ ᠠᠰᠫ ᠢᠷᠠᠨᠲ ᠡᠯᠰᠡ ᠬᠦ ᠰᠢᠯᠭᠠᠯᠲ ᠠ ᠬᠢᠴᠢ ᠶᠡᠯ ᠲᠥᠷᠥᠯ ᠦᠨ ᠲᠥᠯ ᠥᠭᠡᠯ ᠡᠬᠦ ᠨᠣᠮᠧᠷ ᠵᠢᠴ ᠢ ᠨᠡᠷᠡᠢᠳᠦᠯ ᠄ 891 ︽ ᠺᠣᠮ ᠫᠢᠦ᠋ ᠲ᠋ᠧᠷ ᠮᠡᠷᠭ ᠡᠵᠢᠯ ᠦᠨ ᠶ ᠡᠷᠦᠩᠬᠡ ᠢ ᠰᠡᠳ ᠦᠪ ︾ (ᠳ᠋ᠠᠢᠲ᠋ᠠ ᠶᠢᠨ ᠪᠦᠲᠦᠴ ᠡ᠂ ᠠᠵᠢᠯᠯᠠᠭᠤᠯ ᠬᠤ ᠰ ᠢᠰᠲ᠋ ᠧᠮ ᠪ ᠠᠭᠲᠠᠨ ᠠ) ᠲᠣᠬᠢᠷᠠᠯ ᠴᠠᠬᠤ ᠲᠤ ᠰᠬᠠᠢ ᠮᠡᠷᠭ ᠡᠵᠢᠯ᠄  ᠺᠣᠮ ᠫᠢᠦ᠋ᠲ᠋ ᠧᠷ ᠤᠨ ᠰᠢᠨᠵᠢ ᠯᠡᠬᠦ ᠤᠬᠠᠭ ᠠᠨ ᠵᠢᠴ ᠢ ᠮᠡ ᠷᠭᠡᠵᠢ ᠯ  ᠵᠥᠭᠡᠯ ᠡᠨ ᠲᠣ ᠨᠣᠭ ᠤᠨ ᠢᠨᠵᠧᠨᠧᠷ ᠢᠩ ***大学招收 2008 年硕士研究生初试自命题试题 科目代码及名称： 891 计算机专业 综合 （ 包含 数据结构与操作系统 ） 在此试题纸上答题无效 !须使用报考点提供的答题纸答题 ! 本科目考试卷面满分为 150 分，考试时长 3 小时。 算法与 数据结构部分 （ 75） 一 . 简答 (10 分，每个要点 1 分 ) 1. 数据的存储结构有哪几种 ? 2. 什么是算法 ? 3. 什么是非线性结构 ? 二 . 简要回答下列问题 (35 分，每小题 5 分 ) 1)完成下列非递归的中序遍历二叉树的算法 stack 是一个栈，主要函数有 int empty()、 void push(p)、 BTNode*pop() void inorder Travel(BTNode* root) { p=root; while (p p=p- } else { p= ; visite (p); ∥访问 p p=p- ; } ∥ while } ///~ 2)请给出图 .1 中二叉树的前序、中序和后序三种遍历序列。 (3)顶点集合为｛ A， B， C， D， E， F｝，从 A 出发，深度优先遍历图 .2，请给出遍历序列和遍 历生成树 。 (4)对序列 35， 12， 20， 11， 45， 24， 8， 13， 56 进行归并排序，请给出每越归并后的序列 状态 (5)将 23， 45， 43， 12， 67， 54， 22 依次插入初始为空的 Hash 表， Hash 函数是 ： H(k)=k％ 7，用线性探测再散列解决冲突。 (6)请用 Prim(普里姆 )算法求图 .3 的最小 生成树， A 是起点，给出最小生成树及边的选中顺 序 。 (7)a,b,c,d,e,f,g 的权分别是 2， 5， 3， 8， 1， 4， 6。请构造其 Huffman 树。 三 . 算法设计 (30 分，每小题 10 分 ) 说明 :可使用 (类 ) Pascal、 (类 )C、 (类 )C++或 (类 )Java 语言。 请标明你使用的语言， 算法中的主 要数据结构要说明用途。简要说明算法思想 ， 算法中要有必要的注释 ， 参数 ， 变量做必要的 注释 ， 以增加可读性 。 (1)用数组 a[n]和 b[n]表示两个 n 位正整数 (也可能少于 n 位 )，设计一个算法，求它们的和， 和放在数组 c[n]中，最高进位溢出时，舍去之，有溢出返回 1，否则返回 0。 (2)一个带表头结点的双向链表 La，设计一个算法将该链表逆转。例如 : (3)数组 heap[n]是一整数序列，且是一不减序列。设计一个算法将其调整为一个大顶堆。算 法的时间复杂度为 O(n)。 操作系统部分 (50 分 ) 一 . 填空 (每空 1 分，共 12 分 ) 1)操作系统的五大基本功能包括 :CPU 管理、 _________管理、 _________管理、 ________管理 和操作系统接口 。 2)若系统采用在内核中实现线程，则 CPU 分配的基本单位是 _________。 3)使用资源的静态分配方法预防死锁时，破坏了产生死锁的四个必要条件中的 ________条件。 4)地址重定位是指将 _________地址转换成 _________地址。 5)根据信息交换单位可将设备分为 _________设备和 _________设备。 6)常用的文件物理结构有 3 种 _________、 _________和 _________。 二 . 单项选择 (每小题 2 分，共 12 分 ) 1)操作系统是一种 ( )。 A.应用软件 B.工具软件 C.系统软件 D.实用软件 2)下面的进程状态转换中 ( )是不可能的。 A.运行→就绪 B.就绪→运行 C.运行→阻塞 D.就绪→阻塞 3)若信号量 S 的初值为 3，当前值是 -2，则表示有 ( )个在该信号量上等待的 进程。 A.2 B.3 C.4 D.5 4)在可变分区管理方案中，最佳适配算法将空困分区按 ( )次序进行排列。 A.容量递增 B.一容量递减 C.地址递增 D.地址递减 5)（ ）是操作系统中采用的以空间换取时间的技术。 A.覆盖与交换技术 B.虚拟存储技术 C. Spooling 技术 D.通道技术 6)在文件系统中解决“命名冲突”通常采用 ( )方法。 A.存取控制 B.多级目录 C .索引结构 D.文件共享 三 . 判断对错 (每小题 2 分，共 10 分 ) 1)并发性是指若干个事件在同一时刻发生。 ( ) 2)段页式存储管理中的逻辑地址是二维的。 ( ) 3)引入缓冲技术的最主要目的是为了解决 CPU 与外设之间速度不匹配的矛盾。 4)UNX 的 i 结点是文件内容的一部分。 ( ) 5)屏蔽所有中断是特权指令。 ( ) 四 . 回答问题 (共 41 分 ) 1)(3 分 )一个分层结构的操作系统由棵机、用户、 CPU 调度、文件管理、内存管理和设备管 理等部分组成，请按分层结构的原则从下到上将各都分重新排列。 2)(4 分 )画出 I/O 软件系统的层次 。 3)(4 分 )系统采用位图来管理磁盘空闲空间，设位图的初值为 1000 0000 0000 0000， ,系统总 是从最小编号的块开始寻找空闲块，所以在有 6 块的文件 A 写入之后，该位图为 1111 1110 0000 0000 请说明在完成下列每个附加动作之后位图的值。 a)写入有 5 块的文件 B。 b)删除文件 A。 4)(6 分 )假定 4 个进程到达就绪队列的时间和估计运行时间如下表所示 ： 分别采用下列进程调度算法，给出进程的调度次序，并计算平均进程周转时间。 a)时间片轮转法 (时间片长度为 2) b)非抢占 式的最短进程优先 5)(6 分 )一个程序有 5 个虚拟页面，编号从 0 到 4，其页面问次序为 :012301401234，计算将 FIFO 页面置换算法用到 3 个页 帧 和 4 个页 帧 时，分别会发生多少次页面失效 (给出计算过程 )? 你从中得到的结论是什么 ? 6)(6 分 )磁盘请求以柱面 70， 120， 80， 160， 60， 150 的次序进入磁盘驱动器，假设磁头起 始于柱面 130，且正向柱面 0 方向移动，求在先来先服务和电梯算法下的磁头移动顺序及移 动总量 (以柱面数计 )。 7)(6 分 )系统中有 5 个进程和 4 类资源，在银行家算法中，若出现如下资源分配状况： 问： a)当前系统是否安全 ? b)如果进程 P3 发出请求｛ 0， 1， 0｝，系统能否分配给它 ?为什么 ? 8)(6 分 )四个进程 A、 B、 C、 D 都要读一个共享文件 F，系统允许多个进程同时读文件 F。但 限制进程 A 和进程 C 不能同时读文件 F，进程 B 和进程 D 也不能同时读文件 F。为了使这四 个进程并发执行时能按系统要求使用文件，现用信号量和 down/up 操作进行管理。请回答 下面的问题 : a)应定义的信号量及初值 :_______________________________________。 b)在下列程序中填上相关信号量的 down/up 操作，以保证四个进程能正确并发工作。 A() B() C() D() { { { { ① ； ③ ； ⑤ ； ⑦ ； read F； read F； read F； read F； ② ； ④ ； ⑥ ； ⑧ ； } } } }