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

数据结构算法习题通关:树遍历 / 哈夫曼 / 拓扑 / 哈希 / Dijkstra 全解析

  • 已知一棵二叉树先序遍历和中序遍历分别为 ABDEGCFH 和 DBGEACHF,请画出这个二叉树的逻辑结构并写出后序遍历的序列。

先序遍历:ABDEGCFH

中序遍历:DBGEACHF

先序遍历看出根为A,左子树DBGE,右子树CHF

A的左子树

再看先序遍历,可以看出左子树的根为B,右子树根为C

看中序遍历 D为B的左子树,右子树要知道GE的关系看先序,E先输出,所以B的右子树为E,要看G为E的左子树还是右子树要看中序遍历,G先输出说明G为E的左子树

A的右子树

看先序遍历,FH都在C的后面输出,所以都在右子树上,并且F先输出所以H为右子树的根,看H为F的左子树还是右子树,看中序遍历H先输出,所以H为F的左子树。

  • 假定用于通信的某电文仅由8个字母构成,各字母在电文中出现的频率分别为(12,5,3,7,14,21,9,15)。请完成:
  1. 构造哈夫曼树;2)为这8个字母设计不等长的Huffman编码,并计算WPL。

N个节点构造的构造哈夫曼树,最后会有2N-1个节点

先排序 3 5 7 9 12 14 15 21

  • 使用序列 {57,40,38,11,13,34,48,75,6,19,9,7} 构造一个大顶堆,请给出构成完成的初始序列。

堆:完全二叉树

存储结构:数组存储

0   1   2   3   4   5   6   7   8  9  10 11

57,40,38,11,13,34,48,75,6,19,9,7

  1. 找到最后一个分支节点,因为后面都是叶子结点,一定符合堆的规则(根大于左右子树的根),这个节点在下标n/2的位置。
  2. 左孩子 :2n+1 右孩子 :2n+2

直接在数组中进行建堆:

7的下标为11,所以最后一个分支节点下标 5 ,就是34

根节点 左孩子           右孩子 交换情况

5 - 34     11 - 7 不交换

4 - 13 9 - 19          10 - 9 19与 13交换

0       1      2      3     4    5       6      7    8    9    10  11

57,40,38,11,19,34,48,75,6,13,9,7

3 - 11   7 - 75   8 - 6 75与11交换

0       1      2      3     4    5       6      7    8    9    10  11

57,40,38,7519,34,48,11,6,13,9,7

2 - 38 5 - 34   6 - 48         48与38交换

0       1      2      3     4    5       6      7    8    9    10  11

57,40,487519,34,3811,6,13,9,7

1 - 40 3 - 75   4 - 19  75与40交换

0       1      2      3     4    5       6      7    8    9    10  11

57,75484019,34,3811,6,13,9,7

0 - 57 1 - 75   2 - 48  75与57交换

0       1      2      3     4    5       6      7    8    9    10  11

75,57,484019,34,3811,6,13,9,7

  • 设有向图G中有向边的集合E={<1,2>,<2,3>,<1,4>,<4,2>,<4,3>},请给出拓扑排序的序列。

  • 若一棵度为 4 的树中度为 2、3、4 的结点个数分别为 3、2、2,请计算出该树的叶子结点的个数。

度的和:2*3 + 3*2 + 4*2 = 20

树的节点数:度的和 + 1 = 21 (度可以理解为指向他后继的边,所以根节点没有前驱指向他,所以节点数为度+1)

叶子节点度为0 :21 - 3 - 2 - 2 = 14

  • 在结点数是 67 的完全二叉树,按层次,从左到右编号,请计算最后一个非叶子结点的编号。

67 / 2 = 33就是求最后一个分支节点的下标 题3

  • 一个线性序列(36,13,40,63,22,6),假定采用散列函数Hash(key)=key%7来计算散列地址,将其散列存储在A[0~9]中,采用线性探测再散列解决冲突。构造哈希表,并计算等概率情况下的查找成功和不成功的平均查找长度。

  • 在下面的网图中使用Dijkstra算法,从顶点0出发,到各顶点的最短路径,要求写出计算过程。

 

v0到V1的最短路径5 ,路径节点:V0 -> V3 -> V1

v0到V2的最短路径1 ,路径节点:V0 -> V2

v0到V3的最短路径2 ,路径节点:V0 -> V3

v0到V4的最短路径4 ,路径节点:V0 -> V2 -> V4

 

http://www.xdnf.cn/news/380629.html

相关文章:

  • Python中的列表list使用详解
  • 重复的子字符串
  • 【ts】defineProps数组的类型声明
  • 人工智能100问☞第19问:什么是专家系统?
  • 自定义类型-结构体(二)
  • 基于ssm的超市库存商品管理系统(全套)
  • Vue.js框架的优缺点
  • 2025年PMP 学习六 -第5章 项目范围管理 (5.1,5.2,5.3)
  • ubunut20.04 安装运行lvi-sam
  • JavaSE核心知识点02面向对象编程02-05(方法)
  • 【比赛真题解析】混合可乐
  • 翻转数位题目解释和代码
  • C语言复习--动态内存管理
  • 同步、异步、并发的区别
  • Python与YOLO:自动驾驶中的实时物体检测
  • comfyui 如何优雅的从Hugging Face 下载模型,文件夹
  • 2025年特种作业操作证考试题库及答案(登高架设作业)
  • AST(抽象语法树)与 HBO(基于历史的优化)详解
  • 使用 Jackson 在 Java 中解析和生成 JSON
  • Spring事务管理实现机制
  • Windows右键管理工具:轻松添加/删除/修改右键菜单项!
  • xml与注解的区别
  • 机器学习 day01
  • 如何更改typora图片存储位置
  • 将一张100 元的钞票换成1 元、2元、5 元和10 元的零钱,每种零钞至少一张
  • CH579 CH573 CH582 CH592 蓝牙主机(Central)实例应用讲解
  • C. scanf 函数基础
  • Linux--JsonCpp
  • 【C++】内存管理
  • Lettuce 节点刷新、连接优化与 Spring 升级适配全解析:从环境约束到生产验证