【数据结构】二叉树经典例题---<你真的掌握二叉树了吗?>(第二弹)

本次选题都为选择题。涉及到二叉树总结点和叶子结点的计算、二叉树的基本性质、根据二叉树的前序/后序和中序遍历画出二叉树、哈夫曼树等等…希望对你有帮助哦~😝

1.若一颗二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数为()
A.9 B.11 C.15 D.不确定

分析:本题为求解二叉树的度为0的结点个数,也就是求叶子结点。 在做此类题时,我们一般设两个未知数,即总结点n,和叶结点   n 0 {\ n_0}  n0。 计算方法即,从两个角度看二叉树,从而列出等式。
二叉树的总结点树等于各不同性质结点之和即 n = n 0 + n 1 + n 2 {n=n_0+n_1+n_2} n=n0+n1+n2,从而, n = n 0 + 5 + 10 {n=n_0+5+10} n=n0+5+10。 二叉树的终结点数等于
结点的度*该性质结点的个数+1,(这个加的1即为这个树的根节点)即 n = 10 ∗ 2 + 5 ∗ 1 + 1 = 26 n=10*2+5*1+1=26 n=102+51+1=26,从而可以解得 n 0 = 11 n_0=11 n0=11.
故此题选B。

2.一颗完全二叉树上有1001个结点,其中叶子结点的个数为()
A.250 B.500 C.502 D.以上均不对

分析:本题涉及到了满二叉树的总结点数和层结点数的基本知识。

对于一颗满二叉树而言,若有k层,那么这颗满二叉树总结点数等于 2 k − 1 {2^k-1} 2k1,
它在第k层的结点总数为 ( 2 k − 1 + 1 ) / 2 = 2 k − 1 (2^k-1+1)/2=2^{k-1} 2k1+1/2=2k1


那么具有k层的完全二叉树呢?它可以看作是k-1层满二叉树+最后一层叶结点。
对于本题,完全二叉树有1001个结点,我们推断:具有10层的满二叉树共有1023个结点,具有9层的满二叉树具有511个结点,所有该完全二叉树共有10层。
前9层共有结点数511,那么最后一层结点数为1001-511=490。但是这不是总的叶结点数。
我们还需要计算第9层的叶结点数。第九层的总结点数:(511+1)/2=256,第九层的叶结点数:256-490/2=11,故总的叶结点数为:490+11=501.
故本题选D。

3.具有10个叶子结点的完全二叉树中有()个度为2的结点。
A.8 B.9 C.10.D11

分析:根据二叉树的性质,对任何一棵二叉树T,如果其终端结点数为 n 0 n_0 n0,度为2的结点数为 n 2 n_2 n2,则 n 0 = n 2 + 1 n_0=n_2+1 n0n2+1
对于这个性质呢,我是根据二叉树的两种结点的计算方法联立,消去 n 1 , n n_1,n n1n,从而得到 n 0 n_0 n0 n 2 n_2 n2的关系式。


故本题选B。

4.设给定权值结点总数有n个,那么哈夫曼树的结点总数为()。
A.不确定 B.2n C.2n+1 D.2n-1

分析:
这个题需要理解哈夫曼树的构造,哈夫曼树即是将森林中的树不断地合二为一,最终形成最优二叉树。我是根据基本的规律得出结论,给定权值结点的总数为2,那么哈夫曼树结点为3;给定权值结点的总数为3,那么哈夫曼树的结点为5…那么给定权值结点的总数为n,则哈夫曼树的结点总数为2n-1。

故本题选D。

5.用一组权值{3,6,8,10,11}构造一颗哈夫曼树,它的带权路径长度为()。
A.92 B.35 C.38 D.85

分析:本题的考察内容为哈夫曼树的构造以及基本的概念。
哈夫曼树构造的算法思想:
已知一组叶子结点的权值为 w 1 , w 2 , w 3 , . . . , w n w_1,w_2,w_3,...,w_n w1,w2,w3,...,wn则构造哈夫曼树的构成如下
①首先把n个叶子结点看作n棵树(仅有一个结点的二叉树),n棵树构成一颗森林。
②在森林中把权值最小和次小的两棵树合并成一棵树,该树结点的权值是两棵树根结点的权值之和,这时森林中就会减少一棵树。
③重复第②步直到森林中只有一颗二叉树为止。

对于本题,设权值{3,6,8,10,11}对应的结点分别是a、b、c、d、e。
首先,这5棵树构成森林:


其次,选权值最小的a树和b合并成一棵树:

再次,选权值最小的也就是新构成的这个权值为9的树和c树构成合并成一颗新树:

然后,我们选择d树和e树合并成一棵树:

最后,我们将两棵树合并成一棵树:

我们现在已经构造好这一棵哈夫曼树,题目让求它的带权路径长度:
明确带权路径:

结点的带权路径长度从根结点到该结点之间的路径长度与该结点的权的乘积。
树的带权路径长度:树中所有叶子结点的带权路径长度之和。记作:
W P L = ∑ k = 1 n w k l k WPL=\sum _{k=1}^n w_kl_k WPL=k=1nwklk
其中, w k w_k wk是权值, l k l_k lk是结点到根的路径长度,Weighted Path Length。

即: 3×3+3×6+2×8+2×10+2×11=85。
故本题选D。

6.下列有关二叉树的说法中,正确的是()
A.二叉树的度为2
B.一颗二叉树的度可以小于2
C.二叉树中至少有一个结点的度为2
D.二叉树中任何一个结点的度都为2

分析:二叉树中的任何结点的度都小于等于2,可以为0,1,2。
故此题选B

7.二叉树的第i层上最多含有结点数为()
A. 2 i 2^i 2i B. 2 i − 1 2^{i-1} 2i1-1 C. 2 i − 1 2^{i-1} 2i1 D. 2 i 2^i 2i-1

分析:二叉树的基本性质,第i层上最多含有 2 i − 1 2^{i-1} 2i1个结点。
故本题选C。

8.一颗具有n个结点的完全二叉树的深度为()
A. [ log ⁡ 2 n ] + 1 [\log_2n]+1 [log2n]+1 B. log ⁡ 2 n + 1 \log_2n+1 log2n+1 C.[ log ⁡ 2 n \log_2n log2n] D. log ⁡ 2 n − 1 \log_2n-1 log2n1

分析:二叉树的基本性质,一颗具有n个结点的完全二叉树的深度为 [ log ⁡ 2 n ] + 1 [\log_2n]+1 [log2n]+1
故本题选A。

9.在一棵深度为k的满二叉树中,结点总数为()
A. 2 k − 1 2^{k-1} 2k1 B. 2 k 2^k 2k C. 2 k − 1 2^k-1 2k1 D.[ log ⁡ 2 k \log2^k log2k]+1

分析:二叉树的基本性质,在一棵深度为k的满二叉树中,结点总数为 2 k − 1 2^k-1 2k1
故此题选C。

10.一颗二叉树的先序遍历序列为ABCDEFG,它的中序遍历序列可能是() A.CABDEFG B.ABCDEFG C.DACEFBG D.ADCEFG

分析:这个题,可以从很多方面进行排除。
首先,我们可以很确定的是这棵树的根节点为A。
我比较喜欢采用中序遍历的特点,将这棵树可能的形状进行想象,从而排除。
中序遍历的特点就是,将一颗树压扁之后,即压制同一水平线,就是中序遍历的结果。


例如这颗二叉树,我将其压扁,之后的排序就是,dgbeafhc。
根据中序遍历的特点,我们逐个排除选项。
对于A选项,CABDEFG,则这颗二叉树部分一定是
C为A的左子树。右边我们可以不先进行判断,如果是这样的话,那么它的前序遍历一定是AC…所以排除A选项。

对于B选项,ABCDEFG,这棵树的部分一定是:

即这棵树只有右子树,没有左子树。那么对应它的先序遍历AB…,首先基本的看不出错误。
对于C选项DACEFBG,它的部分一定是,

那么它对应的前序遍历一定是 DA…,所以排除C选项。
对于D选项,ADCEFG那么它对应的二叉树的部分一定是:

那么它对应的前序遍历一定是 AD…不符,所以排除D选项。
故此题选B。

11.已知某二叉树的后序遍历序列为DABEC,中序遍历序列为DEBAC,它的先序遍历序列是()。
A.ACBED B.DECAB C.DEABC D.CEDBA

分析:此类题目是经典根据中序遍历和先序/后序遍历得出后序/先序遍历的题。此类题需要我们根据已知的信息发出这颗二叉树,从而得出它的先序/后序遍历。
做这类题都是根据先序、中序、后序遍历的特点分析:先序顺序即:根->左子树->右子树,中序遍历为:左子树->根->右子树,后序遍历为:左子树->右子树->根。

对于本题,根据后序遍历,得出根节点C。


根据我们画出来的二叉树,从而得出它的先序遍历是 CEDBA。
故本题选择D。

