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

设散列函数H(key)=key mod 11(mod表示求余运算)，给出键值序列为66，13，41，15，44，6，68，17，26，31，39，46，用链地址法解决冲突，试画出相应的散列表，并计算在等概率情况下查找成功时的平均查找长度。

带头结点的单链表的结点结构如下：

typedef struct node

{  int data;

   struct node *next;

}Node, *LinkList;

试编写单链表的删除运算算法void DeleteLinklist( LinkList head，int i)

写出直接选择排序算法。

题32图所示二叉排序树的各结点的值为1~10中的数，试标出各结点的数值。

题32图

已知含五个顶点A，B，C，D，E的连通带权图的邻接矩阵如题31图所示，试画出它所表示的连通带权图及该连通带权图的最小生成树。

          题31图

如题29图所示，在栈的输入端依次输入元素A，B，C，试写出在栈的输出端可以得到的所有输出序列，并给出每个序列的操作过程(用push(A)表示A进栈，pop(A)表示A出栈)。

题29图

将题30图所示的一棵树转换为对应的二叉树。

题30图

堆排序算法的时间复杂度为________。

如果要将序列{60，18，28，69，99，75，78}建成堆，则只需把60与________相互交换。

在顺序查找、二分查找、散列查找和索引顺序查找四种查找方法中，平均查找长度与元素个数没有关系的查找方法是________。