【2014年数据结构真题】
41. (13分)二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。
给定一棵二叉树T,采用二叉链表存储,结点结构如下:

其中叶结点的weight域保存该结点的非负权值。 设root为指向T的根结点的指针, 请设计求T
的WPL的算法, 要求:
-
给出算法的基本设计思想。
-
使用C或C++语言, 给出二叉树结点的数据类型定义。
-
根据设计思想, 采用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

题 42 图 Rl 构造的网络拓扑

请回答下列问题。
-
本题中的网络可抽象为数据结构中的哪种逻辑结构?
-
针对题42表中的内容, 设计合理的链式存储结构, 以保存题 42表中的链路状态信息
(LSI)。要求给出链式存储结构的数据类型定义,并画出对应 题42表的链式存储结构示意图(示意图中可仅以ID标识结点)。
3)按照迪杰斯特拉( Dijksta)算法 r 的策略, 依次给出R1到达题42图中子网192.1.x.x的
最短路径及费用。
解;
(1) 题中的网络是简单的网络拓扑图,可以抽象理解为无向图
(2) 链式存储结构如下图所示
第二问考试的时候能跳就跳吧



(3)计算结果如下所示


相关文章:
【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)(四)
你可以的,去飞吧! 同步代码和异步代码 回调函数地狱和 Promise 链式调用 回调函数地狱 缔造“回调地狱”↓ 制造里层回调错误,却在最外层接收错误→无法捕获 axios源码抛出异常(未捕获) <!DOCTYPE html> <ht…...
TechSmith Camtasia 2024破解版功能介绍及使用教程
在现在的网络互联网时代,越来越多的人走上了自媒体的道路。有些自媒体人会自己在网络上录制精彩视频,也有一些人会将精彩、热门的电影剪辑出来再加上自己给它的配音,做成大家喜欢看的电影剪辑片段。相信不管大家是自己平时有独特的爱好也好、…...
【无线网络技术】——无线传输技术基础(学习笔记)
目录 🕒 1. 无线传输媒体🕘 1.1 地面微波🕘 1.2 卫星微波🕘 1.3 广播无线电波🕘 1.4 红外线🕘 1.5 光波 🕒 2. 天线🕘 2.1 辐射模式🕘 2.2 天线类型🕤 2.2.1 …...
【Liunx】部署WEB服务:Apache
【Liunx】部署WEB服务:Apache 概述Apache1.介绍2.Apache文件路径3.Apache详解(1)安装Apache(2)启动Apache(3)配置文件a.Apache主配置文件:vim /etc/httpd/conf/httpd.conf信息:b.基于主机头的虚拟主机 (4)开始演示:a.新建两个网站根目录b.分别…...
数字媒体技术基础之:常见图片文件格式
在数字图像处理和图形设计领域,了解不同的图片文件格式及其特点是至关重要的。每种格式都有其独特的用途和优势。以下介绍一些最常见的图片文件格式。 JPEG Joint Photographic Experts Group 扩展名:.jpg 或 .jpeg 特点: 1、有损压缩&#x…...
2023-2024-2 高级语言程序设计-二维数组
7-1 矩阵运算 给定一个nn的方阵,本题要求计算该矩阵除副对角线、最后一列和最后一行以外的所有元素之和。副对角线为从矩阵的右上角至左下角的连线。 输入格式: 输入第一行给出正整数n(1<n≤10);随后n行,每行给出…...
【uniapp】确认弹出框,选择确定和取消
代码如下: <view style"display: flex; justify-content: space-around;"><button class"button" click"submit">t提交</button> </view>submit(){let thatthisuni.showModal({title: 提示:,con…...
阿里云容器镜像服务的运维总结
一、背景 容器镜像服务,作为一个可选付费产品,主要作用是存储docker的镜像仓库,供k8s拉取到Pod节点里。 你可以自己搭建一个harbor镜像仓库,在公司的开发环境下,将image推送到仓库;然后在生产k8s从仓库拉取…...
修炼k8s+flink+hdfs+dlink(七:flinkcdc)
一 :flinkcdc官网链接。 https://ververica.github.io/flink-cdc-connectors/release-2.1/content/about.html 二:在flink中添加jar包。 在flink lib目录下增加你所需要的包。 https://kdocs.cn/join/gv467qi?f101 邀请你加入共享群「工作使用重要工具…...
华为云AI开发平台ModelArts
华为云ModelArts:重塑AI开发流程的“智能引擎”与“创新加速器”! 在人工智能浪潮席卷全球的2025年,企业拥抱AI的意愿空前高涨,但技术门槛高、流程复杂、资源投入巨大的现实,却让许多创新构想止步于实验室。数据科学家…...
云计算——弹性云计算器(ECS)
弹性云服务器:ECS 概述 云计算重构了ICT系统,云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台,包含如下主要概念。 ECS(Elastic Cloud Server):即弹性云服务器,是云计算…...
学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...
音视频——I2S 协议详解
I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议,专门用于在数字音频设备之间传输数字音频数据。它由飞利浦(Philips)公司开发,以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...
Qemu arm操作系统开发环境
使用qemu虚拟arm硬件比较合适。 步骤如下: 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载,下载地址:https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...
关于uniapp展示PDF的解决方案
在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项: 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库: npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...
脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)
一、OpenBCI_GUI 项目概述 (一)项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台,其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言,首次接触 OpenBCI 设备时,往…...
保姆级【快数学会Android端“动画“】+ 实现补间动画和逐帧动画!!!
目录 补间动画 1.创建资源文件夹 2.设置文件夹类型 3.创建.xml文件 4.样式设计 5.动画设置 6.动画的实现 内容拓展 7.在原基础上继续添加.xml文件 8.xml代码编写 (1)rotate_anim (2)scale_anim (3)translate_anim 9.MainActivity.java代码汇总 10.效果展示 逐帧…...
【java面试】微服务篇
【java面试】微服务篇 一、总体框架二、Springcloud(一)Springcloud五大组件(二)服务注册和发现1、Eureka2、Nacos (三)负载均衡1、Ribbon负载均衡流程2、Ribbon负载均衡策略3、自定义负载均衡策略4、总结 …...
PydanticAI快速入门示例
参考链接:https://ai.pydantic.dev/#why-use-pydanticai 示例代码 from pydantic_ai import Agent from pydantic_ai.models.openai import OpenAIModel from pydantic_ai.providers.openai import OpenAIProvider# 配置使用阿里云通义千问模型 model OpenAIMode…...
