2024年12月Gesp七级备考知识点拾遗第一期(图的定义及遍历)

目录

总序言

知识点拾遗​编辑

度数

二叉树

图的遍历

深度优先

广度优先

连通与强连通

有什么不同

构成分别至少需要几条边(易错题)?

无向连通图

有向强连通图

完全图

什么是完全图

无向完全图最少边数

有向完全图最少边数

邻接矩阵

邻接表

小测


总序言

一晃眼过了CSP初赛复赛,又到了一季一度的Gesp考试时间了(12.7),作者也开始做真题了,接下来几个星期内,我会整理出一系列的七级备考知识点拾遗。

知识点拾遗

度数

无向图中,一个顶点的度数是指与该顶点相连的边的数量。

有向图中,一个顶点的度数分为入度和出度

        入度:指向该顶点的边的数量。

        出度:从该顶点出发的边的数量。

有向图中,所有顶点的入度和出度的总和就是图的边数的两倍

无向图中,的定义就是起点和终点相同,且至少经过三个顶点的闭合路径。

有向图中,环是指一个顶点经过至少一个其他顶点到自身的路径。

二叉树

二叉树是图的一种特殊形式,其中每个节点最多有两个子节点。

图的遍历

深度优先

从一个顶点开始,尽可能深地搜索图的分支。深度优先搜索沿着图的边深入探索,直到达到一个没有未访问邻居的顶点为止,然后回溯到上一个顶点,继续探索其他分支。

广度优先

从图中的某个节点开始,一层层向外扩展,先访问起始节点的所有邻接节点,然后是这些邻接节点的邻接节点,依此类推。

连通与强连通

有什么不同

在连通图中,如果将边的方向忽略(无向图),任意两个顶点都是可达的。

强连通图要求在考虑边的方向的情况下(有向图),图中任意两个顶点之间都是相互可达的。

构成分别至少需要几条边(易错题)?

无向连通图

至少需要顶点个数 - 1条边

有向强连通图

至少需要顶点个数条边

完全图

什么是完全图

在完全图中,任意两个不同的顶点之间都恰好有一条边相连。

无向完全图最少边数

边数 = (顶点数) * (顶点数 - 1) / 2 根据等差数列推算。

有向完全图最少边数

边数 = (顶点数) * (顶点数 - 1) 每个顶点都要与其它的顶点相连。

邻接矩阵

定义G[x][y] = 1时代表有边相连,为0时无边,同时也可存储权值。

邻接表

每个顶点都拥有一个列表存储邻接点

泛洪算法

泛洪算法(Flood Fill Algorithm)是一种图遍历算法,主要用于填充图中的区域。它从一个起始点开始,沿着图的连接路径,访问并标记所有与起始点相连的区域。

小测

关于图的深度优先搜索和广度优先搜索,下列说法错误的是(D)。

  • A. 二叉树也是⼀种图。
  • B. 二叉树的前序遍历和后序遍历都是深度优先搜索的⼀种。
  • C. 深度优先搜索可以从任意根节点开始。
  • D. 二叉树的后序遍历也是广度优先搜索的⼀种。

以下哪个方案不能合理解决或缓解哈希表冲突(A)。

  • A. 丢弃发生冲突的新元素。
  • B. 在每个哈希表项处,使用不同的哈希函数再建立一个哈希表,管理该表项的冲突元素。
  • C. 在每个哈希表项处,建立二叉排序树,管理该表项的冲突元素。
  • D. 使用不同的哈希函数建立额外的哈希表,用来管理所有发生冲突的元素。

下面关于图的说法正确的是(D)。

  • A. 在无向图中,环是指至少包含三个不同顶点,并且第一个顶点和最后一个顶点是相同的路径。
  • B. 在有向图中,环是指一个顶点经过至少另一个顶点到自身的路径。
  • C. 在有向图中,如果任意两个顶点之间都存在一条边,则这个图一定是强连通图。
  • D. 在有向图中,所有顶点的入度和出度的总和就是图的边数的两倍。

图的存储和遍历算法,下面说法错误的是(B)。

  • A. 图的深度优先搜索和广度优先搜索对有向图和无向图都适用。
  • B. 图的深度优先搜索和二叉树的先序遍历道理是不一样的。
  • C. 图的深度优先搜索需要借助栈来完成。
  • D. 邻接表中,顶点对应的链表中的边结点数目正好是顶点的度。

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

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

相关文章

家庭智慧工程师:如何通过科技提升家居生活质量

在今天的数字化时代,家居生活已经不再只是简单的“住”的地方。随着物联网(IoT)、人工智能(AI)以及自动化技术的快速发展,越来越多的家庭开始拥抱智慧家居技术,将他们的家变得更加智能化、便捷和…

图像处理实验报告

实验一 图像处理的MATLAB基础 实验目的:熟悉数字图象处理的基本软件工具和操作 实验内容:Matlab应用复习,矩阵产生、操作;矩阵运算以及字符运算。 1.利用增量产生向量[0,2,4,6,8,10]。 2.利用magic(n)函数产生7维魔鬼矩阵A&am…

SpringBoot+SpringCloud面试题整理附答案

什么是SpringBoot? 1、用来简化spring初始搭建和开发过程使用特定的方式进行配置(properties或者yml文件) 2、创建独立的spring引用程序main方法运行 3、嵌入Tomcat无需部署war包,直接打成jar包nohup java -jar – & 启动就好 4、简化了maven的配置 …

Linux之管道,system V的共享内存,消息队列和信号量

