数据结构试题
年级班级姓名学号
一、填空题
1、一颗深度为6的二叉树总结点数值少为，最多为；一颗深度为6的完全二叉树第5层上的结点数为____，总结点数最小值为，总结点数最多时称为
二叉树。
2、对于一颗具有n个结点的二叉树，当它为一颗完全二叉树时具有最小高度，高度
为，当它为一颗单支树具有最大高度，高度为。
3、一颗完全二叉树第6层有7个结点，则共有个结点，其中度为1的结点有个，度为0的结点有个，若按从上到下，从左到右次序给结点编号（从1开始），编号最大的非叶子结点是，编号最小的叶子结点是。
4、设高度为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为，至多为。
5、对于一颗具有n个结点的二叉树，当进行二叉链表存储时，其指针域的总数为个，其中个用于链接孩子
结点，个空闲着。
6、已知二叉树中叶子数为50，仅一个孩子的结点数为30，则总结点数____；在有50个叶子结点的哈夫曼树中，总结点数是_ ___。
7、有5813个结点构成一棵完全二叉树，其叶子结点数为；有5813个结点构成一棵二叉树，已知2度结点数为0，则树高是。
8、先序为a,b,c，且后序为c,b,a，的二叉树有棵。
9、在二叉链表中，数据域值为data，左右子树的指针分别为lchild和rchild，则判断某指针p所指结点为0度结点的条件是；p所指结点为1度结点的条件是；p所指结点为2度结点的条件是。
10、由带权为3，9，6，2，5的5个叶子结点构成一颗Huffman树，则带权路径长度
为。
二、选择题
1、按照二叉树的定义，具有三个结点的二叉树有种形状。
A、3
B、4
C、5
D、6
2、一棵二叉树的叶子结点数为6，则度为1的结点个数为。
A、5
B、7
C、6
D、不能确定
3、在非空二叉树的中序遍历序列中，根结点的右边。
A、只有右子树上的所有结点
B、只有右子树上的部分结点
C、只有左子树上的部分结点
D、只有左子树上的所有结点
4、下列陈述中正确的是。
A、二叉树是度为2的有序树
B、二叉树中结点只有一个孩子时无左右之分
C、二叉树中必有度为2的结点
D、二叉树中最多只有两棵子树，并且有左右之分
5、对有100个结点的完全二叉树按层次依次编号，则编号为49的结点右孩子编号为。
A、98
B、51
C、99
D、97
6、如果n1和n2是二叉树T中两个不同结点，n2是n1的孩子，那么按遍历二叉树T时，结点n2一定比结点n1先被访问。
A、先序
B、中序
C、后序
D、逆中序
7、某二叉树的中序序列和后序序列正好相反，则该二叉树一定是的二叉树。
A、空或只有一个结点
B、高度等于其结点数
C、任一结点无左孩子
D、任一结点无右孩子
8、某二叉树的先序序列和后序序列正好相同，则该二叉树一定是的二叉树。
A、空或只有一个结点
二叉树定义
B、高度等于其结点数
C、任一结点无左孩子
D、任一结点无右孩子
9、一棵深度为8（根的层次号为1）的满二叉树有个叶子结点
A、256
B、255
C、128
D、127
10、如图是用孩子兄弟链表法所表示的一个森林，则该森林是由棵树构成。
A．1 B．2 C．3 D．4
三、算法阅读
设二叉树以二叉链表为存储结构，结点类型定义如下：
typedef struct tnode{
char data;
struct tnode *lchild, *rchild /* lchild指向左孩子，rchild 指向右孩子*/
}BiTNode, *BiTree;
1、对应二叉链表存储的二叉树已建立（如下图），根结点地址为T，请给出调用ex1(T)函数的输出结果。
void ex1(BiTree T)
{ if(T)
{ ex1(T-> lchild);
ex1(T-> rchild);
if(T->data>=’0’ && T->data<=’9’)
printf(“%c”, T->data);
}
}
2、下面的函数ex2是统计二叉树中2度结点的个数，请填充适当的内容，使得该算法可以完成相应的功能。
void ex2(BiTree T, int *n) /* n指向存放统计结果变量的指针变量*/
{ if(T)
{ex2(T->lchild, n);
if( )
;
ex2(T->rchild, n);
}
}
四、应用题
1、有一个完全二叉树按层次顺序存放在一维数组中，如下所示：
请指出结点P的父结点，左子女，右子女。
2、有一棵二叉树按顺序结构存放在一维数组中，如下所示：
a    b    c    d    e    f g h
请画出该二叉树的二叉链表存储结构。
3、假设在通信中要传输一组字符“ABC,AAABCC,ABC,DDC,AAA”。
（1）构造相应的赫夫曼树（左结点的权小于右结点的权）
（2）求出带权路径的长度WPL
（3）给出每个字符的赫夫曼编码（左分支为“0”，有分支为“1”）
4、已知一颗二叉树的先序和中序遍历的结点序列分别为IJKLMNO及JLKINMO，试画出此二叉树，并给出后序遍历序列结果
五、算法设计题
设二叉树以二叉链表为存储结构，结点类型定义如下：
typedef struct tnode{
int data;
struct tnode *left, *right /*left指向左孩子，right 指向右孩子*/
}BiTNode, *BiTree;
1、请编写一个函数int Count (BTree T)，其功能是计算T所指的二叉树中结点值为偶数的结点数并返回该值。
2、试编写一个函数BiTree InorderFirstNode(BiTree T)，其功能是二叉树中序遍历第一个结点并返回该结点地址。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。