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

【数据结构】练习集

  1. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的存储结构。(F)

  2. 在顺序表中逻辑上相邻的元素,其对应的物理位置也是相邻的。(T)

  3. 若一个栈的输入序列为{1, 2, 3, 4, 5},则不可能得到{3, 4, 1, 2, 5}这样的出栈序列。(T)

  4. 栈和队列的存储方式,既可以是顺序方式,也可以是链式方式。(T)

  • 顺序栈和顺序队列适合需要快速随机访问且大小相对固定的情况
  • 链式栈和链式队列适合需要动态调整大小的情况,且不需要频繁的随机访问
  1. 环形队列中有多少个元素可以根据队首指针和队尾指针的值来计算。(T)

  2. 可以通过少用一个存储空间的方法解决循环队列中队空和队满条件的区分。(T)

  3. 二叉树中至少存在一个度为2的结点。(F)

  4. 哈夫曼树中一定没有度为 1 的结点。(T)

  5. 哈夫曼树一定是完全二叉树。(F)

  6. 对于任何一个图,从它的某个顶点进行一次深度或广度优先搜索可以访问到该图的每个顶点。(F)

  7. 连通图上各边权值均不相同,则该图的最小生成树是唯一的。(T)

  8. 从n个顶点的连通图中选取n-1条权值最小的边即可构成最小生成树。(F)

  • 在 Kruskal’s 算法中,我们需要确保所选择的边不会形成环(即回路)。而在 Prim’s 算法中,由于每次选择的边都是连接已访问顶点和未访问顶点,因此天然不会形成环。
  1. 在线性表的顺序存储结构中,插入和删除元素时,移动元素的个数与该元素的位置有关。(T)

  2. 链式存储的优点是插入、删除元素时不会引起后续元素的移动,缺点是只能顺序访问各元素。(T)

  3. 通过对堆栈S操作:Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出的序列为:123。(F)

  4. 在n个元素连续进栈以后,它们的出栈顺序和进栈顺序一定正好相反。(T)

  5. 若采用“队首指针和队尾指针的值相等”作为环形队列为空的标志,则在设置一个空队时只需将队首指针和队尾指针赋同一个值,不管什么值都可以。(T)

  6. 可以通过少用一个存储空间的方法解决循环队列假溢出现象。(F)

  7. 一棵有124个结点的完全二叉树,其叶结点个数是确定的。(T)

  • 如果完全二叉树的总结点数 n 是奇数,则叶结点数 l 等于 ( n + 1 ) / 2
  • 如果完全二叉树的总结点数 n 是偶数,则叶结点数 l 等于 n / 2
  • l = 124 / 2 = 62,因此,这棵有 124 个结点的完全二叉树的叶结点个数是 62
  1. 哈夫曼树的结点个数不能是偶数。(T)
  • 哈夫曼树的结点个数不能是偶数。 除叶子节点外,其他节点都有左右子节点,再加上根节点,所以是奇数
  1. 哈夫曼树是带权路径长度最短的树,路径上权值较大的结点离根较近。(T)
  • 哈夫曼树是一种特殊的二叉树,其特点是带权路径长度最短,也就是说,它是所有可能的树形结构中带权路径长度(即各节点的权值乘以到根节点的路径长度之和)最小的树。
  1. 图的深度优先遍历非递归算法通常采用队列实现,广度优先遍历非递归算法通常采用堆栈实现。(F)
  • 图的广度优先搜索(BFS)通常使用队列来实现,而深度优先搜索(DFS)通常使用堆栈(或者递归调用栈)来实现
  1. Prim 算法是通过每步添加一条边及其相连的顶点到一棵树,从而逐步生成最小生成树。(T)
  • 对于非连通图来说,生成树只包含每个连通分量中的所有顶点,而不是整个图的所有顶点。
  1. 连通图的生成树包含了图中的所有顶点。(T)
  • 如果连通图G的一个子图是一棵包含G的所有顶点的树,则该子图称为G的生成树(SpanningTree)
  • 生成树是连通图的包含图中的所有顶点的极小连通子图
  • 图的生成树不惟一
  1. 对于顺序存储的长度为N的线性表,删除第一个元素和插入最后一个元素的时间复杂度分别对应为O(1)和O(N)。(F)
  • 删除第一个元素的时间复杂度为 O(N):
  • 删除第一个元素意味着需要将数组中所有元素向前移动一个位置,以填补删除的空缺。具体操作包括将第二个元素移到第一个位置,第三个元素移到第二个位置,以此类推,直到最后一个元素移动到倒数第二个位置。这种操作的时间复杂度是线性的,即 O(N)
  • 删除第一个元素的时间复杂度为 O(N),因为需要移动剩余元素来填补空缺
  • 插入最后一个元素的时间复杂度为 O(1):
  • 在数组末尾插入一个元素通常是比较高效的操作,因为只需要在数组的末尾位置写入新的元素,并更新数组的长度信息。这个过程是常数时间的操作,即 O(1)。
  • 插入最后一个元素的时间复杂度为 O(1),因为直接在数组末尾插入元素而无需移动其他元素
  1. 顺序存储结构的主要缺点是不利于插入或删除操作。(T)

  2. 顺序存储方式只能用于存储线性结构。(F)

  3. 对单链表来说,只有从头结点开始才能访问到表中所有结点。(T)

  4. 下列函数试图求链式存储的线性表的表长,是否正确?(F)

