3．已知有n个顶点的有向图邻接表，设计算法分别实现下列功能： （1）求出图G中每个顶点的出度、入度。 （2）计算图中度为0的顶点数。
六、完成：实验3――栈、队列、递归程序设计 实验4——图的存储方式和应用
根据实验要求（见教材P203）认真完成本实验，并提交实验报告。
作业3部分答案
一、单项选择题
1．B 2．B 3．D 4．C 5．B 6．A 7．A 8．C 9．A 10. D 11. A 12．C 13．C 14．B 15．B 16．C 17．B 18．C 19．A 20．B 21．D 22．B 23. B 24. B 25. C 26. A 27．A 28．C
三、综合题
1．写出如下图所示的二叉树的先序、中序和后序遍历序列。
答：二叉树的定义是递归的，所以，一棵二叉树可看作由根结点，左子树和右子树这三个基本部分组成，即依次遍历整个二叉树，又左子树或者右子树又可看作一棵二叉树并继续分为根结点、左子树和右子树三个部分…..，这样划分一直进行到树叶结点。
(1)先序为“根左右”，先序序列为：fdbacegihl (2)中序为“左根右”，中序序列为：abcdefghij (3)后序为“左右根”，后序序列为：acbedhjigf
2．已知某二叉树的先序遍历结果是：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）二叉树图形表示如下：
ABDGLHKEIMCFJ （2）该二叉树后序遍历的结果是：G、D、B、L、H、K、M、I、E、J、F、C和A。
3．答
⑴ 已知深度为k的二叉树最多有2k-1个结点(K≥1)， 29-1<892< 210-1，故树的高度为10
⑵ 对于完全二叉树来说，度为1的结点只能是0或1 因为n=n0+n1+n2和n0=n2+1
得：设n1=0，892=n0+0+n2=2n2+1 得n2不为整数出错 设n1=1，892=n0+1+n2=2n2+2 得n2 =445→ n0=n2+1=446 叶子结点数为446。 ⑶ 由⑵得单支结点数为1
⑷ 对于n个结点的完全二叉树，最后一个树叶结点，即序号为n的叶结点其双亲结点 即为最后一个非终端结点，
序号为892/2=446。
4．
（1）先序序列和中序序列相同的二叉树为空树或任一结点均无左孩子的非空二叉树 （2）中序和后序序列相同的二叉树为空树或任一结点均无右孩子的非空二叉树 （3）先序和后序序列相同的二叉树为空树或仅有一个结点 5．
（1）哈夫曼树如图B-4所示。
01120105C02F13G1B0015D08E11130I010A07H 图B-4
（2）其带权路径长度WPL值为270。
（3）每个字符的哈夫曼编码为：A:100, B:11, C:1010, D:000, E:0010, F:10110, G:10111, H:0011, I:01
6．答
（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 7．
① g1的图示和图g1的邻接表如下图所示。
v1v4v2 图G
② 图G的邻接矩阵如下图所示：
v12 141244523^ ^ ^3^5^v3v50 1 0 1 0 1 0 0 1 1 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0
v2v3v4v5图G的邻接矩阵 图G的邻接表
③ V1、V2、V3、V4、V5的度分别为：2，3，2，3，2 四、程序分析题
1. (1) return c1+1
(2) NodeLevel(BT->right,X) (3) (c2>=1) return c2+1
2．(1)for(j=0; j 五、算法设计题 1．写一个将一棵二叉树复制给另一棵二叉树的算法。 define NULL 0 typedef struct btnode { elemtype data; struct btnode *lchild, *rchild; }bitnode, *bitree; bitree *CopyTree( bitnode *p ) { /*复制一棵二叉树*/ bitnode *t; if ( p!=NULL )
相关推荐：
loading