Linux之管道,systemV共享内存和信号量 一.进程间通信1.1进程间通信的目的1.2进程间通信的方式 二.管道2.1管道的概念2.2匿名管道2.3命名管道 三.system V3.1共享内存3.2消息队列3.3信号量 一.进程间通信 在我们之前有关Linux指令的学习时我们使用过“|”这个命令&a…

Figma入门-基本操作制作登录页

Figma入门-基本操作制作登录页 前言 在之前的工作中,大家的原型图都是使用 Axure 制作的,印象中 Figma 一直是个专业设计软件。 最近,很多产品朋友告诉我,很多原型图都开始用Figma制作了,并且很多组件都是内置的&am…

Django实现智能问答助手-数据库方式读取问题和答案

扩展 增加问答数据库,通过 Django Admin 添加问题和答案。实现更复杂的问答逻辑,比如使用自然语言处理(NLP)库。使用前端框架(如 Bootstrap)增强用户界面 1.注册模型到 Django Admin(admin.py…

SQL注入--文件读写注入--理论

什么是文件读写注入? MySQL中有 读取文件的函数:load_file() 写入文件的函数:Into outfile(能写入多行,按格式输出)和 into dumpfile(只能写入一行且没有输出格式) 利用这些函数在S…

《最小生成树算法详解:Kruskal的优雅实现》

前置知识和本篇介绍 前置知识: 数据结构-优先级队列, 数据结构-并查集。 Kruskal算法不需要建图, 因此不会建图的模板也没事。 本篇介绍一最小生成树的概念和Kruskal算法。 有关prim算法(另一种最小生成树的算法)&am…

云计算-华为HCIA-学习笔记

笔者今年7月底考取了华为云计算方向的HCIE认证,回顾从IA到IE的学习和项目实战,想整合和分享自己的学习历程,欢迎志同道合的朋友们一起讨论! 第二章:服务器基础 服务器是什么? 服务器本质上就是个性能超强的…

uniapp接入高德地图

下面代码兼容安卓APP和H5 高德地图官网:我的应用 | 高德控制台 ,绑定服务选择《Web端(JS API)》 /utils/map.js 需要设置你自己的key和安全密钥 export function myAMap() {return new Promise(function(resolve, reject) {if (typeof window.onLoadM…

C++:探索AVL树旋转的奥秘

文章目录 前言 AVL树为什么要旋转?一、插入一个值的大概过程1. 插入一个值的大致过程2. 平衡因子更新原则3. 旋转处理的目的 二、左单旋1. 左单旋旋转方式总处理图2. 左单旋具体会遇到的情况3. 左单旋代码总结 三、右单旋1. 右单旋旋转方式总处理图2. 右单旋具体会遇…

文小言1:

✨✨ 欢迎大家来访Srlua的博文(づ ̄3 ̄)づ╭❤~✨✨ 🌟🌟 欢迎各位亲爱的读者,感谢你们抽出宝贵的时间来阅读我的文章。 我是Srlua小谢,在这里我会分享我的知识和经验。&am…

uni-app 界面TabBar中间大图标设置的两种方法

一、前言 最近写基于uni-app 写app项目的时候,底部导航栏 中间有一个固定的大图标,并且没有激活状态。这里记录下实现方案。效果如下(党组织这个图标): 方法一:midButton的使用 官方文档:ta…

CentOS7(Linux)详细安装教程(图文详解)

一、软件准备 本文CentOS7安装在VMware Workstation虚拟机软件,故安装前请自行安装该软件。VMware Workstation官网链接:VMware Workstation官网地址CentOS7下载地址:centos7镜像 如下是最常使用的版本(任选版本)centos-7.9.2009-isos-x86_64安装包下载_开源镜像站-阿里…

【实战】基于urllib和BeautifulSoup爬取jsp网站的数据

文章目录 前言目标网站分析目标网页爬取数据解析导出数据其他问题处理分页检索及多关键字搜索去重cookie问题工具封装经验总结前言 网络数据爬取大致分为两类: 静态爬取:该种方式针对那种架构比较老的网站,使用模版方式,通过浏览器F12只能找到静态页面,找不到返回json数…

玩转数字与运算:用C语言实现24点游戏的扑克牌魅力

✅作者简介:2022年博客新星 第八。热爱国学的Java后端开发者,修心和技术同步精进。 🍎个人主页:Java Fans的博客 🍊个人信条:不迁怒,不贰过。小知识,大智慧。 💞当前专栏…

【MySQL】sql注入相关内容

【MySQL】sql注入相关内容 1. 为什么使用sql注入的时候,url传值的时候要使用–而不是– 使用–进行注释的时候需要在后面加一个空格才可以被认为是注释,url传值的过程中会将空格自动忽略,使用则可以在传输中保留为空格符号。(同…

shell脚本(完结)

声明:学习视频来自b站up主 泷羽sec,如涉及侵权马上删除文章 感谢泷羽sec 团队的教学 视频地址:shell编程(完结)_哔哩哔哩_bilibili 本文主要讲解不同shell脚本中的相互调用以及输入输出重定向操作。 一、不同脚本之间…

【bug】使用transformers训练二分类任务时,训练损失异常大

使用transformers训练二分类任务时,训练损失异常大 问题分析 问题 training_loss异常大,在二分类损失中,收敛在1~2附近,而eval_loss却正常(小于0.5) 分析 参考: Bug in gradient accumulation…

深入解析 EasyExcel 组件原理与应用

✨深入解析 EasyExcel 组件原理与应用✨ 官方:EasyExcel官方文档 - 基于Java的Excel处理工具 | Easy Excel 官网 在日常的 Java 开发工作中,处理 Excel 文件的导入导出是极为常见的需求。 今天,咱们就一起来深入了解一款非常实用的操作 Exce…