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

简介: 数据结构:二叉树经典例题(单选题)-->你真的掌握二叉树了吗?(第二弹)

前言:

承接上篇的二叉树经典例题,本期再来给大家带来一期关于二叉树的经典例题,话不多说,直接开始!!

一、

1. 设某种二叉树有如下特点:每个结点要么是叶子结点,要么有2棵子树。假如一棵这样的二叉树中有m(m>0)个叶子结点,那么该二叉树上的结点总数为(  )

A.2m+1

B.2(m-1)

C.2m-1

D.2m

题解: C

根据二叉树的性质,在任意的二叉树中,度为0的节点比度为2的节点多了1个----见二叉树的性质

现在叶子节点为m个,即度为0的节点有m个,那度为2的节点个数就为m-1个

而题目说该二叉树中只有度为2和度为0的节点 ,因此总的节点数就为:m+m-1 = 2m-1

故选择C

二、

2. 设根结点的深度为1,则一个拥有n个结点的二叉树的深度一定在(   )区间内

A.[log(n + 1),n]

B.[logn,n]

C.[log(n + 1),n - 1]

D.[log(n + 1),n + 1]

题解: A

假设深度为h,则该二叉树最多有2^h - 1个结点。

因此,我们可以列出不等式: 2^(h-1) <= n <= 2^h - 1 对不等式两边同时取对数

得到: h-1 <= logn <= h-1+log2 因为log2 = 1

所以: h-1 <= logn <= h 将上述不等式转化为区间表示

则有: h <= logn + 1 <= h+1

因此,选项A是正确的。

三、

3. 对任意一颗二叉树,设N0、N1、N2分别是度为0、1、2的结点数,则下列式子中一定正确的是(  )

A.N0 = N2 + 1

B.N1 = N0 + 1

C.N2 = N0 + 1

D.N2 = N1 + 1

题解: A

节点总数N: N = N0 + N1 + N2

度和边的关系: N - 1 = 0 * N0 + 1 * N1 + 2 * N2

上面两个式子可以推出: N0 + N1 + N2 - 1 = N1 + 2 * N2

可得: N0 = N2 + 1

四、

4. 二叉树的(  )遍历相当于广度优先遍历,(  )遍历相当于深度优先遍历

A.前序 中序

B.中序 前序

C.层序 后序

D.层序 前序

题解: D

广度优先需要把下一步所有可能的位置全部遍历完,才会进行更深层次的遍历,层序遍历就是一种广度优先遍历。

深度优先是先遍历完一条完整的路径(从根到叶子的完整路径),才会向上层折返,再去遍历下一个路径,前序遍历就是一种深度优先遍历。

五、

5.  如果一颗二叉树的前序遍历的结果是ABCD,则满足条件的不同的二叉树有(  )种

A.13

B.14

C.15

D.16

题解: B

对于一棵二叉树,它的前序遍历序列的第一个元素一定是根节点。因此,对于给定的前序遍历序列ABCD,我们可以将它的第一个元素A作为根节点,然后考虑将剩余的元素分配到左子树和右子树中。 由于左子树和右子树可以为空,因此我们可以按照以下方式尝试构建二叉树:

  1. A作为根节点,BCD为空树。
  2. A作为根节点,B作为左子节点,CD为空树。
  3. A作为根节点,B作为右子节点,CD为空树。
  4. A作为根节点,B作为左子节点,C作为右子节点,D为空树。
  5. A作为根节点,B作为右子节点,C作为左子节点,D为空树。
  6. A作为根节点,B作为左子节点,C和D作为右子节点。
  7. A作为根节点,B作为右子节点,C和D作为左子节点。
  8. A作为根节点,C作为左子节点,BD为空树。
  9. A作为根节点,C作为右子节点,BD为空树。
  10. A作为根节点,C作为左子节点,B作为右子节点,D为空树。
  11. A作为根节点,C作为右子节点,B作为左子节点,D为空树。
  12. A作为根节点,C作为左子节点,D作为右子节点,B为空树。
  13. A作为根节点,C作为右子节点,D作为左子节点,B为空树。
  14. A作为根节点,B和C作为左右子节点,D为空树。
  15. A作为根节点,B和C作为右左子节点,D为空树。因此,满足条件的不同的二叉树有14种。

六、

6. 有n个元素的完全二叉树的深度是(   )

A.nlogn

B.nlogn+1

C.logn

D.logn+1

题解: D

参考完全二叉树的性质,高度h = log(n)向上取整 注意:底数是2

故选择D

七、

7. 已知某二叉树的前序遍历序列为ABDEC,中序遍历序列为BDEAC,则该二叉树(  )

A.是满二叉树

B.是完全二叉树,不是满二叉树

C.不是完全二叉树

D.是所有的结点都没有右子树的二叉树

题解: C

前序确定根,中序找到根确定根的左右子树,最后还原二叉树为:

八、

8. 一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反,则该二叉树一定满足(  )

A.所有的结点均无左孩子

B.所有的结点均无右孩子

C.只有一个叶子结点

D.至多只有一个结点

题解: C

前序遍历:根 左 右

后序遍历:左 右 根

从二叉树 前序 和 后序遍历结果规则中可以看出,如果树中每个节点只有一个孩子时,遍历结果肯定是反的

比如下面这前序和中序序列所构成的树的结构:

12345

54321

朋友们、伙计们,美好的时光总是短暂的,我们本期的的分享就到此结束,最后看完别忘了留下你们弥足珍贵的三连喔,感谢大家的支持!

目录
相关文章
|
7月前
|
存储 算法 Java
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
194 10
 算法系列之数据结构-二叉树
|
9月前
|
Java C++
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
186 12
|
9月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
166 10
|
9月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
262 3
|
10月前
|
数据库
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
|
11月前
|
机器学习/深度学习 存储 算法
数据结构实验之二叉树实验基础
本实验旨在掌握二叉树的基本特性和遍历算法,包括先序、中序、后序的递归与非递归遍历方法。通过编程实践,加深对二叉树结构的理解,学习如何计算二叉树的深度、叶子节点数等属性。实验内容涉及创建二叉树、实现各种遍历算法及求解特定节点数量。
259 4
|
11月前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
690 8
|
11月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
224 59
|
4月前
|
编译器 C语言 C++
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因,涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问,修改了变量`i`的值,导致`for`循环条件始终为真,形成死循环。原因是VS2022栈区从低地址到高地址分配内存,`arr`数组与`i`相邻,`arr[15]`恰好覆盖`i`的地址。而在VS2019中,栈区先分配高地址再分配低地址,因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致,需避免数组越界以确保代码健壮性。
52 0
栈区的非法访问导致的死循环(x64)
232.用栈实现队列,225. 用队列实现栈
在232题中,通过两个栈(`stIn`和`stOut`)模拟队列的先入先出(FIFO)行为。`push`操作将元素压入`stIn`,`pop`和`peek`操作则通过将`stIn`的元素转移到`stOut`来实现队列的顺序访问。 225题则是利用单个队列(`que`)模拟栈的后入先出(LIFO)特性。通过多次调整队列头部元素的位置,确保弹出顺序符合栈的要求。`top`操作直接返回队列尾部元素,`empty`判断队列是否为空。 两题均仅使用基础数据结构操作,展示了栈与队列之间的转换逻辑。