数据结构作业：第6章二叉树作业答案.docx资源-CSDN文库

132 浏览量 2022-12-13 21:27:25 上传评论收藏 80KB DOCX 举报

资源推荐

资源详情

资源评论

一、下面是有关二叉树的叙述，请判断正误（V ） 3.二叉树中每个结点的两棵子树是有序的。

题号

—-

三

四

五

六

总分

题分

10

15

11

20

20

24

100

得分

（X ） 4.二叉树中每个结点有两棵非空子树或有两棵空子树。

（X ） 6.-叉树中所有结点个数是2

k ,

-l,其中k是树的深度。（应2"）（X ） 7.二叉树中所有结点，如果不存在非空

左子树，则不存在非空右子树。

（X ） 8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2」1个结点。（应2"）二、填空

2.【计算机研2000] 一棵深度为6的满二叉树有2的=32个叶子。

3. 一棵具有2 5 7个结点的完全二叉树，它的深度为 9 （注：用Llog2（n） J+l=|_8.xx _|+1=94.【计算机研2001】用

5个权值｛3, 2,4,5, 1｝构造的哈夫曼（Huffman）树的带权路径长度是33 。

解：先构造哈夫曼树，得到各叶子的路径长度之后便可求出WPL= （4+5+3） X24- （1+2） X3=33

（注：两个合并值先后不同会导致编码不同，即哈夫曼编码不唯一）5.在一棵二叉树中，度为零的结点

的个数为N0,度为2的结点的个数为N2,则有N0二一N2+1。

四、单项选择题（每小题1分，共11分）（C ） 1.不含任何结点的空树o（A）是一棵树；（B ）是一棵二叉树；

（C）是一棵树也是一棵二叉树；（D ）既不是树也不是二叉树

答：以前的标答是B,因为那时树的定义是nNl（C ） 2.二叉树是非线性数据结构，所以

。

（A）它不能用顺序存储结构存储；（B ）它不能用链式存储结构存储；

（C）顺序存储结构和链式存储结构都能存储；（D）顺序存储结构和链式存储结

构都不能使用（C ） 3. K01年计算机研题』具有n（n>0）个结点的完全二叉树的

深度为°（A）Flog2（n）l （B） L log2（n）J （C） L log2（n） J+l （D

）「log2（n）+ll注1：「x]表示不小于x的最小整数；Lx」表示不大于x的最大整数，它们与■含义不

同！注2：选（A）是错误的。例如当n为2的整数昴时就会少算一层。似乎Llog2（n）+1」是对的？

4.除第一层外，满二叉树中每一层结点个数是上一层结点个数的（C ）

A）l/2 倍B）1 倍C）2 倍D）3 倍5.权值为｛1,2,6,8｝的四个结点构成的哈夫曼树的带权路径长度是（D ）。

第6章树和二叉树姓名班级

,

（注：原题为选择题：A. 32

B. 33

C. 34

D. 15)

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余2页未读，立即下载

内容反馈

Mmnnnbb123

粉丝: 679
资源: 8万+

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip