数据结构课后练习题(树).doc

《数据结构课后练习题(树).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构习题书面作业练习题习题六树和二叉树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

2、．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.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论____是正确的。A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同C.树的

3、先根遍历序列与其对应的二叉树的中序遍历序列相同D.以上都不对8.深度为5的二叉树至多有____个结点。A.16B.32C.31D.109.树最适合用来表示____。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据10.设有13个值，用它们组成一棵赫夫曼树，则该赫夫曼树共有()个结点。A．13B.12C.26D.256.2应用题1.有一棵树如图8.12所示，回答下面的问题：⑴这棵树的根结点是____；⑵这棵树的叶子结点是____；⑶结点k3的度是____；⑷这棵树的度是____；⑸这棵树的深度是____；⑹结

4、点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）试画出对

5、应的哈夫曼树；（2）每个字符的哈夫曼编码；（3）求带权外部路径长度(WPL)。6.3算法设计题:试编写算法，统计二叉树的叶子的个数。6.4证明题:证明：在非空二叉树的第i层上，至多有2i个结点（i≥0）。