来源：跨考2011-12-08
应用题
1．名词解释：
哈希表【燕山大学 1999 一、4（2分）】【哈尔滨工业大学 1999 一、3 （3分）】【首都经贸大学 1997 一、2 （4分）】
同义词： 【山东大学 1998 二、1 (2分)】【山东工业大学 2000 二、1 （2分）】
叙述B-树定义，主要用途是什么？它和B+树的主要差异是什么？【青岛大学 2001 五 （5分）】
B-树【南开大学 1996 五、4 (3分) 1998 五、4 (4分) 2000 二、2 （2）】【山东大学 2000 三 ( 8分)】
平衡二叉树（AVL树）？【南开大学 1996 五 、3 (3分) 1998 五、3 (4分)】【厦门大学 1998 四、2 （5分）】
平衡因子【西北工业大学 1999 一、2 (3分)】 平均查找长度（ASL）【西北工业大学 1999 一 、3 (3分)】
trie树【中山大学 1997 一、3 （3分）】
【参考答案】
概念是基本知识的主要部分，要牢固掌握。这里只列出一部分，目的是引起重视，解答略。
2．回答问题并填空【山东工业大学 1999 四（15分）】
（1）（2分）散列表存储的基本思想是什么？
（2）（4分）散列表存储中解决碰撞的基本方法有哪些？其基本思想是什么？
（3）（4分）用分离的同义词子表解决碰撞和用结合的同义词表解决碰撞属于哪种基本方法？他们各有何特点？
（4）（3分）用线性探查法解决碰撞时，如何处理被删除的结点？为什么？
（5）（2分）散列法的平均检索长度不随( )的增加而增加，而是随( )的增大而增加。
【参考答案】
（1）散列表存储的基本思想是用关键字的值决定数据元素的存储地址
（2）散列表存储中解决碰撞的基本方法：
① 开放定址法 形成地址序列的公式是：Hi=（H（key）+di）% m，其中m是表长，di是增量。根据di取法不同，又分为三种：
a．di =1，2，…，m-1 称为线性探测再散列，其特点是逐个探测表空间，只要散列表中有空闲空间，就可解决碰撞，缺点是容易造成“聚集”，即不是同义词的关键字争夺同一散列地址。
b．di =12，-12，22，-22，… ，±k2（k≤m/2） 称为二次探测再散列，它减少了聚集，但不容易探测到全部表空间，只有当表长为形如4j+3（j为整数）的素数时才有可能。
c．di =伪随机数序列，称为随机探测再散列。
② 再散列法 Hi=RHi（key） i=1，2，…，k，是不同的散列函数，即在同义词产生碰撞时，用另一散列函数计算散列地址，直到解决碰撞。该方法不易产生“聚集”，但增加了计算时间。
③ 链地址法 将关键字为同义词的记录存储在同一链表中，散列表地址区间用H[0..m-1]表示，分量初始值为空指针。凡散列地址为i（0≤i≤m-1）的记录均插在以H[i]为头指针的链表中。这种解决方法中数据元素个数不受表长限制，插入和删除操作方便，但增加了指针的空间开销。这种散列表常称为开散列表，而①中的散列表称闭散列表，含义是元素个数受表长限制。
④ 建立公共溢出区 设H[0..m-1]为基本表，凡关键字为同义词的记录，都填入溢出区O[0..m-1]。
（3）用分离的同义词表和结合的同义词表解决碰撞均属于链地址法。链地址向量空间中的每个元素不是简单的地址，而是关键字和指针两个域，散列地址为i（0≤i≤m-1）的第一个关键字存储在地址空间向量第i个分量的“关键字”域。前者的指针域是动态指针，指向同义词的链表，具有上面③的优缺点；后者实际是静态链表，同义词存在同一地址向量空间（从最后向前找空闲单元），以指针相连。节省了空间，但易产生“堆积”，查找效率低。
（4）要在被删除结点的散列地址处作标记，不能物理的删除。否则，中断了查找通路。
（5）记录 负载因子