2020年整合-树-练习-答案名师精品资料

1、B.无序数据元素D.元素之间无联系的数据单项选择题（每题2分，共26分）1）树最适合用来表示（ C ）A 有序数据元素C.元素之间具有分支层次关系的数据2）如图所示的4棵二叉树中，（ C ）不是完全二叉树。3）二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说法（B）A. 正确B.错误4）如图1-1所示二叉树的中序遍历序列是（B ）。A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefgh5）如果是T2是由有序树T1转换而来的二叉树，那么T1中结点的先序就是 T2中结点的（ A ）。A.先序B.中序C.后序D.层次序6）某二叉树的先序遍历

2、序列和后序遍历序列正好相反，则该二叉树一定是（D ）。A.空或只有一个结点B.完全二叉树C.二叉排序树D.高度等于其结点数7）树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。结论（A ）是正确的。A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同。B. 树的后根遍历序列与其对应的二叉树的后序遍历序列相同。C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同。D. 以上都不对8)如图所示的结点。T2是由森林T1转换而来的二叉树，那么森里T1有（ C ）个叶子9)A. 4深度为A. 1

3、6个结点。C的二叉树至多有B. 32C. 31D. 1010)）。B.只有右子树的部分结点C.只有左子树上的部分结点D. 只有左子树上的所有结点11)设n, m为一棵二叉树上的两个结点,A. n在m右方 B. n是m是祖先在中序遍历时,C. n在m左方n在m前的条件是（C ）。D. n是m子孙在一非空二叉树的中序遍历序列中，根结点的右边（A.只有右子树上的所有结点12)线索二叉树是一种（C ）结构。A.逻辑 B.逻辑和存储C.物理 D.线性（说明：线索二叉树是二叉树的一种存储（物理）结构）13)根据使用频率为5个字符设计的哈夫曼编码不可能是（A. 111,110,10,01,00B. 000,

4、001,010,011,1十四、C. 100,11,10,1,0填空题D. 001,000,01,11,101)有一棵树如图所示，回答下面的问题（7分）：这棵树的根节点（k1）;这棵树的叶子结点是（ 结点k3的度是（2）； 这棵树的度是（3）； 这棵树的深度是（4）;结点k3的孩子结点是（结点k3的双亲结点是（(1)k2,k5,k7,k4)；k5,k6)；2)（7）指出树和二叉树的三个主要差别k1k3k5k6k1）树的结点个数至少为1，k7而二叉树的结点个数可以为0）,树中结点的最大度数没有限制，而二叉树结点的最大度数为2）,（树的结点无左、右之分，而二叉树的结点有左右之分）。（3分）3）一棵

5、二叉树的结点数据采用顺序存储结构，存储于数组t中，如图所示，则该二叉树的链式存储表示形式为（）。（5分）1234567891011121314151617181920214）在一棵二叉树中，度为零的结点的个数为 no，度为2的结点的个数为 门2,则有n°=（n2+1） （ 2 分）5）现有按中序遍历二叉树的结果为abc,问有（5）种不同形态的二叉树可以得到这一遍历结果，这些二叉树分别是（）。（6分）6）由如图所示的二叉树，回答以下问题。（1）其中序遍历序列为（dgbaechif）； （ 2分）（2）其先序遍历序列为（Abdgcefhi）；（ 2分）（3）其后序遍历序列为（gdbeih

6、fca）；（ 2（4）该二叉树的中序线索二叉树为（）；（5分）（5分）NULL（5）该二叉树的后序线索二叉链表为（）;（6）该二叉树对应的森林是（）。（3分）0b10a0、X、s1d0 J1e1NULLFlFTngrrJ f卜11r *1h0十五、简答题1）假设二叉树采用顺序存储结构，如图所示eadcbjfghi （ 3 分）abcdjefhgi （ 3 分）bcjdahigfe （ 3 分）h2）知某 debac,给出它的先序遍历序列。（2）写出先序遍历，中序遍历和后序遍历的结果; 解：先序遍历序列：中序遍历序列：后序遍历序列：（3 分）（3）写出结点值c的双亲结点，其左、右孩子；解：c的双亲结点为d，左孩子为b，没有右孩子。（5分）解：该二叉树的先序遍历序列为cedba3）有一份电文中共使用5个字符：a、b、c、d、e，它们的出现频率依次为4、7、5、2、9，试画出对应的哈夫曼树 （请按左子树根结点的权小于等于右子树根结点的权次序构造），并求出每个字符的哈夫曼编码。（6分）a：011b：10c：00d：010e：11解:270