《计算机软件技术基础》课后题答案 - 图文(9)

度数为1的分支结点 C．若初始森林中共有n棵二叉树，最终求得的哈夫曼树共有2n-1个结点 *D．若初始森林中共有n棵二叉树，进行2n-1次合并后才能剩下一棵最终的哈夫曼树

5．深度为6的二叉树最多有( )个结点。 A．64 *B．63 C．32 D．31

6．将含有41个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为21的双亲结点编号为( )。 *A．10 B．11 C．41 D．20

7．任何一棵二叉树的叶结点在其前序、中序、后序遍历序列中的相对位置( )。 A．肯定发生变化 B．有时发生变化 *C．肯定不发生变化 D．无法确定

8．设二叉树有n个结点，则其深度为( )。 A．n-1 B．n C．└log2n┘+1 *D．无法确定

9．设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含结点总数最少( )个。

A．k+l B．2k *C．2k-1 D．2k+1 10．下列说法正确的是( )。

*A．树的前序遍历序列与其对应的二叉树的前序遍历序列相同 B．树的前序遍历序列与其对应的二叉树的后序遍历序列相同 C．树的后序遍历序列与其对应的二叉树的前序遍历序列相同 D．树的后序遍历序列与其对应的二叉树的后序遍历序列相同 11．下列说法中正确的是( )。

A．任何一棵二叉树中至少有一个结点的度为2 B．任何一棵二叉树中每个结点的度都为2 C．任何一棵二叉树中的每个结点的度肯定等于2 *D．任

41

何一棵二叉树中的每个结点的度都可以小于2

12．一棵二叉树满足下列条件：对任意结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。现采用( )遍历方式就可以得到这棵二叉树所有结点的递减序列。 A．前序 *B．中序 C．后序 D．层次

13．设森林T中有4棵树，结点个数分别是n1、n2、n3、n4，当把森林T转换成一棵二叉树后，根结点的右子树上有( )个结点。 A．n1-1 B．n1 C．n1+n2+n3 *D． n2+n3+n4

14．对含有( )个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。

A．0 *B．1 C．2 D．不存在这样的二叉树 15．如图6-1所示的二叉树的中序遍历序列是( )。

A．abcdgef *B．dfebagc C．dbaefcg D．defbagc

16．已知某二叉树的后序遍历序列是deacb，中序遍历序列是deabc，它的前序遍历序列是( )。

A．acbed *B．baedc C．dceab D．cedba

17．如果T1是由有序树转化而来的二叉树，那么T中结点的前序就是T1中结点的( )。

*A．前序 B．中序 C．后序 D．层次序

42

18．某二叉树的前序遍历的结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是( )。

A．bdgcefha B．gdbecfha C．bdgechfa *D．gdbehfca 19．在图6-2中的二叉树中，( )不是完全二叉树。（*C）

20．树最适合用来表示( )。

A．有序数据元素 B．无序数据元素 *C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据

21．在计算递归函数时，如不使用递归过程，则一般情况下必须借助于( )数据结构。

*A．栈 B．树 C．双向队列 D．顺序表

22．设二叉树根结点的层次为0，一棵高度为h的满二叉树中的结点个数是( )。 A．2 B．2 C．2-1 *D．2-1 23．以下说法错误的是( )。

h

h-1

h

h+1

A．存在这样的二叉树，对它采用任何次序的遍历，其结点访问序列均相同 *B．二叉树是树的特殊情形 C．由树转换成二叉树，其根结点的右子树总是空的 D．在二叉树只有一棵子树的情况下也要明确指出该子树是左子树还是右子树

24．已知一个算式的中缀表达式为a+(b-c)/d，则其后缀表达式是( )。 A．a+(b-c)/d *B．abc-d/+ C．bc-d/a+ D．a+bc-d/

25．按照二叉树的定义，具有4个结点所能构造的不同的二叉树的个数是( )。 A．4 B．8 C．12 *D．14

43

26．在一棵度为3的树中，度为3的结点的个数为2，度为2的结点的个数为1，则度为0的结点的个数为( )。 A．4 B．5 *C．6 D．7

27．3个结点可构成( )棵不同形态的二叉树。 A．2 B．3 C．4 *D．5 28．哈夫曼树的带权路径长度是( )。

A．所有结点权值之和 *B．所有叶结点带权路径长度之和 C．带权结点的值 D．除根以外所有结点权值之和

29．设有一棵22个结点的完全二叉树，那么整棵二叉树有( )个度为0的结点。 A．6 B．7 C．8 *D．11

30．已知完全二叉树有26个结点，则整棵二叉树有( )个度为1的结点。 A．0 *B．1 C．2 D．13

31．在树的孩子兄弟表示法中，( )操作花时间最多。

A. 求某结点的兄弟 B．求某结点的第i个孩子 *C．求某结点的父结点 D．求树的根结点

32． 已知如图6-3所示的哈夫曼树，那么电文CDAA的编码是( )。 A．110100 *B．11011100 C．010110111 D．11111100

33．在n个结点的完全二叉树中，对任一结点i(1≤i≤n)，i的左孩子可能是( )。

A．i/2 B．2i+1 *C．2i D．都不是

44

34．已给出图6-3所示的二叉树，A，B，C，D的权值分别为7，5，2，4，则该树的带权路径长度为( )。

A．46 B．36 *C．35 D．都不是 35．下列叙述中不正确的是( )。

A．二叉树是度为2的有序树 B．二叉树中结点只有一个孩子时有左右之分 *C．二叉树中必有度为2的结点 D．二叉树中结点最多有两棵子树，并且有左右之分

36．图6-4所示的几种结构中属于树形结构的是( )。（*B）

二、判断题

╳1．二叉树是树的特殊形式。

√2．树和二叉树之间最主要的差别是：二叉树的结点的子树要区分为左右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。 √3．一棵有n个结点的d度树，若用多重链表表示，树中每个结点都有d个链域，则在树的n*d个链域中，有n*(d-1)+1个是空链域，只有n-1个是非空的。 √4．前序遍历树和前序遍历与该树对应的二叉树，其结果相同。 ╳5．中序遍历树和中序遍历与该树对应的二叉树，其结果不同。 √6．前序遍历森林和前序遍历与该森林对应的二叉树，其结果相同。 ╳7．中序遍历森林和中序遍历与该森林对应的二叉树，其结果不同。 √8．若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必须是该子树的前序遍历序列中的最后一个结点。

√9．二叉树中具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女。

45