设有一组关键字序列{19,23,14,55,84,11,13}, 1)依次取各数据,构造一棵二叉排序树; 2)求该排序树等概率情况下查找成功时的平均查找长度。
时间: 2023-12-15 19:05:14 浏览: 47
好的,我可以回答你的问题。
1)依次取各数据,构造一棵二叉排序树如下所示:
```
19
/ \
14 23
/ \
11 55
\ \
13 84
```
2)该排序树等概率情况下查找成功时的平均查找长度为:
```
ASL = (1/7)*1 + (1/7)*2 + (1/7)*3 + (1/7)*3 + (1/7)*4 + (1/7)*4 + (1/7)*4 = 2.57
```
其中,ASL表示平均查找长度。
相关问题
将关键字序列(9,1,23,14,55,20,84,27)依次插入初始为空的二叉树
好的,我来回答你的问题。将这个关键字序列依次插入初始为空的二叉树,插入的顺序如下:
1. 将 9 插入根节点。
2. 将 1 插入 9 的左子树。
3. 将 23 插入 9 的右子树。
4. 将 14 插入 1 的右子树。
5. 将 55 插入 23 的右子树。
6. 将 20 插入 14 的右子树。
7. 将 84 插入 55 的右子树。
8. 将 27 插入 23 的左子树。
最终的二叉树如下所示:
```
9
/ \
1 23
/ \
27 55
/ \
20 84
/
14
```
设有一组关键字{19,01,23,14,55,20,84,27,68,11,10,77},采用散列函数H(key)=key%13,采用开放地址法的二次探测再散列方法解决冲突,试在0~18的散列地址空间中对该关键字序列构造散列表。
好的,让我来回答你的问题。
根据题目中所给的关键字和散列函数,我们可以得到以下散列地址:
- 19 -> 6
- 01 -> 1
- 23 -> 10
- 14 -> 1
- 55 -> 3
- 20 -> 7
- 84 -> 11
- 27 -> 1
- 68 -> 4
- 11 -> 11
- 10 -> 10
- 77 -> 5
其中,关键字14和27的散列地址与关键字01相同,发生了冲突。我们可以采用开放地址法中的二次探测再散列方法解决冲突。具体地,如果第一次散列地址为h,冲突解决的第i步散列地址为:
$h_i = (h + c_1i + c_2i^2) \mod m$
其中,c1和c2是正整数,m是散列表的大小。
在本题中,我们可以取c1=1,c2=3,m=13。则,关键字14的散列地址为2,关键字27的散列地址为12。最终的散列表如下:
- 0:
- 1: 01
- 2: 14
- 3: 55
- 4: 68
- 5: 77
- 6: 19
- 7: 20
- 8:
- 9: 23
- 10: 10
- 11: 84, 11
- 12: 27
这样,我们就成功地构造出了一个散列表,其中每个关键字都被正确地插入到了对应的散列地址处。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)