数据结构习题书面作业练习题习题六树和二叉树6.1单项选择题1.下图所示的4棵二叉树，____不是完全二叉树。2.下列编码中属前缀码的是()（A）{1,01,000,001}（B）{1,01,011,010}（C）{0,10,110,11}（D）{0,1,00,113.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是____。A.acbedB.decabC.deabcD.cedba4．设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是。A．a在b的右方B．a在b的左方C．a是b的祖先D．a是b的子孙5.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为个。A．15B．16C．17D．476.按照二叉树的定义，具有3个结点的二叉树有____种。A.3B.4C.5D.67.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论____是正确的。树的先根遍历序列与其对应的二叉树的先序遍历序列相同树的后根遍历序列与其对应的二叉树的后序遍历序列相同树的先根遍历序列与其对应的二叉树的中序遍历序列相同以上都不对8.深度为5的二叉树至多有____个结点。A.16B.32C.31D.109.树最适合用来表示____。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据10.设有13个值，用它们组成一棵赫夫曼树，则该赫夫曼树共有()个结点。A．13B.12C.26D.256.2应用题1.有一棵树如图8.12所示，回答下面的问题：⑴这棵树的根结点是____；⑵这棵树的叶子结点是____；⑶结点k3的度是____；⑷这棵树的度是____；⑸这棵树的深度是____；⑹结点k3的子女是____；⑺结点k3的父结点是____；2.深度为k的完全二叉树至少有____个结点。至多有____个结点，若按自上而下，从左到右次序给结点编号（从0开始），则编号最小的叶子结点的编号是____。3.结点最少的树为____，结点最少的二叉树为____。4.由如图8.17所示的二叉树，该二叉树对应的森林是?。5.已知一棵树如图8.20所示，画出其转换为的一棵二叉树。该树的先根遍历序列、后根遍历序列？6.有一份电文中共使用8个字符：a、b、c、d、e、f、g、h，它们出现的频率是5,29,7,8,14,23,3,11（9分）（1）试画出对应的哈夫曼树；（2）每个字符的哈夫曼编码；（3）求带权外部路径长度(WPL)。6.3算法设计题:试编写算法，统计二叉树的叶子的个数。6.4证明题:证明：在非空二叉树的第i层上，至多有2i个结点（i≥0）。