4．以下说法错误的是( )。
A．一般在哈夫曼树中，权值越大的叶子离根结点越近 B．哈夫曼树中没有度数为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．任何一棵二叉树中的每个结点的度都可以小于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．层次序
18．某二叉树的前序遍历的结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是( )。
A．bdgcefha B．gdbecfha C．bdgechfa *D．gdbehfca 19．在图6-2中的二叉树中，( )不是完全二叉树。（*C）
16
20．树最适合用来表示( )。
A．有序数据元素 B．无序数据元素 *C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据
21．在计算递归函数时，如不使用递归过程，则一般情况下必须借助于( )数据结构。 *A．栈 B．树 C．双向队列 D．顺序表
22．设二叉树根结点的层次为0，一棵高度为h的满二叉树中的结点个数是( )。 A．2h B．2h-1 C．2h-1 *D．2h+1-1 23．以下说法错误的是( )。
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
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．都不是
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）
17
二、判断题
╳1．二叉树是树的特殊形式。
√2．树和二叉树之间最主要的差别是：二叉树的结点的子树要区分为左右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。
√3．一棵有n个结点的d度树，若用多重链表表示，树中每个结点都有d个链域，则在树的n*d个链域中，有n*(d-1)+1个是空链域，只有n-1个是非空的。
√4．前序遍历树和前序遍历与该树对应的二叉树，其结果相同。 ╳5．中序遍历树和中序遍历与该树对应的二叉树，其结果不同。
√6．前序遍历森林和前序遍历与该森林对应的二叉树，其结果相同。 ╳7．中序遍历森林和中序遍历与该森林对应的二叉树，其结果不同。
√8．若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必须是该子树的前序遍历序列中的最后一个结点。
√9．二叉树中具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女。 ╳10．在二叉树中，具有一个子女的父结点，在中序遍历中，它没有后继的子女结点。 ╳11．在二叉树中插入结点，该二叉树便不再是二叉树。
╳12．用一维数组存储二叉树时，总是以前序遍历存储结点。
√13．已知二叉树的前序遍历和后序遍历序列不能惟一地确定这棵树。 √14．不使用递归，也可以实现二叉树的前序、中序、后序遍历。
√15．在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点之后。 ╳16．有n个结点的不同二叉树有n!棵。
╳17．在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应做特殊处理。 三、填空题
1．树(及一切树形结构)是一种__层次__结构。在树中，__根_结点没有直接前驱。对树上任一结点x来说，x是它的任一子树的根结点惟一的_双亲_。
2．一棵树上的任何结点(不包括根本身)称为根的__子孙__。若B是A的子孙，则称A是B的__祖先__。 3．二叉树第i(i>0)层上至多有__2i-1__个结点。 4．深度为k(k>0)的二叉树至多有__2k-1__个结点。
5．对任何二叉树，若度为2的节点数为n2，则叶子数n0=__n2+1__。
6．满二叉树上各层的节点数已达到了二叉树可以容纳的__最大值_。满二叉树也是__完全__二叉树，但反之不然。
7．具有n个结点的完全二叉树的深度为___│log2n│+1___。
8．在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是__ │log2i│ =│ log2j│ ____。 9．如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(0
10．二叉树通常有___顺序____存储结构和___链式__存储结构两类存储结构。
11．每个二叉链表还必须有一个指向__根__结点的指针，该指针具有标识二叉链表的作用。 12．对二叉链表的访问只能从___根__指针开始。
13．具有n个结点的二叉树中，一共有__2n__个指针域，其中只有__n-1_个用来指向结点的左右孩子，其余的__n+1__个指针域为NULL。
14．已知二叉树中叶子数为40，仅有一个孩子的结点数为20，则总结点数为__99（40+39+20）___。 15．二叉树有不同的链式存储结构，其中最常用的是_二叉链表___与__三叉链表__。 16．可通过在非完全二叉树的“残缺”位置上增设__空指针___将其转化为完全二叉树。 17．具有100个结点的完全二叉树的深度是__7___。
18．深度为90的满二叉树上，第10层有___512___个结点。
19．在__前序__遍历二叉树的序列中，任何结点的子树上的所有结点都是直接跟在该结点之后。
20．具有n个结点的完全二叉树，若按层次从上到下、从左到右对其编号(根结点为1号)，则编号最大的分支结点序号是__│n/2│___，编号最小的分支结点序号是__1_，编号最大的叶结点序号是_n_，编号最小的叶结点序号是__│n/2│+1____。
21．若一棵二叉树的叶子数为n，则该二叉树中左、右子树皆非空的结点个数为__n-1__。
18
22．任意一棵具有n个结点的二叉树，若它有m个叶子，则该二叉树上度数为1的结点为__n-2m+1__个。 23．设有30个值，用它们构造一棵哈夫曼树，则该哈夫曼树中共有___59__个结点。
24．现有按中序遍历二叉树的结果为ABC，有__5___种不同形态的二叉树可以得到这一遍历结果。 25．以数据集{4，5，6，7，10}为叶结点的权值所构造的哈夫曼树的带权路径长度为_63_.
26．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有__16_个叶结点。
27．设树T的度为4，其中度为1、2、3和4的结点个数分别是4、2、1和1，则T中叶结点的个数是__8_。 28．如果结点a有三个兄弟，而b是a的双亲，则b的度是__4__。
29．一棵树的形状如图6-5所示，它的根结点是__A_，叶结点是__E,J,K,L,O,P,Q,R,N,I__，结点H的度是__3__，这棵树的度是_4_，这棵树的深度是__5__，结点F的儿子结点是_J,K__，结点G的父结点是__C__。
30．设结点x有左孩子结点y、右孩子结点z，用三种基本遍历方法得到的遍历序列中x__不一定___是y的前驱，x__不一定__是z的后继，y__一定__是z的前驱(填“一定”，“不”、“不一定”)。
31．在树结构里，有且仅有一个结点没有前驱，称为根。非根结点有且仅有一个_前驱__，且存在一条从根到该结点的__惟一路径__。
32．含有2n个结点的二叉树高度至少是__n+1___，至多是__2n_(仅含根结点的二叉树高度为1)。
h
33．设高度为h的二叉树只有度为0和2的结点，则此类二叉树的结点数至少为_2h-1__，至多为__2-1__。 四、应用题
1．分别画出含3个结点的树与二叉树的所有不同形态。 答：略。
2．设在树中，结点x是结点y的双亲，用
(1)哪个是根结点？ (2)哪些是叶结点？ (3)哪个是g的双亲？ (4)哪些是g的祖先？ (5)哪些是e的子孙？ (6)哪些是f的兄弟？ (7)结点b和j的层次各是多少？ (8)树的深度是多少？ (9)树的度数是多少？ 答：略。
3．任意一个有n(n>0)个结点的二叉树，已知它有m个叶结点，试证明非叶结点有m-1个度为2，其余度为1。 答：设度为1的结点数n1, 设度为2的结点数n2,分支数B,则有: m+n1+n2=n, B+1=n, B=1*n1+2*n2,即: m+n1+n2=n, n1+2n2+1=n, 解之可得:n2=m-1
4．分别画出图6-6所示二叉树的二叉链表、三叉链表和顺序存储结构。
答：略.
5．分别写出图6-7所示二叉树的前序、中序和后序序列。
19
答：前序：ABCDEF、中序：CBEFDA和后序：CFEDBA
6．已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，试画出这棵二叉树，并写出其前序遍历序列。
答：前序遍历序列：ABCDEFGH
7．二叉树中的结点进行按层次顺序(每层自左到右)的访问操作称为二叉树的层次遍历，遍历所得到的结点序列称为二叉树的层次序列。现已知一棵二叉树的层次序列为ABCDEFGHIJ，中序序列为DBGEHJACIF，请画出该二又树。 答：略.
8．将图6-9所示的森林转换成二叉树。
答：略.
9．分别画出图6-10所示二叉树对应的森林，并写出森林的前序和后序遍历序列。
答：前序：ABDGCEFHIJK，后序：DGBAECIHJKF。
10．设某密码电文由8个字母组成，每个字母在电文中的出现频率分别是7，19，2，6，32，3，21，10，试为这8个字母设计相应的哈夫曼编码。 答：略.
11．将代数式y=3*(x+a)-a/x2描述成表达式树，并写出前缀式和后缀式。 答：前缀式：-*3+xa/a*xx，后缀式:3xa+*axx*/-。
13．试证明：任一棵高度为h>1的二叉树，其内部结点(除根、叶子之外的结点)的数目小于2h-1-1，而叶结点数目小于或等于2h-1。
答：高度为h的满二叉树包含的结点个数最多,最下层是叶子,除根外,其余是内部结点,不包含叶子的子树高度是h-1,该子树的最多结点数是2h-1-1. 除根外, 内部结点的数目应小于2h-1-1.而整个树所含的最多结点数是2h-1,所以,叶子数最多为2h-1-(2h-1-1)= 2h-1个.
14．编码{00，01，10，11}、{0，1，00，11，}、{0，10，110，111}哪一组不是前缀码? 答：编码{00，01，10，11}、{0，10，110，111}不是前缀码, {0，1，00，11}是前缀码.
15．一棵度为k的树有n1个度为1的结点，n2个度为2的结点，??，nk个度为k的结点，问该树中有多少个叶结点?
答：n=n0+n1+??+nk=1*n1+2*n2+??k*nk n0=1+n2+2n3+??+(k-1)nk
20
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库软件基础习题 答案 - 图文(4)在线全文阅读。
相关推荐：