《树习题》由会员分享,可在线阅读,更多相关《树习题(19页珍藏版)》请在金锄头文库上搜索。
1、第四章 树习题,一、选择题,1、3个结点可构成_棵不同形态的二叉树。a 2 b 3 c 4 d 5,d,一、选择题,2、某二叉树的先序序列和后序序列正好相反,则该二叉树一定是_的二叉树。a 任一结点无左孩子b 任一结点无右孩子 c 高度等于其结点数d 空或者只有一个结点,c,一、选择题,3、深度为6(根的层次为1)的二叉树至多有_结点。a 32 b 31 c 64 d 63,d,一、选择题,4、在有n个结点的二叉链表中,值为非空的链域的个数是_。a n-1 b 2n-1 c n+1 d 2n+1,c,一、选择题,5、将一棵有100个结点的完全二叉树从根这一层开始,每一层上从左到右依次对结点进行
2、编号,根结点的编号为1,则编号为49的结点的左孩子编号为_。a 98 b 99 c 50 d 48,a,一、选择题,6、在有n个叶子结点的哈夫曼树中,其结点总数为_。a 不确定 b 2n c 2n1 d 2n1,d,二、判断题,1、哈夫曼树的带权路径长度等于其中所有分支结点中的权值之和。( ) 2、一棵树中的叶子结点数和其对应的二叉树中的叶子数一定相同。( ),二、判断题,3、先序序列中最后一个结点是叶子结点。( ) 4、完全二叉树度为1的结点可能超过1个。( ),三、填空题,1、3个结点可构成_棵不同形态的树。 2、树有三种常用的存储结构。即_ ,孩子链表法和孩子兄弟链表法。,双亲表示法,2
3、,三、填空题,3、有105个结点的完全二叉树有_ 个叶子结点。 4、具有100个结点的完全二叉树的深度为_。,7,53,三、填空题,5、在有n个叶子结点的哈夫曼树中,其总结点数是_。 6、以1,2,4,5,6,8,9作为叶子结点的权值所构造的哈夫曼树的带权路径长度是_。,2n-1,91,解,wpl=3+7+15+11+20+35=91,四、应用题,1、已知一棵二叉树的先序和中序序列如下,试画出该二叉树。 先序:ABCDEFG 中序:CDBEAFG,解,五、算法设计题,1、设二叉树采用二叉链表表示,设计算法求在先序序列中处于第K个位置的结点。 2、设二叉树采用二叉链表表示,设计算法求求此二叉树中
4、的结点的个数。,解,五、算法设计题,1、设二叉树采用二叉链表表示,设计算法求在先序序列中处于第K个位置的结点值。,解,bnode *Knode(bnode *t,int k) bnode *temp=null;int num=0;preorder(t);return(temp); ,void preorder(bnode *t) if(t!=null) num+;if(num=k) temp=t;return;preorder(t-lchild);preorder(t-rchlid); ,五、算法设计题,2、设二叉树采用二叉链表表示,设计算法求求此二叉树中的结点的个数。,解,int nodenum(bnode *t) int num=0;preorder(t);return(num); ,void preorder(bnode *t) if(t!=null) num+;preorder(t-lchild);preorder(t-rchlid); ,课后思考题,如何求采用二叉链表表示的二叉树的叶子结点的个数?,第4章习题结束,二、判断题,1、哈夫曼树的带权路径长度等于其中所有分支结点中的权值之和。( ) 2、一棵树中的叶子结点数和其对应的二叉树中的叶子数一定相同。( ),