int  Length ( List  *PtrL )
{    List  *p = PtrL;      int  j = 0;while ( p ) { p++; j++;                 }   return  j;
}
  • 指针p的增加操作:在链表中,应该使用指针p指向当前节点的下一个节点,而不是简单地使用 p++。链表的遍历应该通过节点的指针域来进行,例如 p = p->next; 这样的操作
  • 指针p的类型:如果List *p是指向链表节点的指针,那么 p++ 实际上是在指针上进行递增,而不是在节点上。应该使用指向节点的指针,例如 ListNode *p = PtrL->next;,然后使用p=p->next
  1. 线性表的顺序存储表示优于链式存储表示。(F)
  • 顺序存储适合于元素数量不变、频繁进行查找和更新操作的场景,例如数组。
  • 链式存储适合于需要频繁插入和删除操作、元素数量变化较大或者未知的场景,例如链表。
  1. 在具有N个结点的单链表中,访问结点和增加结点的时间复杂度分别对应为O(1)和O(N)。(F)
  • 访问结点的时间复杂度:
  • 如果知道要访问的结点的位置(例如第k个结点),那么访问这个结点的时间复杂度为O(k)。如果要访问头结点(第一个结点),时间复杂度是O(1)。如果要访问尾结点,需要从头结点开始遍历到尾结点,时间复杂度为O(N),其中N是链表中的结点数。
  • 总结: 单链表中访问结点的时间复杂度可以是O(1)(访问头结点)到O(N)(访问尾结点)之间
  • 增加结点的时间复杂度:
  • 如果在已知位置后面插入结点,可以在O(1)的时间内完成,因为只需修改前一个结点的指针即可。如果在链表末尾插入结点,需要先遍历到尾结点,时间复杂度为O(N),然后再进行插入操作。
  • 总结: 单链表中增加结点的时间复杂度可以是O(1)(在已知位置后插入)或者O(N)(在末尾插入)
  1. 线性表采用链式存储表示时,所有结点之间的存储单元地址可以连续也可以不连续。(T)
  • 因为链式存储方式通过使用指针(或引用)来连接各个结点,每个结点存储自身的数据以及指向下一个结点的指针。
  1. 在具有头结点的链式存储结构中,头指针指向链表中的第一个元素结点。(F)
  • 在具有头结点的链式存储结构中,头指针指向链表中的第一个元素结点之前的一个特殊结点,这个特殊结点称为头结点(dummy node)或者哨兵结点(sentinel node)
  1. 在线性表的顺序存储结构中可实现快速的随机存取,而在链式存储结构中则只能进行顺序存取。(T)

  2. 若一个栈的输入序列为1,2,3,…,N,输出序列的第一个元素是i,则第j个输出元素是j−i−1。(F)

  3. 栈底元素是不能删除的元素。

  • 在栈(Stack)数据结构中,栈底元素是指最先进入栈的元素,通常是最底部的元素。在标准的栈实现中,确实是不能直接删除栈底元素的。
  • 从栈的设计和操作角度来看,栈底元素通常是不可直接删除的。如果需要删除栈底元素,一般需要先将栈中的其他元素依次出栈,直到要删除的元素变成栈顶元素,然后再将它出栈。
  1. 栈顶元素和栈底元素有可能是冋一个元素。(T)

  2. 栈是一种对进栈、出栈操作总次数做了限制的线性表。(F)

  3. 对顺序栈进行进栈、出栈操作不涉及元素的前、后移动问题。(T)

  4. 在用数组表示的循环队列中,front值一定小于等于rear值。

  • 循环队列是把顺序队列首尾相连,把存储队列元素的表从逻辑上看成一个环,成为循环队列。在逻辑上是一个循环结构,即frt和rar的位置是任意的。
  • 由于出队与入队操作front = (front+1)% n,rear = (rear + 1)% n;
  • 我们只能保证front与rear是在0到n-1之间的,但是我们无法保证front是一直小于等于rear的。
  1. 队列是一种插入和删除操作分别在表的两端进行的线性表,是一种先进后出的结构。(F)

  2. 不论是入队列操作还是入栈操作,在顺序存储结构上都需要考虑"溢出"情况。(T)

  3. 循环队列也存在着空间溢出问题。(T)

  4. 循环队列执行出队操作时会引起大量元素的移动。(F)

  • 循环队列执行出队操作时通常不会引起大量元素的移动,它通过指针的移动来实现高效的出队操作,是队列数据结构中一种常见且有效的实现方式
  1. n个元素进队的顺序和出队的顺序总是一致的。(T)

  2. 在对不带头结点的链队列作出队操作时,不会改变头指针的值。(F)

  • 在进行不带头结点的链队列的出队操作时,头指针的值会发生变化。这是因为头指针始终指向队首元素,当队首元素被出队后,头指针需要指向新的队列首元素,以确保队列的正确性和连续性。因此,头指针的值在出队操作后会改变,以指向新的队列首元素。
  1. 将一棵完全二叉树存于数组中(根结点的下标为1)。则下标为23和24的两个结点是兄弟。(F)

  2. 一棵有9层结点的完全二叉树(层次从1开始计数),至少有255个结点。(F)

  • 完全二叉树的节点数量可以通过以下公式计算:2^k - 1
  • 节点总数:2^9 − 1 = 512 − 1 = 511
  • 2^k − 1 ≥ 255,得出 h = 8
  • 一个有8层结点的完全二叉树,恰好满足至少有255个结点的条件
  1. 一棵有9层结点的完全二叉树(层次从1开始计数),至少有512个结点。(F)
  • 2^k − 1 ≥ 512,得出 h = 10
  • 一个有10层结点的完全二叉树,恰好满足至少有512个结点的条件
  1. 对N(≥2)个权值均不相同的字符构造哈夫曼树,则树中任一非叶结点的权值一定不小于下一层任一结点的权值。(T)

  2. 需要借助于一个队列来实现DFS算法。(F)

  • 深度优先搜索(DFS)是一种常用的图和树的遍历算法,通常使用递归或栈来实现。虽然队列通常用于广度优先搜索(BFS),但我们可以通过在DFS中使用显式的栈(或模拟栈的数据结构)来实现。
  1. 如果无向图G必须进行3次深度优先搜索才能访问其所有顶点,则G一定有3个连通分量。(T)

  2. 如果无向图G必须进行两次广度优先搜索才能访问其所有顶点,则G一定有2个连通分量。(T)

  3. 图的深度优先遍历非递归算法通常采用栈实现,广度优先遍历非递归算法通常采用队列实现。(T)

  4. 图的深度优先遍历相当于二叉树的先序遍历。(T)

  5. 图的深度优先遍历相当于二叉树的层次遍历。(F)

  6. 采用邻接表存储的图,其广度优先遍历类似于二叉树的先序遍历。(F)

  • 相当于按层遍历
  1. 图的广度优先遍历相当于二叉树的层次遍历。(T)

  2. 图的广度优先遍历相当于二叉树的后序遍历。(F)

  3. 若有向图不存在回路,即使不用访问标志位同一结点也不会被访问两次。(F)

  4. Prim 算法是维护一个森林,每一步把两棵树合并成一棵。(F)

  5. 带权无向图的最小生成树必是唯一的。(F)

  6. 最小生成树是指边数最少的生成树。(F)

  7. 若图G为连通图,则G必有唯一的一棵最小生成树。(F)

  8. 对于带权无向图 G = (V, E),M 是 G 的最小生成树,则 M 中任意两点 V1 到 V2 的路径一定是它们之间的最短路径。(F)

  9. 连通图的最小生成树一定是唯一的。(F)

  10. 如果 e 是有权无向图 G 唯一的一条最短边,那么边 e 一定会在该图的最小生成树上。(T)

  11. 一个带权的无向连通图的最小生成树的权值之和是唯一的。(T)

  12. 关于二叉树,下列说法正确的是(AC)

  • A. 每个结点至多有两个子树
  • B. 二叉树的子树无左右之分
  • C. 树的结点包含一个数据元素和指向其子树的分支
  • D. 二叉树只能进行链式存储
  1. 以下哪些项是栈元素操作的基本特点:(BC)
  • A. 先进先出
  • B. 先进后出
  • C. 后进先出
  • D. 后进后出

