数据结构与算法-考研试题(暨南大学 2023年二叉树)

判断题（2023年暨南大学）

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

答案解析

错

讨论

数据结构与算法

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

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

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

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

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

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

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

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

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

将一棵有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个结点的数据值。

一棵二叉树按中序遍历时各结点被访问的次序和这棵二叉树按后序遍历时各结点被访问的次序能否唯一确定这棵二叉树的结构？为什么？若已知一棵二叉树按先序遍历时各结点被访问的次序和这棵二叉树按后序遍历时各结点被访问的次序，能否唯一确定这棵二叉树的结构？为什么？

对于二叉树T 的两个结点 n1 和 n2 ，我们应该选择树 T 结点的前序、中序和后序中哪两个序列来判断结点 n1 必定是结点 n2的祖先，并给出判断的方法。不需证明判断方法的正确性。

证明一棵二叉树无论进行先序、中序、后序遍历，其叶子结点的相对次序不发生改变。

对二叉排序树进行【】遍历，可以得到该二叉树所有结点构成的排序序列。

树和二叉树

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

若二叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，利用【】遍历方法最合适。

什么是啥夫曼（Huffman）树？

在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树，该说法【】。

如果一棵huffman树T有n0个叶子结点，那么，树T有多少个结点？要求给出求解过程。

求具有最小带权路径长度的二叉树的算法称为__________算法。对于给出的一组权W={10，12，16，21，30}，通过该算法示出的二叉树的带权路径长度为__________。

二叉树中，具有两个子女的结点的中序后继结点最多只能有一个子女。

完全二叉树的特点是叶子结点分布在最后两层，且除最后一层之外，其他层的结点数都达到最大值，那么25个结点的完全二叉树的高度(即层数)为【】。

在数据结构中，【】是与存储结构无关的术语。

已知某二叉树的先序遍历序列为ABCD，后序遍历序列为CDBA，则该二叉树为【】。