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

单项选择（2023年暨南大学）

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

A、34

B、36

C、70

D、71

答案解析

C

讨论

二叉树

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

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

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

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

设二叉树中度为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个结点的数据值。

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

完全二叉树

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

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

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

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

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

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

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

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

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

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

树和二叉树

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

线索二叉树是一种【】结构。

二叉树在线索化后，仍不能有效求解的问题是【】。

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

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

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

对二叉树中的结点如下编号：树根结点编号为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。

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

在有 6 个字符组成的字符集 S 中，各个字符出现的频次分别为 3、4、5、6、8、10，为 S 构造的哈夫曼树的加权平均长度为【】

有n个数顺序（依次）进栈，则出栈顺序有Cn种。Cn=×