目录
- 题1
- 题2
- 题3
- 题4
- 题5
- 题6
- 题7
- 题8
- 题9
题1
1、设高度为h的二叉树上只有度为0和度为2的结点,则该二叉树中所包含的结点数至少为(),最多为()。
A、h ;2h-1
B、2h-1 ; 2h-1
C、2h+1; 2h-1-1
D、h+1;2h-1
解析:(B)
最少的情况下,除了根结点该层为1个结点以外,其余h-1层都有2个结点,得2(h-1),即2(h-1)+1=2h-1。
最多的情况下,除了最后一层度为0,其余结点都是度为2的结点,即 2h-1个。
题2
2、一棵有124个叶结点的完全二叉树,最多有( )个结点。
A、247
B、248
C、249
D、250
解析:(B)
由于n0=n2+1,且N=n0+n1+n2,度为0和度为1的结点相差为1,所以完全二叉树中度为1的结点n1只可能是0或1,即当总结点数为偶数时n1=1,为奇数时n0=0。
本题中,n0=124,可得n2=123,由于是考虑最多结点数,即n1=1,所以N=124+123+1=248。
题3
3、若一棵二叉树有126个结点,在第7层(根结点在第1层)至多有()个结点。
A、32
B、64
C、63
D、不存在第7层
解析:(C)
考虑第1层到第6层结点都是满的情况,即第1层到第6层结点的结点数量为1+2+4+8+16+32=63个。第7层最多可有64个结点,由于二叉树有126个结点,即第7层还有126-63=63个结点。
题4
4 、一棵有n个结点的二叉树采用二次链表存储结点,其中非空指针数为(),空指针数为()。
A、n+1;n-1
B、n;n-1
C、n-1;n+1
D、2n;2n-1
解析:(A)
n个结点的数有n-1条分支,每个分支对应一个指针,所以非空指针数为n-1;另外,由于每个结点中包含2个指针域(左指针域lchild、右指针域rchild),总指针域数量减去非空指针数即为空指针数,2n-(n-1)=n+1。
题5
5、在二叉树的前序序列、中序序列和后序序列中,所有叶子结点的先后顺序是()。
A、都不相同
B、完全相同
C、前序序列和中序序列相同,与后序序列不同
D、中序序列和后序序列相同,与前序序列不同
解析:(B)
三种遍历方式中,访问左右子树的顺序是相同的,只是访问根结点的先后顺序不同,故所有叶子结点的先后顺序是相同的。
题6
6、线索二叉树是一种()结构。
A、逻辑
B、逻辑和存储
C、物理
D、线性
解析:(C)
二叉树是一种逻辑结构,而线索二叉树是加上线索的链表结构,是一种物理结构。
题7
7、在有n个叶子结点的哈夫曼树中,非叶子结点的总数是();若该哈夫曼树有215个结点,对其进行哈夫曼编码,可以得到()个不同的码字。
A、n-1;108
B、n;107
C、2n-1;214
D、2n;215
解析:(A)
哈夫曼树中只有度为0和2的结点,由n0=n2+1,可得:非叶子结点的总数为n-1。
结点总数N=n0+n2,且n0=n2+1,N=215代入可得,n0=108。
题8
8、(判断)哈夫曼编码树中,两个频率相同的字符具有相同的哈夫曼编码。
解析:(×)
不会有相同的哈夫曼编码,除非它们的字符相同,从而得到的哈夫曼编码也相同。
题9
9、找出下列条件的二叉树:
A、先序遍历序列与后序遍历序列相同,为()
B、中序遍历序列与后序遍历序列相同,为()
C、先序遍历序列与中序遍历序列相同,为()
D、中序遍历序列与层次遍历序列相同,为()
解析:
A、空树或只有根结点的二叉树;
B、空树或任一结点至多只有左子树;
C、空树或任一结点至多只有右子树;
D、空树或任一结点至多只有右子树。