南京航空航天大学922数据结构与操作系统真题2018年硕士研究生入学考试初试试题.pdf
科目代码:922 科目名称:数据结构与操作系统(专业学位) 第 1 页 共4页 南京航空航天大学 2018 年硕士研究生入学考试初试试题 ( A卷 ) 科目代码: 922 满分: 150 分 科目名称: 数据结构与操作系统(专业学位) 注意: 认真阅读答题纸上的注意事项;所有答案必须写在答题纸上,写在本试题纸或草稿纸上均无 效;本试题纸须随答题纸一起装入试题袋中交回! 数据结构部分 1 (5 分)设 n*n 的矩阵 A1.n,1.n为三角特殊矩阵,其逆对角线以上为 0,逆对角线以 及逆对角线以下的所有元素按行序压缩存储在一维数组 B1.n*(n+1)/2中, 根据 i、j 在满足何种条件下,计算元素A ij 的存储位置,给出推导过程。 2 (10分)给出下图所示树的二种存储结构示意图。 (1)带双亲的孩子链表表示法 (2)孩子兄弟表示法 并说明这二种存储结构的优缺点。 3 (10 分)给定 n 个村庄之间的交通图,边上的值表示这条道路的长度,现在要从这 n 个 村庄中选择一个村庄建一所医院,问这所医院应建在哪个村庄,才能使离医院最远的村庄 到医院的路程最短?试选择或构造一种适当的数据结构并设计一个算法,并应用该算法解 答下图所示的实例,给出算法执行示意图。 4 (10分)详细解释哈希表的工作原理。以此为例,将关键字序列(51,83,43,15,62, 59,74,61)存储在长度为 10 的哈希表中,使用哈希函数 H(key) = Key % 10 ,并采用链 地址法解决冲突,画出哈希表示意图。 A E D C I K G B H F J V3 V2 V4 V1 3 4 6 10 2 科目代码:922 科目名称:数据结构与操作系统(专业学位) 第 2 页 共4页 5 (10 分)设有一批需实时处理的数据元素组成集合 S,实时处理开始后,每隔一秒钟收 到一个新的数据元素加入S。现要求在每次接收一个新元素之前,找出S中现有的最小元素 并将其输出(从S中删除) 。试选择或构造一种适当的数据结构并设计一个算法,尽可能高 效地完成上述任务。例如:S=(59,31,29,18,78,26,48,10,65,35),新接受的数据为 39,12, 46.。以此为例说明算法执行过程示意图。 6 (10 分)设一个带头结点的单链表 L,数据元素为整数,其中大部分为正数,少数为负 数,编写函数,采用高效的算法调整链表,实现将负数结点移到链表尾部,并返回调整后 链表中的第一个负数结点位置。先给出算法思想,再写相应代码。 7.(10 分)设二叉树 T,用二叉链表结构存储,元素值为整数且互不相同。编写非递归函 数,对给定的2个整数,若2个都不是T的元素,输出-2;若1个不是T的元素,输出-1; 若2个都是T的元素,输出两者所在的层数的间隔数。先给出算法思想,再写出相应代码。 8 (10 分)设有 N 个顶点的有向无环图 G,以邻接矩阵方式存储。编写函数,对 G 中的每 个顶点进行遍历,若顶点V到顶点W存在一条有向边(弧) ,则要求顶点V在顶点W之前访 问。先给出算法思想,再写出相应代码。 操作系统部分 1.填空题(2分x5=10分) (1).操作系统的两大特征是( ) 。 (2).单道系统中,假设一批作业同时到达,若想平均周转时间最短,采用( ) 调度算法。 (3).时间片轮转调度算法中,如果时间片无穷大,该算法变成了( )调度算法。 (4).在某系统中有5个并发进程,都需要同类资源6个,问该系统肯定不会发生死锁 时最少资源数是( ) 。 (5). 对于首次适应算法、最佳适应算法和循环首次适应算法,可以保留高地址部分 的大空闲区的算法是( ) 。 2.简答题(4分x5=20分) (1) 画出引入挂起和激活机制后,进程状态转换图。 (2) 处理机调度分为哪三级?各自的主要任务是什么? (3) 内存管理中连续分配有何缺点,为何要引入离散分配? (4) 相对于顺序文件和索引文件,索引顺序文件有何优点?如果在一个索引顺序文件中 含有N 个记录, 如何设计索引顺序文件, 令检索指定关键字记录的平均查找次数最少? (5) 装入时动态链接和运行时动态链接有何区别?哪种更节约内存? 科目代码:922 科目名称:数据结构与操作系统(专业学位) 第 3 页 共4页 3. (9 分)多道程序系统有一个 CPU 和两台独占设备,即 IO1 和 IO2,现在有 3 个优先级 别从高到低的作业J1、J2、J3到达,它们使用资源的先后顺序和占用时间分别是: J1:IO2(60) ;CPU(20) ;IO1(60) ;CPU(20) J2:IO1(40) ;CPU(40) ;IO2(80) J3:CPU(60) ;IO1(40) 假设处理机调度采用可抢占的优先级算法,设备不能抢占,忽略调度时间,时间单位为分 钟。计算下列问题: (1)分别计算3个作业的周转时间(3分) (2)3个作业全部完成时CPU的利用率(3分) (3)3个作业全部完成时IO1的利用率(3分) 4. (9 分)磁盘请求柱面按 10, 22, 20, 2, 40, 6, 38 的次序到达,当前磁头在柱面 20 上。 (1)磁盘访问时间由哪几部组成,如何计算?(3分) (2)计算采用SSTF,SCAN算法(先由小到大)磁头移动顺序。 (3分) (3)如何应用RAID(廉价磁盘冗余阵列)提高磁盘的访问速度,请画图示意。 (3分) 5. (9 分)五个进程 P1,P2,P3,P4,P5 均需要使用资源 A、B、C。其中,A、B、C 资源 的总数分别为10,5,7。当前已分配资源情况和各进程的最大资源需求如下表所示。 进程 最大需求资源 已分配资源 P1 (7,5,3) (0,1,0) P2 (3,2,2) (2,0,0) P3 (9,0,2) (3,0,2) P4 (2,2,2) (2,1,1) P5 (4,3,3) (0,0,2) (1) 什么是安全状态?(2分) (2) 系统进入不安全状态是否一定会产生死锁?(3分) (3) P1请求资源(1,0,2) ,请根据银行家算法判断是否应该为其分配资源?(4分) 6 (9分)某教学楼楼梯较窄,为了安全规定课间,一旦有人从上往下走,则不允许任何人 从下往上走,但此时可以允许多人同时往下走,反之依然。请用设置合适的信号量(2 分) , 应用PV操作完成此同步问题(5分) ,并分析是否会产生饥饿现象(2分) 。 科目代码:922 科目名称:数据结构与操作系统(专业学位) 第 4 页 共4页 7. (9 分)为什么操作系统要引入缓冲?(3 分)对于单缓冲,假设从磁盘把一块数据输 入缓冲区的时间为 T, 将数据从缓冲区传送到用户区的时间为 M, CPU 处理这块数据的时间 为C,请计算系统对每块数据的处理时间,并画出示意图(3分) 。除了单缓冲,还有哪些常 见的缓冲形式,为何要引入这些缓冲?(3分)