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

北航数据结构与程序设计第五次作业选填题复习

选填题考的很多都是基础概念,对于巩固复习一些仡佬拐角的知识点是很有用的。非北航学生也可以来看看这些题,这一节主要是树方面的习题:


一、
在这里插入图片描述我们首先需要知道一个公式
在这里插入图片描述
这是证明:
在这里插入图片描述
知道了这个公式,我们把题目中的数据带入即可:
n0=n2+2n3+3n4+1
=1+2 * 10+3 * 20+1
=82


二、
在这里插入图片描述
两个知识点:
1、二叉树的分支个数等于节点个数-1,适用于任何二叉树,则m=n-1
2、满二叉树的深度与结点个数之间的关系:n=2^h-1 , h=log(n+1)。
因此选D很明显


三、
在这里插入图片描述这个题蛮有意思,正着想不太好想,那我们就把每个选项都试一试,看看哪个符合要求。
A.空和仅有一个节点,前序遍历和后序遍历长得一样,要说相反好像勉强也行。这个选项暂时保留,大概率肯定不是,我们往下看。

B.我们画个图实际演示一下
在这里插入图片描述前序遍历:A B C D E
后序遍历:E D C B A
诶好像可以诶!!但是别高兴太早了,我们发现D选项囊括了B选项,那我们就要思考一下,这种情况会不会不全面呢?

C.其实有了上一个题的疑问,我们实际可以直接先验证D选项:
在这里插入图片描述

这是一个分支节点的度都为1的树,我们来验证一下他的前后序遍历:
前序遍历:A B C D E
后序遍历:E D C B A
正好相反,因此,正确答案为D


四、
在这里插入图片描述这道题的正确答案应该是A
二叉查找树的查找效率由平均查找长度(ASL)来决定:

在这里插入图片描述在这里插入图片描述
查找第一层的元素,需要比较1次,查找第二层的元素,需要比较2次……查找第n层的元素,需要查找n次,那么上述树的平均查找长度就为:(1 * 1 + 2 * 2 + 3 * 4 + 4 * 2)/9=25/9

在来看时间复杂度:理想情况下,查找一个元素需要比较的最多次数为深度次,也就是从树冠比到树根,那么时间复杂度就是O(h),h=logn (我们这里只说数量级,不考虑具体是满二叉树还是完全二叉树还是普通二叉树),时间复杂度也可以表示为:O(logn)。也就是说,二叉查找树查找的时间复杂度是由深度决定的。

注意,当二叉查找树退化时,也就是说,差不多快变成一个链表的时候(左右子树深度之差过大),那么这个时候查找的时间复杂度就和在链表里查找的时间复杂度差不多了,就变成O(n)了。


六、
在这里插入图片描述
这道题的正确答案应该为D
但是我对此存疑,我再问问助教去……


七、
在这里插入图片描述
中缀转前缀的方法为:

  1. 从右到左扫描表达式

  2. 遇到操作数直接输出,输出顺序从右到左

  3. 遇到操作符:
    1.遇到 ‘ )’,入栈
    2.操作符栈空,入栈
    3.当前操作符优先级 >= 栈顶操作符,入栈(注意,中缀转后缀是要大于才入栈)
    4.当前操作符优先级 < 栈顶操作符,栈顶操作符出栈,然后与新的栈顶元素比较,直到栈空优先级大于等于栈顶操作符遇到‘ )’ 时,入栈。

  4. 遇到括号:
    1.遇到右括号,入栈
    2.遇到左括号,将栈内运算符依次弹出并从右到左输出,直到遇到左括号,左括号弹出,但左括号不输出

  5. 将栈内剩余操作符从右到左依次弹出并输出


八、
在这里插入图片描述
前缀编码,任何一个编码都不能成为其他编码的前缀,但是B中,10是101的前缀。


九、
在这里插入图片描述
先来了解一下哈夫曼树的构造原理:
1.树的带权路径长度WPL:
在这里插入图片描述
wi为第i个叶结点被赋予的权值,li为根节点到第i个叶结点的路径长度

