【数据结构】查找(一)

这篇具有很好参考价值的文章主要介绍了【数据结构】查找(一)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

因为时间关系(现阶段来不及),先不学红黑树和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)

【数据结构】查找(一)
【数据结构】查找(一)

用散列方法处理冲突时可能出现堆积(聚集)现象,平均查找长度会受堆积现象直接影响

19.注意求ASL(失败)的方法文章来源地址https://www.toymoban.com/news/detail-486433.html

到了这里,关于【数据结构】查找(一)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构--6.3查找算法(静态、动态)(插值查找)

    静态查找:数据集合稳定,不需要添加,删除元素的查找操作。 动态查找:数据集合在查找的过程中需要同时添加或删除元素的查找操作。 对于静态查找来说,我们不妨可以用线性表结构组织数据,这样可以使用顺序查找算法,如果我们在对进行排序,则可以使用折

    2024年02月09日
    浏览(42)
  • 数据结构-查找(顺序查找与二分查找的讲解与代码实现)

    顺序查找概念:从表的另一端开始,一次将记录的和给定值进行比较,若某个记录的和给定的值相等,则查找成功,反之则查找失败。 ASL:平均查找长度 pi查找概率,ci查找次数 eg:序列1,2,3 查找1的次数为1概率为1/3,2为两次概率1/3,3的次数为3概率1/3  将12

    2024年02月06日
    浏览(68)
  • 折半查找实验 (数据结构)

    一、实验目的 掌握折半查找算法的基本思想 掌握折半查找算法的实现方法 掌握折半查找的时间性能 掌握折半查找类的定义和使用 二、实验要求 熟悉C++语言编程 了解折半查找的原理 了解折半查找类的定义、应用 三、实验内容 1、问题描述 在一个有序序列中,折半查找一个

    2024年02月08日
    浏览(85)
  • 【数据结构】查找(一)

    因为时间关系(现阶段来不及),先不学红黑树和B树,所以这是查找(一)。 先写一下二分查找,数据结构数上叫的“折半查找”。 下面依旧是对王道书上选择题的一个简单纠错(摸鱼),希望6.10能写完查找部分,6.11写完排序部分 1.(B) 对于顺序查找,每个元素查找成功

    2024年02月09日
    浏览(12)
  • 数据结构-查找1

    1.对n个元素的表做顺序查找时,若查找每个元素的概率相同,则平均查找长度为(   )。 A.(n-1)/2       B. n/2        C.(n+1)/2        D.n  答案:C 解释:总查找次数N=1+2+3+…+n=n(n+1)/2,则平均查找长度为N/n=(n+1)/2。 2.适用于折半查找的表的存储方式及元素排列要求为(

    2024年02月03日
    浏览(37)
  • 数据结构-查找2(详解)

    1 .在一棵由包含 4、5、6 等等一系列整数结点构成的二叉搜索树中,如果结点 4 和 6 在树的同一层,那么可以断定结点 5 一定是结点 4 和 6 的父亲结点。  错    解析:         反例  2.二叉搜索树的查找和折半查找的时间复杂度相同。 错   解析:不一定相同。二叉排序树

    2024年02月02日
    浏览(36)
  • 数据结构——查找

    目录 1.查找的基本概念 1.1基本概念 ​编辑1.2对查找表的常见操作 以此分为静态查找表和动态查找表:​编辑1.3查找算法的评价指标 2.顺序查找 2.1算法思想 2.2算法实现 2.2.1顺序表查找的实现 2.2.2顺序表查找的实现(哨兵) 2.3顺序查找效率及算法优化 3.折半查找⭐ 3.1算法思想

    2024年02月06日
    浏览(17)
  • 数据结构之查找详解

    1.1 定义 查找表是由同一类型的数据元素构成的集合。 例如电话号码簿和字典都可以看作是一张查找表。 1.2 查找表的几种操作: 1)在查找表中查找某个具体的数据元素; 2)在查找表中插入数据元素; 3)从查找表中删除数据元素; 1.3 静态查找表和动态查找表 在查找表中

    2024年01月16日
    浏览(32)
  • 数据结构_查找

    目录 1. 查找的基本概念 2. 顺序查找和折半查找 2.1 顺序查找 2.1.1 一般线性表的顺序查找 2.1.2 有序表的顺序查找 2.2 折半查找 2.3 分块查找 2.4 相关练习 3. 树型查找         3.1 二叉排序树 3.1.1 二叉排序树的定义 3.1.2 二叉排序树的查找 3.1.3 二叉排序树的插入 3.1.4 二叉排序

    2024年02月04日
    浏览(25)
  • 数据结构习题9---查找

    一、填空题 1 .   在数据的存放无规律而言的线性表中进行检索的最佳方法是    顺序查找(线性查找)    。 2 . 线性有序表( a 1 , a 2 , a 3 ,…, a 256 ) 是从小到大排列的,对一个给定的值k,用二分法检索表中与k相等的元素,在查找不成功的情况下,最多需要检索   

    2024年02月09日
    浏览(63)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包