数据结构与算法(test3)

七、查找

1. 看图填空

查找表是由同一类型的数据元素(或记录)构成的集合。例如上图就是一个查找表。

期中(1)是______________. (2)是______________(3)是_____关键字_______。

2. 查找(Searching) 就是根据给定的某个值,  在查找表中确定一个其____________等于给定值的_______________。

3. 列出常见的三种查找算法:______________、______________、______________。

4. ___________又叫线性查找, 是最基本的查找技术,它的查找过程是: 从表中第一个(或最后1个)记录开始,

逐个进行记录的_________与给定值比较,一直到找到相等的记录,它的时间复杂度是_____________。

它对表中记录是否有序___________(有 / 没有)要求。

5. ___________又称为二分查找,它的前提是线性表中的记录必须是________________, 线性表必须采用__________存储。它的时间复杂度是_____________。

6. ___________查找,是把数据集的记录分成若干块,并且这些块需要满足两个条件:

(1). 块内的记录特点:____________________________________。

(2). 块间的记录特点:____________________________________。

7. 二叉排序树,又称为二叉查找树,它或者是一棵空树,或者是具有下列性质:

(1). 若它的左子树不空, 则左子树上所有结点的值均小于它的_____结点的值。

(2). 若它的右子树不空, 则右子树上所有结点的值均大于它的_____结点的值。

(3). 它的左、右子树也分别为_________树。

它的时间复杂度是________________.

8. 二叉排序树是以____________方式存储,这种存储结构在执行插入、删除时不用移动元素的优点。找到合适的插入、删除位置后,仅需要修改__________即可。

9. 散列技术是在记录的_________和它的__________之间建立一个确定的对应关系f, 使得每个_________对应一个存储位置f(key)。

查找时,根据这个确定的对应关系找到给定值key的映射 f(key), 若查找集合中存在这个记录,则必定在f(key)的位置上。

这里我们把对应关系f 称为_________函数,又称为______函数。

采用散列技术将记录存储在一块地址___________的存储空间中,这块连续的存储空间称为______表或_____表。关键字对应的记录位置我们称为_______地址。


10. 散列技术即是一种存储方法,也是一种查找方法,它的时间复杂度是________________。

11. 散列表查找,如果没有冲突,它的效率很高,它的时间复杂度是________。可惜,没有冲突的散列只是一种理想,在实际的应用中,冲突是不可避免的,他的平均查找性能,取决于以下3个因素。

(1) 散列函数的好坏直接影响着出现冲突的频繁程度,它的主要指标是_______________。

(2)处理冲突的方法____________________。

(3) 散列表的装填因子。请解释装填因子是什么_____________________________________。

12. 给定一个长度为n的整形数组 int data[n],  它的数据以按从小到大排序。请用折半查找法,

完成以下函数,要求: 如果查找到目标数据target,则返回所在位置的数组下标,否则返回-1.

int findIndex(int data[], int size, int target)

{

}


 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/15681.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

机器学习在癌症分子亚型分类中的应用

学习笔记:机器学习在癌症分子亚型分类中的应用——Cancer Cell 研究解析 1. 文章基本信息 标题:Classification of non-TCGA cancer samples to TCGA molecular subtypes using machine learning发表期刊:Cancer Cell发表时间:20…

48V电气架构全面科普和解析:下一代智能电动汽车核心驱动

