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

【2014年数据结构真题】

41. (13分)二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。

给定一棵二叉树T,采用二叉链表存储,结点结构如下:

image.png

其中叶结点的weight域保存该结点的非负权值。 设root为指向T的根结点的指针, 请设计求T

的WPL的算法, 要求:

  1. 给出算法的基本设计思想。

  2. 使用C或C++语言, 给出二叉树结点的数据类型定义。

  3. 根据设计思想, 采用C或C++语言描述算法, 关键之处给出注释。

最优解

此题比较简单,直接用最优解

typedef struct BTNode{int weight;struct BTNode *left,*right;
}BTNode;int fun(BTNode *root,int deep){int A,B;if(root==NULL)return 0;if(root->left==NULL&&root->right==NULL)return (root->weight)*deep;A=fun(root->left,deep+1);B=fun(root->right,deep+1);return A+B;
}void main(BTNode *root){fun(root,0);
}

42. (10分)某网络中的路由器运行OSPF路由协议, 题42表是路由器R1维护的主要链路状态信息(LSI),题42图是根据题42表及R1的接口名构造出来的网络拓扑。

题42表 R1 所维护的 LSI

image.png

题 42 图 Rl 构造的网络拓扑

image.png

请回答下列问题。

  1. 本题中的网络可抽象为数据结构中的哪种逻辑结构?

  2. 针对题42表中的内容, 设计合理的链式存储结构, 以保存题 42表中的链路状态信息
    (LSI)。要求给出链式存储结构的数据类型定义,并画出对应 题42表的链式存储结构示意图(示意图中可仅以ID标识结点)。

3)按照迪杰斯特拉( Dijksta)算法 r 的策略, 依次给出R1到达题42图中子网192.1.x.x的

最短路径及费用。

解;

(1) 题中的网络是简单的网络拓扑图,可以抽象理解为无向图

(2) 链式存储结构如下图所示

第二问考试的时候能跳就跳吧

image.png

image.png

image.png

(3)计算结果如下所示

image.png

image.png

相关文章:

【2014年数据结构真题】

41. (13分)二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。 给定一棵二叉树T,采用二叉链表存储,结点结构如下: 其中叶结点的weight域保存该结点的非负权值。 设root为指向T的根结点的指针, 请设计求T 的WPL…...

PostgreSQL基本操作

目录 1.源码安装PostgreSQL 1.1.前置条件(root下操作) 1.1.1.卸载yum安装的postgresql 1.1.2.创建postgres用户 1.1.3.安装部分依赖 1.1.4.源码安装uuid 1.2.安装PostgreSQL 1.2.1.使用postgres用户管理PostgreSQL 1.2.2.下载解压postgres12源码…...

hadoop 大数据环境配置 ssh免密登录 centos配置免密登录 hadoop(四)

1. 找到.ssh文件夹 cd ~ # 在.ssh文件夹下生成 # cd .ssh 2. 生成私钥公钥命令: ssh-keygen -t rsa3. 发送到需要免密机器: # hadoop23 是我做了配置。在host配置得机器ip和名称得映射 ssh-copy-id hadoop23 4. 成功...

Django 的国际化与本地化详解

概要 随着全球化的发展,为 Web 应用提供多语言支持变得日益重要。Django 作为一个功能强大的 Web 框架,提供了一套完整的国际化(i18n)和本地化(l10n)工具,使得开发多语言应用变得简单。本文将详…...

Java19新增特性

前言 前面的文章,我们对Java9、Java10、Java11、Java12 、Java13、Java14、Java15、Java16、Java17、Java18 的特性进行了介绍,对应的文章如下 Java9新增特性 Java10新增特性 Java11新增特性 Java12新增特性 Java13新增特性 Java14新增特性 Java15新增特…...

[文件读取]metinfo_6.0.0 任意文件读取漏洞复现

1.1漏洞描述 漏洞编号--漏洞类型文件读取漏洞等级⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐漏洞环境windows漏洞名称MetInfo 6.0.0 任意文件读取漏洞 MetInfo 是一套使用PHP 和MySQL 开发的内容管理系统。MetInfo 6.0.0 版本中的 /app/system/include/module/old_thumb.class.php 文件存在任意文件…...

[量化投资-学习笔记015]Python+TDengine从零开始搭建量化分析平台-量化知识点汇总

之前的章节介绍了多个技术分析指标,以下进行一个简单的总结。 看过之前章节的同学就可以不用打开了。 技术指标 MAEMAMACDCCIATRKDJ MA 最基础的技术指标,对一段周期内的收盘价进行简单平均,是一切指标的基础。 def calc_ma(period,ma):ma_…...

VSCode 好用的插件分享

文章目录 Introlistcode runner 【在文本编辑器中编辑好各类语言的源代码,然后一键运行】gitlens - 【git提交信息即时查看,类似IDEA中的 show annotation】还有更多,会日常补充。 Intro 大四毕业前,我只有一台dell latitude 455…...

C++虚基类详解

多继承(Multiple Inheritance) 是指从多个直接基类中产生派生类的能力,多继承的派生类继承了所有父类的成员。尽管概念上非常简单,但是多个基类的相互交织可能会带来错综复杂的设计问题,命名冲突就是不可回避的一个。…...

Mac M2/M3 芯片环境配置以及常用软件安装-前端

最近换了台新 Mac,所有的配置和软件就重新安装下,顺便写个文章。 一、环境配置 1. 安装 Homebrew 安装 Homebrew【Mac 安装 Homebrew】 通过国内镜像安装会比较快 /bin/zsh -c "$(curl -fsSL https://gitee.com/cunkai/HomebrewCN/raw/master/Ho…...

