`
128kj
  • 浏览: 613189 次
  • 来自: ...
社区版块
存档分类
最新评论

二叉树:填空题

阅读更多
填空:
1. 由3个结点所构成的二叉树有(5)种形态。

2.  一棵深度为6的满二叉树有 ( 31 ) 个分支结点和(  32 ) 个叶子。
    注:满二叉树没有度为1的结点,所以分支结点数就是二度结点数。

3. 一棵具有257个结点的完全二叉树,它的深度为 (  9 )。
   注:用[log2(n)]+1=9
4. 设一棵完全二叉树有700个结点,则共有  350  个叶子结点。
答:最快方法:用叶子数=[n/2]=350

5. 设一棵完全二叉树具有1000个结点,则此完全二叉树有 (500 ) 个叶子结点,有(  499 )  个度为2的结点,
   有 (  1  ) 个结点只有非空左子树,有(  0  ) 个结点只有非空右子树。
答:最快方法:用叶子数=[n/2]=500 ,n2=n0-1=499。 另外,最后一结点为2i属于左叶子,右叶子是空的,所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况,所以非空右子树数=0.

6.  一棵含有n个结点的k叉树,可能达到的最大深度为 ( n ) ,最小深度为( 2 ) 。
答:当k=1(单叉树)时应该最深,深度=n(层);当k=n-1(n-1叉树)时应该最浅,深度=2(层),但不包括n=0或1时的特例情况。)

7.   二叉树的基本组成部分是:根(N)、左子树(L)和右子树(R)。因而二叉树的遍历次序有六种。最常用的是三种:前序法(即按N L R次序),
后序法(即按L R N次序)和中序法(也称对称序法,即按L N R次序)。这三种方法相互之间有关联。
若已知一棵二叉树的前序序列是BEFCGDH,中序序列是FEBGCHD,则它的后序序列必是( F E G H D C B)         。
解:法1:先由已知条件画图,再后序遍历得到结果;

    法2:不画图也能快速得出后序序列,只要找到根的位置特征。由前序先确定root,由中序先确定左子树。例如,前序遍历BEFCGDH中,根结点在最前面,是B;则后序遍历中B一定在最后面。

    法3:递归计算。如B在前序序列中第一,中序中在中间(可知左右子树上有哪些元素),则在后序中必为最后。如法对B的左右子树同样处理,则问题得解。

8.中序遍历的递归算法平均空间复杂度为    O(n)   。

9.  用5个权值{3, 2, 4, 5, 1}构造的哈夫曼(Huffman)树的带权路径长度是( 33 )  。
解:先构造哈夫曼树,得到各叶子的路径长度之后便可求出WPL=(4+5+3)×2+(1+2)×3=33
    
分享到:
评论

相关推荐

    二叉树习题

    二叉树是计算机科学中一种重要的数据结构,它在很多领域有着广泛的应用,如文件系统、编译器设计、图形处理等。二叉树的概念基于树的定义,但具有更特殊的性质,使得它们更容易被处理和操作。 首先,我们要理解树的...

    【计算机求职笔试】涵盖计算机基础、编程语言、数据结构与算法的笔试题详解:选择题、填空题、简答题及编程题示例计算机求职笔试题

    填空题补充了计算机存储单位、系统组成、C++函数重载条件、二叉树遍历方式、数据库关系模型、HTTP协议端口、Java方法修饰、快速排序复杂度、Python异常处理、设计模式原则等细节。简答题则深入探讨了计算机网络功能...

    【计算机等级考试】全国计算机二级Access数据库程序设计笔试样卷:选择题与填空题详解及备考指南

    文档分为选择题和填空题两大部分,涵盖了程序设计风格、软件设计流程、数据库生命周期、关系运算、SQL语言、Access表结构与操作、VBA编程等多个知识点。选择题部分考察了考生对基础知识的理解和应用能力,涉及算法...

    树和二叉树习题(老师给的题)含答案

    二、填空题 9. 如果某二叉树的前根次序遍历结果为 stuvw,中序遍历为 uwtvs,那么该二叉树的后序为 wutsv。 10. 二叉树的前序遍历序列中,任意一个结点均处在其子女结点的前面,这种说法正确。 答案:A. 正确 11...

    【C语言程序设计】C语言程序设计试卷二:涵盖选择题、填空题、编程题及综合题的考试内容与参考答案

    内容概要:本文档为《C语言程序设计试卷二》,主要包括四个部分:选择题、填空题、编程题和综合题。选择题涵盖了基本数据类型、运算符、数组、函数参数传递、内存分配、预处理器指令、结构体等知识点;填空题涉及位...

    树与二叉树的主观题部分.doc

    在IT领域,树和二叉树是数据结构的重要组成部分,它们在算法设计和优化中扮演着关键角色。这里我们将深入探讨题目中提到的一些知识点。 首先,我们了解树的路径长度。树的路径长度是从树根到每个节点的路径长度之和...

    数据结构习题

    6. **二叉树遍历**:题目描述和填空题10涉及到二叉树的前序、中序和后序遍历。给定这些遍历序列,我们可以重建二叉树的结构。对于一个完全二叉树,根据遍历序列,可以推断出结点的双亲、左孩子和右孩子的编号关系。 ...

    【Python编程】递归函数基础测试卷:涵盖选择题、填空题及编程实践的递归算法考核

    文档分为四个部分:选择题、填空题、代码编程题和综合题。选择题部分涵盖递归函数的基本概念、应用场景、优缺点、时间复杂度、空间复杂度等内容;填空题部分要求补充完成常见的递归函数代码片段,如计算斐波那契数列...

    专升本数据结构选择填空题

    在专升本数据结构的选择填空题中,考生需要对上述知识点有深入的理解和灵活运用,才能在考试中取得理想成绩。通过反复练习和理解这些基本概念,可以有效提升数据结构的学习效果。所以,这份"专升本数据结构选择填空...

    【Python测试开发】算法能力测试卷:涵盖选择题、填空题、编程题及综合题的全面考核

    内容概要:本文档是一份针对Python测试开发工程师的算法能力测试卷,涵盖选择题、填空题、编程题和综合题四个部分。选择题考察Python基础知识、数据结构与算法、HTTP协议等;填空题涉及递归、排序、设计模式、HTTP...

    2018年重庆邮电大学802数据结构真题高清原版PDF.pdf

    在提供的文件内容中,我们可以看到涉及的是数据结构相关的考试题目,其中包含了一系列关于数据结构基础概念、算法和数据结构应用的选择题和填空题。下面我将详细介绍这些知识点。 ### 选择题知识点总结 1. **时间...

    C语言 填空题整理

    对于一个完全二叉树,如果最后一层的结点数为m,则该二叉树的结点总数为2^h + m - 1,其中h是树的高度。 ### 44. 顺序查找的时间复杂度 - **选项解析**:顺序查找的时间复杂度为O(n),即在最坏的情况下,需要遍历...

    【Python编程】Python面试基础题目:涵盖选择题、填空题、编程题及综合题设计了文档的主要内容

    内容概要:本文档《Python 面试基础题目.pdf》主要针对Python面试的基础题目进行整理,涵盖选择题、填空题、代码编程题以及综合题四个部分。选择题涉及操作符优先级、列表切片、__slots__特性、协程、线程安全的数据...

    树和二叉树自测试题.doc

    2. **填空题解析**: - 树是一种“分支层次”结构,根结点没有直接前趋。 - 树上的任何结点(不包括根)是根的后代,A是B的祖先。 - 二叉树的基本形态包括:空二叉树、只有一个根的二叉树、只有左子树的二叉树、...

    数据结构复习材料试题

    16. **二叉树的结点关系**:填空题第二题,若二叉树有10个叶子结点,那么有2个孩子的结点数量是9。 17. **满二叉树的结点数**:填空题第三题,高度为h的满二叉树的结点数是2^h - 1。 18. **顺序表的创建**:填空题...

    计算机二级公共基础知识(填空题40道)

    以上是对计算机二级公共基础知识中部分填空题涉及知识点的详细解析,这些内容涵盖了算法、数据结构、数据库管理、软件工程等多个核心领域。理解并掌握这些知识点对于通过计算机等级考试至关重要。

    数据结构1800题树及二叉树章节答案

    在本题集中,主要涉及了树与二叉树的选择题、判断题和填空题,涵盖了很多重要的知识点。 首先,从选择题中,我们可以看到涉及到二叉树性质的考察,如节点数量的计算公式,例如第12题,通过二叉树的节点公式n = n0 +...

    2015-2016 第一学期试题A答案201511121

    三、填空题解析 1. O(n):该题考查了算法的时间复杂度分析。 2. s->next=p->next; p->next=s:该题考查了链表的基本操作,例如插入和删除节点。 3. (1,3,2,4,5):该题考查了排序算法的基本概念和分类。 4. n-1:该...

    数据结构第6章二叉树自测卷附答案

    **填空题部分**: 1. 3个节点构成的二叉树有5种形态。 2. 深度为6的满二叉树有31个分支结点和32个叶子结点。 3. 具有257个节点的完全二叉树深度为9。 4. 700个节点的完全二叉树有350个叶子结点。 5. 1000个节点的...

Global site tag (gtag.js) - Google Analytics