第五章 树练习答案.doc

单项选择题（每题2分，共26分） 树最适合用来表示（ C ） A．有序数据元素 B.无序数据元素 C. 元素之间具有分支层次关系的数据 D.元素之间无联系的数据 如图所示的4棵二叉树中，（ C ）不是完全二叉树。 二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说法（ B ） A. 正确 B.错误 如图1-1所示二叉树的中序遍历序列是（ B ）。 A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefgh 如果是T2是由有序树T1转换而来的二叉树，那么T1中结点的先序就是T2中结点的（ A ）。 A. 先序 B. 中序 C. 后序 D. 层次序 某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是（ D ）。 A. 空或只有一个结点 B. 完全二叉树 C. 二叉排序树 D. 高度等于其结点数 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。结论（ A ）是正确的。 树的先根遍历序列与其对应的二叉树的先序遍历序列相同。 树的后根遍历序列与其对应的二叉树的后序遍历序列相同。 树的先根遍历序列与其对应的二叉树的中序遍历序列相同。 以上都不对 如图所示的T2是由森林T1转换而来的二叉树，那么森里T1有（ C ）个叶子结点。 A. 4 B. 5 C. 6 D. 7 深度为5的二叉树至多有（ C ）个结点。 A. 16 B. 32 C. 31 D. 10 在一非空二叉树的中序遍历序列中，根结点的右边（ A ）。 A. 只有右子树上的所有结点 B. 只有右子树的部分结点 C. 只有左子树上的部分结点 D. 只有左子树上的所有结点 设n，m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是（ C ）。 A. n在m右方 B. n是m是祖先 C. n在m左方 D. n是m子孙 线索二叉树是一种（ C ）结构。 A. 逻辑 B. 逻辑和存储 C. 物理 D. 线性 （说明：线索二叉树是二叉树的一种存储（物理）结构） 根据使用频率为5个字符设计的哈夫曼编码不可能是（ C ）。 A. 111,110,10,01,00 B. 000,001,010,011,1 C. 100,11,10,1,0 D. 001,000,01,11,10 填空题 有一棵树如图所示，回答下面的问题（7分）： 这棵树的根节点（k1）； 这棵树的叶子结点是（k2,k5,k7,k4）； 结点k3的度是（2）； 这棵树的度是（3）； 这棵树的深度是（4）； 结点k3的孩子结点是（k5,k6）； 结点k3的双亲结点是（k1） 指出树和二叉树的三个主要差别（树的结点个数至少为1，而二叉树的结点个数可以为0），树中结点的最大度数没有限制，而二叉树结点的最大度数为2），（树的结点无左、右之分，而二叉树的结点有左右之分）。（3分） 一棵二叉树的结点数据采用顺序存储结构，存储于数组t中，如图所示，则该二叉树的链式存储表示形式为（ ）。（5分） 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 e a f d g c j i h b 在一棵二叉树中，度为零的结点的个数为n0，度为2的结点的个数为n2，则有 n0=（n2+1）（2分） 现有按中序遍历二叉树的结果为abc，问有（5）种不同形态的二叉树可以得到这一遍历结果，这些二叉树分别是（ ）。（6分） 由如图所示的二叉树，回答以下问题。 其中序遍历序列为（dgbaechif）；（2分） 其先序遍历序列为（Abdgcefhi）；（2分） 其后序遍历序列为（gdbeihfca）；（2分） 该二叉树的中序线索二叉树为（）；（5分） 该二叉树的后序线索二叉链表为（）；（5分） 该二叉树对应的森林是（）。（3分） 简答题 假设二叉树采用顺序存储结构，如图所示 1 2