因为时间关系(现阶段来不及),先不学红黑树和B树,所以这是查找(一)。
先写一下二分查找,数据结构数上叫的“折半查找”。
二分查找
左闭右闭区间
左闭右开区间
下面依旧是对王道书上选择题的一个简单纠错(摸鱼),希望6.10能写完查找部分,6.11写完排序部分
顺序查找和折半查找
1.(B)
对于顺序查找,每个元素查找成功需要比较的次数只与其位置有关,与序列是否有序没半毛钱关系
2.(A)计算错误
3.折半查找过程对应的判定树是平衡二叉树
4.(A)(B)
次数最少的情况就是很正常的每次除以2,统计最后到1的次数
次数最多的情况,用公式就是:
H=[log(n+1)]以2为底
5.(A)(D)
折半查找的判定树怎么画
6.(B)
用公式ASL=(s^2+2s+n)/2s
7.(A)暂时不是很懂答案怎么想出来的
二叉排序树
定义
查找
非递归法(最坏空间复杂度O(1))
递归法(最坏空间复杂度O(h))
插入
构造
二叉树的构造也是用的递归,按顺序,第一个元素作为根节点,之后按照小于根节点的在左子树,大于根节点的在右子树
的递归原则,递归下去
删除
要删除的结点有三种情况
- 只有左子树
- 只有右子树
- 左右子树都有
查找效率
- 最优:O(logn),以2为底
- 最差:O(n)
平衡二叉树
选择题的重点是如何调整成平衡二叉树
先不管什么左旋右旋,只要记得顶点旋转后的位置,剩下的按照中序遍历的序列去写
RR
A左下旋转,B左上旋转
RL
LL
RR
平衡二叉树的删除
删完了之后为了保持平衡,主要还是遵循上图的规则,王道PPT上面都有写,我也跟着浅写了一遍,也不是非常非常重要的部分
选择题错题
二叉排序树的查找过程:
- 先查找根结点 若相同则结束
- 否则根据比较结果,沿着左子树或者右子树继续向下找
2.(C)
当插入的关键字有序时,二叉排序树会形成一个长链,此时深度最大
3.(D)
含有20个结点的平衡二叉树的最大深度为6
使用平衡二叉树结点的递推公式,构造5层平衡二叉树最少要12个结点,构造6层要至少20个
5.(A)
6.(B)
所有非叶结点的平衡因子均为1,说明平衡二叉树满足最少结点的情况
用递推公式得20个结点
7.
8.(D)
画图
9.(D)
平衡二叉树是一种高度平衡的二叉树,二叉排序树的中序序列是一个升序序列,题中说的是降序序列
(A)只有两个结点的平衡二叉树根结点的度为1
(B)树中最大元素一定无右子树,可能有左子树,所以不一定是叶结点
(C)最后插入的元素可能导致平衡调整,而该元素不一定是叶结点,有时候还是根结点
10.(A)
太难了,隔行如隔山,这很难评,这分在我这基础阶段是不要了
散列选择题纠错
只能在顺序存储结构上进行查找的方法是
折半查找法
12.(A)
-
同义词冲突不等于聚集
-
链地址法处理冲突时将同义词放在同一个链表中,不会引起聚集现象
采用开放地址解决冲突的散列查找中,发生聚集的主要原因是
解决冲突的方法选择不当
15.(A)(C)
H的取值有17种可能,对应到不同的链表中,所以链表的个数为17。H(key)的取值范围为0-16,所以数组下标为0-16
16.(A)
错因:画图画错了
17.(D)
用散列方法处理冲突时可能出现堆积(聚集)现象,
平均查找长度
会受堆积现象直接影响文章来源:https://www.toymoban.com/news/detail-486433.html
19.注意求ASL(失败)的方法文章来源地址https://www.toymoban.com/news/detail-486433.html
到了这里,关于【数据结构】查找(一)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!