2.哈夫曼树的定义:
给定一组权值,构造出的具有最小带权路径长度的二叉树即哈夫曼树
3.哈夫曼树特点:

  • 权值越大,离根越近,权值越小,离根越小

  • 无度为1的节点

  • 哈夫曼树不唯一

4.哈夫曼树的构造

  • 对于给定的权值W={w1,w2,…… ,wm},构造出树林F={T1,T2,…… ,Tm},其中Ti为左右子树为空,且根节点的权值为wi的二叉树
  • 将F中根节点权值最小的两棵二叉树合并成为一棵新的二叉树,将这两棵二叉树作为新二叉树的左右子树,并将新二叉树的根结点的权值定为这两棵二叉树权值的和。将新二叉树加入F,同时从F中删除之前的两棵二叉树
  • 重复上一步,直到F中只有一棵二叉树。

在这里插入图片描述
按照上述步骤,我们构造出了一棵哈夫曼树,那么带权路径长度就为:
2 * 3 + 3 * 3 + 5 * 2 + 6 * 2 + 9 * 2 = 55


二、
在这里插入图片描述
度为k,那么要求最多个结点,我们就让每个分支节点的度都为K,那么第一层就有k^0个结点,
第二层有k^1个,
第三层:k^2,
第四层:k^3,
以此类推,第i层最多就有k^(i-1)个节点


三、
在这里插入图片描述
满二叉树的深度和结点个数关系:n=2^h-1,则h=log(n+1),可得深度为:log(2048)=11,最后一层的节点个数,也就是叶结点个数为n=2 ^ (h-1)=2 ^ 10 = 1024。


四、
在这里插入图片描述先恢复一下二叉树:
在这里插入图片描述

那么后续序列就为:

HIDJEBFGCA


五、
在这里插入图片描述
每个结点都有left和right两个指针,因此共有2n个指针域
分支节点个数等于节点个数减一,那么就意味着n-1个指针指向孩子节点,剩下的2n-(n-1)=n+1个指针域就指向空


六、
在这里插入图片描述先恢复一下二叉树
在这里插入图片描述
那么后序遍历结果就是:DCBFGEA


七、
在这里插入图片描述处在同一层,说明深度一样,
2^ (h-1) - 1 < i < 2 ^ (h) - 1
2^ (h-1) - 1 < j < 2 ^ (h) - 1


八、
在这里插入图片描述
这个注意,做减法和除法的时候,先弹出的减(除)后弹出的,和后缀表达式计算不太一样。


九、
在这里插入图片描述在这里插入图片描述
建立好的二叉查找树如上图,62先和54比,再和73比,再和62比,发现找到,结束比较,工比较三次。


十、
在这里插入图片描述在这里插入图片描述
则带权路径长度为:4×3+5×3+8×2+6×2+7×2=12+15+16+12+14=69

相关文章:

北航数据结构与程序设计第五次作业选填题复习

选填题考的很多都是基础概念&#xff0c;对于巩固复习一些仡佬拐角的知识点是很有用的。非北航学生也可以来看看这些题&#xff0c;这一节主要是树方面的习题&#xff1a; 一、 我们首先需要知道一个公式 这是证明&#xff1a; 知道了这个公式&#xff0c;我们把题目中的数据…...

【WEB前端2024】3D智体编程:乔布斯3D纪念馆-第40课-实时订阅后端数据

【WEB前端2024】3D智体编程&#xff1a;乔布斯3D纪念馆-第40课-实时订阅后端数据 使用dtns.network德塔世界&#xff08;开源的智体世界引擎&#xff09;&#xff0c;策划和设计《乔布斯超大型的开源3D纪念馆》的系列教程。dtns.network是一款主要由JavaScript编写的智体世界引…...

系统集成知识科普:核心原理与关键技术

