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

ᠥᠪᠥ ᠷ ᠮᠣᠩᠭ ᠣᠯ ᠤᠨ ᠶᠡᠬᠡ ᠰᠤ ᠷᠭᠠᠭᠤᠯ ᠢ ᠶᠢᠨ 20 17 ᠣᠨ ᠤ ᠠᠰᠫ ᠢᠷᠠᠨᠲ ᠡᠯᠰᠡ ᠬᠦ ᠰᠢᠯᠭᠠᠯᠲ ᠠ ᠬᠢᠴᠢ ᠶᠡᠯ ᠲᠥᠷᠥᠯ ᠦᠨ ᠲᠥᠯ ᠥᠭᠡᠯ ᠡᠬᠦ ᠨᠣᠮᠧᠷ ᠵᠢᠴ ᠢ ᠨᠡᠷᠡᠢᠳᠦᠯ ᠄ 893 ︽ ᠳ᠋ᠠᠢᠲ᠋ᠠ ᠶᠢᠨ ᠪᠦᠲᠦᠴ ᠡ᠂ ᠠᠵᠢᠯᠯᠠᠭᠤᠯᠬᠤ ᠰᠢᠰᠲ᠋ᠧᠮ ︾ ᠲᠣᠬᠢᠷᠠᠯ ᠴᠠᠬᠤ ᠲᠤ ᠰᠬᠠᠢ ᠮᠡᠷᠭ ᠡᠵᠢᠯ᠄  ᠺᠣᠮ ᠫᠢᠦ᠋ᠲ᠋ ᠧᠷ ᠤᠨ ᠰᠢᠨᠵᠢ ᠯᠡᠬᠦ ᠤᠬᠠᠭ ᠠᠨ ᠵᠢᠴ ᠢ ᠮᠡ ᠷᠭᠡᠵᠢ ᠯ  ᠵᠥᠭᠡᠯ ᠡᠨ ᠲᠣ ᠨᠣᠭ ᠤᠨ ᠢᠨᠵᠧᠨᠧᠷ ᠢᠩ ***大学招收 2017年硕士研究生初试自命题试题科目代码及名称： 893数据结构与操作系统（自命题）在此试题纸上答题无效 !须使用报考点提供的答题纸答题 ! 本科目考试卷面满分为 150分，考试时长 3小时。数据结构部分（ 75）一 .简答题（ 20分，每个要点 2分） 1. 数据结构研究的主要内容有哪 3部分？简述其内容。 2. 算法的有穷性、确定性和可行性是什么？ 3. n个结点的二又树，第 i层上最多有几个结点？最低高度是多少？ 4. 图有哪 2种遍历方法？简述遍历方法。二 .回答下列问题（ 40分，每小题 8分） 1. 将图 -1中的树转换为二叉树，并给出该二叉树的中序线索树。 2. 将 15， 12， 21， 16， 10， 35， 25， 32， 48，依次插入初始为空二叉査找树，画出二叉查找树。然后删除 21，简述删除步骤，给出结果。 3. 简述迪杰斯特拉（ Dijkstra）算法思想，求图 -2 中 A 到其他各顶点的最短路径长度及最短路径 4. 待排序序列为 12， 8， 14， 9， 21， 15 给出冒泡排序的每趟冒泡后的序列状态给出直接插入排序的每次插入后的序列状态。 5. 简述普里姆（ Pim）算法思想，从 A出发，求图 -3的最小生成树（ MST）。按选中顺序列出 MST的边。三 .算法设计题 (15分，第 1小题 7分，第 2 小题 8分 ) 说明：算法言可使用（类） C、（类） C＋＋就类 Java，请标明你使用的语言。算法中的主要数据结构要说明用途，简要说明算法思想，算法中要有多法中要必要的注释，参数、変量做必要的注释，以增加可读性。 1. 自然数 1到 n存放在一个带表头的单链表中，设计一个算法，将链表拆分成奇数和偶数两个链表。 2. 设计一个递归算法，将一棵以二叉链表存储的二叉树按下列形式输出每个结点，同层的结点输出在同一列上。操作系统部分 (75 分 ) 一 .简答题（本大题共 7小题，共 33分） 1. (4分 )在操作系统中的所谓“虚拟”是指什么 ?可以用哪两种方式来实现虚拟技术 ?常见的虚拟技术有哪些 ? 2. (4分 )什么是临界区 ?什么是临界资源 ? 3. (4分 )死锁发生的必要条件有哪些 ? 4. (5分 )文件有哪几种逻辑结构 ?有哪几种物理结构 ? 5. (5分 )目前广泛采用的目录结构形式是哪种 ?它有什么优点 ? 6. (5分 )I/O软件一般分为哪几个层次 ?在设备寄存器中设置命令是在哪一层完成的 ? 7. (6分 )在较高档的计算机中，存储层次分为哪六级 ? 二 .计算题 (本大题共 4小题，每小题 7分，共 28分 ) 1. 有 A、 B两个程序，程序 A按顺序使用 CPU 10s，使用设备甲 5s，使用 CPU 5s，使用设备乙 10s，最后使用 CPU 10s。程序 B按顺序使用设备甲 10s，使用 CPU10s，使用设备乙 5s，使用 CPU 5，使用设备乙 10s。试问 : 1) 在单道程序环境下，顺序执行程序 A和程序 B， CPU的利用率是多少 ? 2) 在多道程序环境下，并发执行程序 A和程序 B， CPU的利用率是多少 ? 2. 对于下列三个作业，采用不可抢占的调度方式 : 先来先服务 (FCFS)和短作业优先 (SJF)调度算法，分别计算它们的平均周转时间。注意调度在时刻 0.0 就已经开始，时间单位为分钟。 3. 设某作业占有 7个页面，如果在主存中只允许装入 4个工作页面（即工作集为 4），作业运行时访问页面的序号是 1， 2， 3， 6， 4， 7， 3， 2， 1， 4， 7， 5． 6， 5， 2， 1。试用 FIFO与 LRU页面调度算法，列出各自的淘汰页面的序号和页面置换次数，以及最后留驻主存 4 页的页面序号。假设开始的 4个页面已装入主存。 4. 磁盘请求以 10、 22、 20、 2、 40、 6、 38 柱面的次序到达磁盘驱动器。寻道时每个柱面移动需 6ms，磁头起始位于第 20 柱面并向磁道号增加的方向移动，分别计算采用以下算法时的寻道时间。 1) 最短寻道时间优先 SSTF 2) 扫描算法 SCAN（又称电梯调度）。三．应用题（本大题共 2小题，共 14分） 1. （ 8分）利用信号量实现下图所示的前趋关系。 2. （ 6分） 3个进程 P1、 P2和 P3利用同一个单缓冲区 buffer 合作解决数值打印问题： P1 负责将整数放入 buffer； P2 负责将 buffer中的奇数取出打印： P3负责将 buffer中的偶数取出打印。规定 buffer为空时只能放一个数值用于打印。请用记录型信号量的 wait、 signal操作来保证 3个进程的同步。

