2017年武汉工程大学数据结构(C语言版)之数据结构(C语言版)考研复试核心题库
● 摘要
一、应用题
1． 写出下列排序算法的基本思想，并写出对序列（23，12，35，47，16，25，36，19，21，16）进行排序时每一趟的结果。
【答案】此排序为双向起泡排序：从前向后一趟排序下来得到一个最大值，若其中发生交换，则再从后向前一趟排序，得到一个最小值。
第一趟：12，23，35，16，25，36， 19，21，16， 47 第二趟：12，16，23，35，16，25，36， 19，21，47 第三趟：12，16，23，16，25，35， 19，21，36， 47 第四趟：12， 16， 16，23， 19， 25， 35， 21， 36，47 第五趟：12，16，16，19，23，25，21，35， 36， 47 第六趟：12，16，16，19，21， 23，25，35， 36， 47 第七趟：12，16，16，19，21，23，25，35， 36， 47
2． 从概念上讲，树、森林和二叉树是三种不同的数据结构，将树、森林转化为二叉树的基本目的是什么？ 并指出树和二叉树的主要区別。
【答案】（1）基本目的
树的孩子兄弟链表表示法和二叉树的二叉链表表示法本质是一样的，只是解释不同，也就是说树（树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树唯一表示，并可使用二叉树的一些算法去解决树和森林中的问题。
（2）主要区别
一是二叉树的度至多为2，树无此限制；二是二叉树有左右子树之分，即使在只有一个分支的情况下，也必须指出是左子树还是右子树，树无此限制：三是二叉树允许为空，树一般不允许为空（有些书上考虑到与二叉树的转换，允许树为空）。
3． 设将n （n ＞l ）个整数存放到一维数组R 中。试设计一个在时间和空间两方面都尽可能高效的算法，将R 中存有的序列循环左移P （0＜P ＜n ）个位置，即将R 中的数据由
变换为
（1）给出算法的基本设计思想。 （2）根据设计思想，采用C 或
或JA V A 语言描述算法，关键之处给出注释。
原地逆置，
得到
（3）说明你所设计算法的时间复杂度和空间复杂度。 【答案】（1）算法的基本设计思想：先将n
个数据由然后再将数组R 中的前
，
（2）用C 语言算法描述如下：
（3）说明算法的复杂性：上述算法中3个Reverse 函数的的时间复杂度分别
为
为O
故算法的时间复杂度为
，算法的空间复杂度为0（1）。
4． （1）对于有向无环图，叙述求拓扑有序序列的步骤；
（2）对于图1，写出它的四个不同的拓扑有序序列。
个数和后P 个数分别原地逆置，
最终得到结果
要求：
图1
【答案】（1）对有向图，求拓扑序列步骤为：
1）在有向图中选一个没有前驱（即入度为0）的顶点并输出。
2）在图中删除该顶点及所有以它为尾的弧。
3）重复1）和2）, 直至全部顶点输出，这时拓扑排序完成；否则，图中存在环，拓扑排序失败。
（2）拓扑有序序列如图2:
图2 拓扑有序序列
5． 在如图1所示的伙伴系统中，回收两块首地址分别为768及128、大小为的存储块，请画出回收后该伙伴系统的状态图。
图1
【答案】因为小为
因为
所以768和所以首址
大小为
互为伙伴，伙伴合并后，首址为768，块大的块和首址512、大小为的块合并，成为首址
将其插入可利用空间表中。回
其伙伴地址为
512、；大小为的空闲块。因为收后该伙伴系统的状态图如图2所示：