设哈希表HT表长m为13，哈希函数为H（k）=kMODm，给定的关键值序列为{19，14，23，10，68，20，84，

(1)【◆题库问题◆】：[问答题] 设哈希表HT表长m为13，哈希函数为H（k）=kMODm，给定的关键值序列为{19，14，23，10，68，20，84，27，55，11}。试求出用线性探测法解决冲突时所构造的哈希表，并求出在等概率的情况下查找成功的平均查找长度ASL。

【◆参考答案◆】：（1）表形态：(2)平均查找长度：ASL(10)=(1*5+2*4+3*1)/10=1.6

(2)【◆题库问题◆】：[单选] 设有广义表D=（a，b，D），其长度为（）。
A．无穷大
B．3
C．2
D．5

【◆参考答案◆】：B

(3)【◆题库问题◆】：[单选] 单链表的一个存储结点包含（）。
A．数据域或指针域
B．指针域或链域
C．指针域和链域
D．数据域和指针域

【◆参考答案◆】：D

(4)【◆题库问题◆】：[单选] 线性表采用链式存储时，节点的存储的地址（）。
A．必须是不连续的
B．连续与否均可
C．必须是连续的
D．和头节点的存储地址相连续

【◆参考答案◆】：B

(5)【◆题库问题◆】：[判断题] 哈夫曼树一定是完全二叉树。
A．正确
B．错误

【◆参考答案◆】：正确

(6)【◆题库问题◆】：[填空题] 数据结构按逻辑结构可分为两大类，它们分别是（）和（）。

【◆参考答案◆】：线性结构 非线性结构

(7)【◆题库问题◆】：[问答题] 假设用于通讯的电文仅由8个字母A．B．C．D．E．F．G．H组成，字母在电文中出现的频率分别为：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。请为这8个字母设计哈夫曼编码。

【◆参考答案◆】：

(8)【◆题库问题◆】：[名词解释] 堆排序

【◆参考答案◆】：
首先将根结点的记录与当前树中具有最大序号的记录交换，把交换后具有最大序号的记录输出，得到一个排序的结果。这时的树不再是堆树，排序暂时停止。然后，必须把树重新调整成堆树，再重复上述过程，直到所有记录都排好序。

(9)【◆题库问题◆】：[填空题] 三叉链表比二叉链表多一个指向（）的指针域。

【◆参考答案◆】：双亲结点

(10)【◆题库问题◆】：[判断题] 链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序表中效率高
A．正确
B．错误

【◆参考答案◆】：正确