2001南航数据结构真题

《2001南航数据结构真题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、旨京航空航天大学二OO—年硕士研究生入学考试试题考试科目:数据结构与程序设计说明：下列每道题10分。编程题可用任何一种编程语言编写-、根拋下图所示广义表的储存结构，写出此阁的广义表。二、试找fli分別满足下列条件的所有二叉树。(1)先序序列和中序序列相同(2)屮序序列和后序序列相同(3)先序序列和后序序列相同三、根裾下图所示的一棵3阶B树(冇些教材称为B—树)(1)分别给出插入关键字2，12，16，17和18之后的结果。(2)分别给出在原图上删除8和9之后的结果。四、设侖两个链表，ha为单甸链表，hb为单向循环链表。编写算法，将两个链

2、表合并一个单向链表，要求算法所需时间与链表长度无关。(8分)五、简要叙述堆排序的算法思想。并对如F关键字序列(3,8,85,12,37,50)按堆排序算法进行从小到大排序，要求ffl出排序全过程的示意图。（10分）六、设有一个数组中存放了一个无序的关键序列Kl、K2、...KN。现要求将KN放在将元素排序后的正确位置上;试编写实现该功能的算法,耍求比较尖键字的次数不超过n。（注：用程序实现）（12分）七、设有一个带尖结点的单向链表,数据项递减有序。写一算法，重新排列链表,使数据项递增有序，要求算法吋间复杂度为O（n）。（注：川程序实现

3、）（10分）八、编写程序，将自然数1〜〜n2按“蛇行“填入的距阵中。例（1〜〜42）如图所示:（注：用程序实现）（12分）九、设s、t为两个字符串，分别放在两个一堆数组中，m、n分别为其长度，判断t是否为5的子串。如果是，输出子串所在位g（第-个字符），否则输出0。（注：用程序实现）（1（）分）十、已知二叉树采用二叉链表存储结构，mot指向其根结点，编写算法，求二叉树的深度。（注：用程序实现）（10分）十一、求a的•〒方根可用公式Xn=（Xn.,+a/Xn.i）/2,X（）取意值（X（）=l）。编写算法求a，直到误差小于e。（注：用程

4、序实现）（1（）分）考试科目:操作系统（100分）说明:答案一律写在答题纸上一、名词术语解释（每小题3分共24分）1、临界资源和临界区2、进程控制块PCB3、多道程序设计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。

5、假设分得的奴框数是3,并且开始时页框中是空的，贝IJ分别采川最佳转换算法和LRU页面转换算法，在访W过程中发牛.缺页中断的次数分别是和04、一台计算机有1（）台磁带机被m个进程竞争，每个进程最多需要三台磁带机，那么m为吋，系统没有死锁的危险。5、磁盘话•求以10,22,20,2,40,6,38柱面的次序到达磁盘驱动器。寻道吋每个柱面移动需要6ms,则采用先到先服务算法的寻道时间为:采用电梯算法（起始移动方向向外）的寻道吋间为。（假没磁头开始位S在柱面20）三、回答下列问题（每小题7分，共42分）1、何谓系统的安全状态，试说明银行家算法

6、避免死锁的原理？2、在实现文件系统时把文件目录的目录项分解成两部分:索引结点和符号名目录项，有什么好处？（需图示说明）3、在存储管理中分页与分段的主要区别是什么？分页与分段两种方法中，哪个更易于实现共享，为什么？4、在设备管理中引入单缓冲，如果从磁盘把一块数据输入到缓冲区中花费的时间为B;把缓冲区屮的数裾送到用户区，所花费的时叫为M;CPU对数裾进行处理的时M为C，贝IJ系统对每-块数据的处理吋间足多少？要求写出由B,C，M组成的表达式，并说明其屮的道理。5、提高磁盘I/O速度的方法有哪些？并分别加以简单的说明。6、程序顺序执行和并发

7、执行分别柯哪些牲？程序外发执行的条件是什么？对于下列语川，哪些能并发执行，哪些不能，说明理由。Sl:a=5-x；S2:b=a*x:S3:c=4*x；S4:d=b+c;S5:e=d+3;四、（14分）一个主修动物行为学、辅修计算机科学的学生参加了一个课题，调查花果山的猴子是否能被教会理解死锁。他找到一处峡谷，横跨峡谷拉了一根绳索（假设为南北方向）,这样猴了•就可以攀着绳索越过峡谷人。只要它们朝着相同的方向，同一时刻可以冇多只猴了通过。但是如果在相反的力*14上同时杏猴子通过则会发生死锁（这些猴子将被卡在绳索屮虬假设这些猴子无法在绳索上从

8、另一只猴子身上翻过去）。如果一只猴子相越过峡谷，它必须看当前是否奋别的猴子在逆14通过。请使川信号暈写一个避免死锁的积序來解决该问题。五、（10分）在分页式存储管理中，什么叫快表，说明艽工作原理和过程，Mfli具冇快表的