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

数据结构练习

1.

快速排序的非递归是通过栈来实现的,则前序与层次可以通过控制入栈的顺序来实现,因为递归是会一直开辟栈区空间,所以非递归的实现只需要一个栈的大小,而这个大小是小于递归所要的,

非递归与递归的时间复杂度是一样的,本质没有变化 

 

2.

直接插入排序:是把元素从前先后一个一个插入进去,若是相同值的相对位置也不会改变,所以稳定性好

归并排序: 实现方法是分成多组,但是合并的时候还是要比较大小来合,所以相同值的相对位置也不会改变

选择排序:每次选出一个最值,若是最大值有多个会有稳定性不好的情况,但是可以控制变成稳定性好

冒泡排序:冒泡排序是每趟俩俩排序,相同值的相对位置是不会改变的

 

3.

选择排序:每次会选出一个最大值或者最小值,可以确定位置

快速排序:每次的基准值位置可以确定

堆排序:每次堆顶的元素是可以确定的

归并排序:是分组进行排序的,不能确定一个准确的位置 

 

4.

题目给的序列接近有序的,插入排序在这里的时间复杂度接近为O(n),而快排在这种情况接近O(n^2),归并排序和堆排序都是O(nlogn) 

 

5.

快速排序:初始顺序影响大,如果为有序,则性能最差

插入排序:如果初始为有序,则性能最好

希尔排序:希尔是插入排序的优化,而在有序的情况下插入反而更快

堆排序与归并排序对初始数据的顺序不怎么影响 

 

6.

从题目来看25,21,47,68这些数字位置被确定了,而选择排序确定的最值,所以是希尔排序,

第一次的基准值为25,左边都比25小,右边都比25大,第二次的基准值为20,47(因为第一行的左边与右边的数字是21与47),则第三次的基准值就为15,21,35,68  

7.

这里的辅助空间就是空间复杂度为多少,快速排序递归过程中会开辟栈的空间,递归的深度为二叉树的深度为logn,而非递归实现是通过栈来实现 ,最大空间也就是把从头到叶结点,因为每次是成对放入栈里面,所以最大为数的高度俩倍,2*logn

所以空间复杂度就为logn 

8.

快速排序会确定基准值的位置 ,所以找满足基准值,因为第二趟所以需要找到俩个基准值,若没有俩个则就不可能为快速排序的第二趟,

a:第一趟可以为2,第二趟可以为3,满足情况

b:第一趟可以为2,第二趟可以为9

c:第一趟基准值只能是9(基准值的位置跟排序好的位置是一样的),则第二趟没有基准值了

d:第一趟可以为9,第二趟可以为5

 

9.

归并排序需要用到格外辅助空间,要开辟一个跟原数据一样大的空间

归并排序是一种二分排序算法,每次给n个元素排序(理想),排序的过程中深度为logn,所以时间复杂度为nlongn

因为操作是在左右子树排完序之后,进行合并,合并是在遍历完左右子树的情况下,所以就是左右根,所以是后序、

归并排序相同值的相对位置不会改变,稳定性好 

10.

因为要通过堆排序来进行降序,所以要建小堆,而满足情况只用a为小堆 

 

 

 

 

相关文章:

数据结构练习

1. 快速排序的非递归是通过栈来实现的,则前序与层次可以通过控制入栈的顺序来实现,因为递归是会一直开辟栈区空间,所以非递归的实现只需要一个栈的大小,而这个大小是小于递归所要的, 非递归与递归的时间复杂度是一样的…...

手动安装Ruby 1.9.3并升级RubyGems

手动安装Ruby 1.9.3并升级RubyGems ###Ruby 1.9.3 p125安装 wget http://ftp.ruby-lang.org/pub/ruby/1.9/ruby-1.9.3-p125.tar.gz \ && tar -xzvf ruby-1.9.3-p125.tar.gz \ && cd ruby-1.9.3-p125 \ && ./configure --with-openssl-dir/usr/lib/op…...

go语言day11 错误 defer(),panic(),recover()

错误: 创建错误 1)fmt包下提供的方法 fmt.Errorf(" 格式化字符串信息 " , 空接口类型对象 ) 2)errors包下提供的方法 errors.New(" 字符串信息 ") 创建自定义错误 需要实现error接口,而error接口…...

构建docker镜像实战

构建docker镜像 构建基础容器镜像(Base Image)是创建容器化应用程序的第一步。基础镜像提供了一个最低限度的操作系统环境,您可以在其上安装所需的软件包和应用程序。 Dockerfile语法说明 Dockerfile 是 Docker 构建镜像的描述文件&#x…...

生信算法9 - 正则表达式匹配氨基酸序列、核型和字符串

建议在Jupyter实践。 1. 使用正则表达式匹配指定的氨基酸序列 import re# 氨基酸序列 seq VSVLTMFRYAGWLDRLYMLVGTQLAAIIHGVALPLMMLI# 正则表达式匹配 match re.search(r[A|G]W, seq)# 打印match及匹配到开始位置和结束位置 print(match) # <re.Match object; span(10, …...

linux ext2文件系统浅析

文章目录 前言ext2内容概述实验准备二进制对比分析1 super block2 group desc3 block bitmap4 inode bitmap5 inode_tableinode 1inode 2inode 11inode 12 6 dir entry7 data区8 间接块9 块组 前言 网上关于ext2文件系统的博客有很多&#xff0c;但看完之后还是有些云里雾里&a…...

「树莓派入门」树莓派进阶02-传感器应用与交通灯项目

传感器是树莓派实现智能化的关键。通过本教程,你可以开始尝试使用传感器来增强树莓派的功能。 一、传感器在树莓派中的作用 传感器是树莓派与外界环境交互的重要工具。它们可以检测各种物理量,如光、声音、温度等,并将这些物理量转换为电信号,供树莓派读取和处理。 二、数…...

pytorch 指定GPU设备

使用os.environ["CUDA_VISIBLE_DEVICES"] 这种方法是通过环境变量限制可见的CUDA设备&#xff0c;从而在多个GPU的机器上只让PyTorch看到并使用指定的GPU。这种方式的好处是所有后续的CUDA调用都会使用这个GPU&#xff0c;并且代码中不需要显式地指定设备索引。 im…...

华为od-C卷200分题目6 - 5G 网络建设

华为od-C卷200分题目6 - 5G 网络建设 题目描述 现需要在某城市进行 5G 网络建设&#xff0c;已经选取 N 个地点设置 5G 基站&#xff0c;编号固定为 1 到 N&#xff0c;接下来需要各个基站之间使用光纤进行连接以确保基站能互联互通&#xff0c;不同基站之间架设光纤的成本各不…...

步进电机(STM32+28BYJ-48)

一、简介 步进电动机&#xff08;stepping motor&#xff09;把电脉冲信号变换成角位移以控制转子转动的执行机构。在自动控制装置中作为执行器。每输入一个脉冲信号&#xff0c;步进电动机前进一步&#xff0c;故又称脉冲电动机。步进电动机多用于数字式计算机的外部设备&…...

Node.js介绍 , 安装与使用

1.Node.js 1 什么是Node.js 官网&#xff1a;https://nodejs.org/zh-cn/ 中文学习网&#xff1a;http://nodejs.cn/learn1.Node.js 是一个基于 Chrome V8 引擎的 JavaScript 运行环境。Node.js 使用了一个事件驱动、非阻塞式 I/O 的模型,使其轻量又高效。 2.前端的底层 html…...

JavaEE初阶-网络原理1

文章目录 前言一、UDP报头二、UDP校验和2.1 CRC2.2 md5 前言 学习一个网络协议&#xff0c;最主要就是学习的报文格式&#xff0c;对于UDP来说&#xff0c;应用层数据到达UDP之后&#xff0c;会给应用层数据报前面加上UDP报头。 UDP数据报UDP包头载荷 一、UDP报头 如上图UDP的…...

leetcode秋招冲刺 (专题16--18)

专题16&#xff1a;分治 题目169&#xff1a;多数元素&#xff08;YES&#xff09; 解题思路&#xff1a;使用哈希表可以统计出现次数的性质&#xff0c;直接统计就行。 给定一个大小为 n 的数组 nums &#xff0c;返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊…...