12.二叉树的先序遍历序列为EFHIGJK,中序遍历为HFIEJKG,该二叉树根的右子树的根是()
A.E B.F C.G D.H

分析:同上题一样,我们先画出此二叉树,从而得出结论。

我们画出此二叉树。从而可以知道该二叉树的右子树的根为G。
故此题选C。

13.某二叉树的先序序列和后序序列正好相反,则该二叉树一定是()的二叉树。
A.空或只有一个结点 B.任一结点无左子树 C.高度等于其结点数 D.任一结点无右子树

分析:先序序列:根->左子树->右子树
反过来:右子树->左子树->根
后序序列:左子树->右子树->根
因此树只有根结点,或者根结点只有左子树或右子树,依此类推,其子树有同样的性质,任意结点只能有一个孩子,才能满足先序序列和后序序列正好相反。树形应该为一个长链。

所以选B。

14.在有n个结点的二叉树中的二叉链表表示中,空指针数()。
A.不定 B.n+1 C.n Dn-1

分析:二叉链表即如下图所示。
在n个结点中,有叶子结点,其两个指针域都是空指针。有有一个孩子的结点,其有一个指针域不为空,有一个指针域为空。有有两个孩子的结点,其两个指针域都不为空。那么空指针数等于叶子结点数×2+有一个孩子的结点数。
设所求空指针数为m,则 m = 2 n 0 + n 1 m=2n_0+n_1 m2n0n1
我仍然根据两个基本的方程进行联立,从而得到:

故本题选B。

15.若某二叉树有20个叶子结点,有20个结点仅仅有一个孩子,则该二叉树的总结点数是()。
A.40 B.55 C.59 D.61

分析:本题是求二叉树的总结点树。此类题目,我们仍然从两个角度去列方程。> 首先,先设总结点树为n,设有两个孩子的结点树为 n 2 n_2 n2:> 则 n = n 0 + n 1 + n 2 = 20 + 20 + n 2 n=n_0+n_1+n_2=20+20+n_2 n=n0+n1+n2=20+20+n2> n= 20 ∗ 1 + n 2 ∗ 2 + 1 20*1+n_2*2+1 201+n22+1> 联立解得n=59。
故本题选C。

16.假设一颗二叉树中,双分支结点数为15,单分支结点数为30个,则叶子结点数为()个。
A.40 B.55 C.59 D.61

分析:由题可以转化,有两个孩子的结点数为15,有一个孩子的结点数为30。
我们同上个题目一样,列方程解出。
设总结点数为n,叶子结点数为 n 0 n_0 n0.
则有 n = n 0 + n 1 + n 2 = n 0 + 30 + 15 n=n_0+n_1+n_2=n_0+30+15 n=n0+n1+n2=n0+30+15
n = 15 ∗ 2 + 30 ∗ 1 + 1 = 61 n=15*2+30*1+1=61 n=152+301+1=61

从而解得, n 0 n_0 n0=16。
故本题选B。

17.按照二叉树的定义,具有三个结点的二叉树有()种。
A.3 B.4 C.5 D.6

分析:二叉树是有序树,因而具有三个节点的二叉树有以下五种:

故本题选C。

18.根据先序序列ABDC和中序序列DBAC确定对应的二叉树,该二叉树()。
A.是完全二叉树 B.不是完全二叉树 C.是满二叉树 D. 不是满二叉树

分析:我们根据先序遍历和中序遍历画出此二叉树即可。


由树的形态可知,该树为完全二叉树。
故本题选A。

19.某二叉树的中序遍历为ABCDEFG,后序遍历为BDCAFGE,则其左子树中结点数目为()
A.3 B.2 C.4 D.5

分析:题目只要求 求左子树中的结点数目即可。所以我们可以直接进行分析,不需要具体画出此二叉树。 根据后序遍历,我们可以得之,这棵树的根节点为E,根据根节点E,从中序遍历结果中即可看出,左子树的所有结点为ABCD,右子树的所有结点为FG。
故本题选择C。

20.将一颗有100个结点的完全二叉树从根这一层开始,每一层上从左到右一次对结点进行编号,根节点的编号为1,则编号为49的结点的左孩子的编号为()
A.98 B.99 C.50 D.48

分析: 2 5 < 49 < 2 6 2^5<49<2^6 25<49<26,故编号为49的结点在第5层上面。
并且可以得之,编号为49的结点为第5层的第49-32+1=18个结点。
第6层的结点从64开始,63+17*2=97,则编号为49的结点的左孩子的编号为98。

故本题选A。

