南京航空航天大学2004数据结构与操作系统考研真题

南 京 航 空 航 天 大 学

二 ○ ○ 四 年 硕 士 研 究 生 入 学 考 试 试 题

考试科目:数据结构与操作系统

说 明:答案一律写在答题纸上,数据结构部分编程语言不限

第一部分:数据结构部分（75分）

1、（5分）判别以下序列是否为堆（小顶堆），如不是，将其调整为堆，画出调整过程。（29，51，63，39，24，55，50，13，49，39） 2、（10分）设一单链表，结点由整型数据和指针项组成，计算链表中数据只出现1次的结点个数，要求空间复杂度为O(1)。编写程序，并写出算法思想。 3、（10分）设一信号灯，产生的颜色有（RED，GREEN，BLUE，YELLOW，BLACK，BROWN，WHITE）出现的概率分别为（0.04，0.12，0.3，0.14，0.25，0.1，0.05），试用二进制对其编码，使产生的数据量最少。 4、（10分）设有存放整型数据的一维数组A[0…n-1],编写程序，将数组中的所有奇数调整到所有的偶数前面，要求时间复杂度为O（1），时间复杂度为O（n），并写出算法思想。 5、（10分）设有向无环图G：顶点集合为{v1,v2,v3,v4,v5,v6,v7},弧的集合为{,,,, , , , , , },(注：表示v1到v2有一条弧，权值为3)画出该图，并写出求解关键路径的过程。 6、（10分）编写程序，计算一棵二叉链表表示的二叉树的每层结点个数，并写出算法思想。 7、（10分）设树T采用双亲表示的储存结构，编写程序，计算树T的高度，并写出算法思想。 8、（10分）设有向图G以邻接矩阵方式储存，编写程序，判别从顶点i到顶点j是否存在一条长度为k的简单路径，并写出算法思想。

1

第二部分：操作系统（75分）

一、多项选择题（本大题共5题，每小题2分，共10分）

在每小题列出的五个备选项中有二个至五个选项是符合题目要求的，请将其代码填写在题后的括号内，错选，多选，少选或未选均无分。

1、 当处理机处于管态时，处理机可以执行的指令可以是_______。 A、访管指令 B、特权指令 C、逻辑运算指令 D、非法指令 E、算数运算指令

2、下列对进程状态转换中，可能发生的有________。

A、执行—>等待 B、执行—>就绪 C、等待—>执行 D、等待—>就绪 E、执行—>结束

3、在下列储存管理方案中，一个作业在内存中一定是连续存放的有_________。 A、单一连续分配 B、固定式分区分配 C、可变分区式分配 D、段式 E、可重定位分区分配 F、页式 G、段页式 4、下列叙述中正确的是_____________________-。

A、在磁盘上的顺序文件中插入新的记录时，必须复制整个文件 B、由于磁带的价格比磁盘便宜，用磁带实现索引文件更经济

C、在磁盘上的顺序文件的最后添加新的记录时，不必复制整个文件 D、变更磁盘上的顺序文件的记录内容时，不一定复制整个文件 E、在磁盘上的顺序文件中插入新的记录时，必须复制整个文件 5、引起I/O中断的事件有_______。

A、数据传送完毕 B、设备出错 C、设备正在处理数据 D、指令错 E、缺页

二、填空（共20分，答案要写在答题纸上，并请给出必要的解题过程或说明）

1、（4分）在某系统中有100个并发进程，都需要同类资源101个，问该系统不会发生死琐时最少资源数是______个。 2、（4分）设磁盘的I/O请求队列中的柱面号为：55，58，39，18，90，160，150，38，184，磁头初始位置为100，方向为向磁道外侧，若采用SSTF（最短寻道时间优先）的磁盘调度算法，磁头移动______个磁道。若采用SCAN（电梯调度算法）的磁盘调度算法，磁头移动______个磁道。 3、（4分）设有4个作业，它们的到达时间、所需运行时间如下图所示，若采用先来先服务、短作业优先和静态优先权的调度算法则平均周转时间分别为__________，__________，_________。 作业号 1 2 3 4 到达时间 0 1 2 3 所需运行时间（小时） 2 5 8 3 优先数 4 9 1 8 4、（4分）在一个请求分页系统中，采用FIFO页面置换算时，假如一个作业的页面走向为1，2，3，4，1，2，5，1，2，3，4，5，当分配给作业的物理块数M为3和4时，访问过

2

程中发生的缺页次数分别为：_____-次、______次。（假设开始时，物理块为空） 5、（4分）该系统中有三种类型的资源（A，B，C）和五个进程（P0，P1，P2，P3，P4，P5），某时刻的状态如下： Allocation A B C P0 0 1 0 P1 1 0 2 P2 3 0 2 P3 2 1 1 P4 1 0 2 Max A B C 9 5 8 3 3 2 9 0 3 6 2 2 4 3 3 Available A B C 2 3 0 根据银行家算法可知，该时刻存在着一个安全序列：____________________。（如不存在填无）

三、回答下列问题（共28分）

1、 下图是成组链接法的空闲盘块成组链接示意图（5分）：

请说明组链接法法的基本原理和分配与释放的过程。 2、 进程控制块中主要信息有哪些？（3分）

3、 终端用户的“注册”和“注销”各起什么作用？（4分）

4、 信箱通信机制中有那些基本通信原语？它们的功能是什么？（4分） 5、 什么是通道，通道经常采用如图所示的交叉连接，为什么？（4分）

3

I/O设备1 通道1 控制器1 I/O设备2 存储器 通道2 控制器2 I/O设备3 I/O设备4

6、 从中断事件的性质来看，中断可以分成哪几种类型？（4分） 7、 文件系统中，为什么要设置“打开”和“关闭”操作？（4分） 四、（8分）某系统采用段页式存储管理，有关的数据结构如下图所示。 （1）说明在段页式系统中动态地址变换过程。

（2）计算虚地址69732的物理地址，要求用十进制表示，并写出计算过程。

4

五、（9分）幼儿园的小朋友在做一种游戏，操场中间放一个窄垫子，一次只能有一个小朋友通过，可以锻炼小朋友的平衡能力。现把小朋友分成人数相同的2组，分别在这个垫子的两侧，老师发令后，垫子两端的小朋友可以争抢着上垫子，但不能发生小朋友在垫子上面对面碰撞的情况。一个组的小朋友通过垫子的总时间短者的为胜者。如果一个小朋友想通过垫子，他（她）必须看当前是否有别的小朋友在对面方向通过，如果有则不能上垫子，否则可以上垫子通过，并且同一时刻可以有多个小朋友朝同一个方向通过垫子。请使用信号量和PV操作写一个避免发生小朋友在垫子上面面对面碰撞（可以看成多个进程死琐）的程序。

5

本文来源：https://www.bwwdw.com/article/l92v.html