数据结构与算法-考研试题(暨南大学 2023年树的概念与性质)

判断题（2023年暨南大学）

在一棵树中，堂兄弟的双亲是兄弟关系。

答案解析

错

讨论

数据结构与算法

已知一颗二叉树的先序序列和后序序列，一定能构造出该树。

顺序表查找指的是在顺序存储结构上进行查找。

在一棵二叉树中，中序遍历的第一个结点，是二叉树的最左下结点。

用邻接表表示图进行广度优先遍历时，通常采用【】来实现算法。

算法的时间复杂度不是O(nlogn)的算法是【】

如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是【】

表达式a*(b+c)-d 的后缀表达式是【】

深度优先遍历类似于二叉树的【】

任何一个无向连通图的最小生成树【】

按照二叉树的定义，具有3个结点的二叉树有【】种。

树的概念与性质

已知一棵度为m的树中有N1个度为1的结点，N2个度为2的结点，...，Nm个度为m的结点。试问该树中有多少个叶子结点？

某二又树的先序遍历序列为 ABCDFGE，中序遍历序列为 BAFDGCE。以下关于该二又树的叙述中，正确的是【】。

对于一般的树结构，可以采用孩子-兄弟表示法，即每个结点设置两个指针域，一个指针(左指针)指示当前结点的第一个孩子结点，另一个指针(右指针)指示当前结点的下一个兄弟结点。某树的孩子-兄弟表示如下图所示。以下关于结点 D 与 E 的关系的叙述中，正确的是【】。

对下图所示的二叉树进行中序遍历(左子树、根结点、右子树)的结果是【】。

树是结点的集合，它的根结点数目是【】

如果只考虑有序树的情形，那么具有7个结点的不同形态的树共有【】

若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是【】

循环链表的主要优点是【】

将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为35的结点的左孩子编号为【】。

不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。

树和二叉树

由树转化为二叉树，该二叉树的右子树不一定为空。

设二叉树中度为0的结点数为30，度为1的结点数为20，则该二叉树中总共有_____个结点数。

在N个结点的线索二叉树中线索的数目为______.

阅读下面的程序代码，写出此函数的功能。void F(Bitree T,Stack &S){ if(T){ Push(S,T->data); if(!T->Lchild && !T->Rchild)PrintStack(S); else{ F(T->Lchild,S); F(T->Rchild,S); } Pop(S); }}

假设表中关键字序列为(41，36，58，12，79，25)，将关键字依次插入一棵初始为空的二叉排序树，然后删除结点 41。(1) 画出二叉排序树的生成过程；(2)画出删除结点41后的二叉排序树。

假设二叉树采用二叉链表存储结构，试编写一个非递归算法，输出中序遍历序列中第k个结点的数据值。

一个深度为 h 的满 m 叉树有如下性质：第 h 层上的结点都是叶结点，其各层上每个结点有 m 棵非空子树。问：（1）第 k 层最多有多少个结点？（k≤h )（2）整棵树最多有多少个结点？（3）若按层次从上到下，每层从左到右的顺序从1开始对全部结点编号，编号为 i 的结汽的双亲结点的编号是什么？编号为 i 的结点的第 j 个孩子结点（若存在）的编号是什么？

证明，由一棵二叉树的前序序列和中序序列可唯一地确定这棵二叉树。设一棵二叉树的前序序列为ABDGECFH，中序序列为DGBEAFHC，试画出该二叉树。

已知一棵二叉树的前序遍历结果是ADCEBFIHGJ，中序遍历结果是CDEBAFHGIJ，试画出这棵二叉树。

用一维数组存放的一棵完全二叉树如下：A、B、C、D、E、F、G、H、I、J、K、L写出后序遍历该二叉树时访问结点的顺序。