当前位置: 首页 > 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…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

Keil 中设置 STM32 Flash 和 RAM 地址详解

文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

20个超级好用的 CSS 动画库

分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码&#xff0c;而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库&#xff0c;可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画&#xff0c;可以包含在你的网页或应用项目中。 3.An…...