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

填空题（2023年暨南大学）

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

答案解析

暂无答案

讨论

数据结构与算法

在折半查找中，要求待查找的关键字序列必须________，这样才能进行查找操作。

一组记录的排序码为(45，35，71，51，20，26，61，12)，则利用快速排序的方法，以第一个记录为基准得到的第一次划分结果为____________________.

无向图的邻接矩阵是对称的，因此可只存储矩阵的下三角阵。

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

一个图按广度优先遍历的结果是唯一的。

分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。

冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。

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

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

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

二叉树

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

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

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

在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个结点的数据值。

已知一棵二叉树，如果先序遍历的顺序是ADCEFGHB，中序遍历的顺序是CDFEGHAB，则后序遍历的结果为【】。

具有n个叶子的二叉树，每个叶子的权值为wi（1≤i≤n），其中带权路径长度最小的二叉树称为__________。

啥夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。

树和二叉树

什么是啥夫曼（Huffman）树？

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

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

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

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

与算术表达式3-(2+7)/4对应的二又树为【】。

对二叉树中的结点如下编号：树根结点编号为1，根的左孩子结点编号为2、右孩子结点编号为3，以此类推，对于编号为i的结点，其左孩子编号为2i、右孩子编号为2i+1。例如，下图所示二又树中有6个结点，结点a、b、c、d、e、f的编号分别为1、2、3、5、7、11。那么，当结点数为n(n>0)的【】时，其最后一个结点编号为2n-1。

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

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

某二叉树的先序遍历(根、左、右)序列为 EFHIGJK、中序遍历(左、根、右)序列为HFIEJKG，则该二叉树根结点的左孩子结点和右孩子结点分别是【】