目录 1.系统集成的核心原理 1.1 模块化原理 1.1.1 定义&#xff1a; 1.1.2 优势&#xff1a; 1.1.3 实现方式&#xff1a; 1.2 标准化原理 1.2.1 定义&#xff1a; 1.2.2 作用&#xff1a; 1.2.3 实践案例&#xff1a; 1.2.4 制定与遵循&#xff1a; 1.3 协同性原理…...

Coze+Discord:打造你的免费AI助手(教您如何免费使用GPT-4o/Gemini等最新最强的大模型/Discord如何正确连接Coze)

文章目录 📖 介绍 📖🏡 演示环境 🏡📒 文章内容 📒📝 准备Discord📝 准备Coze🔌 连接💡 测试效果⚓️ 相关链接 ⚓️📖 介绍 📖 你是否想免费使用GPT-4o/Gemini等最新最强的大模型,但又不想花费高昂的费用?本文将教你如何通过Coze搭建Bot,并将其转发…...

「OC」UI练习(二)——照片墙

「OC」UI练习——照片墙 文章目录 「OC」UI练习——照片墙UITapGestureRecognizer介绍照片墙实现 UITapGestureRecognizer介绍 UITapGestureRecognizer是UIKit框架中的一个手势识别器类&#xff0c;用于检测用户在视图上的轻击手势。它是UIGestureRecognizer的一个子类&#x…...

一手洞悉巴西slot游戏包投放本土网盟CPI广告优势

一手洞悉巴西slot游戏包投放本土网盟CPI广告优势 在巴西这片热土上&#xff0c;slot游戏包的投放本土网盟CPI广告是一项既充满挑战又富有机遇的任务。CPI&#xff08;Cost Per Install&#xff09;广告模式&#xff0c;即按安装付费&#xff0c;已经成为许多游戏开发商推广产品…...

中国环保网引领元宇宙新纪元 -探索绿色未来

在数字化浪潮的推动下&#xff0c;元宇宙这一概念正逐渐进入公众视野&#xff0c;成为科技与创新交汇的新前沿。作为环境保护的坚定倡导者&#xff0c;中国环保网秉承着推动绿色发展、构建生态文明的使命&#xff0c;正式踏入元宇宙领域&#xff0c;旨在通过高科技手段为环保事…...

2024最新流媒体在线音乐系统网站源码 音乐社区 多语言开心版

本文来自&#xff1a;2024最新流媒体在线音乐系统网站源码 音乐社区 多语言开心版 - 源码1688 应用介绍 简介&#xff1a; 2024最新流媒体在线音乐系统网站源码| 音乐社区 | 多语言 | 开心版 图片&#xff1a;...

【Java】解决Java报错:FileNotFoundException

文章目录 引言1. 错误详解2. 常见的出错场景2.1 文件路径错误2.2 文件名拼写错误2.3 文件权限问题2.4 文件路径未正确拼接 3. 解决方案3.1 检查文件路径3.2 使用相对路径和类路径3.3 检查文件权限3.4 使用文件选择器 4. 预防措施4.1 使用配置文件4.2 使用日志记录4.3 使用单元测…...

Seate分布式锁

XA模式 在第一阶段资源协调者&#xff08;TC&#xff09;会向资源管理者&#xff08;RM&#xff09;发出一个准备的请求&#xff0c;RM开始处理自身的业务&#xff0c;处理完成后不提交事务&#xff0c;而是向TC响应一个执行结果&#xff0c;表明自己成功还是失败&#xff0c;如…...

金融科技助力绿色金融:可持续发展新动力

随着全球气候变化和环境问题的日益严重&#xff0c;绿色金融作为推动环境保护和经济可持续发展的重要手段&#xff0c;已经受到越来越多的关注。而金融科技&#xff0c;作为科技与金融深度融合的产物&#xff0c;正以其独特的优势为绿色金融的发展注入新动力。本文将探讨金融科…...

灾备建设中虚拟机细粒度恢复的含义及技术使用

