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

假设树采用孩子兄弟链表表示法，其结构定义如下：

typedef struct tnode

{ DataType data;

  struct tnode *son, *brother;

}*Tree;

试编写算法void leveltree(Tree root)实现树的按层次遍历。

单链表的结点结构定义如下：

typedef struct node

{  int data;

   struct node *next;}

Node, *LinkList;

试编写在带头结点的单链表head中查找第1个元素值小于x的结点的实现算法Node *GetLinklist( LinkList head, int x)，若找到，则返回指向该结点的指针，否则返回NULL。

应用直接选择排序算法，对初始关键字序列为48，35，61，98，82，18，29，48的记录进行从小到大排序，写出排序过程和结果。

给定表(28，15，55，3，71，75，10，22，56)，试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树。

已知连通带权图如题31图所示，试利用普里姆(Prim)算法，从顶点A出发，构造它的最小生成树，画出构造过程。

                     题31图

设二叉树的先序遍历序列为DCBAHEIFG，中序遍历序列为ABCHDIEFG，试画出该二叉树并写出后序遍历序列。

堆分为最小堆和最大堆，若键值序列{k₁, k₂, …, k_n}，满足，则这n个键值序列{k₁, k₂,…, k_n}是__________。

设一个链栈的输入序列为X，Y，Z，试写出出栈的所有可能的输出序列及其操作步骤。

用键值通过散列函数获取存储位置的这种存储方式构造的存储结构称为__________。

若在线性表中采用二分查找法查找元素，则该线性表必须按值有序，并且采用__________存储结构。