首页 > 其他分享 >查找的一些问题

查找的一些问题

时间:2023-11-30 22:57:53浏览次数:34  
标签:折半 22 元素 问题 查找 哈希 一些 100

1.对n个元素的表做顺序查找时,若查找每个元素的概率相同,则平均查找长度为((n+1)/2 )。

解析:第一次比较的次数为1,第二次为2····第n次的比较次数为n,所以总的比较次数为n(n+1)/2,平均比较次数=(n+1)/2。

2.适用于折半查找的表的存储方式及元素排列要求为( 顺序方式存储,元素有序)。

解析:折半查找过程中需要定位待查找表的上界下界和中间位置,因此线性表必须餐区顺序存储结构,而表中元素按关键字有序排列。

3.如果要求一个线性表既能较快的查找,又能适应动态变化的要求,最好采用(分块查找 )查找法。

解析:顺序查找:简单效率低

           折半查找:不适合线性表的动态变化

          哈希查找:映射关系

           分块查找(索引顺序查找):在表中插入或删除元素数据元素时,只要找到该元素对应的块,就可以在该块内进行查找和删除运算。由于块内的无序的,因此插入删除比较容易,无需大量移动。

4.折半查找有序表(4,6,10,12,20,30,50,70,88,100)。若查找表中元素58,则它将依次与表中( 20,70,30,50)比较大小,查找结果是失败。

           十个数,向下取整 mid(1+10)=5.5->5,先于20比较,58>20在右子表中查找;{30,50,70,88,100}中查找,[(6+10)/2]=8,与第8个数70比较,58<70,在左子表中进行查找;对于左子表{30,50},取(6+7)/2取整6,与第六个元素30比较,58>30```````58>50,查找失败。

5.对22个记录的有序表作折半查找,当查找失败时,至少需要比较( 4)次关键字。

判定树的深度为[log2^22]+1=5,且该判定树不是满二叉树,既查找失败时最多比较5次最少比较4次

第一次11 mid=(0+21)/2=10

不相等在[0,9]中查找或者在[11,22]查找。

第二次mid=(0+9)/2=4或者mid=(11+22)/2=16

不相等在[0,3]或者[16,22]中查找

第三次mid=(0+3)/2=1或者(16+22)/2=19

不相等[0,0]或者[20,22]中查找

第四次直接判断第一个位置或者(19+22)/2=21

第五次[22,22]最后一个位置直接判断一下。

6.折半搜索与二叉排序树的时间性能( 有时不相同)。

折半查找:必须要求记录有序却时顺序存储,利用这个特点,折半查找小路更高,对于数量大时候非常块,时间复杂度O(logN)

二叉查找树:如果它的左子树不是空的那么左子树中所有结点都小于根节点;如果右子树不是空,那么右子树中所有结点都大于根节点的值,它的左子树和右子树都是二叉搜索树。

因此二叉排序树不一定时平衡树,它只需要左右子树和根节点的大小关系,但是由于没有左右子树层次差异,所以通过二叉排序树搜索可能不满足logn

7.

分别以下列序列构造二叉排序树,与用其它三个序列所构造的结果不同的是( c)。

A.

(100,80, 90, 60, 120,110,130)

B.

(100,120,110,130,80, 60, 90)

C.

(100,60, 80, 90, 120,110,130)

D.

(100,80, 60, 90, 120,130,110)

解析:如果它的左子树不是空的那么左子树中所有结点都小于根节点;如果右子树不是空,那么右子树中所有结点都大于根节点的值,

8.在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作(LR)型调整以使其平衡。

 

9.下面关于哈希查找的说法,正确的是( c)。

A.

哈希函数构造的越复杂越好,因为这样随机性好,冲突小

B.

除留余数法是所有哈希函数中最好的

C.

不存在特别好与坏的哈希函数,要视情况而定

D.

哈希表的平均查找长度有时也和记录总数有关

10.

下面关于哈希查找的说法,不正确的是(a )。

A.

采用链地址法处理冲突时,查找一个元素的时间是相同的

B.

采用链地址法处理冲突时,若插入规定总是在链首,则插入任一个元素的时间是相同的

C.

用链地址法处理冲突,不会引起二次聚集现象

D.

用链地址法处理冲突,适合表长不确定的情况

解析:哈希表提供了很多解决哈希冲突的方案,必须线性探索发,再哈希法,连地址法。

链地址法:将所有哈希地址相同记录都链接再同一链表中。

11采用线性探测法处理冲突,可能要探测多个位置,在查找成功的情况下,所探测的这些位置上的关键字 (不一定都是同义词 )。

解析:同义词是指具有相同散列函数值的关键字。

散列表的存储结构时根据关键字的散列函数值来确定关键字再散列表中的存储位置,对同义词的处理根据不同情况右不同的冲突处理方式。

用线性探测法查找闭散列表,可能探测东哥散列地址,这些位置上的键值不一定都是同义词,因为同义词不一定右相同的哈希值,不一定存放在相邻的位置。

标签:折半,22,元素,问题,查找,哈希,一些,100
From: https://www.cnblogs.com/aixin52129211/p/17868597.html

相关文章

  • JSONObject参数顺序问题
    签名需要规定参数顺序不能错。一开始是这么写的JSONObjectparam=newJSONObject();param.put("idcard",user.getIdCard());param.put("mobile",user.getPhone());param.put("uid",user.getId());param.put("username",user.getName());期望得到的顺序应该......
  • 商家转账到零钱全攻略:开通、使用、区别与常见问题解答
    一、商家转账到零钱功能介绍微信作为中国最受欢迎的社交平台之一,其支付功能也相当强大。其中,商家转账到零钱功能可以让商家直接将款项转入用户的微信零钱,方便快捷。本文将详细介绍商家转账到零钱的功能、开通条件、使用方法以及常见问题解答。二、商家转账到零钱场景说明商家转......
  • SqlServer中常用的一些操作语句
    我们在维护数据库数据的时候,通常会用到各种SQL语句对数据进行操作或者维护,如:查看某个数据库中有哪些用户数据表、每个数据表中总共有多少条数据……SqlServer官方地址:https://learn.microsoft.com/zh-cn/sql1、整理说明我们在维护数据库数据的时候,通常会用到各种SQL语句对数......
  • python打包本地pip包需要注意哪些问题
    参考资料:https://packaging.python.org/tutorials/packaging-projects/提到Python的包管理器,大多数人都会想到pip和conda,其中又尤以pip简单好用。那么如果有一天你写了一个有用的项目,想要发布给公众,或者实现方便的安装,那么你可能就会想要自己去打包一个pip包。毕竟,......
  • axios(ajax)发送请求响应码200,但获取不到数据,无法加载响应数据: No datafound for res
    问题截图:没有响应数据控制台报错其实是由于浏览器的跨域资源共享(CORS)策略导致,前后端跨域请求是不行的。什么是域,看页面的url,比如https://www.baidu.com/下的网页都是属于baidu.com这个域。如果你是和我一样是从本地文件打开html的方式来调试ajax,那么一定会出现这个问题,因为本......
  • Ascend C 算子开发遇到的问题及解决方法
    摘要:在学习AscendC算子开发进阶课程的时候,进行AscendC自定义算子工程、算子调用等实验,在开发环境中遇到了一些问题,在这里记录一下。首先如果在启智社区CANN版本为6.3,要进行AscendC算子开发,需要更新CANN版本。在CANN社区根据你的架构,比如我的为CPU架构位aarch64,所以下载Ascend-......
  • 浅谈一类高斯求和问题
    引入相信大家都知道高斯求和公式:首项加末项的和乘项数除以二等于等差数列的和。实际应用中往往不会这么简单,常常会告诉你等差数列的和然后让你反过来求等差数列的信息,这时候对于边界的处理就很重要。P1014[NOIP1999普及组]Cantor表显然可以\(O(N)\)模拟,但这太慢了。先......
  • 使用keepalive针对页面缓存的一些问题的解决方法
    场景介绍在项目前端设计中有一个需求,需要跳转到其他页面先拿到数据,再返回到原界面,但是原界面填写的数据会被刷新,因此在这个地方需要对页面的数据进行缓存需求分析项目使用的是Vue3,对于页面缓存,在网上搜索后锁定了keepAlive做缓存简介keep-alive是Vue的内置组件,当它包裹动态组......
  • `pd.Timestamp.now()`和`datetime.datetime.now()`都是用来获取当前时间的函数,但它们
    `pd.Timestamp.now()`和`datetime.datetime.now()`都是用来获取当前时间的函数,但它们之间存在一些差异¹²。-`pd.Timestamp.now()`返回的是Pandas的Timestamp对象,这个对象是在UTC(协调世界时)时区下的当前时间¹²。-`datetime.datetime.now()`返回的是Python的datetime对象,这个......
  • uni-app打包成H5,与PC不适配的问题
    既然是写专门的H5站,那说明希望在pc打开,也是H5的排版,比如一体机上,它是网页打开,但是尺寸是1080*1920,在pages.json配置:这里我配置了1920,是因为网页端还有1920的尺寸最大宽度是配置了1920,超出两边留白,这个我测了一下,似乎有点变形,但是我这边目前只需要适配1080的宽度,所以这一点留给大......