21.树最适合用来表示()
A.有序数据元素
B.无序数据元素
C.元素之间具有分支层次关系的数据
D.元素之间无关联的数据

分析:树型数据结构是一种重要的非线性数据结构,是以分支关系定义的层次结构。故树适合用于用来表示元素之间具有分支层次关系的数据。
故本题选C。

22.下面说法中正确的是()。
A.度为2的树是二叉树。
B.度为2的有序树是二叉树。
C.子树有严格左右之分的树是二叉树。
D.子树有严格之分,且度不超过2的树是二叉树。

分析:二叉树的度可以为1或0.比如:
一个只有根结点的树的度为0,左边这个二叉树的度为1。
故子树有严格之分,且度不超过2的树为二叉树。
本题选D。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/146405.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

arcgis--二维建筑面的三维显示设置

1、打开ArcScene软件&#xff0c;导入数据&#xff0c;如下&#xff1a; 2、 对建筑面进行拉伸。双击建筑物面图层&#xff0c;打开属性表&#xff0c;选择【拉伸】选项卡&#xff0c;参数设置如下&#xff1a; 显示结果如下&#xff1a;

优化了

v2.0.2版本在 github 发布了。 ## 优化的功能 优化(定时任务): 测试计划与定时任务模块进行了合并&#xff0c;极大的简化了操作步聚。 1、前端页面&#xff0c;测试计划plan&#xff0c;加入1个接口&#xff0c;设置每分钟运行1次。 2、开启定时任务服务&#xff0c;后台日志 …

C#中.NET 6.0 Windows窗体应用通过EF访问数据库并对数据库追加、删除记录

目录 一、应用程序设计 二、应用程序源码 三、生成效果 前文作者发布了在.NET 6.0 控制台应用中通过EF访问已有数据库&#xff0c;事实上&#xff0c;在.NET 6.0 Windows窗体应用中通过EF访问已有数据库也是一样的。操作方法基本一样&#xff0c;数据库EF模型和上下文都是自…

Elastic stack8.10.4搭建、启用安全认证,启用https,TLS,SSL 安全配置详解

ELK大家应该很了解了&#xff0c;废话不多说开始部署 kafka在其中作为消息队列解耦和让logstash高可用 kafka和zk 的安装可以参考这篇文章 深入理解Kafka3.6.0的核心概念&#xff0c;搭建与使用-CSDN博客 第一步、官网下载安装包 需要 elasticsearch-8.10.4 logstash-8.…

HBase学习笔记(3)—— HBase整合Phoenix

目录 Phoenix Shell 操作 Phoenix JDBC 操作 Phoenix 二级索引 HBase整合Phoenix Phoenix 简介 Phoenix 是 HBase 的开源 SQL 皮肤。可以使用标准 JDBC API 代替 HBase 客户端 API来创建表&#xff0c;插入数据和查询 HBase 数据 使用Phoenix的优点 在 Client 和 HBase …

leetcode:138. 随机链表的复制

一、题目&#xff1a; 138. 随机链表的复制 - 力扣&#xff08;LeetCode&#xff09; 函数原型&#xff1a; struct Node* copyRandomList(struct Node* head) 二、思路 本题是给出一个单链表&#xff0c;单链表的每个结点还额外有一个随机指针&#xff0c;随机指向其他结点&am…

使用VSCode进行Python模块调试

使用VSCode进行Python模块调试 创建测试文件 创建文件test/a/b.py&#xff0c;且当前工作路径为test/ b.py文件内容&#xff1a; def cal(numa, numb):print(int(numa) int(numb))if __name__ "__main__":import sys# 判断系统参数长度是否为4且判断第2个参数是…

【机器学习基础】机器学习的模型评估(评估方法及性能度量原理及主要公式)

&#x1f680;个人主页&#xff1a;为梦而生~ 关注我一起学习吧&#xff01; &#x1f4a1;专栏&#xff1a;机器学习 欢迎订阅&#xff01;后面的内容会越来越有意思~ &#x1f4a1;往期推荐&#xff1a; 【机器学习基础】机器学习入门&#xff08;1&#xff09; 【机器学习基…

【广州华锐互动】VR居家防火逃生模拟演练增强训练的真实性

VR软件开发公司广州华锐互动在消防培训领域已开发了多款VR产品&#xff0c;今天为大家介绍VR居家防火逃生模拟演练系统&#xff0c;这是一种基于虚拟现实技术的消防教育训练设备&#xff0c;通过模拟真实的火灾场景&#xff0c;让使用者身临其境地体验火灾逃生过程&#xff0c;…

