数据结构导论2011年10月真题及答案解析（02142）

n个结点的完全二叉树按结点编号将值顺序存放在一维数组元素A[1]至A[n]中，试编写算法实现将顺序存储结构转换为二叉链表存储结构，其中根结点由tree指向。

试写出冒泡排序算法。

判别以下序列是否为堆。如果不是，则把它调整为堆。

(1)(100，86，48，73，35，39，42，57，66，21);

(2)(12，70，33，65，24，56，48，92，86，33)。

对于有向无环图：

(1)叙述求拓扑排序算法的基本步骤;

(2)对于题32图，写出它的4个不同的拓扑排序序列。

将题31图所示的一棵二叉树转换成森林。

题31图

一棵二叉树如题30图所示，写出该二叉树的先根遍历序列、中根遍历序列和后根遍历序列。

冒泡排序的平均时间复杂度为________。

将序列(60，20，23，68，94，70，73)建成堆，则只需把20与________互相交换。

如题29图所示，在栈的输入端元素的输入顺序为A，B，C，D，进栈过程中可以退栈，写出在栈的输出端以A开头和以B开头的所有输出序列。

中根遍历二叉排序树所得到的结点访问序列是键值的________序列。