《数据结构练习题》树与二叉树

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

1、第6章树和二叉树6.1写出图6.23中树的叶子结点、非终端结点、各结点的度和树深。图6.236.2分别画出含3个结点的无序树与二叉树的所有不同形态。6.3分别画出图6.24中所示二叉树的二叉链表、三叉链表和顺序存储结构示意图。图6.246.4分别写出图6.24中所示二叉树的先根遍历、中根遍历、后根遍历的结点访问序列。6.5试找出分别满足下列条件的所有二叉树：(1)先根序列和中根序列相同；(2)后根序列和中根序列相同；(3)先根序列和后根序列相同。6.6已知一棵二叉树的中根序列和后根序列分别为BDCEAFHG和DECB

2、HGFA，试画出这棵二叉树。6.7分别写出图6.23中所示树的先根遍历、后根遍历和层次遍历的结点访问序列。6.8　如果一棵树有n1个度为1的结点，n2个度为2的结点，……，nm个度为m的结点，则该树共有多少个叶子结点？6.9　已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，试求该树含有的叶子结点的数目。6．10已知一棵二叉树的中序序列与后序序列:BDCAEHGKFDCBHKGFEA试恢复该二叉树6．11高度为h的完全二叉树至少有多少个结点？至多有多少个结点？6．12在具有n个结点的k叉树（k≥2

3、）的k叉树链表表示中，有多少个空指针？6．13高度为h的严格二叉树至少有多少个结点？至多有多少个结点？6.14　编一算法判别给定的二叉树是否是满二叉树。6.15　将图6.25中所示的森林转换为二叉树。图6.256.16　分别画出图6.26中所示二叉树对应的森林。图6.266.17　给定权值(7,18,3,32,5,26,12,8)，构造相应的哈夫曼树。6.18　假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为7,19,2,6,32,3,21,10，试为这8个字母设计哈夫曼编码。6.19　试编写一个将百

4、分制转换成五分制的算法，要求其时间性能尽可能的高(即平均比较次数尽可能少)。假定学生成绩分布情况如下：分数　0~59　60~69　70~79　80~89　90~100比例　0.05　　0.15　0.40　0.30　0.10