Telnet 测试 UDP 端口?

Telnet 并不支持 UDP 端口的测试&#xff0c;可以使用 nc 命令来进行测试。nc 命令两种都支持&#xff1a; TCP # nc -z -v -u [hostname/IP address] [port number] # nc -z -v 192.168.10.12 22 Connection to 192.118.20.95 22 port [tcp/ssh] succeeded! UDP # nc -z -v…

假如我是Langchain专家,你会问什么来测试我的水平

推荐Langchain YouTube 视频排行榜 1. 假如我是Langchain专家&#xff0c;你会问什么来测试我的水平&#xff1b; 作为Langchain专家&#xff0c;您可能需要回答一系列深入和具体的问题&#xff0c;这些问题旨在测试您对Langchain的理解和实际应用能力。以下是一些可能的问题…

浅谈:Flutter现状、与为什么选择Flutter——其实大家都在用只是你不知道罢了

浅谈&#xff1a;谁将会动那些抵制学习还装懂的人的蛋糕 开发环境现状与为什么选择Flutter 我本从不屑于写这种技术外的技术文章&#xff0c;但是今天刷某应用优点上头&#xff0c;想发唯一一篇。这篇文章可能会得罪一些就喜欢地址学新架构的&#xff0c;以及还不了解就开始起哄…

【go】报错整理与解决

文章目录 依赖下载失败checksum mismatch启动报错missing go.sum 依赖下载失败checksum mismatch > go get github.com/hibiken/asynqmon go: downloading github.com/hibiken/asynqmon v0.7.2 go: github.com/hibiken/asynqmonv0.7.2: verifying module: checksum mismatc…

Q learning算法

Q learning算法 代码仓库:https://github.com/daiyizheng/DL/tree/master/09-rl Q Learning是强化学习算法中的一个经典算法。在一个决策过程中&#xff0c;我们不知道完整的计算模型&#xff0c;所以需要我们去不停的尝试。 算法流程 整体流程如下&#xff1a; Q-table 初…

XUbuntu22.04之安装pkg-config(一百九十二)

简介&#xff1a; CSDN博客专家&#xff0c;专注Android/Linux系统&#xff0c;分享多mic语音方案、音视频、编解码等技术&#xff0c;与大家一起成长&#xff01; 优质专栏&#xff1a;Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 人生格言&#xff1a; 人生…

自定义GPT已经出现,并将影响人工智能的一切,做好被挑战的准备了吗?

原创 | 文 BFT机器人 OpenAI凭借最新突破&#xff1a;定制GPT站在创新的最前沿。预示着个性化数字协助的新时代到来&#xff0c;ChatGPT以前所未有的精度来满足个人需求和专业需求。 从本质上讲&#xff0c;自定义GPT是之前的ChatGPT的高度专业化版本或代理&#xff0c;但自定…

kafka单节点创建 topic 超时

1.根据之前的知道&#xff0c;安装kafka的时候改了config的server.properies文件中的listeners配置 之前这一行是没有注释掉的&#xff0c;结果创建topic的时候时钟报错连接超时 结果资料&#xff0c;发现就是因为listeners的问题 https://blog.csdn.net/weixin_42133361/art…

【2013年数据结构真题】

highlight: a11y-dark 41题 王道解析&#xff1a; 算法的策略是从前向后扫描数组元素&#xff0c;标记出一个可能成为主元素的元素Num 。然后重新计数&#xff0c;确认Num是否是主元素。算法可分为以下两步&#xff1a; 选取候选的主元素&#xff1a;依次扫描所给数组中的每个…

CCNA课程实验-14-Final_Lab

目录 实验条件网络拓朴需求 配置实现1. 配置PC1~3, DHCP_Server的vlan2. VLAN10、20的网关为MSW1对应的SVI&#xff0c;VLAN30、40的网关为MSW2对应的SVI&#xff1b;3. 配置5台交换机之间线路均为Trunk4. 配置5台交换机均启用Rapid-PVST(RSTP)5. 配置DHCP Server&#xff0c;创…

CCF ChinaSoft 2023 论坛巡礼|自动驾驶仿真测试论坛

2023年CCF中国软件大会&#xff08;CCF ChinaSoft 2023&#xff09;由CCF主办&#xff0c;CCF系统软件专委会、形式化方法专委会、软件工程专委会以及复旦大学联合承办&#xff0c;将于2023年12月1-3日在上海国际会议中心举行。 本次大会主题是“智能化软件创新推动数字经济与社…