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

二叉树的二叉链表类型定义如下：

typedef struct btnode {

       datatype data;

       struct btnode *lchild, *rchild;

} bitreptr;

写出后根遍历根指针为t的二叉树的递归算法( void postorder( bitreptr *t ))。

设线性表A =(a1，a2，…，am)，B=(b1，b2，…，bn)，试写一个按下列规则合并A，B为线性表C的算法，使得

       C=(a1，b1，…，am，bm，bm+1，…，bn) 当m≤n时;

或者 C=(a1，b1，…，an，bn，an+1，…，am) 当m>n时。

线性表A，B和C均以带头结点的单链表作为存储结构，且C表利用A表和B表中的结点空间构成。(注意：单链表的长度值m和n均未显式存储。)

用冒泡排序法对数据序列(55，38，65，97，76，138，27，49)进行排序，写出排序过程中的各趟结果。

写出题31图的邻接矩阵和每个顶点的入度与出度。

题31图

二叉排序树的各结点的值依次为20~28，请在题32图中标出各结点的值。

                             题32图

给定权值{3，9，13，5，7｝，构造相应的哈夫曼(Huffman)树，并计算其带权路径长度。

要将序列{51，18，23，68，94，70，73}建成堆，则只需把18与________相互交换。

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

题29图

二分查找算法的时间复杂度是________。

除第一个顶点和最后一个顶点相同外，其余顶点不重复的回路，称为________。