填空:
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
分享到:
相关推荐
二叉树是计算机科学中一种重要的数据结构,它在很多领域有着广泛的应用,如文件系统、编译器设计、图形处理等。二叉树的概念基于树的定义,但具有更特殊的性质,使得它们更容易被处理和操作。 首先,我们要理解树的...
在IT领域,树和二叉树是数据结构的重要组成部分,它们在算法设计和优化中扮演着关键角色。这里我们将深入探讨题目中提到的一些知识点。 首先,我们了解树的路径长度。树的路径长度是从树根到每个节点的路径长度之和...
二、填空题 9. 如果某二叉树的前根次序遍历结果为 stuvw,中序遍历为 uwtvs,那么该二叉树的后序为 wutsv。 10. 二叉树的前序遍历序列中,任意一个结点均处在其子女结点的前面,这种说法正确。 答案:A. 正确 11...
6. **二叉树遍历**:题目描述和填空题10涉及到二叉树的前序、中序和后序遍历。给定这些遍历序列,我们可以重建二叉树的结构。对于一个完全二叉树,根据遍历序列,可以推断出结点的双亲、左孩子和右孩子的编号关系。 ...
在专升本数据结构的选择填空题中,考生需要对上述知识点有深入的理解和灵活运用,才能在考试中取得理想成绩。通过反复练习和理解这些基本概念,可以有效提升数据结构的学习效果。所以,这份"专升本数据结构选择填空...
在提供的文件内容中,我们可以看到涉及的是数据结构相关的考试题目,其中包含了一系列关于数据结构基础概念、算法和数据结构应用的选择题和填空题。下面我将详细介绍这些知识点。 ### 选择题知识点总结 1. **时间...
对于一个完全二叉树,如果最后一层的结点数为m,则该二叉树的结点总数为2^h + m - 1,其中h是树的高度。 ### 44. 顺序查找的时间复杂度 - **选项解析**:顺序查找的时间复杂度为O(n),即在最坏的情况下,需要遍历...
2. **填空题解析**: - 树是一种“分支层次”结构,根结点没有直接前趋。 - 树上的任何结点(不包括根)是根的后代,A是B的祖先。 - 二叉树的基本形态包括:空二叉树、只有一个根的二叉树、只有左子树的二叉树、...
16. **二叉树的结点关系**:填空题第二题,若二叉树有10个叶子结点,那么有2个孩子的结点数量是9。 17. **满二叉树的结点数**:填空题第三题,高度为h的满二叉树的结点数是2^h - 1。 18. **顺序表的创建**:填空题...
以上是对计算机二级公共基础知识中部分填空题涉及知识点的详细解析,这些内容涵盖了算法、数据结构、数据库管理、软件工程等多个核心领域。理解并掌握这些知识点对于通过计算机等级考试至关重要。
在本题集中,主要涉及了树与二叉树的选择题、判断题和填空题,涵盖了很多重要的知识点。 首先,从选择题中,我们可以看到涉及到二叉树性质的考察,如节点数量的计算公式,例如第12题,通过二叉树的节点公式n = n0 +...
三、填空题解析 1. O(n):该题考查了算法的时间复杂度分析。 2. s->next=p->next; p->next=s:该题考查了链表的基本操作,例如插入和删除节点。 3. (1,3,2,4,5):该题考查了排序算法的基本概念和分类。 4. n-1:该...
**填空题部分**: 1. 3个节点构成的二叉树有5种形态。 2. 深度为6的满二叉树有31个分支结点和32个叶子结点。 3. 具有257个节点的完全二叉树深度为9。 4. 700个节点的完全二叉树有350个叶子结点。 5. 1000个节点的...
填空题3计算完全二叉树的高度,完全二叉树是高度优化的二叉树结构,高度与节点数量有直接关系。 10. **共享存储区的栈操作**: 填空题4讨论了两个栈共享同一存储区的情况,栈顶指针的变化反映了栈的状态,如空栈...
### 填空题解析 #### 1. 路径长度 - **答案解析**:树的路径长度是指从树根到每个结点的路径长度之和。对于结点数相同的树而言,路径长度最短的是完全二叉树。 #### 2. 哈夫曼树的结点总数 - **答案解析**:在有n...
第六章主要讲解了树和二叉树的基本概念和特性,涉及了多项选择题和填空题,涵盖了多个知识点。以下是对这些知识点的详细说明: 1. 满二叉树的性质:在一棵具有5层的满二叉树中,结点总数可以通过公式2^(h-1)-1计算...
- 填空题第1题,后序遍历二叉树结果为YDEBFZXCA,这涉及到二叉树的遍历算法。 8. **链表结构** - 填空题第2题,链表节点包含数据域和指针域。 9. **软件文档** - 填空题第3题,软件是程序、数据和文档的集合。 ...
#### 二、填空题知识点解析 1. **二叉树的形态**: - **知识点**:由3个节点构成的不同形态的二叉树数量。 - **解析**:由3个节点构成的不同形态的二叉树共有5种不同的形态。 2. **满二叉树的节点数量**: - **...