做查找之前先看这个

哈希查找方法_Anthony_4926-CSDN博客_哈希快速查找https://blog.csdn.net/weixin_38233103/article/details/118971876

本文以例题形式讲解散列查找中，散列表的构建，以及查找成功的ASL和失败的ASL。重点讲解求解失败的ASL的过程，巨详细（后边还有其他例题）

【2010年全国试题41（10分）】将关键字序列（7、8、30、11、18、9、14）散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组，散列函数为： H(key) = (keyx3) MOD 7，处理冲突采用线性探测再散列法，要求装填（载）因子为0.7。

(1) 请画出所构造的散列表。

(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。

（1）装填因子, 所以 n = 10

（2）根据表1-1中 查找查找成功需要探测次数，

求解查找失败的ASL需要计算出每个散列位置（即每个模对应的值）查找失败所需要的的次数，本题散列函数模的是7，所以只需要计算模为0,1,2,3,4,5,6的关键字查找失败所需要的次数。查找到空说明查找失败，查找示意图如下

 将上述过程整理成表格如下

查找失败的平均比较次数为：

2.【东北大学2002 二、2 (5分)】设有一组关键字(9, 01,23, 14, 55, 20, 84,27)，采用哈希函数: H(key)=key mod 7，表长为10，用开放地址法的二次探测再散列方法

解决冲突。要求:对该关键字序列构造哈希表，并计算查找成功的平均查找长度。

6

查找成功所需的

3.设散列表的表长m=15,散列函数H(key)=key mod 13,关键码集合为（53, 17,12, 61, 89, 70, 87, 25, 64, 46),采用二次探测法处理冲突,试构造闭散列表,并计算查找成功的平均查找长度。

查找成功的

4【东北大学2001六(18分)】对下面的关键字集(30, 15, 21, 40, 25,26, 36, 37)，若查找表的装填因子为0.8，采用线性探测再散列方法解决冲突。

(1)设计哈希函数; (2)画出哈希表; (3)计算查找成功和查找失败的平均查找长度;

（1） Hey(key) = key % 7;

取模的数一般是比不超过表长的最大质数

（2）

（3）查找成功的平均查找长度

 查找失败的平均查找长度

画出对长度为18的有序的顺序表进行折半查找时的判定树，并指出在等概率时查找成功的平均查找长度，以及查找失败时所需的最多的关键字比较次数。【哈尔滨工业大学2005 四、1（8分）】

判定树如下：

查找成功时的

查找失败时

以4*13=52为例，解释一下数字的含义。

【厦门大学 2002】一颗二叉排序树结构如下，各节点的值从大到小依次为1-9，请标出各节点的值。

二叉排序有一个特点，就是他的中序遍历是从小到大的顺序，因此我们对图1-1进行中序遍历，然后将1-9填入即可

 可以生成下图所示的二叉排序树的关键字初始序列有几种?试写出其中的任意4种。【电子科技大学2005三、2 (6分)】

首先可以确定，第一个数肯定是8。

那么，对于左子树，必须是4是第一个，2和6谁先谁后也无所谓。

所以，根据左子树可以有两个顺序，

8     4     2      6

8     4     6      2

对于9，什么时候插，怎么插也不会插到左子树上去。所以，对于上边那个序列，9可以在下边的下划线的任何一个位置。

8  _ 4  _   2   _   6   _

8  _ 4  _   6   _   2  _

 一共有8种，任意四种如下：

设T是一棵高度平衡树(又称平衡树)，给定关键词K，如果在T中查找K失败，且查找路径上的任一结点的平衡系数皆为零，试回答用高度平衡树插入算法在中插入关键词为K的新结点后，树T的高度是否一定增加?并回答为什么。【吉林大学1996四、2 (7分)】

树的高度一定增加。因为“查找路径上的任一结点的平衡系数皆为零”，从根结点开始查找，根结点的平衡因子为零，说明根的左右子树等高(不一定是满二叉树)。沿左(或右)子树向下查找时，查找路径上所有结点的平衡因子皆为零，说明任一结点的左右子树等高，查找失败是在叶子结点，插入也是在叶子结点，树的高度自然增加。