一、简答题(共3题，共26分)

1. (8分)散列表长度为13， 散列函数为Hash(k) =k%13。 请分别写出序列(12, 8,16，27,21,17,3，28，47)的线性开型寻址散列存储结构和链表散列结构。

2. (10 分)假设用于通信的电文由字符集{a, b, c, d, e, f, g}中的字母构成，它们在电文中出现的频率分别为{31，16, 10, 8, 11, 20, 4}.

(1)画出霍夫曼树(霍夫曼树构造中，左子树权值小于等于右子树)，并求WPL;

(2)为这7个字母设计霍夫曼编码(分支编码左0右1);

(3)对这7个字母进行等长编码，至少需要几位二进制数?霍夫曼编码比等长编码使电文总长压缩多少?

3. (8 分)如何判别以邻接表方式存储的无向图中是否存在由顶点u到顶点v的路径(u≠v)，请描述出实现思路。

二、算法题(共2题，每小题12分，共24分)

1. (12分)在包含n个元素的单向链表中，找到链表中倒数第k个元素，k<n.要求时间复杂性为0(n)。(1) 描述算法的设计思想(2) 根据设计思想,给出算法实现,关键之处请给出注释.

2. (12分)设二叉树采用链表描述，t为指向根节点的指针，节点结构为(1eftchi ld, data, rightchild),其中data为元素的值，leftchild 和rightchild分别表示指向左孩子结点和右孩子结点的指针。设计算法，判断二叉树是否为最小堆。(1)描述算法的设计思想(2)根据设计思想,给出算法实现,关键之处请给出注释.(3)说明你所设计算法的时间复杂度。