资料详情
资料内容：
2012年南京航空航天大学922数据结构与操作系统(专业学位)考研真题
真题原文：
南京航空航天大学
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）。要求先给出算法思想，再写出相应代码。
资料截图：
下载地址：
 |
2012年南京航空航天大学922数据结构与操作系统(专业学位)考研真题 |
![](/list-192.ht</li>
</ul>
</div>
</div>
</div>
<!--返回顶部-->
<div class="fixed backtop" data-offset-fixed="0">
<a class="win-backtop"></a>
</div>
<!--详情层-->
<div class="detailsbox">
<div class="warp clearfix">
<div class="detailsimg float-left" style="background-color: #fff;; overflow:hidden"><center><img src=/uploads/allimg/171103/7-1G10313122c34-lp.png height=){kind=link}