南京航空航天大学
二○○六年硕士研究生入学考试试题
考试科目数据结构与操作系统数据结构与操作系统
说明答案一律写在答题纸上写在试卷上无效
数据结构部分75分数据结构部分
1、分）求解具有
个结点的完全二叉树的深度，写出计算结果。（5
2、（10分）已知树的先根遍历序列为：EAFGBHDC，后根遍历序列为：FABDHGCE，画出对应的树，并简单说明原理。
3、（10分）画出广义表L（dfdabce）的一种存储结构图。
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分）已知（a1a2a3…a
1）是堆，编写程序，将（a1a2a3…a
1a
）调整为堆，要求时间复杂度为O（log
），写出算法思想。
8、（10分）编写程序，判断一个用邻接表存储的有向图是否存在回路，并写出算法思想。
1
f操作系统部分（操作系统部分（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）102、在某系统中有4个并发进程，都需要同类资源5个，问该系统不会发生死锁地最少资源为_____个。（A）20（B）9（C）17（D）123、设磁盘的IO请求队列中的柱面号为：55，58，39，18，90，160，150，38，184，磁头移动_____个磁道。（A）250（B）298（C）323（D）2484、磁盘上的文件以______为单位读写。（A）块（B）记录（C）柱面（D）字节5、在磁盘文件系统中，对于下列物理结构，_____不具有直接读写文件任意一个记录的能力。（A）顺序结构（B）链接结构（C）索引结构（D）哈希结构6、要实现两个进程互斥，设一个互斥信号量mutex，当mutex为0时，表示______（A）没有进程进入临界区（B）有1个进程进入临界区（C）有1r