南 京 航 空 航 天 大 学
二 ○ ○ 六 年 硕 士 研 究 生 入 学 考 试 试 题
考试科目:数据结构与操作系统
说 明:答案一律写在答题纸上,写在试卷上无效
数据结构部分(75分
1、（5分）求解具有n个结点的完全二叉树的深度，写出计算结果。 2、（10分）已知树的先根遍历序列为：EAFGBHDC，后根遍历序列为：FABDHGCE，画出对应的树，并简单说明原理。
3、（10分）画出广义表L=（(d,(f,d,(a,(b,c,e）的一种存储结构图。
4、（10分）从空树开始，画出按以下序列向3阶B—树插入关键字的建树过程：58，36，50，20，54，95，30，45，40，画出删除58，36后的B—树。 5、（10分）已知有单链表A、B，数据（设为整型）都为递增有序，填写程序，利用原结点将A中与B具有相同数据的结点删除，并将B中与原A表不同数据的结点A中，保持A的递增有序，分析时间复杂度，并写出算法思想。
6、（10分）已知有一棵二叉链表表示的二叉树，编写程序，输出从根结点到叶子结点的最长一枝上的所有结点，并写出算法思想。
7、（10分）已知（a1,a2,a3,…an-1）是堆，编写程序，将（a1,a2,a3,…an-1,an）调整为堆，要求时间复杂度为O（logn），写出算法思想。
8、（10分）编写程序，判断一个用邻接表存储的有向图是否存在回路，并写出算
法思想。
操作系统部分（75分）
一、 选择题（本大题共8小题，每空2分，共18分）
1、 在一个请求分页系统中，采用先进先出页面置换算时，假如一个作业的页面走向为1，2，3，4，1，2，5，1，2，3，4，5，当分配给该作业的物理块数M为3时，访问过程中发生的缺页次数为______次。当分配给该作业的物理块数M为4时，访问过程中发生的缺页次数为______次。（假设开始时，物理块中为空）
（A）7 （B）8 （C）9 （D）10
2、在某系统中有4个并发进程，都需要同类资源5个，问该系统不会发生死锁地最少资源为_____个。
（A）20 （B）9 （C）17 （D）12
3、设磁盘的I/O请求队列中的柱面号为：55，58，39，18，90，160，150，38，184，磁头移动_____个磁道。
（A）250 （B）298 （C）323 （D）248 4、磁盘上的文件以______为单位读写。 （A）块 （B）记录 （C） 柱面 （D）字节
5、在磁盘文件系统中，对于下列物理结构，_____不具有直接读写文件任意一个记录的能力。
（A）顺序结构 （B）链接结构 （C）索引结构 （D）哈希结构
6、要实现两个进程互斥，设一个互斥信号量mutex，当mutex为0时，表示______.
（A）没有进程进入临界区 （B）有1个进程进入临界区
（C）有1个进程进入临界区，另外1个进程在等待 （D）2个进程都进入临界区
7、资源的按按序分配策略可以破坏_______条件。 （A）互斥使用资源 （B）占有且等待资源 （C）非剥夺资源 （D）循环等待资源
8、设有4个作业同时到达，若采用最短作业优先调度算法，则作业的平均周转时间为______.
作业号
所需远行时间（小时）
优先数
1 2 3 4
2 5 8 3
2 3 7 5
（A）1.5小时 （B）10.5小时 （C）6.75小时 （D）10.25小时 二、 解答下列问题（共28分）
1、（10分）设一个文件占据了100个物理块，对于连续、链接和索引的文件，如果要将1块信息： （1）从文件的头部删去 （2）从文件的尾部删去
试问分别需要启动多少次I/O操作？请做必要的说明。
2、（5分）设系统中有3种类型的资源（A，B，C）和5个进程（P0，P1，P2，P3，P4），某时刻的状态如下： Allocation Max Available A B C A B C A B C P0 0 1 0 7 5 3 2 3 0 P1 1 0 2 3 3 2 P2 3 0 2 9 0 2 P3 2 1 1 6 2 2 P4 0 0 2 4 3 3
首先给出银行家算法的基本思想，然后根据银行家算法判断该时刻是否处于安全状态。
3、（4分）说明进程的基本状态及其转换关系，以及状态转换的典型原因。
南京航空航天大学2006数据结构与操作系统考研真题.
