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

ᠥᠪᠥ ᠷ ᠮᠣᠩᠭ ᠣᠯ ᠤᠨ ᠶᠡᠬᠡ ᠰᠤ ᠷᠭᠠᠭᠤᠯ ᠢ ᠶᠢᠨ 20 15 ᠣᠨ ᠤ ᠠᠰᠫ ᠢᠷᠠᠨᠲ ᠡᠯᠰᠡ ᠬᠦ ᠰᠢᠯᠭᠠᠯᠲ ᠠ ᠬᠢᠴᠢ ᠶᠡᠯ ᠲᠥᠷᠥᠯ ᠦᠨ ᠲᠥᠯ ᠥᠭᠡᠯ ᠡᠬᠦ ᠨᠣᠮᠧᠷ ᠵᠢᠴ ᠢ ᠨᠡᠷᠡᠢᠳᠦᠯ ᠄ 893 ︽ ᠳ᠋ᠠᠢᠲ᠋ᠠ ᠶᠢᠨ ᠪᠦ ᠲᠦᠴ ᠡ᠂ ᠠᠵᠢᠯᠯᠠᠭᠤᠯ ᠬᠤ ᠰ ᠢᠰᠲ᠋ᠧᠮ ︾ ᠲᠣᠬᠢᠷᠠᠯ ᠴᠠᠬᠤ ᠲᠤ ᠰᠬᠠᠢ ᠮᠡᠷᠭ ᠡᠵᠢᠯ᠄  ᠺᠣᠮ ᠫᠢᠦ᠋ᠲ᠋ ᠧᠷ ᠤᠨ ᠰᠢ ᠨᠵᠢᠯᠡᠬ ᠦ ᠤᠬᠠᠭᠠᠨ ᠵᠢᠴ ᠢ ᠮᠡ ᠷᠭᠡᠵᠢᠯ  ᠵᠥᠭᠡᠯ ᠡᠨ ᠲᠣ ᠨᠣᠭ ᠤᠨ ᠢᠨᠵᠧᠨᠧᠷ ᠢᠩ ***大学招收 2015年硕士研究生初试自命题试题 科目代码及名称： 893数据结构与操作系统 （自命题） 在此试题纸上答题无效 !须使用报考点提供的答题纸答题 ! 本科目考试卷面满分为 150分，考试时长 3小时。 数据结构部分 （ 75） 一 .单项选择题 (每小题 2分，共 20分 ） 1. 下面关于算法描述正确的是 () A.算法最终必须由计算机程序实现 B.为解决某问题的算法与为该问题编写的程序含义是相同的 C.算法的确定性是指指令不能有二义性 D.算法的执行可以无限循环 2. 以下属于顺序结构的是 ( A.二又链表 B.循环链表 C.哈希表 D.邻接表 3. 链表不具有的特点是 ()。 A.插入、删除不需要移动元素 B.可随机访问任一元素 C.不必事先估计存储空间 D.存储空间可以不连续 4. .在有向图 G 的拓扑序列中，若顶点 Vi 在顶点 Vj之前，则说明以下哪种情况是正确的 ()。 A.G中一定有弧＜ Vi， Vj＞ B.G中一定有一条从 Vi到 Vj的路径 C.G中一定没有弧＜ Vi， Vj＞ D.G 中可能有一条从 Vj到 Vi的路径 5. 输入序列为 123，经过以下 ( )栈 操作序列，可以变为 213。 A. push, pop, push, pop, push, pop B. push, push,push,pop, pop, pop C. push, push, pop, pop, push,pop D. push, pop, push push, pop, pop 6. 为了操作方便，用单链表表示的链式队列的队头应设在链表的 ( )位置。 A.表头 B.表尾 C.链中 D.表头和表尾均可 7. 若串 S＝ ‘ 123’ ，其子串的数目是 ( )。 A.8 B.3 C.6 D.7 8. 外部排序的时间主要取决于 ( )。 A.产生归并段的时间 B.读写外存的时间 C.内部归并所需时间 D.都不是 9. 对于有 n个结点的二 叉 树，其高度最小值为 ( )。 A. nlog2𝑛 B. log2𝑛 C. [log2𝑛] +1 D.不确定 10. m阶 B-树是一棵 ()。 A.m叉 排序树 B.m叉 平衡排序树 C.m-1叉平衡排序树 D.m+1叉 平衡排序树 二 .简答与计算题 (每小题 4分，共 20分，要求写出解题步骤 ) 1. 在 N 个元素的顺序表中做顺序查找，若查找成功和査找失败的概率相同，并且查找每 个元素的概率也相同，求总的平均查找长度。 2. 一个 nXn的对称矩阵 A，如果以行为主序将其下三角部分存入一维数组 B中，则 B的长 度为多少 ?并求元素 A[i,j](I=j)在数组 B中对应的下标值。 3. 若顺序 栈 S，其最大容量为 Maxsize， 栈 顶指针 top总是指向栈顶元素，则 top的初 始值应该是什么，写出出 栈 和入 栈 操作。 4. 已知完全二叉树的第七层有 10个叶子结点，则整个二叉树的结点数最少是多少 ? 5. 设有数据逻辑结构为 B=(K,R),K={k1,k2,……,k8}， R={(k1,k3),(k1,k8),(k2,k3)， (k2,k4),(k2,k5)(k5,k6),(k4,k7),(k4,k6)(k4， k8)｝，画出该逻辑结构的邻 接表 。 三 .算法应用题 (每题 5分，共 15分 ) 1. 哈希表长度为 10，哈希函数为 H(ky)=key％ 7，采用线性探测再散列方法解决冲突，将下 面的关键字集 {30,15,21,40,25,26,36,37}放入哈希表 ： (1) 画出哈希表 ； (2) 等概率情况下，计算查找成功和查找失败的平均查找长度。 2. 对初始序列 53， 17， 78， 45， 65， 8， 23， 29， 52， 65， 73，请用归并排序做升序排序， 写出每一趟排序后的结果 。 3. 对如下无向带权图，顶点的编号为 1-6，从顶点 1开始利用 Prim算法生成最小生成树。 要求 : (1) 按照算法步骤依次写出选出的顶点和边。 (2) 画出构造出的最小生成树。 四、算法设计题 (每题 10分，共 20分 ) 1. 假设一个单循环链表，其结点含有三个域 pre、 data、 next。其中 data 为数据域 ;pre 为 指针域，它的值为空指针 (NULL):next为指针域 ,它指向后继结点。请设计算法，将此表改 成双向循环链表。 2. 假设以双亲表示法作为树的存储结构，写出双亲表示的类定义，并编写求树的深度的算 法。 (注 :已知树中结点数 ) 操作系统部分 (75 分 ) 一 .单项选择 (本大题共 10小题，每小题 2分，共 20分 ) 1. 设计多道批处理系统时，首先要考虑的是 ( )。 A、灵活性和可适应性 B、系统效率和吞吐量 C、交互性和响应时间 D、实时性和可靠性 2. 若当前进程因时间片用完而让出处理机时，该进程应转变为 ( )状态。 A、就绪 B、等待 C、运行 D、完成 3. 进程在执行中发生了缺页中断，经操作系统处理后，应让其执行 ( )指令。 A、被中断的前一条 B、被中断的 C、被中断的后一条 D、启动时的第一条 4. 系统采用 SPOOLing技术，实质是将 ( )转化为共享 设备的技术。 A、虚拟设备 B、独占设备 C、脱机设备 D、块设备 5. 用磁带作为文件存贮介质时，文件只能组织成 ( ) A、顺序文件 B、链接文件 C、索引文件 D、目录文件 6. 进程调度时需保护处理机的现场信息，这是指将处理机现场信息保存至 ( )。 A、磁盘 B、相应的寄存器 C、进程的 PCB D、内存系统区 7. 静态重定位的时机是 ( )。 A、程序编译时 B、程序链接时 C、程序装入时 D、程序运行时 8. 常用的文件存取方法有两种 :顺序存取和 ()存取。 A、流式 B、并行 C、索引 D、随机 9. 设备管理程序对设备的管理是借助一些数据结构来进行的，下面的 ( )不属 于设备管理数据结构。 A、 JCB B、 DCT C、 COCT D、 CHCT 10. 采用时间片轮转法进行进程调度是为了 ( )。 A、先来先服务 B、多个终端用户都能得到系统的及时响应 C、优先级较高的进程能得到及时调度 D、需要 CPU最短的进程先执行 二 .简答 (本大题共 5小题，共 29分 ) 1.(6分 )微机操作系统按运行方式可分为哪 3类 ?对每类操作系统举出一个最有代表性的实例 。 2.(5分 )何为抢占方式的进程调度 ?可基于哪些原则抢占 ? 3.(5分 )什么是虚拟存储器 ?有何特征 ? 4.(5分 )目前常用的外存分配方式有哪几种 ? Windows98中的 FAT32采用的是哪种 ?UNX系统 采用的是哪种 ? 5.(8分 )利用记录型信号量和 wait/signal操作实现如下所示的前趋图。 三 ． 计算并回答问题 (本大题共 4小题，共 26分 ） 1. (7分 )一个计算机系统，有一台输入机和一台打印机。现有两道程序并发运行， 且程序 A先开始运行，程序 B后开始运行。程序 A的运行轨迹为 :计算 50ms、打印 100ms、 再计算 50ms、再打印 100ms，结束。程序 B的运行轨迹为 :计算 50ms、输入 80ms、再 计算 100ms结束。 (1) 画出两道程序并发运行的时间关系图。 (2) CPU 有无空闲等待 ?若有，在哪段时间内等待 ?程序 A、 B 有无等待 CPU 的情况 ? 若有，在哪段时间内等待 ? (3) 计算 CPU的平均利用率是多少 ? 2. (7分 )某系统采用银行家算法避免死锁，系统现有 A、 B、 C类型的 3种资源和 4 个进程，在 T0 时刻系统的资源分配状态见下表，此刻系统可利用资源向量为 (2， 1， 2)。 (1)计算系统中各种资源的总数和进程对资源的需求矩阵。 (2)判定此刻系统的安全性。如果是安全的，写出安全序列 ;如果是不安全的，写出 参与死锁的进程。 3. (6 分 )假设柱面的编号从 0 到 199。如果现在读写磁头正在 53 号柱面上执行 输入输出操作，且磁头正在向柱面号增大方向移动，而等待访问者依次要访问的柱面为 98， 183， 37， 122， 14， 124， 65， 67。 (1)给出采用先来先服务 (FCFS)算法时的柱面访问次序，并计算平均寻道长度。 (2)给出采用循环扫描 ( CSCAN)算法时的柱面访问次序，并计算平均寻道长度。 4. (6 分 )某分页存储管理系统中，物理地址占 20 位，逻辑地址中页号占 6 位， 页的大小为 IKB，问 : (1)该系统的内存空间大小是多少 ?每个物理块 (页帧 )的大小是多少 ? (2)逻辑地址共几位 ?每个进程的最大长度是多少 ? (3)若有如下页表，计算逻辑地址 0420H(H表示十六进制 )对应的物理地址是什么 ? 5.