灾备建设中为了考虑虚拟机恢复的效率与实际的用途&#xff0c;在恢复上出了普通的恢复虚拟机&#xff0c;也有其余的恢复功能&#xff0c;比如瞬时恢复&#xff0c;细粒度恢复等。这里谈的就是细粒度恢复。 首先细粒度恢复是什么&#xff0c;这个恢复可以恢复单个备份下来的文…...

十种排序方法

目录 1.冒泡排序&#xff08;Bubble Sort&#xff09;代码实现 2.选择排序&#xff08;Selection Sort&#xff09;代码实现 3.插入排序&#xff08;Insertion Sort&#xff09; 4.希尔排序&#xff08;Shell Sort&#xff09;代码实现 5.快速排序&#xff08;Quick Sort&…...

docker-compose启动oracle11、并使用navicat进行连接

一、docker-compose.yml version: 3.9 services:oracle:image: registry.cn-hangzhou.aliyuncs.com/helowin/oracle_11grestart: alwaysprivileged: truecontainer_name: oracle11gvolumes:- ./data:/u01/app/oracleports:- 1521:1521network_mode: "host"logging:d…...

使用ffmpeg进行音频处理

音频处理是数字媒体制作中不可或缺的一部分,而ffmpeg作为一款强大的多媒体处理工具,为我们提供了丰富的音频处理功能。 一、查看音频信息 在处理音频之前,了解音频的基本信息是非常重要的。FFmpeg的ffprobe工具可以帮助我们查看音频的详细信息,如采样率、位深等。 示例命…...

重装系统,以及设置 深度 学习环境

因为联想y7000在ubantu系统上连不到wifi,所以打算弄双系统 第一步&#xff1a;下载win10镜像&#xff0c;之后在系统用gparted新建个分区&#xff0c;格式化成ntfs&#xff0c;用来装win10系统 第二步&#xff0c;制作win10启动盘&#xff0c;这个需要先把u盘用disks格式化&a…...

深入理解渲染引擎:打造逼真图像的关键

在数字世界中&#xff0c;图像渲染是创造逼真视觉效果的核心技术。渲染引擎&#xff0c;作为这一过程中的关键组件&#xff0c;负责将二维或三维的模型、纹理、光照等数据转化为人们肉眼可见的二维图像。本文将深入探讨渲染引擎的工作原理及其在打造逼真图像中所起的关键作用。…...

【LeetCode最详尽解答】128_最长连续序列 Longest-Consecutive-Sequence

欢迎收藏Star我的Machine Learning Blog:https://github.com/purepisces/Wenqing-Machine_Learning_Blog。如果收藏star, 有问题可以随时与我交流, 谢谢大家&#xff01; 链接: 128_最长连续序列 直觉 输入: nums [100, 4, 200, 1, 3, 2]输出: 4解释: 最长的连续元素序列是…...

盒马鲜生礼品卡如何使用?

盒马鲜生的礼品卡除了在门店用以外&#xff0c;还有什么用处啊 毕竟家附近的盒马距离都太远了&#xff0c;好多卡最后都闲置下来了&#xff0c;而且以前都不知道盒马卡还会过期&#xff0c;浪费了好多 还好最近发现了 盒马鲜生礼品卡现在也能在收卡云上兑现了&#xff0c;而且…...

有哪些常用ORM框架

ORM&#xff08;Object-Relational Mapping&#xff0c;对象关系映射&#xff09;是一种编程技术&#xff0c;它允许开发者使用面向对象的编程语言来操作关系型数据库。ORM的主要目的是将数据库中的数据表映射到编程语言中的对象&#xff0c;从而使得开发者可以使用对象的方式来…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

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

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

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

Angular微前端架构:Module Federation + ngx-build-plus (Webpack)

以下是一个完整的 Angular 微前端示例&#xff0c;其中使用的是 Module Federation 和 npx-build-plus 实现了主应用&#xff08;Shell&#xff09;与子应用&#xff08;Remote&#xff09;的集成。 &#x1f6e0;️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...