当前位置: 首页 > news >正文

910数据结构(2020年真题)

算法设计题

问题1

现有两个单链表A和B,其中的元素递增有序,在不破坏原链表的情况下,请设计一个算法,求这两个链表的交集,并将结果存放在链表C中。
(1)描述算法的基本设计思想;
(2)根据设计思想,给出C语言描述算法,关键之处请给出简要注释。

(1)基本思想:A、B两个链表的元素均递增有序,所以可以按顺序同时从A中和B中各取出一个结点的值来对比;如果A中结点的值比较小,则A中的指针后移;如果B中结点的值比较小,则B中的指针后移;如果相等,则将结点值取出,赋于s结点;并将s结点插入C链表中;然后A、B中的指针分别后移

LinkList getCommon(LinkList A, LinkList B, LinkList &C){C->next = null; //将C置为空链表LNode *r = C;//初始化指针LNode *p = A->next;LNode *q = B->next;while(p!=null && q!=null){if(q->data < p->data){//谁的值小谁右移q = q->next;}else if(p->data < q->data){p = p->next;}else{//值相等都右移LNode *s = (LNode *)malloc(sizeof(LNode));//创建*s结点s->data = p->data;//*s结点赋值r->next = s;//将*s结点写入链表中r = s;//C链表中的指针右移//A、B链表中剩余的元素继续比较p = p->next;q = q->next;}}r->next = null;
}

问题2

若设二叉树T采用二叉链表存储,设计一个算法,求指定结点p的父结点。要求:
(1)描述算法的基本设计思想;
(2)根据设计思想,给出C语言描述算法,关键之处请给出简要注释。
(1)基本思想:利用栈,对二叉树采用后序遍历非递归的方法,当遍历到p结点时,由于是后序遍历方法,栈中所有元素都是p的祖先结点,栈顶就是p的父节点。