学懂C#编程:实用方法——string字符串指定连接符拼接之 string.Join 的详细用法

在C#中&#xff0c;string.Join 方法用于将一个字符串数组或集合中的元素连接成一个单一的字符串&#xff0c;并在每个元素之间插入指定的分隔符。这个方法非常有用&#xff0c;特别是在需要将多个字符串合并成一个字符串时。以下是 string.Join 方法的详细用法&#xff1a; 方…...

Javascript常见数据结构和设计模式

在JavaScript中&#xff0c;常见的数据结构包括两大类&#xff1a;原始数据类型&#xff08;Primitive Types&#xff09;和对象类型&#xff08;Object Types&#xff09;。对象类型又可以进一步细分为多种内置对象、数组、函数等。下面是一些JavaScript中常见的数据结构&…...

【ChatGPT】全面解析 ChatGPT:从起源到未来

ChatGPT 是由 OpenAI 开发的一个基于 GPT&#xff08;Generative Pre-training Transformer&#xff09;架构的聊天机器人。通过自然语言处理&#xff08;NLP&#xff09;技术&#xff0c;ChatGPT 能够理解和生成语言&#xff0c;与人类进行对话。本文将深入探讨其起源、发展、…...

html+css+js贪吃蛇游戏

贪吃蛇游戏&#x1f579;四个按钮控制方向&#x1f3ae; 源代码在图片后面 点赞❤️关注&#x1f64f;收藏⭐️ 互粉必回&#x1f64f;&#x1f64f;&#x1f60d;&#x1f60d;&#x1f60d; 源代码&#x1f4df; <!DOCTYPE html> <html lang"en"&…...

新手必学:掌握Excel中这些常用公式,轻松提升数据处理能力

各位同学好&#xff0c;今天和大家来分享几个常用函数公式的典型用法。 1、提取指定条件的不重复名单 如下图所示&#xff0c;某公司课程比赛&#xff0c;同一员工有多个比赛项目。希望从左侧的列表中&#xff0c;提取出财务部的参赛人员名单。F2单元格输入以下公式&#xff0…...

经济寒冬:竞品凶猛,你的产品如何求生?

那些年曾被竞品干掉的产品 1997年到2010年左右是国内互联网行业的快速发展和多元化发展的时期&#xff0c;这一时期涌现出来一大批优秀的产品&#xff0c;市场竞争越来越激烈。苹果 在20 世纪 80 年代&#xff0c;乔布斯的苹果电脑&#xff0c;在当时可是PC行业的老大&#xf…...

信号量——Linux并发之魂

欢迎来到 破晓的历程的 博客 引言 今天&#xff0c;我们继续学习Linux线程本分&#xff0c;在Linux条件变量中&#xff0c;我们对条件变量的做了详细的说明&#xff0c;今天我们要利用条件变量来引出我们的另一个话题——信号量内容的学习。 1.复习条件变量 在上一期博客中&…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

Mysql8 忘记密码重置,以及问题解决

1.使用免密登录 找到配置MySQL文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

tauri项目,如何在rust端读取电脑环境变量

如果想在前端通过调用来获取环境变量的值&#xff0c;可以通过标准的依赖&#xff1a; std::env::var(name).ok() 想在前端通过调用来获取&#xff0c;可以写一个command函数&#xff1a; #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...

Linux中《基础IO》详细介绍

目录 理解"文件"狭义理解广义理解文件操作的归类认知系统角度文件类别 回顾C文件接口打开文件写文件读文件稍作修改&#xff0c;实现简单cat命令 输出信息到显示器&#xff0c;你有哪些方法stdin & stdout & stderr打开文件的方式 系统⽂件I/O⼀种传递标志位…...

Oracle实用参考(13)——Oracle for Linux物理DG环境搭建(2)

13.2. Oracle for Linux物理DG环境搭建 Oracle 数据库的DataGuard技术方案,业界也称为DG,其在数据库高可用、容灾及负载分离等方面,都有着非常广泛的应用,对此,前面相关章节已做过较为详尽的讲解,此处不再赘述。 需要说明的是, DG方案又分为物理DG和逻辑DG,两者的搭建…...