ᠳ᠋ᠣᠺ ᠤᠩᠰᠢᠵᠤ ᠪᠣᠢ ᠁ ᠲᠦᠷ ᠬᠦᠯᠢᠶᠡᠭᠡᠷᠡᠢ︕
ᠤᠷᠲᠤ ᠬᠤᠭᠤᠴᠠᠭ᠎ᠠ ᠨᠡᠭᠡᠭᠡᠭᠳᠡᠭᠰᠡᠨ ᠦᠭᠡᠢ ᠪᠣᠯ᠂ ᠲᠣᠪᠴᠢᠳᠠᠨ ᠰᠢᠨᠡᠳᠬᠡᠵᠦ ᠦᠵᠡᠭᠡᠷᠡᠢ︕

ᠳ᠋ᠣᠺ ᠢ ᠮᠠᠰᠢᠨ ᠳᠠᠭᠠᠨ ᠪᠠᠭᠤᠯᠭᠠᠪᠠᠯ ᠠᠭᠤᠯᠭ᠎ᠠ ᠬᠠᠢᠢᠬᠤ ᠪᠤᠶᠤ ᠬᠡᠷᠡᠭᠯᠡᠵᠦ ᠠᠰᠢᠭᠯᠠᠬᠤ ᠳᠦ ᠨᠡᠩ ᠬᠢᠯᠪᠠᠷ ᠪᠣᠯᠣᠨ᠎ᠠ

5 ᠮᠥᠩᠭᠥ 0 ᠬᠥᠮᠥᠨ ᠪᠠᠭᠤᠯᠭᠠᠪᠠ

ᠪᠠᠭᠤᠯᠭᠠᠶ᠎ᠠ

VIP ᠪᠣᠯᠵᠤ᠂ ᠬᠤᠪᠢᠶᠠᠯᠴᠠᠭᠰᠠᠨ ᠡᠬᠢ ᠰᠤᠷᠪᠤᠯᠵᠢ ᠶᠢ ᠪᠠᠭᠤᠯᠭᠠᠬᠤ