Karmada更高效地实现故障转移

随着云原生技术的发展,其应用场景不断扩大。越来越多的企业开始将应用程序部署在 Kubernetes 集群中,随着 Kubernetes 集群规模的不断扩大,也带来了许多管理挑战,例如多集群间负载均衡、资源调度、故障转移等问题。为了解决这些问…...

前端AJAX入门到实战,学习前端框架前必会的(ajax+node.js+webpack+git)(四)

你可以的&#xff0c;去飞吧&#xff01; 同步代码和异步代码 回调函数地狱和 Promise 链式调用 回调函数地狱 缔造“回调地狱”↓ 制造里层回调错误&#xff0c;却在最外层接收错误→无法捕获 axios源码抛出异常&#xff08;未捕获&#xff09; <!DOCTYPE html> <ht…...

​TechSmith Camtasia 2024破解版功能介绍及使用教程

在现在的网络互联网时代&#xff0c;越来越多的人走上了自媒体的道路。有些自媒体人会自己在网络上录制精彩视频&#xff0c;也有一些人会将精彩、热门的电影剪辑出来再加上自己给它的配音&#xff0c;做成大家喜欢看的电影剪辑片段。相信不管大家是自己平时有独特的爱好也好、…...

【无线网络技术】——无线传输技术基础(学习笔记)

目录 &#x1f552; 1. 无线传输媒体&#x1f558; 1.1 地面微波&#x1f558; 1.2 卫星微波&#x1f558; 1.3 广播无线电波&#x1f558; 1.4 红外线&#x1f558; 1.5 光波 &#x1f552; 2. 天线&#x1f558; 2.1 辐射模式&#x1f558; 2.2 天线类型&#x1f564; 2.2.1 …...

【Liunx】部署WEB服务:Apache

【Liunx】部署WEB服务:Apache 概述Apache1.介绍2.Apache文件路径3.Apache详解(1)安装Apache(2)启动Apache(3)配置文件a.Apache主配置文件&#xff1a;vim /etc/httpd/conf/httpd.conf信息&#xff1a;b.基于主机头的虚拟主机 (4)开始演示&#xff1a;a.新建两个网站根目录b.分别…...

数字媒体技术基础之:常见图片文件格式

在数字图像处理和图形设计领域&#xff0c;了解不同的图片文件格式及其特点是至关重要的。每种格式都有其独特的用途和优势。以下介绍一些最常见的图片文件格式。 JPEG Joint Photographic Experts Group 扩展名&#xff1a;.jpg 或 .jpeg 特点&#xff1a; 1、有损压缩&#x…...

2023-2024-2 高级语言程序设计-二维数组

7-1 矩阵运算 给定一个nn的方阵&#xff0c;本题要求计算该矩阵除副对角线、最后一列和最后一行以外的所有元素之和。副对角线为从矩阵的右上角至左下角的连线。 输入格式: 输入第一行给出正整数n&#xff08;1<n≤10&#xff09;&#xff1b;随后n行&#xff0c;每行给出…...

【uniapp】确认弹出框,选择确定和取消

代码如下&#xff1a; <view style"display: flex; justify-content: space-around;"><button class"button" click"submit">t提交</button> </view>submit(){let thatthisuni.showModal({title: 提示&#xff1a;,con…...

阿里云容器镜像服务的运维总结

一、背景 容器镜像服务&#xff0c;作为一个可选付费产品&#xff0c;主要作用是存储docker的镜像仓库&#xff0c;供k8s拉取到Pod节点里。 你可以自己搭建一个harbor镜像仓库&#xff0c;在公司的开发环境下&#xff0c;将image推送到仓库&#xff1b;然后在生产k8s从仓库拉取…...

修炼k8s+flink+hdfs+dlink(七:flinkcdc)

一 &#xff1a;flinkcdc官网链接。 https://ververica.github.io/flink-cdc-connectors/release-2.1/content/about.html 二&#xff1a;在flink中添加jar包。 在flink lib目录下增加你所需要的包。 https://kdocs.cn/join/gv467qi?f101 邀请你加入共享群「工作使用重要工具…...

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散

前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说&#xff0c;在叠衣服的过程中&#xff0c;我会带着团队对比各种模型、方法、策略&#xff0c;毕竟针对各个场景始终寻找更优的解决方案&#xff0c;是我个人和我司「七月在线」的职责之一 且个人认为&#xff0c…...

数据结构:递归的种类(Types of Recursion)

目录 尾递归&#xff08;Tail Recursion&#xff09; 什么是 Loop&#xff08;循环&#xff09;&#xff1f; 复杂度分析 头递归&#xff08;Head Recursion&#xff09; 树形递归&#xff08;Tree Recursion&#xff09; 线性递归&#xff08;Linear Recursion&#xff09;…...

32位寻址与64位寻址

32位寻址与64位寻址 32位寻址是什么&#xff1f; 32位寻址是指计算机的CPU、内存或总线系统使用32位二进制数来标识和访问内存中的存储单元&#xff08;地址&#xff09;&#xff0c;其核心含义与能力如下&#xff1a; 1. 核心定义 地址位宽&#xff1a;CPU或内存控制器用32位…...

C#最佳实践:为何优先使用as或is而非强制转换

C#最佳实践&#xff1a;为何优先使用as或is而非强制转换 在 C# 的编程世界里&#xff0c;类型转换是我们经常会遇到的操作。就像在现实生活中&#xff0c;我们可能需要把不同形状的物品重新整理归类一样&#xff0c;在代码里&#xff0c;我们也常常需要将一个数据类型转换为另…...