相关文章:

【数据结构】练习集

数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的存储结构。(F) 在顺序表中逻辑上相邻的元素,其对应的物理位置也是相邻的。(T) 若一个栈的输入序列为{1, 2, 3, 4, 5},则不可能得到…...

驱动开发(四):Linux内核中断

驱动开发系列文章: 驱动开发(一):驱动代码的基本框架 驱动开发(二):创建字符设备驱动 驱动开发(三):内核层控制硬件层 驱动开发(四&#xf…...

btrace:binder_transaction+eBPF+Golang实现通用的Android APP动态行为追踪工具

一、简介: 在进行Android恶意APP检测时,需要进行自动化的行为分析,一般至少包括行为采集和行为分析两个模块。其中,行为分析有基于规则、基于机器学习、基于深度学习甚至基于大模型的方案,各有各的优缺点,不…...

C# OCCT Winform 界面搭建

目录 1.创建一个WInform项目 2.代码总览 代码解析 3.添加模型到场景 4.鼠标交互 1.创建一个WInform项目 2.代码总览 using Macad.Occt.Helper; using Macad.Occt; using System; using System.Collections.Generic; using System.Linq; using System.Runtime.Remoting.Co…...

System.Dynamic.ExpandoObject的使用说明

官方文档 ExpandoObject 类 (System.Dynamic) | Microsoft Learn https://learn.microsoft.com/zh-cn/dotnet/api/system.dynamic.expandoobject?viewnet-8.0 System.Dynamic.ExpandoObject 类 - .NET | Microsoft Learn https://learn.microsoft.com/zh-cn/dotnet/fundame…...

adb之ps命令用法

目录 前言一、命令参数二、输出结果含义 前言 在adb shell终端,输入 ps,可查看手机当前所有的进程状态,其中ps的英文全称是Process Status。 ps命令对于分析系统异常情况时都是必备的技能,需要通过这个简单命令来查看系统真实的状…...

Ubuntu-24.04-live-server-amd64安装界面中文版

系列文章目录 Ubuntu安装qemu-guest-agent Ubuntu-24.04-live-server-amd64启用ssh Ubuntu乌班图安装VIM文本编辑器工具 文章目录 系列文章目录前言一、准备工作二、开始安装三、测试效果总结 前言 Centos结束,转战Ubuntu。我之所以写这篇文章,是因为我…...

Git的3个主要区域

一般来说,日常使用只要记住下图6个命令,就可以了。但是熟练使用,恐怕要记住60~100个命令。 下面是我整理的常用 Git 命令清单。几个专用名词的译名如下。 Workspace:工作区 Index / Stage:暂存区 Reposito…...

【操作系统】操作系统实验02-生产者消费者程序改进

1. 说明文档中原有程序实现的功能、实现方法。(用语言、程序流程图、为原有程序添加注释等方式均可) 1.//const.h 2.//定义宏变量 3.#ifndef CONST_H 4.#define CONST_H 5. 6.#define TRUE 1 7.#define FALSE 0 8.#define ERROR 0 9.#define OVERFLOW -…...

TCP协议是安全的吗?

不安全 虽然 TCP 提供了一种可靠且高效的数据传输方式,但它不提供任何加密或身份验证机制来保护数据。因此,传输的数据可能会被未经授权的用户拦截和读取,而且其真实性无法验证。 因此,为了确保 TCP 通信的安全,必须…...

c语言回顾-结构体(2)

前言 前面讲了结构体的概念,定义,赋值,访问等知识,本节内容小编将讲解结构体的内存大小的计算以及通过结构体实现位段,话不多说,直接上干货!!! 1.结构体内存对齐 说到计…...

Prometheus常见exporter安装部署

Prometheus常见exporter安装部署 在稳定性环境的监控当中需要收集各种各样的数据,这样的数据收集是通过各种exporter进行的,在这里我们进行最常用稳定性数据的收集exporter安装部署介绍。 node_exporter安装部署 node_exporter主要监控服务器本身的一…...

DGit的使用

将Remix连接到远程Git仓库 1.指定克隆的分支和深度 2.清理,如果您不在工作区上工作,请将其删除或推送至 GitHub 或 IPFS 以确保安全。 为了进行推送和拉取,你需要一个 PAT — 个人访问令牌 当使用 dGIT 插件在 GitHub 上推送、拉取、访问私…...

ElasticSearch学习篇13_《检索技术核心20讲》进阶篇之LSM树

背景 学习极客实践课程《检索技术核心20讲》https://time.geekbang.org/column/article/215243,文档形式记录笔记。 内容 磁盘和内存数据读取特点 工业界中数据量往往很庞大,比如数据无法全部加载进内存,无法支持索引的高效实时更新&…...

简单好用的C++日志库spdlog使用示例

文章目录 前言一、spdlog的日志风格fmt风格printf风格 二、日志格式pattern三、sink,多端写入四、异步写入五、注意事项六、自己封装了的代码usespdlog.h封装代码解释使用示例 前言 C日志库有很多,glog,log4cpp,easylogging, eas…...

python 方法运行计时装饰模式实现

在代码开发过程中,需要记录方法的执行时间,每个方法都硬代码也可以实现,但是不是最好的方式,考虑到设计模式和模版代码,通过装饰模式实现方法运行计时 在Python中,装饰器可以接受参数,这样可以…...

【权威出版/投稿优惠】2024年水利水电与能源环境科学国际会议(WRHEES 2024)

2024 International Conference on Water Resources, Hydropower, Energy and Environmental Science 2024年水利水电与能源环境科学国际会议 【会议信息】 会议简称:WRHEES 2024 大会时间:点击查看 截稿时间:点击查看 大会地点:…...

阿赵UE引擎C++编程学习笔记——场景加载和切换

大家好,我是阿赵。   继续学习UE引擎,这次来学习一下切换和加载场景的各种做法。 一、 蓝图实现 1、 切换关卡 所谓切换关卡,就是从当前关卡进入到一个新的关卡, 旧关卡的数据将会被放弃。进入新的关卡后,将会执行…...

【LLM之RAG】RAFT论文阅读笔记

研究背景 论文针对的主要问题是如何将预训练的大型语言模型(LLMs)适应特定领域的检索增强生成(RAG)。这些模型通常在广泛的文本数据上进行预训练,已经表现出在广义知识推理任务上的优越性能。然而,在特定领…...

【Android】使用Binder(AIDL)实现利用自定义Bean进行的进程间通信(二)

项目前置 这是我之前写的关于Binder的一些知识点和使用基本数据类型在通信的文章,感兴趣的可以看一下: Binder(一)Binder的介绍和AIDL使用Binder的实例 项目目标 在两个APP之间进行数据传递,使用Android推荐的Binder通讯&#…...

HTTP中get与post的区别?在传输数据类型上有什么区别?【面试】

HTTP中的GET和POST是两种最常见的请求方法,它们在数据传输和使用场景上有一些关键的区别: GET请求: 数据传输方式:GET请求将数据附加在URL之后,形成查询字符串(namevalue的形式),数…...

「51媒体-年中大促」天津有哪些媒体资源-媒体宣传服务公司

传媒如春雨,润物细无声,大家好,我是51媒体网胡老师。 天津的媒体资源相当丰富,涵盖了报纸、电视、广播、新闻门户网站、央媒驻天津机构、视频媒体以及全国媒体资源等多个方面。以下是详细的媒体资源分类和具体信息: 一…...

Thinkphp校园新闻发布系统源码 毕业设计项目实例

Thinkphp校园新闻发布系统源码 毕业设计项目实例 校园新闻发布系统模块: 用户模块:注册,登陆,查看个人信息,修改个人信息,站内搜索,新闻浏览等功能, 后台管理员模块:会员…...

前端老古董execCommand——操作 选中文本 样式

文章目录 ⭐前言⭐exe command api用法💖 example示例💖 测试效果 ⭐execommand和getSelection 的联系⭐总结⭐结束 ⭐前言 大家好,我是yma16,本文分享关于 前端老古董execCommand——操作选中文本。 execommand 当一个 HTML 文…...

elementui写一个自定义的rangeInput的组件

组件定义 使用el-row确保元素都在一行上对外暴露的prop是minValue和maxValue,但是不建议直接使用,使用计算属性minValueComputed和maxValueComputed更改计算属性的值的不要直接更改计算属性,也不要直接更改原本的prop,通知外层的父…...

护眼灯哪些牌子好?一文刨析护眼灯怎么选择!

护眼灯哪些牌子好?护眼台灯作为对抗视力挑战的一种方法,逐渐赢得了众多家长的青睐。这些台灯利用尖端光学技术,发出柔和且无刺激的照明,有助于保护眼睛不受伤害。它们不但可以调节亮度和色温,打造一个舒适且自然的阅读…...

抖音短剧看剧系统是怎么做的?怎么样搭建上线运营?

前言: 当前热门短剧已深入大家的日常,针对一些好的短剧更是吸金无数。今天给大家介绍一下短剧这个项目整个运作模式。 一、一部短剧是怎么样呈现到观众眼前的? 首先影视作品公司拍摄剪辑好短剧 ,弄好一切审核后,放到…...

2024.06.06校招 实习 内推 面经

绿*泡*泡VX: neituijunsir 交流*裙 ,内推/实习/校招汇总表格 1、校招 | 追觅科技2025届校园招聘/正式启动! 校招 | 追觅科技2025届校园招聘正式启动! 2、校招&实习&社招 | 博世海外招聘—德国/专场正式启动&#xff0…...

神经网络模型---ResNet

一、ResNet 1.导入包 import tensorflow as tf from tensorflow.keras import layers, models, datasets, optimizersoptimizers是用于更新模型参数以最小化损失函数的算法 2.加载数据集、归一化、转为独热编码的内容一致 3.增加颜色通道 train_images train_images[...,…...

Linux之网络编程

Linux之网络编程 TCP协议 TCP(Transmission ControlProtocol) : 传输控制协议,是一个 面向连接的、可靠的、基于字节流的传输层的协议。TCP 协议建立的是一种点到点的,一对一的可靠连接协议 特点: 数据无丢失数据无失序数据无错误数据无重…...