48V电气架构:下一代智能电动汽车核心驱动 随着全球汽车产业迈入电动化、智能化的新时代,传统12V电气系统逐渐暴露出其无法满足现代高功率需求的不足。在此背景下,48V电气架构应运而生,成为现代电动汽车(EV&#xff09…

Mac(m1)本地部署deepseek-R1模型

1. 下载安装ollama 直接下载软件,下载完成之后,安装即可,安装完成之后,命令行中可出现ollama命令 2. 在ollama官网查看需要下载的模型下载命令 1. 在官网查看deepseek对应的模型 2. 选择使用电脑配置的模型 3. copy 对应模型的安…

操作教程丨使用1Panel开源面板快速部署DeepSeek-R1

近期,DeepSeek-R1模型因其在数学推理、代码生成与自然语言推理等方面的优异表现而受到广泛关注。作为能够有效提升生产力的工具,许多个人和企业用户都希望能在本地部署DeepSeek-R1模型。 通过1Panel的应用商店能够简单、快速地在本地部署DeepSeek-R1模型…

免费在腾讯云Cloud Studio部署DeepSeek-R1大模型

2024年2月2日,腾讯云宣布DeepSeek-R1大模型正式支持一键部署至腾讯云HAI(高性能应用服务)。开发者仅需3分钟即可完成部署并调用模型,大幅简化了传统部署流程中买卡、装驱动、配网络、配存储、装环境、装框架、下载模型等繁琐步骤。…

C语言-结构体

1.共用体: union //联合--共用体 早期的时候,计算机的硬件资源有限, 能不能让多个成员变量 公用同一块空间 //使用方式 类似 结构体 --- 也是构造类型 struct 结构体名 { 成员变量名 }; union 共用体名 { 成员变量名 }; //表示构造了一个共用体…

多头自注意力中的多头作用及相关思考

文章目录 1. num_heads2. pytorch源码演算 1. num_heads 将矩阵的最后一维度进行按照num_heads的方式进行切割矩阵,具体表示如下: 2. pytorch源码演算 pytorch 代码 import torch import torch.nn as nn import torch.nn.functional as Ftorch.set…

数据仓库和商务智能:洞察数据,驱动决策

在数据管理的众多领域中,数据仓库和商务智能(BI)是将数据转化为洞察力、支持决策制定的关键环节。它们通过整合、存储和分析数据,帮助组织更好地理解业务运营,预测市场趋势,从而制定出更明智的战略。今天&a…

C++ ——从C到C++

1、C的学习方法 (1)C知识点概念内容比较多,需要反复复习 (2)偏理论,有的内容不理解,可以先背下来,后续可能会理解更深 (3)学好编程要多练习,简…

半导体制造工艺讲解

目录 一、半导体制造工艺的概述 二、单晶硅片的制造 1.单晶硅的制造 2.晶棒的切割、研磨 3.晶棒的切片、倒角和打磨 4.晶圆的检测和清洗 三、晶圆制造 1.氧化与涂胶 2.光刻与显影 3.刻蚀与脱胶 4.掺杂与退火 5.薄膜沉积、金属化和晶圆减薄 6.MOSFET在晶圆表面的形…

Avnet RFSoC基于maltab得5G 毫米波 开发工具箱

使用 MATLAB 连接到 AMD Zynq™ RFSoC 评估板。使用 RF 附加卡执行 OTA 测试。使用 HDL Coder 部署算法 版本要求: 大于 2023b 需要以下支持包之一: 适用于 Xilinx 基于 Zynq 的无线电(R2023b 及更早版本)的通信工具箱支持包适…

第三节 docker基础之---Commit+Dockerfile制作

docker目前镜像的制作两种方法: 1,基于docker Commit制作镜像 2,基于dockerfile制作镜像,Dockerfile 为主流的制作方式 如果不制作镜像删除容器之后则里面配置的文件也随之删除: [rootdocker ~]# docker images 查看…

推荐一个免费的、开源的大数据工程学习教程

在当今信息爆炸的时代,每一个企业都会产生大量的数据,而大数据也已经成为很多企业发展的重要驱动力,然而如何有效得处理和分析这些海量的数据,却是一个非常有挑战的技术。 今天推荐一个免费的数据工程教程,带你系统化…

【文档智能多模态】英伟达ECLAIR-端到端的文档布局提取,并集成阅读顺序方法

笔者在前期一个系列分享了各种文档智能相关的技术方法,可以参考《文档智能系列栏目》,涵盖各种常见方法。 下面直接看看这个端到端的文档智能结构化方法,供参考。 方法 一、架构 ECLAIR 采用了一个较大的视觉编码器(657M 参数…

解锁Netty:Channel更替与HashMap管理的奇妙联动

个人CSDN博客主页: java之路-CSDN博客 ( 期待您的关注 ) 目录 Netty 的 Channel 机制探秘 HashMap 在 Netty 中的角色 创建新 Channel 时的操作步骤 新 Channel 的创建流程 确定老 Channel 的标识 移除老 Channel 的具体方法 从 HashMap 中移除 关闭和回收老…

小白零基础如何搭建CNN

1.卷积层 在PyTorch中针对卷积操作的对象和使用的场景不同,如有1维卷积、2维卷积、 3维卷积与转置卷积(可以简单理解为卷积操作的逆操作),但它们的使用方法比较相似,都可以从torch.nn模块中调用,需要调用的…

12.翻转、对称二叉树,二叉树的深度

反转二叉树 递归写法 很简单 class Solution { public:TreeNode* invertTree(TreeNode* root) {if(rootnullptr)return root;TreeNode* tmp;tmproot->left;root->leftroot->right;root->righttmp;invertTree(root->left);invertTree(root->right);return …

算法之 博弈问题

文章目录 巴什博弈292.Nim 游戏 尼姆博弈斐波那契博弈其他博弈1025.除数博弈 博弈问题,就是双方之间的PK,关注的重点是 谁先?以及A,B各自赢的条件 一般有数学问题,动态规划,搜索进行求解 巴什博弈 下面的这题Nim 游戏,…

Linux 安装 Ollama

1、下载地址 Download Ollama on Linux 2、有网络直接执行 curl -fsSL https://ollama.com/install.sh | sh 命令 3、下载慢的解决方法 1、curl -fsSL https://ollama.com/install.sh -o ollama_install.sh 2、sed -i s|https://ollama.com/download/ollama-linux|https://…

DDR原理详解

DDR原理详解 存储器主要分为只读存储器 ROM 和随机存取存储器 RAM两大类。 ROM:只读存储器 ROM 所存数据,一般是装入整机前事先写好的,整机工作过程中只能读出,ROM所存数据稳定,断电后所存数据也不会改变。 RAM:随机…