06树与二叉树.doc

作业要求：五：2、3六：2、3、6（1）、7、10七：1、2习题6一名词解释（1）结点（2）结点的度（3）树的度（4）二叉树（5）哈夫曼树二判断题（下列各题，正确的请在前面的括号内打；错误的打）（）（1）树结构中每个结点最多只有一个直接前趋。（）（2）完全二叉树一定是满二叉树。（）（3）由树转换成二叉树，其根结点的右子树一定为空。（）（4）在中序线索二叉树中，右线索若不为空，则一定指向其双亲。（ ）（5）在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点之后。（ ）（6）一棵二叉树中序遍历序列的最后一个结点，必定是该二叉树前序遍历的最后一个结点。（ ）（7）用一维数组来存储二叉树时，总是以前序遍历存储结点。（ ）（8）已知二叉树的前序遍历和后序遍历不能惟一确定这棵二叉树，这是因为不知道根结点是哪一个。（ ）（9）二叉树按某种顺序线索后，任一结点均有指向其前趋和后继的线索。（ ）（10）二叉树的前序遍历中，任意一个结点均处于其子树结点的前面。三填空题 1结点的度是 。2叶子结点是 结点。3树的度是 。4树中结点的最大层次称为树的 。5对于二叉树来说，第i层上至多有 个结点。6深度为h的二叉树至多有 个结点。7对于一棵具有n个结点的树，该树中所有结点的度数之和为： 。8在一棵二叉树中，度为2 的结点有5 个，度为1 的结点有6 个，则叶子结点数有 个。9由一棵二叉树的前序序列和 序列可惟一确定这棵二叉树。10有20个结点的完全二叉树，编码为10的结点的父结点的编号是 。11有20个结点的完全二叉树，编码为10的结点的左子树结点的编号是 。12一棵含有n个结点的完全二叉树，它的高度是 。13树的存储结构有： 。14哈夫曼树是带权路径长度 的二叉树。ABCHEFG15某二叉树的前序遍历序列为：DABEC，中序遍历序列为：DEBAC，则后序遍历序列为： 。给定右图所示的二叉树：16其前序遍历序列为： 。17其中序遍历序列为： 。18其后序遍历序列为： 。19结点最少的二叉树是 。20前序为A，B，C且后序为C，B，A的二叉树共有 种。四选择题1深度为h的二叉树至多有（ ）个结点。A2hB2h-1C2h-1D2h-1-12对于二叉树来说，第K层至多有（ ）个结点。A2KB2K-1C 2K-1D2K-1-13结点前序为ABC的不同二叉树有（ ）种形态。A3B4C5D64某二叉树的先序遍历序列为：IJKLMNO，中序遍历序列为： JLKINMO，则后序遍历序列为（ ）。A JLKMNOIBLKNJOMICLKJNOMIDLKNOJMI5某二叉树的后序遍历序列为：DABEC，中序遍历序列为: DEBAC，则先序遍历序列为（ ）。AACBEDBDECABCDEABCDCEDBA6具有35个结点的完全二叉树的深度为（ ）A5B6C7D87二叉树按某种顺序线索化后，任一结点均有指向其前趋和后继的线索，这种说法（ ）。A正确B错误C不确定D都有可能8根据树的定义，具有3个结点的树有（ ）种树型。A2B3C4D59下列4棵树，（ ）不是完全二叉树。A B C DABCDABCDEABCDEFABCDEFG10树最适合用来表示（ ）。A有序数据元素 B无序数据元素C元素之间无联系的数据 D元素之间有分支层次的关系11对于一棵满二叉树，m个树叶，n个结点，深度为h，则（ ）。An=h+mBh+m=2nCm=h-1Dn=2h-112一棵n个结点的二叉树，其空指针域的个数为（ ）。AnBn+1Cn-1D不确定13任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序（ ）。A不发生改变B发生改变C不能确定D以上都不对14A，B为一棵二叉树上的两个叶子结点，在中序遍历时，A在B前的条件是（ ）。AA在B的右方BA是B的祖先CA在B的左方DA是B的子孙15线索二叉树是一种（ ）结构。A物理B逻辑C逻辑和存储D线性五简答题1什么是一般树？什么是二叉树？*2一棵度为2的树与一棵二叉树有何区别？*3已知一棵树边的集合如下，请画出此树，并回答问题。L，M），（1）哪个是根结点？（2）哪些是叶子结点？（3）哪个是G的双亲？（4）哪些是G的祖先？（5）哪些是G的孩子？（6）哪些是E的子孙？（7）哪些是E的兄弟？哪些是F的兄弟？（8）结点B和N的层次各是多少？（9）树的深度是多少？（10）以结点C为根的子树的深度是多少？（11）树的度数是多少？六应用题1二叉树按中序遍历的结果为：ABC，试问有几种不同形态的二叉树可以得到这一遍历结果？并画出这些二叉树。*2分别画出具有3个结点的树和三个结点的二叉树的所有不同形态。*3已知一棵二叉树的后序遍历和中序遍历的序列分别为：A，C，D，B，G，I，H，F，E和A，B，C，D，E，F，G，H，I。请画出该二叉树，并写出它的先序遍历的序列。4已知一棵二叉树的先序遍历和中序遍历的序列分别为：A，B，D，G，H，C，E，F，I和G，D，H，B，A，E，C，I，F。请画出此二叉树，并写出它的后序遍历的序列。5已知一棵二叉树的层次序列为：A B C D E F G H I J，中序序列为D B G E H J A C I F，请画出该二叉树。6把下列一般树转换为二叉树12435678*（1） （2） ABFEGHIJCD*7把下列森林转换为二叉树FGKIJHACBDEA8把下列二叉树还原为森林EBGFCHDI9画出下列表达式的标识符树，并求它们的后缀表达式。（1）-A+B-C+D（2）（A+B/C-D）*（E*（F+G）*10给定一个权集W=4，5，7，8，6，12，18，请画出相应的哈夫曼树，并计算其带权路径长度WPL。11给定一个权集W=3，15，17，14，6，16，9，2，请画出相应的哈夫曼树，并计算其带权路径长度WPL。七算法设计题以二叉链表为存储结构，设二叉树BT结构为：typedef struct BTchar data;BT *lchild;BT *rchild;