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