精品
树的带权路径长度为树中所有叶子结点的回答正确答案是：带权路径长度之和 题目30 带权路径长度之和。 哈夫曼树又称为回答 最优二叉 ，它是n个带权叶子结点构成的所有二叉树中带权路径长度WPL回答 最小的二叉 。 答案：最优二叉树，最小的二叉树 题目31 若以4，5，6，7，8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是回答69。 正确答案是：69 题目32 具有m个叶子结点的哈夫曼树共有回答正确答案是：2m-1 题目33 2m-1结点。 图的遍历是从图的某一顶点出发，按照一定的搜索方法对图中回答 所有顶点 各做回答 一次 访问的过程。 答案：所有顶点; 一次 题目34 图的深度优先搜索遍历类似于树的回答先序遍历。 感谢下载载
精品
正确答案是：先序
题目35
图的广度优先搜索类似于树的回答正确答案是：按层次
题目36
按层次遍历。
图常用的两种存储结构是_____________和_____________。 邻接矩阵、邻接表
三、综合题（每小题8分，共40分）
题目37
写出如下图所示的二叉树的先序、中序和后序遍历序列。
答：二叉树的定义是递归的，所以，一棵二叉树可看作由根结点，左子树和右子树这三个基本部分组成，即依次遍历整个二叉树，又左子树或者右子树又可看作一棵二叉树并继续分为根结点、左子树和右子树三个部分……，这样划分一直进行到树叶结点。 （1）先序为“根左右”，先序序列为：fdbacegihl （2）中序为“左根右”，中序序列为：abcdefghij （3）后序为“左右根”，后序序列为：acbedhjigf
题目38
已知某二叉树的先序遍历结果是：A，B，D，G，C，E，H，L，I，K，M，F和J，它的中序遍历结果是：G，D，B，A，L，H，E，K，I，M，C，F和J，请画出这棵二叉树，并写出该二叉树后续遍历的结果。 （1）二叉树图形表示如下：
感谢下载载
精品
（2）该二叉树后序遍历的结果是：G、D、B、L、H、K、M、I、E、J、F、C和A。
题目39
假设通信用的报文由9个字母A、B、C、D、E、F、G、H和I组成，它们出现的频率分别是：10、20、5、15、8、2、3、7和30。请请用这9个字母出现的频率作为权值求： （1）设计一棵哈夫曼树； （2）计算其带权路径长度WPL； （3）写出每个字符的哈夫曼编码。 1）哈夫曼树如图B-4所示。
图B-4
（2）其带权路径长度WPL值为270。
（3）每个字符的哈夫曼编码为：A:100, B:11, C:1010, D:000, E:0010, F:10110, G:10111, H:0011, I:01
题目40
请根据以下带权有向图G
（1）给出从结点v1出发分别按深度优先搜索遍历G和广度优先搜索遍历G所得的结点序列；
（2）给出G的一个拓扑序列；
（3）给出从结点v1到结点v8的最短路径。 （1）
深度优先遍历：v1，v2，v3，v8，v5，v7，v4，v6 广度优先遍历：v1，v2，v4，v6，v3，v5，v7，v8
感谢下载载
精品
（2）G的拓扑序列为：v1，v2，v4，v6，v5，v5，v3，v5，v7，v8 （3）最短路径为：v1，v2，v5，v7，v8
题目41
已知无向图G描述如下： G=（V，E）
V={V1，V2，V3，V4，V5}
E={（V1，V2），（V1，V4），（V2，V4），（V3，V4），（V2，V5），（V3，V4），（V3，V5）}
（1）画出G的图示；
（2）然后给出G的邻接矩阵和邻接表； （3）写出每个顶点的度。
① g1的图示和图g1的邻接表如下图所示。
图G
② 图G的邻接矩阵如下图所示：
图G的邻接矩阵
感谢下载载
精品
图G的邻接表
③ V1、V2、V3、V4、V5的度分别为：2，3，2，3，2 四、程序填空题（每空2分，共8分）
题目42 部分正确
获得4.00分中的2.00分
题干
以下是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。 void Inorder (struct BTreeNode *BT) {
if(BT!=NULL){ 回答
;
回答
;
Inorder(BT->right);} } 答案：
（1）Inorder(BT->left) （2）printf(\
题目43
感谢下载载
数据结构(本)形考作业答案
