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

ᠥᠪᠥ ᠷ ᠮᠣᠩᠭ ᠣᠯ ᠤᠨ ᠶᠡᠬᠡ ᠰᠤ ᠷᠭᠠᠭᠤᠯ ᠢ ᠶᠢᠨ 20 14 ᠣᠨ ᠤ ᠠᠰᠫ ᠢᠷᠠᠨᠲ ᠡᠯᠰᠡ ᠬᠦ ᠰᠢᠯᠭᠠᠯᠲ ᠠ ᠬᠢᠴᠢ ᠶᠡᠯ ᠲᠥᠷᠥᠯ ᠦᠨ ᠲᠥᠯ ᠥᠭᠡᠯ ᠡᠬᠦ ᠨᠣᠮᠧᠷ ᠵᠢᠴ ᠢ ᠨᠡᠷᠡᠢᠳᠦᠯ ᠄ 893 ︽ ᠳ᠋ᠠᠢᠲ᠋ᠠ ᠶᠢᠨ ᠪᠦ ᠲᠦᠴ ᠡ᠂ ᠠᠵᠢᠯᠯᠠᠭᠤᠯ ᠬᠤ ᠰ ᠢᠰᠲ᠋ᠧᠮ ︾ ᠲᠣᠬᠢᠷᠠᠯ ᠴᠠᠬᠤ ᠲᠤ ᠰᠬᠠᠢ ᠮᠡᠷᠭ ᠡᠵᠢᠯ᠄  ᠺᠣᠮ ᠫᠢᠦ᠋ᠲ᠋ ᠧᠷ ᠤᠨ ᠰᠢ ᠨᠵᠢᠯᠡᠬ ᠦ ᠤᠬᠠᠭᠠᠨ ᠵᠢᠴ ᠢ ᠮᠡ ᠷᠭᠡᠵᠢᠯ  ᠵᠥᠭᠡᠯ ᠡᠨ ᠲᠣ ᠨᠣᠭ ᠤᠨ ᠢᠨᠵᠧᠨᠧᠷ ᠢᠩ ***大学招收 2014 年硕士研究生初试自命题试题 科目代码及名称： 893 数据结构与操作系统 （自命题） 在此试题纸上答题无效 !须使用报考点提供的答题纸答题 ! 本科目考试卷面满分为 150 分，考试时长 3 小时。 数据结构部分 （ 75） 一 . 填空题 (15 分 ) 1. (2 分 )具有 N 个结点的完全二又树的深度为 ________. 2. (2 分 )树的三种主要的遍历方法是 : ____ , ____和层次遍历。 3. (2 分 )采用散列技术实现散列表时，需要考虑的两个主要问题是 : 构造 ________和解决 ________。 4. (2 分 )索引顺序表上的査找分两个阶段 :(1) ________， (2) ________。 5. (1 分 )散列文件中的记录通常是成组存放的。若干的记录组成 一 个存储单位，称作 ________。 6. (3 分 )假设以 S 和 X 分别表示进栈和出栈操作，则对输入序列 a， b， c， d， e 进行一系列 操作 SSXSXSSXXX 之后，得到的输出 序列为 ________。 7. (3 分 )将下三角矩阵 A[18， 18]的下三角部分逐行地存储到起始 地址为 1000 的内存单 元中，已知每个元素占 4 个单元，则 A [7， 5]的地址是 ________。 二 .应用题 (42 分 ) 1. 给定关键字序列 11， 78， 10， 1， 3， 2， 4， 21，给出下列各题 的步骤和结果 。 1)(8 分 )建立一棵二 叉 查找树，并给出删除 78 后的树。 2) (8 分 )构造一棵 Huffman 树 ， 并给出查找成功的平均查找长度 。 3)(8 分 )构造一个最小堆，然后删除 3。 4)(8 分 )构造一个散列表，实现散列查找 (线性探查法， H(k)＝ k%11)。 5)(10 分 )已知一个图的顶点集 V 和边集 E 分别为： V=(1,2,3,4,5,6,7； E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6， (3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25。 用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。 三 .证明题 (10 分 ) 对于任何一棵非空的 K 叉 树，假设叶子结点的个数为 𝑛0而度数为 i 的结点个数为 𝑛𝑖，请 给出 𝑛0和 𝑛2,…… ,𝑛𝑘之间所满足的关系式 𝑛0 = 𝑓(𝑛2,……,𝑛𝑘)要求给出推导过程 。 四、算法题 (8 分 ) 如果用一个循环数组 a[m]表示队列时， m 是数组的最大尺 寸 ，该队列设有队列头指针 front，队列尾指针 rear，计数器 count 用以记录队列中结点的个数，初始时 count， front 和 rear 都是 0。编写实现队列的四个基本运算 :判空、判满、入队、出队 。 操作系统部分 (75 分 ) 一 . 填空 (共 6 小题，每空 1 分，共 12 分 ) 1) 操作系统的基本特性是 ________性 、 ________性 、 ________性和异步性。 2) ________中记录了操作系统所需的、用于描述进程的当前情况以及 控制进程运 行的全部信息。 3) 某系统有 15 台打印机，由 N 个进程共享，每个进程需要 4 台。 当 N 的取值不 超过 ________时，系统不会发生死锁 。 4) 常规存储器管理方式的特征是 ________性和 ________性。 5) 按照传输速率可将 I/O 设备分为 ________设备 、 ________设备和 ________设备 三类 。 6) 文件的逻辑结构可分为两大类 ： ________文件和 ________文件 。 二 . 单项选择 (本大题共 6 小题，每小题 1 分，共 6 分 ) 1. 操作系统有多种类型 :允许多个用户将一批作业提交给计算机系 统集中处理的操作系统 称为 ( )。 A.批处理操作系统 B.分时操作系统 C.实时操作系统 D.微机操作系统 2. 管道通信是通过 ( )实现进程间的通信的 。 A.信箱 B.文件 C.消息 D.报文 3. 采用资源剩有法可解除死锁，还可以采用 ( )方法解除死锁。 A.执行并行操作 B.拒绝分配新资源 C.撤销进程 D.修 改 信号量 4. ( )存储管理方案不能适应多道程序设计 。 A.单一连续分配 B.分页 C 固 定式分区分配 D.分段 5. 下面关于设备独立性的论述中 ，（ ） 是正确的论述 。 A.是指 I/O 设备具有独立执行 I/O 功能的一种特性 B 是指用户程序独立于具体使用的物理设备的一种特性 C.是指能独立实现设备共享的一种特性 D.是指设备驱动独立于具体使用的物理设备的一种特性 6. 绝对路径是从 ()开始的一条指向指定文件的路径 A.用户文件目录 B.父 目 录 C.当前目录 D.根目录 三 . 判断对错 (共 6 小题，每小题 2 分，共 12 分 ) 1. 系统调用命令 就是访管指令，它的功能是由便件直接提供的。 （ ） 2. 一 个进程正在临界区内执行时，不能被中断。 ( ) 3. 在引入线程的操作系统中，线程是独立运行和独立调度的基本单位 （ ） 4. 页面置换算法中的最佳置换算法仅仅是个理论算法，在实际中很难实现。 ( ) 5. 引入缓冲区能使 CPU 与 I/0 设备之间速度不匹配的情况得到改善，但并不能减少设备中 断 CPU 的次数。 ( ) 6. 隐式链接结构可以提高文件存储空间的利用率，但不适合文件的随机存取。 ( ) 四 . 回答问题 (共 8 小题，共 45 分 ) 1) (4 分 )WO 控制方式有哪四种 ? 2) (5 分 )操作系统的主要功能是什么 ? 3) (6 分 )菜系统采用时间片轮转调度算法，某个时刻根据用户要求创建了一个进 程 P，进程 P 在其存在过程中依次经历了 5 个阶段 (a)进程调度选中了 P 古用 PuU 运行 (b)P 运行一个时间片后被迫让出 CPU (c)进程调度再次选中 P 运行， P 运行中提出资源申请，没有得到满足 (d)P 等待一段时间后得到资源 ; (e)进程调度再次选中 P， P 运行完毕。 请分别给出进程 P 在 5 个阶段的状态变化。 4) (6 分 )有 4 个进程 P1、 P2、 P3 和 P4，其执行时间分别为 6、 5、 7 和 4。假设在 0 时刻，各进程按 P1、 P2、 P3、 P4 的顺序同时依次到达就绪队列，请分别计 算采用先来先服务调度算法和时间片 轮转调度算法 (时间片＝ 3)时，进程的调 度次序和平均周转时间 。 5) (6 分 )某系统有 A、 B、 C、 D 四类资源可供五个进程 P1、 P2、 P3、 P4、 P5 共享。 系统对这四类资源的拥有量为 :A 类 3 个、 B 类 14 个、 C 类 12 个、 D 类 12 个。 进程对资源的需求和分配情况如下 : 按银行家算法回答下列问题 (a)现在系统中的各类资源还剩余多少 ? (b)现在系统是否处于安全状态 ?为什么 ? 6) (6 分 )某操作系统采用动态分区分配存储管 理方案，用户区大小为 512KB，起 始地址为 0，初始时用户区中无任何进程。现有如 下序列 :A 进程申请 300KB， B 进程申请 100KB， A 进程释放 300KB， C 进程申请 150KB， D 进程申请 30KB， E 进程申请 40KB， F 进程申请 60KB， D 进程释放 30KB。回答下列问题： (a)采用首次适应算法完成上述序列，用户区中还存在哪些空闲分区 ?(给出起始地 址和大小 ) (b)采用最佳适应算法完成上述序列，用户区中还存在哪些空闲分区 ?(给出起始地 址和大小 ) 7) (6 分 )若干个等待访问磁盘的进程依次要访问的柱面为 20， 44， 40， 4， 80， 12， 76。假设每移动一个柱面需要 3 毫秒时间，磁头。当前位于 40 号柱面， 分别计算在先来先服务 (FCF9)和最短寻道时间优先 (SSTF)算法下完成上述访问 总共花费的寻道时间。 8) (6 分 )利用记录型信号量和 wait/signal 操作来描述如下所示的前趋图。