已知一表为 (25,18,46,2,53,39,32,4,74, 67,60,11),按表中顺序依次插入初始为空的二 叉排序树,要求: (1画出建立的! 二叉排序树. (2)求出在等概率情况下查找成功的平均查找长 度。
时间: 2023-08-04 12:02:37 浏览: 84
(1) 二叉排序树的建立过程如下图所示:
```
25
\
46
/ \
18 53
/ / \
2 39 74
/ \
32 67
/
60
/
11
```
(2) 在等概率情况下查找成功的平均查找长度为二叉排序树中所有节点深度的平均值。对于本题中的二叉排序树,可以使用中序遍历将节点按顺序输出,得到:
```
2,4,11,18,25,32,39,46,53,60,67,74
```
因此,节点深度分别为:
```
5,4,4,3,2,3,3,1,2,4,4,3
```
平均深度为:
```
(5+4+4+3+2+3+3+1+2+4+4+3)/12 = 3.25
```
因此,在等概率情况下查找成功的平均查找长度为3.25。
相关问题
已知一组关键字为{25,18,46,2,53,39,32,4,74,67,60,11}。按表中的元素顺序依次插入到一棵初始为空的二叉排序树中,画出该二叉排序树,并求在等概率的情况下查找成功和查找不成功情况下的平均查找长度。
插入顺序为25、18、46、2、53、39、32、4、74、67、60、11。初始为空的二叉排序树如下图所示:
```
25
/ \
18 46
/ / \
2 39 53
\ /
4 32
\
74
/
67
/
60
/
11
```
在等概率的情况下查找成功和查找不成功情况下的平均查找长度分别为:
对于查找成功的情况,每个元素被查找到的概率均为1/12,因此平均查找长度为(1+2+2+3+3+3+3+4+4+4+4+5)/12=3.08。
对于查找不成功的情况,需要遍历到每个叶子结点才能确定查找失败,因此平均查找长度为(4+3+3+4+4+4+4+5+5+5+5+6)/12=4.42。
已知一组记录为(46,74,53,14,26,38,86,65.27,34),给出采用下列排序时每一趟的排序结果:
这里给出三种常见的排序算法的每一趟排序结果:
1. 冒泡排序
第一趟排序结果:(46, 53, 14, 26, 38, 74, 65, 27, 34, 86)
第二趟排序结果:(46, 14, 26, 38, 53, 65, 27, 34, 74, 86)
第三趟排序结果:(14, 26, 38, 46, 53, 27, 34, 65, 74, 86)
第四趟排序结果:(14, 26, 38, 46, 27, 34, 53, 65, 74, 86)
第五趟排序结果:(14, 26, 38, 27, 34, 46, 53, 65, 74, 86)
第六趟排序结果:(14, 26, 27, 34, 38, 46, 53, 65, 74, 86)
2. 插入排序
第一趟排序结果:(46, 74, 53, 14, 26, 38, 86, 65, 27, 34)
第二趟排序结果:(46, 53, 74, 14, 26, 38, 86, 65, 27, 34)
第三趟排序结果:(14, 46, 53, 74, 26, 38, 86, 65, 27, 34)
第四趟排序结果:(14, 26, 46, 53, 74, 38, 86, 65, 27, 34)
第五趟排序结果:(14, 26, 38, 46, 53, 74, 86, 65, 27, 34)
第六趟排序结果:(14, 26, 38, 46, 53, 74, 86, 65, 27, 34)
第七趟排序结果:(14, 26, 38, 46, 53, 65, 74, 86, 27, 34)
第八趟排序结果:(14, 26, 27, 38, 46, 53, 65, 74, 86, 34)
第九趟排序结果:(14, 26, 27, 34, 38, 46, 53, 65, 74, 86)
3. 快速排序
第一趟排序结果:(34, 14, 26, 38, 27, 46, 53, 74, 65, 86)
第二趟排序结果:(27, 14, 26, 34, 38, 46, 53, 74, 65, 86)
第三趟排序结果:(14, 26, 27, 34, 38, 46, 53, 74, 65, 86)
可以看出,不同的排序算法会有不同的排序结果和趟数。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)