【2012年数据结构真题】
41题

(1) 最坏情况下比较的总次数
对于长度分别为 m,n 的两个有序表的合并过程,最坏情况下需要一直比较到两个表的表尾元素,比较次数为 m+n-1 次。已知需要 5 次两两合并,故设总比较次数为 X-5, X 就是以 N 个叶子结点表示升序表,以升序表的表长表示结点权重,构造的二叉树的带权路径长度。故只需设计方案使得 X 最小。设计哈夫曼树如下:

这样, 最坏情况下比较的总次数为:
N=(10+35)x4+(40+50+60)x3+200-5=825
(2) N (N≥2)个不等长升序表的合并策略:
以 N 个叶子结点表示升序表, 以升序表的表长表示结点权重, 构造哈夫曼树合并时,从深度最大的结点所代表的升序表开始合并,依深度次序一直进行到根结点。
理由: N 个有序表合并需要进行 N- 1 次两两合并,可设最坏情况下的比较总次数为 X-N+1,X 就是以 N 个叶子结点表示升序表, 以升序表的表长 表示结点权重,构造的二叉树的带权路径长度。根据哈夫曼树的特点,上述设计的比较次数是最小的。
42题
假定采用带头结点的单链表保存单词,当两个单词有相同的后缀,则可共享相同的后缀存储空间, 例如,“loaging"和"being”, 如下图所示。

设 str1 和 str2 分别指向两个单词所在单链表的头结点, 链表结点结构为

请设计一个时间上尽可能高效的算法,找出由 str1 和 str2 所指向两个链表
共同后缀的起始位置(如图中字符 i 所在结点的位置 p)。
要求:
最优解:
(1) 给出算法的基本设计思想。
顺序遍历两个链表到尾结点时,并不能保证两个链表同时到达尾结点。这是 因为两个链表的长度不同。假设一个链表比另一个链表长 k 个结点, 我们 先在长链表上遍历 k 个结点, 之后同步遍历两个链表。这样我们就能够保 证它们同时到达最后一个结点了。由于两个链表从第一个公共结点到链表 的尾结点都是重合的。所以它们肯定同时到达第一个公共结点。

算法的基本设计思想:
- 分别求出 str1 和 str2 所指的两个链表的长度 m 和 n。
- 将两个链表以表尾对齐: 令指针 p、q 分别指 str1 和 str2 的头结点,若 m>=n,则使p指向链表中的第 m-n+1个结点; 若m<n,则使q 指向链表中的第 n-m+1 个结点,即使指针 p 和 q 所指的结点到表尾的长度相等。
- 反复将指针 p 和 q 同向后移动,并判断它们是否指同一结点。若 p 和 q 指向同一结点,则该点即为所求的共同后缀的起始位置。
简单来说就是:
① 求它们的长度 len1, len2;
② 遍历两个链表, 使 p, q 指向的链表等长;
④ 同步遍历两个链表, 直至找到相同结点或链表结束。
(2) 根据设计思想, 采用 C 或 C++或 java 语言描述算法,关键之处给出注释。

