《数据结构作业》PPT课件

《《数据结构作业》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构作业（6）填空题：1.假定一棵树的广义表表示为A（B（E），C（F（H，I，J），G），D），则该树的度为——，树的深度为——，终端结点的个数为——，单分支结点的个数为——，双分支结点的个数为——，三分支结点的个数为——，C结点的双亲结点为——，其孩子结点为——和——。2.对于一个具有n个结点的二叉树，当它为一棵——二叉树时具有最小高度，即为——，当它为一棵单支树具有——高度，即为——。3.由带权为9，2，5,7的4个叶子结点构成一棵赫夫曼树，则带权路径长度为—。4.对于一棵具有n个结点的

2、二叉树，当进行链接存储时，其二叉链表中的指针域的总数为——个，其中——个用于链接孩子结点，——个空闲着。5.一棵具有n个结点的理想平衡二叉树的深度等于——的向上取整或等于——的向下取整加1。6.由a.b.c三个结点构成的二叉树，共有——种不同的结构（画出结构图）。选择题：1.在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为——个。A.4B.5C.6D.72.假定在一棵二叉树中，双分支结点数为15单分支结点数为30个，则叶子结点数为—个。A.1

3、5B.16C.17D.453.用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组R[1…N]中，结点R[i]若有左子女，则左子女是结点——。A.R[2i+1]B.R[2i]C.R[i/2]D.R[2i-1]4.在一棵具有k层的满三叉树中，结点总数为——。A.(3k-1)/2B.3k-1C.(3k-1)/3D.3k5.如果F是由有序树T转换而来的二叉树，那么T中结点的前序就是F中结点的——。A.中序B.前序C.后序D.层次序6.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序——。A

4、.不发生改变B.发生改变C.不能确定D.以上都不对简答题：1.二叉树与树之间有何区别？一棵度为2的树与二叉树有何区别？2.已知一棵二叉树的先序遍历序列为ABCDEFG，中序遍历序列为CBDAEGF，试问能否唯一确定一棵二叉树，若能请画出该二叉树，并给出后序遍历序列。若给定先序遍历序列和后序遍历序列，能否唯一确定，说明理由。3.假定用于通信的电文由8个字母A、B、C、D、E、F、G、H组成，各字母在电文中出现得概率为5%、22%、4%、7%、9%、15%、30%，8%，试为这8个字母设计赫夫曼编码。

5、4.有7个带权结点，其权值分别为4，7，8，2，5，16，30，试以他们为叶子结点构造一棵赫夫曼树（要求按每个结点的左子树根结点的权值小于或等于右子树根结点的权值的次序构造），并计算其带权路径长度WPL。参考答案：填空：1.3，4，6，1，1，2，A，F，G2.完全，log2n+1,最大，n3.444.2n,n-1,n+15.log2(n+1),log2n6.5种，321321332121213选择题：1.B2.B3.B4.A5.B6.A简答题：1.（1）二叉树与树的区别：二叉树的一个结点至多有2

6、个子树，树则不然；二叉树的一个结点有左、右之分，树则没有此要求。（2）度为2的树有2个分支，没有左、右之分，一棵二叉树边也有两个分支，但有左、右之分，且左、右不能交换。2.由先序遍历序列和中序遍历序列可以唯一确定一棵二叉树。后序遍历序列：CDBGFEA由先序遍历和后序遍历序列不能唯一确定一棵二叉树。EBDCGFA3.这8个字母所对应的权值分别为（5，22，4，7，9，15，30，8），且n=8，构造的赫夫曼树如下：所以：A：0001B：01C：0000D：1000E：001F：101G：11H：1

7、00110030182294054871530601594.依据赫夫曼算法可得其对应的赫夫曼树为：26165784215261143072带权路径长度：WPL=（2+4）*5+（5+7+8）*4+16*2+30*1=172