2018江苏南京航空航天大学数据结构与操作系统考研真题.doc

2018江苏南京航空航天大学数据结构与操作系统考研真题
数据结构部分
1．（5分）设n*n的矩阵A[1..n,1..n]为三角特殊矩阵，其逆对角线以上为0，逆对角线以及逆对角线以下的所有元素按行序压缩存储在一维数组B[1..n*(n+1)/2]中，根据i、j
在满足何种条件下，计算元素Aij的存储位置，给出推导过程。

2．（10分）给出下图所示树的二种存储结构示意图。
（1）带双亲的孩子链表表示法
（2）孩子兄弟表示法并说明这二种存储结构的优缺点。

3．（10分）给定n个村庄之间的交通图，边上的值表示这条道路的长度，现在要从这n个
村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄
到医院的路程最短？试选择或构造一种适当的数据结构并设计一个算法，并应用该算法解
答下图所示的实例，给出算法执行示意图。

4．（10分）详细解释哈希表的工作原理。以此为例，将关键字序列（51，83，43，15，62，
59，74，61）存储在长度为10的哈希表中，使用哈希函数H(key)=Key%10，并采用链地址法解决冲突，画出哈希表示意图。

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）装入时动态链接和运行时动态链接有何区别？哪种更节约内存？

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。当前已分配资源情况和各进程的最大资源需求如下表所示。

(