ᠢᠯᠡᠴᠢᠯᠡᠬᠦ ᠵᠣᠬᠢᠶᠠᠭᠴᠢ ᠶᠢᠨ ᠡᠷᠬᠡ ᠪᠡᠨ ᠬᠠᠮᠠᠭᠠᠯᠠᠬᠤ

word ᠬᠡᠯᠪᠡᠷᠢ ᠶᠢᠨ ᠳ᠋ᠣᠺ ᠬᠡᠷᠪᠡ ᠣᠨᠴᠠᠭᠠᠢ ᠲᠣᠳᠣᠷᠬᠠᠢᠯᠠᠯᠲᠠ ᠦᠭᠡᠢ ᠪᠣᠯ ᠴᠥᠮ ᠵᠠᠰᠠᠵᠤ ᠥᠭᠡᠷᠡᠴᠢᠯᠡᠵᠦ ᠪᠣᠯᠣᠨ᠎ᠠ᠃ ᠤᠷᠢᠳᠴᠢᠯᠠᠨ ᠦᠵᠡᠬᠦ ᠳ᠋ᠣᠺ ᠴᠥᠮ ᠠᠪᠴᠢᠭᠤᠯᠤᠭ᠎ᠠ ᠬᠢᠵᠦ ᠥᠩᠭᠡᠷᠡᠭᠰᠡᠨ ᠪᠣᠯᠬᠣᠷ ᠤᠭ ᠹᠠᠢᠢᠯ ᠢ ᠨᠢ ᠪᠠᠭᠤᠯᠭᠠᠪᠠᠯ ᠨᠡᠩ ᠲᠣᠳᠣᠷᠬᠠᠢ︕

ᠮᠣᠩᠭᠣᠯ ᠳ᠋ᠣᠺ ᠤᠨ ᠬᠥᠮᠥᠷᠭᠡ  ᠤᠨ ᠪᠦᠬᠦ ᠠᠭᠤᠯᠭ᠎ᠠ ᠶᠢ ᠬᠡᠷᠡᠭᠯᠡᠭᠴᠢ ᠡᠴᠡ ᠵᠥᠪᠬᠡᠨ ᠰᠦᠯᠵᠢᠶᠡᠨ ᠠᠨᠳᠠ ᠶᠢᠨ ᠰᠤᠷᠤᠯᠴᠠᠯᠭ᠎ᠠ ᠰᠤᠳᠤᠯᠭᠠᠨ ᠳᠤ ᠵᠣᠷᠢᠭᠤᠯᠤᠨ ᠥᠪᠡᠷᠰᠡᠳ ᠢᠶᠡᠨ ᠠᠴᠢᠶᠠᠯᠠᠨ ᠬᠤᠪᠢᠶᠠᠯᠴᠠᠵᠤ᠂ ᠬᠡᠷᠡᠭᠯᠡᠭᠴᠢ ᠶᠢᠨ ᠪᠢᠴᠢᠭ ᠦᠨ ᠬᠡᠯᠪᠡᠷᠢ ᠶᠢᠨ ᠡᠷᠬᠡ ᠣᠯᠭᠣᠯᠲᠠ ᠦᠭᠡᠢ ᠪᠣᠯᠪᠠᠯ ᠪᠤᠰᠤᠳ ᠬᠡᠷᠡᠭᠯᠡᠭᠡᠨ ᠳᠦ ᠪᠢᠲᠡᠭᠡᠢ ᠣᠷᠣᠭᠤᠯᠤᠭᠠᠷᠠᠢ︕

ᠲᠤᠰ ᠳ᠋ᠣᠺ ᠤᠨ ᠲᠤᠬᠠᠢ

ᠰᠢᠯᠢ ᠶᠢᠨ ᠴᠠᠭᠠᠨ ᠱᠣᠩᠬᠤᠷ

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

ᠳ᠋ᠤᠭᠠᠷ᠄ 20190705163032689259

ᠲᠥᠷᠥᠯ ᠵᠦᠢᠯ᠄ ᠬᠤᠪᠢᠶᠠᠯᠴᠠᠯ ᠤᠨ ᠳ᠋ᠣᠺ

ᠬᠡᠯᠪᠡᠷᠢ᠄ DOCX

ᠶᠡᠬᠡ ᠪᠠᠭ᠎ᠠ᠄ 253.63KB

ᠠᠴᠢᠶᠠᠯᠠᠭᠰᠠᠨ ᠴᠠᠭ᠄ 2019-07-06

ᠬᠣᠯᠪᠣᠭᠠᠰᠤ᠄ https://doc.onon.cn/p-20604.html

ᠬᠠᠭᠤᠯᠬᠤ