|
825 数据结构和信息安全概论 第 1 页 共 2 页
南京航空航天大学
2012 年硕士研究生入学考试初试试题（ A 卷）
科目代码： 825 科目名称： 数据结构和信息安全概论 满分： 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）。要求先给出算法
思想，再写出相应代码。
，更多更新年份持续更新，请在本站的考博信息网|www.kaoboinfo.com中的“考研试卷库”学校栏目中查询下载。
|
您现在的位置： 
