2001南航数据结构真题.docVIP

PAGE  PAGE 3 南 京 航 空 航 天 大 学 二 ○ ○ 一 年 硕 士 研 究 生 入 学 考 试 试 题 考试科目:数据结构与程序设计 说明：下列每道题10分。编程题可用任何一种编程语言编写 根据下图所示广义表的储存结构，写出此图的广义表。 1 1 1 1 1 1 1 1 1 1 0 0 0 1 试找出分别满足下列条件的所有二叉树。 先序序列和中序序列相同 中序序列和后序序列相同 先序序列和后序序列相同 根据下图所示的一棵3阶B树（有些教材称为B—树） 分别给出插入关键字2，12，16，17和18之后的结果。 分别给出在原图上删除8和9之后的结果。 设有两个链表，ha为单向链表，hb为单向循环链表。编写算法，将两个链表合并一个单向链表，要求算法所需时间与链表长度无关。（8分） 简要叙述堆排序的算法思想。并对如下关键字序列（3，8，85，12，37，50）按堆排序算法进行从小???大排序，要求画出排序全过程的示意图。（10分） 设有一个数组中存放了一个无序的关键序列K1、K2、…KN。现要求将KN放在将元素排序后的正确位置上；试编写实现该功能的算法，要求比较关键字的次数不超过n。（注：用程序实现）（12分） 设有一个带头结点的单向链表，数据项递减有序。写一算法，重新排列链表，使数据项递增有序，要求算法时间复杂度为O（n）。（注：用程序实现）（10分） 编写程序，将自然数1~~n2按“蛇行“填入n*n的距阵中。例（1~~42）如图所示：（注：用程序实现）（12分） 设s、t为两个字符串，分别放在两个一堆数组中，m、n分别为其长度，判断t是否为s的子串。如果是，输出子串所在位置（第一个字符），否则输出0。（注：用程序实现）（10分） 已知二叉树采用二叉链表存储结构，root指向其根结点，编写算法，求二叉树的深度。（注：用程序实现）（10分） 十一、求a的平方根可用公式Xn=（Xn-1+a/Xn-1）/2，X0取意值（X0=1）。编写算法求a，直到误差小于e。（注：用程序实现）（10分） 考试科目:操作系统（100分） 说明:答案一律写在答题纸上 一、名词术语解释（每小题3分共24分） 1、临界资源和临界区 2、进程控制块PCB 3、多道程序设计 4、计算机操作系统 5、用户态与核心态 6、SPOOLing系统 7、逻辑文件和物理文件 8、进程映像 二、填空（每小题2分，共10分） 1、在具有两级页表的分页存储管理系统中，CPU每次要存取一个数据时，须访问__________次内存。 2、产生死锁的必要条件是_____________________________________________________。 3、在一个请求分页存储管理系统中，某程序的页面走向为:7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。假设分得的页框数是3，并且开始时页框中是空的，则分别采用最佳转换算法和LRU页面转换算法，在访问过程中发生缺页中断的次数分别是__________和__________。 4、一台计算机有10台磁带机被m个进程竞争，每个进程最多需要三台磁带机，那么m为__________时，系统没有死锁的危险。 5、磁盘请求以10,22,20,2，40,6，38柱面的次序到达磁盘驱动器。寻道时每个柱面移动需要6ms，则采用先到先服务算法的寻道时间为__________；采用电梯算法（起始移动方向向外）的寻道时间为__________。（假设磁头开始位置在柱面20） 三、回答下列问题（每小题7分，共42分） 1、何谓系统的安全状态，试说明银行家算法避免死锁的原理？ 2、在实现文件系统时把文件目录的目录项分解成两部分:索引结点和符号名目录项，有什么好处？（需图示说明） 3、在存储管理中分页与分段的主要区别是什么？分页与分段两种方法中，哪个更易于实现共享，为什么？ 4、在设备管理中引入单缓冲，如果从磁盘把一块数据输入到缓冲区中花费的时间为B；把缓冲区中的数据送到用户区，所花费的时间为M；CPU对数据进行处理的时间为C，则系统对每一块数据的处理时间是多少？要求写出由B，C，M组成的表达式，并说明其中的道理。 5、提高磁盘I/O速度的方法有哪些？并分别加以简单的说明。 6、程序顺序执行和并发执行分别有哪些牲？程序并发执行的条件是什么？对于下列语句，哪些能并发执行，哪些不能，说明理由。 S1:a=5-x； S2:b=a*x ； S3:c=4*x ； S4:d=b+c ； S5:e=d+3 ； 四、（14分）一个主修动物行为学、辅修计算机科学的学生参加了一个课题，调查花果山的猴子是否能被教会理解死锁。他找到一处峡谷，横跨峡谷拉了一根绳索（假设为南北方向），这样猴子就可以攀着绳索越过峡谷人