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

软考24-上午题-图1

一、数据结构的回忆

线性结构:(一对一)

        除首结点没有前驱、末尾结点没有后继外,一个结点只有唯一的一个直接前驱和唯一的一个直接后继。

树结构:(一对多)

        除根节点没有前驱节点外,其余的每个节点只有唯一的一个前驱节点和多个后继结点。

图:(多对多

任意两个节点之间都可能有直接的关系,图中一个节点的前驱节点和后继结点的数目没有限定。

二、图的定义

图是由集合V和E构成的二元组,记作G=(V, E) 。

V:图中定点的非空有限集合;(数据元素)

E:图中边的有限集合;(数据元素之间的关系)

示例:

出度(有向图):有某个顶点为起点的边的个数称为该顶点的出度。

入度(无向图):有某个顶点为终点的边的个数称为该顶点的出度。

度(有向图、无向图):入度 + 出度

无向图、有向图:

边数e = 每个顶点的度,相加/2

路径:指图中从一个顶点出发,依次经过若干个顶点到达另一个顶点的一条路线。其中经过的每个顶点在路径中只出现一次;

路径长度:路径上,边、弧的数目;

回路:指从某个顶点出发,经过若干个顶点后回到该顶点的路径。其中经过的每个顶点在路径中只出现一次,除了起点和终点重合的情形。

简单路径:在一个图中从一个顶点到另一个顶点之间没有重复经过任何顶点的路径。简单路径是一条路径,其中顶点没有重复出现。

三、特殊的图

3-1、有向图

图中每条边都是有方向的,顶点之间的关系用<Vi, Vj>表示,它说明从Vi到Vj的一条有向边(也称为弧)。Vi是有向边的起点,称为弧尾;Vj是有向边的终点,称为弧头。

<Vi, Vj>和<Vj, Vi>分别表示两条边。

示例:

3-1-1、强连通图:

有向图中,每一对顶点Vi,Vj,从顶点 Vi到顶点Vj和从顶点 Vj到顶点Vi都存在路径。

强连通图:n个节点,最少有n条边,最多有n(n-1)条边

3-2、无向图 

图中的每条边都是无方向的,顶点Vi和Vj之间的边用(Vi,Vj) 表示。

在无向图中(Vi,Vj) 与(Vj,Vi) 表示的是同条边。

示例:

3-2-1、连通图:

无向图中,任意两个顶点都是连通的(任意两个顶点都有路径);

【注意】:

不一定非的是直接路径!!!

例如:顶点1到顶点5,有路径:(v1, v3)、(V3, V5)

无向连通图:n个节点,最少有n-1条边,最多有n(n-1)/2条边

3-3、完全图

一个图中有n个顶点,每个顶点和其他n-1个顶点之间都有边。(直接的边!!!

完全图的分类:

  • 无向完全图 
  • 有向完全图

含有n个顶点的无向完全图共有n(n-1)/2条边

含有n个顶点的有向完全图共有n(n-1)条边

四、真题

真题1:D

有向图、无向图:边数为e,所有顶点的度数之和为2e 

真题2:

相关文章:

软考24-上午题-图1

一、数据结构的回忆 线性结构&#xff1a;&#xff08;一对一&#xff09; 除首结点没有前驱、末尾结点没有后继外&#xff0c;一个结点只有唯一的一个直接前驱和唯一的一个直接后继。 树结构&#xff1a;&#xff08;一对多&#xff09; 除根节点没有前驱节点外&#xff0c;…...

书生·浦语大模型第四课作业

基础作业&#xff1a; 构建数据集&#xff0c;使用 XTuner 微调 InternLM-Chat-7B 模型, 让模型学习到它是你的智能小助手&#xff0c;效果如下图所示&#xff0c;本作业训练出来的模型的输出需要将不要葱姜蒜大佬替换成自己名字或昵称&#xff01; 1.安装 # 如果你是在 Int…...

勒索攻击风起云涌,Sodinokibi深度分析

前言 Sodinokibi勒索病毒&#xff0c;又称为REvil勒索病毒&#xff0c;这款勒索病毒最早在国内被发现是2019年4月份&#xff0c;笔者在早期分析这款勒索病毒的时候就发现它与其他勒索病毒不同&#xff0c;于是被笔者称为GandCrab勒索病毒的“接班人”&#xff0c;为什么它是Ga…...

1124. 骑马修栅栏(欧拉路径,模板)

农民John每年有很多栅栏要修理。 他总是骑着马穿过每一个栅栏并修复它破损的地方。 John是一个与其他农民一样懒的人。 他讨厌骑马&#xff0c;因此从来不两次经过一个栅栏。 你必须编一个程序&#xff0c;读入栅栏网络的描述&#xff0c;并计算出一条修栅栏的路径&#xf…...

C# CAD2016获取数据操作BlockTableRecord、Polyline、DBObject

一、数据操作说明 //DBObject 基础类 DBObject dbObj (DBObject)tr.GetObject(outerId, OpenMode.ForRead); //Polyline 线段类 Polyline outerPolyline (Polyline)tr.GetObject(outerId, OpenMode.ForRead); //BlockTableRecord 块表类 BlockTableRecord modelSpace (Bloc…...

java SSM新闻管理系统myeclipse开发mysql数据库springMVC模式java编程计算机网页设计

一、源码特点 java SSM新闻管理系统是一套完善的web设计系统&#xff08;系统采用SSM框架进行设计开发&#xff0c;springspringMVCmybatis&#xff09;&#xff0c;对理解JSP java编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S…...

Linux_线程

线程与进程 多级页表 线程控制 线程互斥 线程同步 生产者消费者模型 常见概念 下面选取32位系统举例。 一.线程与进程 上图是曾经我们认为进程所占用的资源的集合。 1.1 线程概念 线程是一个执行分支&#xff0c;执行粒度比进程细&#xff0c;调度成本比进程低线程是cpu…...

【selenium】

selenium是一个Web的自动化测试工具&#xff0c;最初是为网站自动化测试而开发的。Selenium可以直接调用浏览器&#xff0c;它支持所有主流的浏览器。其本质是通过驱动浏览器&#xff0c;完成模拟浏览器操作&#xff0c;比如挑战&#xff0c;输入&#xff0c;点击等。 下载与打…...

HX711压力传感器学习一(STM32)

目录 原理图&#xff1a;​ 引脚介绍&#xff1a; HX711介绍工作原理: 程序讲解&#xff1a; 整套工程&#xff1a; 发送的代码工程&#xff0c;与博客的不一致&#xff0c;如果编译有报错请按照报错和博客进行修改 原理图&#xff1a; 引脚介绍&#xff1a; VCC和GND引…...

作业2.13

1、选择题 1.1、若有定义语句&#xff1a;int a[3][6]; &#xff0c;按在内存中的存放顺序&#xff0c;a 数组的第10个元素是 D A&#xff09;a[0][4] B) a[1][3] C)a[0][3] D)a[1][4] 1.2、有数组 int a[5] {10&#xff0c;20&#xff0c;30&#xff0c;40&#xff0c;50},…...

ArcGIS学习(七)图片数据矢量化

ArcGIS学习(七)图片数据矢量化 通过上面几个任务的学习,大家应该已经掌握了ArcGIS的基础操作,并且学习了坐标系和地理数据库这两个非常重要且稍微难一些的专题。从这一任务开始,让我们进入到实战案例板块。 首先进入第一个案例一一图片数据矢量化。 我们在平时的工作学…...

G口大流量服务器选择的关键点有哪些?

G口服务器指的是接入互联网的带宽达到1Gbps以上的服务器&#xff0c;那么选择使用G口大流量服务器的用户需要注意哪些选择 关键点呢?小编为您整理关于G口大流量服务器的关键点。 G口服务器通常被用于需要大带宽支持的业务场景&#xff0c;比如视频流媒体、金融交易平台、电子商…...

MongoDB聚合:$unset

使用$unset阶段可移除文档中的某些字段。从版本4.2开始支持。 语法 移除单个字段&#xff0c;可以直接指定要移除的字段名&#xff1a; { $unset: "<field>" }移除多个字段&#xff0c;可以指定一个要移除字段名的数组&#xff1a; { $unset: [ "<…...

DS Wannabe之5-AM Project: DS 30day int prep day14

Q1. What is Alexnet? Q2. What is VGGNet? Q3. What is VGG16? Q4. What is ResNet? At the ILSVRC 2015, so-called Residual Neural Network (ResNet) by the Kaiming He et al introduced the anovel architecture with “skip connections” and features heavy b…...

【程序设计竞赛】C++与Java的细节优化

必须强调下&#xff0c;以下的任意一种优化&#xff0c;都应该是在本身采用的算法没有任何问题情况下的“锦上添花”&#xff0c;而不是“雪中送炭”。 如果下面的说法存在误导&#xff0c;请专业大佬评论指正 读写优化 C读写优化——解除流绑定 在ACM里&#xff0c;经常出现…...

Java缓冲流——效率提升深度解析

前言 大家好&#xff0c;我是chowley&#xff0c;在我之前的项目中&#xff0c;用到了缓冲流来提高字符流之间的比较速度&#xff0c;缓冲流的主要作用类似于数据库缓存&#xff0c;提高IO操作效率。 缓冲流 在Java的输入输出操作中&#xff0c;缓冲流是提高性能的重要工具之…...

16 亚稳态原理和解决方案

1. 亚稳态原理 亚稳态是指触发器无法在某个规定的时间段内到达一个可以确认的状态。在同步系统中&#xff0c;输入总是与时钟同步&#xff0c;因此寄存器的setup time和hold time是满足的&#xff0c;一般情况下是不会发生亚稳态情况的。在异步信号采集中&#xff0c;由于异步…...

C# OCR识别图片中的文字

1、从NuGet里面安装Spire.OCR 2、安装之后&#xff0c;找到安装路径下&#xff0c;默认生成的packages文件夹&#xff0c;复制该文件夹路径下的 6 个dll文件到程序的根目录 3、调用读取方法 OcrScanner scanner new OcrScanner(); string path "C:\1.png"; scann…...

使用python-numpy实现一个简单神经网络

目录 前言 导入numpy并初始化数据和激活函数 初始化学习率和模型参数 迭代更新模型参数&#xff08;权重&#xff09; 小彩蛋 前言 这篇文章&#xff0c;小编带大家使用python-numpy实现一个简单的三层神经网络&#xff0c;不使用pytorch等深度学习框架&#xff0c;来理解…...

CSS定位装饰

网页常见布局方式 标准流 块级元素独占一行---垂直布局 行内元素/行内块元素一行显示多个----水平布局 浮动 可以让原本垂直布局的块级元素变成水平布局 定位 可以让元素自由的摆放在网页的任意位置 一般用于盒子之间的层叠情况 使用定位步骤 设置定位方式 属性名&am…...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...

Pinocchio 库详解及其在足式机器人上的应用

Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库&#xff0c;专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性&#xff0c;并提供了一个通用的框架&…...

解析奥地利 XARION激光超声检测系统:无膜光学麦克风 + 无耦合剂的技术协同优势及多元应用

在工业制造领域&#xff0c;无损检测&#xff08;NDT)的精度与效率直接影响产品质量与生产安全。奥地利 XARION开发的激光超声精密检测系统&#xff0c;以非接触式光学麦克风技术为核心&#xff0c;打破传统检测瓶颈&#xff0c;为半导体、航空航天、汽车制造等行业提供了高灵敏…...

什么是VR全景技术

VR全景技术&#xff0c;全称为虚拟现实全景技术&#xff0c;是通过计算机图像模拟生成三维空间中的虚拟世界&#xff0c;使用户能够在该虚拟世界中进行全方位、无死角的观察和交互的技术。VR全景技术模拟人在真实空间中的视觉体验&#xff0c;结合图文、3D、音视频等多媒体元素…...

实战设计模式之模板方法模式

概述 模板方法模式定义了一个操作中的算法骨架&#xff0c;并将某些步骤延迟到子类中实现。模板方法使得子类可以在不改变算法结构的前提下&#xff0c;重新定义算法中的某些步骤。简单来说&#xff0c;就是在一个方法中定义了要执行的步骤顺序或算法框架&#xff0c;但允许子类…...