void nonPost(BiTree T, BiTree p){InitStack(S);q = T;tag = null;while(q || !isEmpty(S)){if(q){push(S,q);if(q == p){cout << "find father successfully!";return;//找父节点成功}q = q->next;}else{getTop(S,q);if(q->rchild && q->rchild != tag){q = q->rchild;push(S,q);if(q == p){cout << "find father successfully!";return;//找父节点成功}q = q->lchild;}else{pop(S,q);visit(q->data);tag = p;p = null;}}//else}//while
}

选择题错题整理

1.用一个高效的算法删除有序顺序表(n)中的所有元素值为x的元素时,在查找元素x时采用二分查找,此时的时间复杂度为()。
A.O(1) B.O(n) C.O(n^2) D.O(log2n)
正确答案
D.O(log2n)
试题分析

2.求删除循环双向链表(带头结点)中p结点的时间复杂度()。
A.O(1) B.O(n) C.O(n^2) D.O(log2n)
正确答案
B.O(n)
试题分析
在双向链表中删除结点,主要时找到待删除结点,然后修改相应指针域即可,不需要移动元素,在链表中查找某一元素只能从表头开始顺序查找,而不能随机查找,故时间复杂度为O(n)。

简答题

1.循环队列是如何提出的?如何判别它的空和满?试简述之。

2.列出先序遍历能得到ABC序列的所有不同的二叉树。

3.简要说明深度优先搜索法(DFS)和广度优先搜索法(BFS)的不同之处。

4.简述堆和二叉排序树的区别。

分析计算题

有一组关键字序列{66,89,8,123,9,44,55,37,200,127,98}:
(1)请将其调整成初始大根堆,并画出初始大根堆的树型表示。
(2)采用堆排序实现按关键字递增排序,请画出当有1个最大的关键字已放置到最终位置时,剩余关键字构成的大根堆。
在这里插入图片描述
在这里插入图片描述
将最终结果最大位,即200输出,200与66替换,继续调整堆,得到以上答案。

相关文章:

910数据结构(2020年真题)

算法设计题 问题1 现有两个单链表A和B&#xff0c;其中的元素递增有序&#xff0c;在不破坏原链表的情况下&#xff0c;请设计一个算法&#xff0c;求这两个链表的交集&#xff0c;并将结果存放在链表C中。 (1)描述算法的基本设计思想&#xff1b; (2)根据设计思想&#xff0…...

MyBatisPlus(八)范围查询

说明 范围查询&#xff0c;包括&#xff1a; 大于大于等于小于小于等于在范围内在范围外 大于&#xff1a;gt 代码 Testvoid gt() {LambdaQueryWrapper<User> wrapper new LambdaQueryWrapper<>();wrapper.gt(User::getAge, 20);List<User> users mapp…...

【day10.04】QT实现TCP服务器客户端搭建的代码

服务器&#xff1a; #include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this);//实例化一个服务器server new QTcpServer(this);//此时&#xff0c;服务器已经成功进入…...

milvus 结合Thowee 文本转向量 ,新建表,存储,搜索,删除

1.向量数据库科普 【上集】向量数据库技术鉴赏 【下集】向量数据库技术鉴赏 milvus连接 from pymilvus import connections, FieldSchema, CollectionSchema, DataType, Collection, utility connections.connect(host124.****, port19530)2.milvus Thowee 文本转向量 使用 …...

GEO生信数据挖掘(三)芯片探针ID与基因名映射处理

检索到目标数据集后&#xff0c;开始数据挖掘&#xff0c;本文以阿尔兹海默症数据集GSE1297为例 目录 处理一个探针对应多个基因 1.删除该行 2.保留分割符号前面的第一个基因 处理多个探针对应一个基因 详细代码案例一删除法 详细代码案例二 多个基因名时保留第一个基因名…...

力扣 -- 96. 不同的二叉搜索树

解题步骤&#xff1a; 参考代码&#xff1a; class Solution { public:int numTrees(int n) {vector<int> dp(n1);//初始化dp[0]1;//填表for(int i1;i<n;i){for(int j1;j<i;j){//状态转移方程dp[i](dp[j-1]*dp[i-j]);}}//返回值return dp[n];} }; 你学会了吗&…...

经典算法-枚举法(百钱买百鸡问题)

题目&#xff1a; 条件&#xff1a;现有 100 元&#xff0c;一共要买公鸡、母鸡、小鸡三种鸡&#xff0c;已知公鸡 5 元一只&#xff0c;母鸡 3 元一只&#xff0c;1 元可以买三只小鸡。 要求&#xff1a;公鸡、母鸡、小鸡都要有&#xff0c;一共买 100 只鸡。有哪几种买法&am…...

Gurobi设置初始可行解

目录 1. 决策变量的Start属性直接设置变量的初始值 1.1 Start&#xff1a;MIP变量的起始值&#xff08;初值&#xff09;double类型&#xff0c;可更改 1.2 StartNodeLimit&#xff1a;限制了在完善一组输入部分变量的初始解时&#xff0c;MIP所探索的分支定界的节点的数量 …...

Zabbix配置监控文件系统可用空间小于30GB自动告警

一、创建监控项 二、配置监控项 #输入名称–>键值点击选择 #找到磁盘容量点击 注&#xff1a; 1、vfs 该键值用于检测磁盘剩余空间&#xff0c;zabbix 内置了非常多的键值可以选着使用 2、单位B不需要修改&#xff0c;后期图表中单位和G拼接起来就是GB 3、更新时间 10S…...

进程调度算法之先来先服务(FCFS),短作业优先(SJF)以及高响应比优先(HRRN)

1.先来先服务&#xff08;FCFS&#xff09; first come first service 1.算法思想 主要从“公平”的角度考虑(类似于我们生活中排队买东西的例子) 2.算法规则 按照作业/进程到达的先后顺序进行服务。 3.用于作业/进程调度 用于作业调度时&#xff0c;考虑的是哪个作业先…...

MyBatisPlus(九)模糊查询

说明 模糊查询&#xff0c;对应SQL语句中的 like 语句&#xff0c;模糊匹配“要查询的内容”。 like /*** 查询用户列表&#xff0c; 查询条件&#xff1a;姓名包含 "J"*/Testvoid like() {String name "J";LambdaQueryWrapper<User> wrapper ne…...

Spring 原理

它是一个全面的、企业应用开发一站式的解决方案&#xff0c;贯穿表现层、业务层、持久层。但是 Spring仍然可以和其他的框架无缝整合。 1 Spring 特点 轻量级控制反转面向切面容器框架集合 2 Spring 核心组件 3 Spring 常用模块 4 Spring 主要包 5 Spring 常用注解 bean…...

基于微信小程序的明星应援小程序设计与实现(源码+lw+部署文档+讲解等)

文章目录 前言系统主要功能&#xff1a;具体实现截图论文参考详细视频演示为什么选择我自己的网站自己的小程序&#xff08;小蔡coding&#xff09;有保障的售后福利 代码参考源码获取 前言 &#x1f497;博主介绍&#xff1a;✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计…...

try catch 中的finally什么时候运行

try catch 中的finally什么时候运行 在Java、C#等编程语言中&#xff0c;try-catch-finally语句块用于处理异常。finally块的执行时机通常是在try块中的代码执行完毕之后&#xff0c;无论try块中的代码是否引发了异常。 具体执行顺序如下&#xff1a; 1、try块中的代码首先被…...

力扣 -- 322. 零钱兑换(完全背包问题)

参考代码&#xff1a; 未优化代码&#xff1a; class Solution { public:int coinChange(vector<int>& coins, int amount) {int n coins.size();const int INF 0x3f3f3f3f;//多开一行&#xff0c;多开一列vector<vector<int>> dp(n 1, vector<i…...

[python]pip安装requiements.txt跳过错误包继续安装

在linux上可以用下面操作进行 while read requirement; do sudo pip install $requirement; done < requirement.txt 在windows上写个脚本 import sys from pip._internal import main as pip_maindef install(package):pip_main([--default-timeout1000,install,-U, pac…...

1.5 计算机网络的类别

思维导图&#xff1a; 1.5.1 计算机网络的定义 我的笔记&#xff1a; #### 精确定义&#xff1a; 计算机网络没有统一的精确定义&#xff0c;但一种较为接近的定义是&#xff1a;计算机网络主要由一些通用的、可编程的硬件互连而成&#xff0c;这些硬件并非专门用来实现某一特…...

Go 基本数据类型和 string 类型介绍

Go 基础之基本数据类型 文章目录 Go 基础之基本数据类型一、整型1.1 平台无关整型1.1.1 基本概念1.1.2 分类有符号整型&#xff08;int8~int64&#xff09;无符号整型&#xff08;uint8~uint64&#xff09; 1.2 平台相关整型1.2.1 基本概念1.2.2 注意点1.2.3 获取三个类型在目标…...

Python中print()打印如何不换行?

文章目录 Python中print()打印如何不换行python2.xpython3.x print()函数语法objects基本语法sep基本语法end基本语法 Python中print()打印如何不换行 print() 函数用于打印输出&#xff0c;是python中最常见的一个内置函数。 如何在Python中打印两个或多个变量、语句时而不进…...

python 学习随笔 4

列表list 将序列前几个进行替换&#xff08;数量可以不同&#xff09; 将序列进行间隔替换&#xff08;必须保证数量相同&#xff0c;否则报错&#xff09; 删除序列内元素 向序列后新增一个元素 向序列后新增多个元素 将序列进行数乘&#xff08;不是产生几个序列哦&#xff0…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...

rm视觉学习1-自瞄部分

首先先感谢中南大学的开源&#xff0c;提供了很全面的思路&#xff0c;减少了很多基础性的开发研究 我看的阅读的是中南大学FYT战队开源视觉代码 链接&#xff1a;https://github.com/CSU-FYT-Vision/FYT2024_vision.git 1.框架&#xff1a; 代码框架结构&#xff1a;readme有…...

命令行关闭Windows防火墙

命令行关闭Windows防火墙 引言一、防火墙:被低估的"智能安检员"二、优先尝试!90%问题无需关闭防火墙方案1:程序白名单(解决软件误拦截)方案2:开放特定端口(解决网游/开发端口不通)三、命令行极速关闭方案方法一:PowerShell(推荐Win10/11)​方法二:CMD命令…...