(3) 说明你所设计算法的时空复杂度。
时间复杂度为O(len1+len2)或O(max(len1,len2)), 其中len1、 len2分别为两个链表 的
长度。
暴力解:
定义两个指针P和G,分别指向想象中的链表,每遍历一个字符i,就全部遍历一次g所指向的单词,所有比较一次。
- P不为空一直往前走
- g不空往前走
- 两者判断比较
#include <cstddef>
typedef struct Lnode { //链表结点的结构定义int data;struct Lnode* next;
} Lnode,* Linklist;Linklist searchCommon(Linklist L1, Linklist L2) {LinkTist p = L1->next;Linklist g = L2->next;while (p != NULL) {while (g != NULL) {if (p == g) {return g;}g = g->next;}p = p->next;g = g->next;return NULL;}
}
相关文章:
【2012年数据结构真题】
41题 (1) 最坏情况下比较的总次数 对于长度分别为 m,n 的两个有序表的合并过程,最坏情况下需要一直比较到两个表的表尾元素,比较次数为 mn-1 次。已知需要 5 次两两合并,故设总比较次数为 X-5, X 就是以 N…...
k8s_base
应用程序在服务器上部署方式的演变,互联网发展到现在为止 应用程序在服务器上部署方式 历经了3个时代1. 传统部署 优点简单 缺点就是操作系统的资源是有限制的,比如说操作系统的磁盘,内存 比如说我8G,部署了3个应用程序,当有一天…...
2023年亚太杯APMCM数学建模大赛数据分析题MySQL的使用
2023年亚太杯APMCM数学建模大赛 以2022年C题全球变暖数据为例 数据分析: 以2022年亚太杯数学建模C题为例,首先在navicat建数据库然后右键“表”,单击“导入向导”,选择对应的数据格式及字符集进行数据导入 导入之后,…...
自学SLAM(8)《第四讲:相机模型与非线性优化》作业
前言 小编研究生的研究方向是视觉SLAM,目前在自学,本篇文章为初学高翔老师课的第四次作业。 文章目录 前言1.图像去畸变2.双目视差的使用3.矩阵微分4.高斯牛顿法的曲线拟合实验 1.图像去畸变 现实⽣活中的图像总存在畸变。原则上来说,针孔透…...
STL—next_permutation函数
目录 1.next_permutation函数的定义 2.简单使用 2.1普通数组全排列 2.2结构体全排列 2.3string 3.补充 1.next_permutation函数的定义 next_permutation函数会按照字母表顺序生成给定序列的下一个较大的排列,直到整个序列为降序为止。与其相对的还有一个函数—…...
Mysql 三种不使用索引的情况
目录 1. 查询语句中使用LIKE关键字 例 1 2. 查询语句中使用多列索引 例 2 3. 查询语句中使用OR关键字 例 3 总结 索引可以提高查询的速度,但并不是使用带有索引的字段查询时,索引都会起作用。使用索引有几种特殊情况,在这些情况下&…...
Ladybug 全景相机, 360°球形成像,带来全方位的视觉体验
360无死角全景照片总能给人带来强烈的视觉震撼,有着大片的既视感。那怎么才能拍出360球形照片呢?它的拍摄原理是通过图片某个点位为中心将图片其他部位螺旋式、旋转式处理,从而达到沉浸式体验的效果。俗话说“工欲善其事,必先利其…...
centos 6.10 安装swig 4.0.2
下载地址 解压文件。 执行下面命令 cd swig-4.0.2 ./configure --prefix/usr/local/swig-4.0.2 make && make install...
mask: rle, polygon
RLE 编码 RLE(Run-Length Encoding)是一种简单而有效的无损数据压缩和编码方法。它的基本思想是将连续相同的数据值序列用一个值和其连续出现的次数来表示,从而减少数据的存储或传输量。 在图像分割领域(如 COCO 数据集中&#…...
【JMeter】JMeter压测过程中遇到Non HTTP response code错误解决方案
压测过程中并发逐步加大后遇到60%的错误率,查看错误是JMeter网页版聚合报告中显示 Non HTTP response code: java.net.NoRouteToHostException/Non HTTP response message: Cannot assign requested address (Address not available) 这是第二次遇到,故…...
【Kingbase FlySync】评估工具安装及使用
【Kingbase FlySync】评估工具使用 概述准备环境目标资源1.测试虚拟机下载地址包含node1,node22.评估工具下载地址3.exam.sql下载地址 评估工具安装1.上传并解压评估工具安装包2.安装数据库驱动包3.设置环境变量4.node1载入样例信息 收集并阅读node1信息1.收集报告2.阅读报告 收…...
pandas教程:Data Aggregation 数据聚合
文章目录 10.2 Data Aggregation(数据聚合)1 Column-Wise and Multiple Function Application(列对列和多函数应用)2 Returning Aggregated Data Without Row Indexes(不使用行索引返回聚合数据) 10.2 Data…...
开启创造力之门:掌握Vue中Slot插槽的使用技巧与灵感
🎬 江城开朗的豌豆:个人主页 🔥 个人专栏 :《 VUE 》 《 javaScript 》 📝 个人网站 :《 江城开朗的豌豆🫛 》 ⛺️ 生活的理想,就是为了理想的生活 ! 目录 ⭐ 专栏简介 📘 文章引言 一、s…...
【算法练习Day48】回文子串最长回文子序列
📝个人主页:Sherry的成长之路 🏠学习社区:Sherry的成长之路(个人社区) 📖专栏链接:练题 🎯长路漫漫浩浩,万事皆有期待 文章目录 回文子串最长回文子序列总结…...
ubuntu下C++调用matplotlibcpp进行画图(超详细)
目录 一、换源 二、安装必要的软件 三、下载matplotlibcpp 四、下载anaconda 1.anaconda下载 2.使用anaconda配置环境 五、下载CLion 1.下载解压CLion 2.替换jbr文件夹 3.安装CLion 4.激活CLion 5.CLion汉化 6.Clion配置 六、使用CLion运行 七、总结 我的环…...
芯科科技推出新的8位MCU系列产品,扩展其强大的MCU平台
新的BB5系列为简单应用提供更多开发选择 中国,北京 - 2023年11月14日 – 致力于以安全、智能无线连接技术,建立更互联世界的全球领导厂商Silicon Labs(亦称“芯科科技”,NASDAQ:SLAB),今日宣布…...
Flink CDC
1、Flink CDC的介绍: 是一种技术,可以帮助我们实时的捕获数据库中数据的变化,并将这些变化的数据以流的形式传输到其他的系统中进行处理和存储。 2、Flink CDC的搭建: 1、开启mysql的binlog功能: # 1、修改mysql配置…...
数据结构-链表的简单操作代码实现3-LinkedList【Java版】
写在前: 本篇博客主要介绍关于双向链表的一些简答操作实现,其中有有部分代码的实现和前两篇博客中的单向链表是相类似的。例如:查找链表中是否包含关键字key、求链表的长度等。 其余的涉及到prev指向的需要特别注意,区分和单向链表之间的差异…...
JTS: 24 MinimumDiameter 最小矩形
文章目录 版本代码 版本 org.locationtech.jts:jts-core:1.19.0 链接: github 代码 package pers.stu.algorithm;import org.locationtech.jts.algorithm.MinimumDiameter; import org.locationtech.jts.geom.Coordinate; import org.locationtech.jts.geom.Geometry; import…...
MacOS Ventura 13 优化配置(ARM架构新手向导)
一、系统配置 1、About My MacBook Pro 2、在当前标签打开新窗口 桌面上创建目录的文件夹,每次新打开一个目录,就会创建一个窗口,这就造成窗口太多,不太好查看和管理,我们可以改成在新标签处打开新目录。需要在&…...
Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
【网络安全产品大调研系列】2. 体验漏洞扫描
前言 2023 年漏洞扫描服务市场规模预计为 3.06(十亿美元)。漏洞扫描服务市场行业预计将从 2024 年的 3.48(十亿美元)增长到 2032 年的 9.54(十亿美元)。预测期内漏洞扫描服务市场 CAGR(增长率&…...
聊聊 Pulsar:Producer 源码解析
一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台,以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中,Producer(生产者) 是连接客户端应用与消息队列的第一步。生产者…...
1.3 VSCode安装与环境配置
进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件,然后打开终端,进入下载文件夹,键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...
CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)
漏洞概览 漏洞名称:Apache Flink REST API 任意文件读取漏洞CVE编号:CVE-2020-17519CVSS评分:7.5影响版本:Apache Flink 1.11.0、1.11.1、1.11.2修复版本:≥ 1.11.3 或 ≥ 1.12.0漏洞类型:路径遍历&#x…...
面向无人机海岸带生态系统监测的语义分割基准数据集
描述:海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而,目前该领域仍面临一个挑战,即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...
使用LangGraph和LangSmith构建多智能体人工智能系统
现在,通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战,比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...
虚拟电厂发展三大趋势:市场化、技术主导、车网互联
市场化:从政策驱动到多元盈利 政策全面赋能 2025年4月,国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》,首次明确虚拟电厂为“独立市场主体”,提出硬性目标:2027年全国调节能力≥2000万千瓦࿰…...
Xela矩阵三轴触觉传感器的工作原理解析与应用场景
Xela矩阵三轴触觉传感器通过先进技术模拟人类触觉感知,帮助设备实现精确的力测量与位移监测。其核心功能基于磁性三维力测量与空间位移测量,能够捕捉多维触觉信息。该传感器的设计不仅提升了触觉感知的精度,还为机器人、医疗设备和制造业的智…...
对象回调初步研究
_OBJECT_TYPE结构分析 在介绍什么是对象回调前,首先要熟悉下结构 以我们上篇线程回调介绍过的导出的PsProcessType 结构为例,用_OBJECT_TYPE这个结构来解析它,0x80处就是今天要介绍的回调链表,但是先不着急,先把目光…...
