当前位置: 首页 > 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 邀请你加入共享群「工作使用重要工具…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...