南 京 航 空 航 天 大 学
二 ○ ○ 六 年 硕 士 研 究 生 入 学 考 试 试 题
考试科目:数据结构与操作系统
说 明:答案一律写在答题纸上,写在试卷上无效
数据结构部分(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数据结构与操作系统考研真题.
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)