已知一个列表长为12,关键字的线性序列为53 17 19 61 98 75 79 63 46 49,假定采用h(key)=key%11,若采用线性探测法处理冲突,构造出该散列表
时间: 2024-02-19 09:00:33 浏览: 22
根据给定的哈希函数h(key)=key%11和线性探测法,可以按照以下步骤构造该散列表:
1. 创建一个长度为11的数组,用于存放关键字。
2. 将数组中所有元素初始化为空位(null)。
3. 依次将线性序列中的关键字插入到散列表中。对于每个关键字,计算其哈希值h(key),如果对应的数组位置为空,则将关键字插入到该位置;否则,按照线性探测法,依次检查下一个位置,直到找到一个空位。
4. 插入完所有关键字后,散列表的构造就完成了。
根据上述步骤,可以得到以下散列表(其中“-”表示空位):
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|53 |17 |46 |79 |98 |75 |19 |63 |- |- |49 |
其中,关键字53、17、46、79、98、75、19、63、和49分别对应数组下标0、1、2、3、4、5、6、7、10,而关键字61和关键字46都发生了冲突,需要按照线性探测法依次往后查找空位,最终关键字61插入到了下标8的位置。
相关问题
已知关键字序列为{53,17,19,61,98,75,79,63,46,40},给出利用这些关键字构造的二叉排序树。
### 回答1:
以下是利用这些关键字构造的二叉排序树:
53
/ \
17 61
\ \
19 98
/ \
75 79
/ /
63 46
\
40
### 回答2:
二叉排序树(Binary Search Tree,BST),也称二叉搜索树或二叉查找树,是一种特殊的二叉树,它的每个节点都包含一个关键字,且对于任意节点,其左子树中的所有关键字均小于该节点的关键字,其右子树中的所有关键字均大于该节点的关键字。利用给定的关键字序列可以构造如下的二叉排序树:
![image](https://cdn.luogu.com.cn/upload/image_hosting/qw52op7r.png)
首先,由于53是第一个关键字,它成为根节点。接下来,从左到右依次遍历每个关键字。17小于53,因此它成为左子树的根节点;19也小于53,但是它大于17,所以它成为17的右孩子;61大于53,因此它成为右子树的根节点;98大于61,因此它成为61的右孩子;75大于61,但是它小于98,所以它成为98的左孩子;79也是同理;63大于53,但是它小于61,所以它成为61的左孩子;46小于53,但是它大于17,所以它成为17的右子树的根节点;40小于53,但是它小于17,因此它成为17的左孩子。
最终,我们得到了上述的BST。这个树的中序遍历序列就是给定的关键字序列的有序排列。在这个树中搜索一个关键字的时间复杂度是O(log n),其中n是树中节点的总数。由于BST能够快速地进行搜索、插入和删除操作,因此它被广泛应用于各种算法和数据结构中。
### 回答3:
二叉排序树又称为二叉搜索树,是一种特殊的二叉树,其中每个节点都包含一个关键字及其数据,并且满足以下性质:
1. 左子树中的所有节点的关键字都小于该节点的关键字。
2. 右子树中的所有节点的关键字都大于该节点的关键字。
3. 左右子树都是二叉排序树。
根据所给的关键字序列 {53,17,19,61,98,75,79,63,46,40},我们可以利用这些关键字构造出以下的二叉排序树:
53
/ \
17 61
/ \ \
19 46 98
/ /
40 75
/ \
63 79
首先,将第一个关键字53设为根节点,后续每个关键字都从根节点开始比较大小,小于根节点的关键字将放到左子树中,大于根节点的关键字将放到右子树中。依此操作,可以构造出以上的二叉排序树。
在该二叉排序树中,最小值为19,最大值为98。若搜索关键字为63,则从根节点开始查找,63小于根节点53,则在左子树中查找;在左子树中,关键字46小于63,则继续在46的右子树中查找;最终找到了关键字为63的节点。
二叉排序树的主要优点是可以高效地进行搜索、插入和删除操作,时间复杂度为O(log n),可以用于解决一些大规模数据的查找问题。
1)已知一个有7个数据元素的有序顺序表,其关键字为|3,18,25,37,69,7. 91,请给出用折半查找方法查找关键字值18的查找过程。 2) 已知关键字序列为(53,17,19,61,98,75,79,63,46,40},请给出利用这些关键字构造的二又排序树。
1) 折半查找方法的基本思想是:在有序表中,先取中间位置的记录进行比较,如果给定值与中间位置的记录相等,则查找成功;否则利用中间位置将有序表分成两个子表,若中间位置的记录大于给定值,则在左半部分继续查找;否则在右半部分继续查找。重复以上过程,直到查找成功或查找失败为止。
按照折半查找方法查找关键字值18的过程如下:
1. 设置左右两个哨兵left和right,初始时left=1,right=7;
2. 取中间位置mid=(left+right)/2=4,即中间位置记录的关键字为37;
3. 给定值18小于中间位置记录的关键字37,因此在左半部分继续查找,将right=mid-1=3;
4. 取新的中间位置mid=(left+right)/2=2,即中间位置记录的关键字为18;
5. 查找成功,返回位置2。
因此,关键字值18的查找过程是:37 -> 18,查找成功,返回位置2。
2) 利用这些关键字构造的二叉排序树如下:
53
/ \
17 61
\ \
19 98
/ \
75 79
\
63
/
46
/
40