南京航空航天大学-922数据结构与操作系统【2012】考研真题
免费
2023-06-21
999+
67.08KB
4 页
侵权投诉
922 数据结构与操作系统（专业学位） 第 1 页 共4页
南京航空航天大学
2012 年硕士研究生入学考试初试试题（ A 卷）
科目代码： 922 科目名称： 数据结构与操作系统( 专业学位) 满分： 150 分
注意: ①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸上，写在本试题纸或
草稿纸上均无效；③本试题纸须随答题纸一起装入试题袋中交回！
数据结构部分（75 分）
1．（5 分）已知一棵完全二叉树共有 691 个结点。结点从 1开始，自上而下自左而右层序编
号，试求以下问题，并给出推导过程。
（1）树的高度； （2）叶子结点的数目；
（3）分支为 1的结点数目； （4）最后一个非终端结点的编号；
（5）还差多少个结点就可以构造成相同高度的满二叉树。
2．（10 分）画出广义表 L=( f , （b, e ) ， ( ( c, d) , a) ) 的两种存储结构图。
3．（10 分）如图 1所示的 AOE 网，试求完成工程最少需要多少天（设边上的权值为天数），
并说明哪些是关键活动。要求给出规范的计算过程。
图1 第3题图
4．（10 分）已知输入数据序列为{ 38, 66, 18, 80, 58, 52, 26, 42, 28, 16} ，给出建立 3
阶 B- 树示意图，再给出删除 28，52 后的 B- 树。
5. （10 分）已知序列{ 108, 170, 503, 87, 512, 161, 175, 53, 897, 462} ，写出采用堆
排序法对该序列作降序排序时的每一趟结果。
6．（10 分）设 L 为带头结点的单链表，元素值为整数。设计一个算法，调整结点的位置，
将所有元素值为负数的结点移动到元素值为正数的结点之前，要求时间复杂度 T（n）=O（n）。
要求先给出算法思想，再写出相应代码。
7．（10 分）设树采用孩子兄弟链表结构进行存储，设计一个算法，求树的宽度（即具有结
点数最多的那一层上的结点个数）。要求先给出算法思想，再写出相应代码。
8．（10 分）设二叉排序树 T 的 key 值为整数，高度为 k，对任意给定的整数 x，查找元素值
小于 x 且最接近 x 的结点并返回结点指针，如该结点不存在则返回指针为空，要求用非递归
算法实现且时间复杂度 T（n）=O（k）。要求先给出算法思想，再写出相应代码。
922 数据结构与操作系统（专业学位） 第 2 页 共4页
操作系统部分（75 分）
1、（8 分）
（1）处理机的调度有哪三个层次？
（2）假设一操作系统以单道批处理方式运行，现有四道作业，进入系统的时间及运行时间
如下表所示，试用响应比高者优先算法进行调度，请给出这组作业的运行顺序、平均周转时
间和带权平均周转时间。
作业号 进入时间 运行时间（小时）
1 7:00 2.00
2 7:50 0.50
3 8:00 0.10
4 8:50 0.20
2、（17 分）
（1）实现进程同步机制必须遵循哪几条准则，含义是什么？
（2）以下程序中，哪些代码应该设为临界区？
（3）假设操作系统采用非抢占调度策略，sys_nc( ) 是主动放弃 CPU的系统函数。对于以下
程序代码，可能违反什么同步准则？
int a;
进程 1（）｛
sys_nc();
a=a+1;
｝
进程 2（）｛
a=a-1;
sys_nc();
｝
（4）采用信号量来进行进程同步可以很好地满足进程同步准则。现假设有一个共享数据库，
允许进程对数据库进行查询和更新两种操作，规则是查询操作可以允许多个进程同时查询，
但更新必须是排他性的，即每次只允许一个进程更新数据库，请用信号量和 P、V操作来完
成这一进程同步问题（要求：必须首先给出所设置信号量的意义及初值）
3、（10 分）
（1）产生死锁的主要原因是什么?
（2）有哪些处理死锁的基本方法？静态分配资源的方法属于哪种处理死锁的方法？而银行
家算法属于哪种死锁处理方法？
（3）设系统中有三种类型的资源（A，B，C）和五个进程（P1，P2，P3，P4，P5），A的
资源的数量为 17，B的资源的数量为 5，C的资源的数量为 20，在 T0 时刻状态如下：
标签： #南京航空航天大学
摘要：
展开>>
收起<<
922” ²Ð T"d
声明：研友网所有资料均为用户上传分享，仅供参考学习使用，版权归原作者所有。若侵犯到您的权益，请告知我们处理！任何个人或组织，在未征得本平台同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。
