1、 科目代码：922 科目名称：数据结构与操作系统(专业学位) 第 1 页 共 4 页 南京航空航天大学南京航空航天大学 2012017 7 年年硕士硕士研究生入学考试初试试题研究生入学考试初试试题（ A A 卷卷 ） 科目代码: 922 科目名称: 数据结构与操作系统(专业学位) 满分: 150 分 注意: 认真阅读答题纸上的注意事项认真阅读答题纸上的注意事项；所有答案必须写在所有答案必须写在答题纸答题纸上上，写在本试题纸或草稿纸上均无写在本试题纸或草稿纸上均无效效；本试题纸须随答题纸一起装入试题袋中交回本试题纸须随答题纸一起装入试题袋中交回！ 数据结构部分数据结构部分（7575 分分） 1
2、（5 分）已知带权图如下所示，用 Kruskal 算法产生最小生成树，并说明算法思想。 2 （10 分）为一个家谱管理程序设计一种数据结构，以一个四代人，11 个家庭成员为例，（A 有 3 个孩子 A1、A2、A3；A1 有 2 个孩子 A11、A12；A2 无子，A3 有 3 个孩子 A31、A32、A33；A11 有 1 个孩子 A111；A32 有 1 个孩子 A321；其余尚无子） ，画出家谱示意图，给出所设计的存储结构示意图，并给出在该存储结构上输出第 k 代所有人员的算法思想。 3. （10 分）设有 8 个字符（a, b, c, d, e, f, g, h） ，其权值为（48,1
3、5,20,12,6,61,8,10） ，给出进行 Huffman 编码所用的数据结构和求解过程数据结构中数据的最后结果。 4 （10 分）已知输入数据序列为 (58,68,42,10,88,32,70,52,55,46 )，给出建立 3 阶 B-树示意图，再给出删除 55，70 后的 B-树。 5 （10 分）试用 Dijkstra 算法，求下图中从 V1 到其余各顶点的最短路径，给出实现算法所用的数据结构和求解过程中每一步的状态。 V2 V4 V5 V6 V1 V37 2 5 8 6 10 3 10 V2 V6 V3 V4 V1 V5 2 1 5 8 9 4 18 3 科目代码：922 科目
4、名称：数据结构与操作系统(专业学位) 第 2 页 共 4 页 6 （10 分）设 A、B 为递减有序（元素值为整型）的单链表，编写函数，利用原结点将它们合并成一个递增有序的单链表，相同元素值只保留一个结点。先给出算法思想，再写出相应代码。 7.（10 分）设二叉树 T，用二叉链表结构存储。编写函数，对于每个元素值为 x 的结点，删去以它为根的子树，并释放相应的空间。要求先给出算法思想，再写出相应代码。 8.（10 分）设有 n 个学生成绩（0-100 整数）的顺序结构线性表 L，编写函数，将该线性表中调整为成绩及格（大于等于 60）在不及格之前，要求 T(n)=O(n), S(n)=O(1)。
5、先给出算法思想，再写出相应代码。 操作系统操作系统部分部分（7575 分分） 1. 单选题（10 分，每题 1 分) （1） 在下列系统中，( )是实时系统。 A.计算机激光照排系统 B.军用反导弹系统 C.办公自动化系统 D.计算机辅助设计系统 （2）. 引入多道程序的目的在于( )。 A.充分利用 CPU，减少 CPU 等待时间 B提高实时响应速度 C.有利于代码共享，减少主、辅存信息交换量 D解放 cpu 对外设的管理 （3） 已经获得除( )以外的所有运行所需资源的进程处于就绪状态 A.存储器 B打印机 CCPU D磁盘空间 （4） 采用时间片轮转法调度是为了( )。 A.多个终端都能
6、得到系统的及时响应 B.先来先服务 C.优先级较高的进程得到及时调度 D.需 CPU 最短的进程先做 （5） 在一段时间内只允许一个进程访问的资源，称为( ) 。 A.共享资源 B临界区 C临界资源 D共享区 （6）.并发性是指若干事件在( )发生 。 A同一时刻 B同一时间间隔内 C不同时刻 D不同时间间隔内 （7） 管道通信是以( )进行写入和读出。 A消息为单位 B自然字符流 C文件 D报文 （8） 操作系统中有一组特殊的程序它们不能被系统中断，在操作系统中称为( ) A.初始化程序 B原语 C子程序 D.控制模块 科目代码：922 科目名称：数据结构与操作系统(专业学位) 第 3 页
7、共 4 页 （9）. 在分段管理中( )。 A以段为单位分配，每段是一个连续存储区 B段与段之间必定不连续 C段与段之间必定连续 D每段是等长的 （10）.通道是一种( )。 A.IO 端口 B数据通道 CIO 专用处理机 D软件工具 2. 简答题（20 分，每题 4 分） （1）. 系统型线程和用户型线程有何区别？ （2）. 多级反馈队列调度算法是如何工作的？ （3）. 分段式系统和分页式系统有何区别？ （4）. 引入缓冲的目的是什么，有哪些常见的缓冲模式？ （5）. SPOOLING 技术如何实现，在操作系统中起何作用？ 3. （9 分） 设有三道作业，它们的提交时间及执行时间由下表给出:
8、 作业号 提交时间 执行时间 1 8.5 2.0 2 9.2 1.6 3 9.4 0.5 （1）周转时间和带权周转时间的区别是什么，为何引入带权周转时间？（2 分） （2）试计算在单道程序环境下，采用先来先服务调度算法和最短作业优先调度算法时的平均周转时间 。 （7 分） 4. （9 分）某系统有 A、B、C、D 四类资源可供五个进程 P1、P2、P3、P4、P5 共享。系统共有这四类资源为:A 类 3 个、B 类 14 个、C 类 12 个、D 类 12 个。进程对资源的需求和分配情况如下： 已占有资源 最大需求数 进程 A B C D A B C D P1 0 0 1 2 0 0 1 2
9、P2 1 0 0 0 1 7 5 0 P3 1 3 5 4 2 3 5 6 P4 0 6 3 2 0 6 5 2 P5 0 0 1 4 0 6 5 6 科目代码：922 科目名称：数据结构与操作系统(专业学位) 第 4 页 共 4 页 （1）现在系统是否处于安全状态？（4 分） （2）如果进程 P2 提出需要 A 类资源 0 个、B 类资源 4 个、C 类资源 2 个和 D 类资源 0 个，系统能否去满足它的请求？（5 分） 5. （9 分）某分页系统，每个页面长为 1KB，某时刻该用户进程的页表如下： 页号 物理块号 是否在快表中 0 8 是 1 7 是 2 4 否 3 10 否 4 5 否
10、 5 3 是 6 2 是 （1） 请写出分页系统的地址转换过程（3 分） （2）计算两个逻辑地址：0AC5H、1AC5H 对应的物理地址（16 进制表示） 。 （3 分） （3）已知主存的一次存取为 2us，对于快表的查询时间可以忽略，则访问上述两个逻辑地址分别耗费多少时间？（3 分） 6. （9 分） 在某请求分页管理系统中，作业执行时一次访问如下页面：1，4，3，1，2，5，1，4，2，1，4，5，若分配给该作业的主存块数为 3. （1）页面置换算法在虚拟存储管理中的重要性。 （2 分） （2）FIFO, LRU 算法各适用于什么场合（3 分） （3）计算 FIFO，LRU，页面置换算法，试求出缺页中断次数。 （4 分） 7. （9 分）一家四口人，儿子喜欢吃苹果，由父亲负责购买, 女儿喜欢吃橘子，由母亲负责购买。父亲和母亲购买水果后放到家中的抽屉里，儿子和女儿从抽屉里取出水果。假设抽屉只能容纳 20 个水果，同时只能一人开关, 用纪录型信号量同步父母子女四个进程。
