河南厂播电现大学现数中心 数据结构（本）形成性考核作业答案 数紧结构（本）作业3 (本都分作业覆差教材第67章的内容) 一、单项选开愿 (1)B 说明：任何一候二义树，若针子结点数为，度为2的精点数为e,则=·1。 k=u+1=15+1=16 该题跟单分支结点数无关。 (2)B (3)D (4)C 说明：根据先序和中序遍历得到二叉树为 a ⑥⊙ ④© 所以后序遍历为地cn: (5)B (6)A (7)A (8)C 说明：任何一保三义树，若叶子结点数为：度为2的结点数为：度为3的结点数为 则m三山+血+1d (9)A 说明，2-1=31 (10)D (11)A 说明！构造的哈夫曼树如图 8 7 DO 19 ①⑥ 每个叶子结点最长带权路径长度的为如 ①，9回，s圆，16@.2 最长叶子结点最长带权路径长度的为：18 第1风共6项 版权所有河南电大现教中心范额，邮箱5@m加m
河南广播电视大学现教中心 第1页 共6页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn 数据结构（本）形成性考核作业答案 数据结构（本）作业 3 （本部分作业覆盖教材第 6-7 章的内容） 一、单项选择题 （1） B 说明：任何一棵二叉树，若叶子结点数为 n0，度为 2 的结点数为 n2，则 n0 = n2 + 1。 n0 = n2 + 1 = 15+1 = 16 该题跟单分支结点数无关。 （2） B （3） D （4） C 说明：根据先序和中序遍历得到二叉树为： a b c d e 所以后序遍历为 debca。 （5） B （6） A （7） A （8） C 说明：任何一棵三叉树，若叶子结点数为 n0，度为 2 的结点数为 n2，度为 3 的结点数为 n3， 则 n0 = n3 + n2 + 1。 （9） A 说明：2 5 -1=31 （10） D （11） A 说明：构造的哈夫曼树如图： 29 9 17 3 6 8 12 每个叶子结点最长带权路径长度的为： 3 ：9 6 ：18 8 ：16 12 ：12 最长叶子结点最长带权路径长度的为：18
河南广播电视大学现黄中心 (12)C (13)C (14)B (15)B 说明：4“+1，那么n-1,+“2n-1… (18)C (17)C (18)C (19)A (20)B (21)D (22)B (23)B (24)B (25)C (26)A (27)A (28)C 二、就空题 (1) 丰空子树数或后雅结点数 (2) 树中所有结点的度的最大植 (3) 分支结点非锋端结点 (4) 叶子结点 终端结点 (5) 子树的根 后继结点 孩子结点 (6》 祖先 (7) 树中结点的最大层数 (8) g:m小I (9) 根结点左子树 右子树 (10)左子树根结点 右子树 (11)左子树右子树根结点 (12)权 (13)梦权路径长度之和 (14)最优二夏树量小的二叉树 (15)69 说明：构迹的哈夫曼树如图： 30 88 ⑥⑦⑧○ ⊙⑤ wPL=(4+5)3+(6+7+8)2=69 第2页共6页 版权所有河南电大规教中心范隔，配箱@a恤田
河南广播电视大学现教中心 第2页 共6页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn （12） C （13） C （14） B （15） B 说明：n0 = n2 + 1，那么 n2 = n0 - 1，n0 + n2 = 2n0 – 1。 （16） C （17） C （18） C （19） A （20） B （21） D （22） B （23） B （24） B （25） C （26） A （27） A （28） C 二、填空题 （1） 非空子树数或后继结点数 （2） 树中所有结点的度的最大值 （3） 分支结点 非终端结点 （4） 叶子结点 终端结点 （5） 子树的根 后继结点 孩子结点 （6） 祖先 （7） 树中结点的最大层数 （8） log 1 2 n + （9） 根结点 左子树 右子树 （10） 左子树 根结点 右子树 （11） 左子树 右子树 根结点 （12） 权 （13） 带权路径长度之和 （14） 最优二叉树 最小的二叉树 （15） 69 说明：构造的哈夫曼树如图： 30 9 17 4 5 8 13 6 7 WPL=（4+5）*3 +（6+7+8）*2 =69
河南广播电视大季现黄中心 (16)2m-1 (17)多对多 (18)所有项点 一次 (19)先序 (20)按层次 (21)2 (22)邻接矩阵 邻接表 (23)2(m-1) (24)m1 (25)栈 三、综合题 1、写出如下图所示的二叉树的先序，中序和后序追历序列。 容：二义树的定复是递自的，所以，一棵二义树可看作由根结点，左子树和右子树这三 个基本都分组成，即依次调历整个二叉树。又左子树或者右子树又可看作一棵二叉树并维续 分为根结点，左子树和右子树三个部分·这样划分一直法行到树叶结点。 (1)先序为“根左右”，先序序列为：fdbacegih (2)中序为“左根右”，中序序列为：edefgh呵 《3)后序为“左右根”，后序序列为：:bedhjigf 2、己知某二义树的先序历结果是：A,B,D,G,C,E,H,L.1,KM,F和J,它 的中序遍历结果是：G。D,B。A,L,H,E,K,I,M,C,F和，请画出这棵二叉 树，并写出该该二叉树后续考历的结果。 (1)二义树图形表示如下： @ ⑧© 可①① ©画①① ①百 (2)该二叉树后序遍历的结果是：G、D,B、L,H,K、M、I,E、、F、C和A 3、答 (1)已知深度为k的二又树最多有k.】个结点（多1）， 29-1<892<210-1,放树的高度为10 (2)对于完全二叉树来说，度为1的结点只能是0或1 因为0+m1+m2和n0=n2+1 得：段nl-0,892-n0+0+n2-2n2+1得n2不为整数出错 段nl-1,892-m0+1+n2-2n2+2 得n2-445+n0-n2+1=446 叶子结点数为446。 (3)由(2)得单支结点数为1 《4)对于个结点的完全二叉树，最后一个树叶结点，即序号为的叶结点其双亲结 点即为最后一个非终瑞结点，序号为892/2-446。 4.答： (1)先序序列和中序序列相同的二义树为空树成任一结点均无左孩子的幸空二叉树 第3项北6页 版权所有河南电大现教中心植额，都箱pm加cm
河南广播电视大学现教中心 第3页 共6页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn （16） 2m-1 （17） 多对多 （18） 所有顶点 一次 （19） 先序 （20） 按层次 （21） n 2 （22） 邻接矩阵 邻接表 （23） 2（n-1） （24） n-1 （25） 栈 三、综合题 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） 二叉树图形表示如下： I K M E H L J F C A B D G （2）该二叉树后序遍历的结果是：G、D、B、L、H、K、M、I、E、J、F、C 和 A。 3、 答: （1）已知深度为 k 的二叉树最多有 2k-1 个结点（K≥1）， 29-1<892< 210-1，故树的高度为 10 （2）对于完全二叉树来说，度为 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。 （3）由（2）得单支结点数为 1 （4）对于 n 个结点的完全二叉树，最后一个树叶结点，即序号为 n 的叶结点其双亲结 点即为最后一个非终端结点，序号为 892/2=446。 4、 答： （1）先序序列和中序序列相同的二叉树为空树或任一结点均无左孩子的非空二叉树
河南厂播电现大学现数中心 (2)中序和后序序列相同的二叉椅为空树或任一结点均无右孩子的非空二叉树 (3)先序和后序序列相同的二叉树为空树或仅有一个结点 5. 答： (1)哈夫曼树如图所示。 100 0 ①① (2)其带权路径长度wPL值为270。 (3)每个字符的哈夫曼编码为：A:0000,B:01,C:00010,D:100,E:1011, F:00110.G00111,h1010,1:11 B A D ⑦ C H E ② F G 6、答： (1)深度优先遍历：v1,v2.v3,8v5.v7.4.6 广度优先期历：vl,v2,v4,6,v3,v5,v7,v8 (2)G的拓扑序列为：v1,2v4.6.5v5.v3v5.v7.8 (3)最短路径为：v1.v2,v5,v7.v8 7、答： ①g1的图示和图g1的邻接表如下图所示， V4 v2 v5 第4风共6项 版权所有河南电大现教中心范制，邮箱5@m加m
河南广播电视大学现教中心 第4页 共6页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn （2）中序和后序序列相同的二叉树为空树或任一结点均无右孩子的非空二叉树 （3）先序和后序序列相同的二叉树为空树或仅有一个结点 5、 答： （1）哈夫曼树如图所示。 100 40 20 5 10 2 3 5 10 15 7 8 15 30 30 60 20 （2）其带权路径长度 WPL 值为 270。 （3）每个字符的哈夫曼编码为：A：0000，B：01，C：00010， D：100， E：1011， F：00110，G：00111，H：1010，I：11 2 3 5 1 0 1 0 1 10 0 7 8 0 1 15 0 1 30 0 1 20 0 1 0 1 F A B C D E G H I 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 的邻接表如下图所示。 v1 v3 v5 v4 v2
河南广播电视大学现黄中心 图G ②图G的忽接矩阵如下图所示： 21 0 010 v2 5 0 v3 11 100 3 01100 v5 23 图G的忽接矩降 图G的忽接表 图V1、V2、V3.V4、V5的度分别为：2,3,2,3,2 四、程序分析是 1、(1)returm c1+1 (2)NodeLevel (BT->right,X (3)(c2>=1)return c2+1 2、(1)for(=0:jm:j+) (2)dfstree (GA.j.n) 五、算祛设计题 1、写一个将一棵二叉树复制给另一绿二叉树的算法。 define NILL 0 typedef struct btmode elemtype data: struet btnode *lchild,*rchild: )bitnode,*bitree: bitree *CopyTree bitnode *p /体复制一棵二叉树/ bitnode 1: if p!-KULL t=(hitnode malloc (sixeof (bitnode)); t->data=p->data: t->lchild=CopyTree (p->lchild) t->rchild-CopyTree (p->rchild); return (t): else 第5项共6页 版权所有河南电大规教中心范隔，船箱5@p恤团
河南广播电视大学现教中心 第5页 共6页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn 图 G ② 图 G 的邻接矩阵如下图所示： 图 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; jdata=p->data; t->lchild=CopyTree（p->lchild）; t->rchild=CopyTree（p->rchild）; return（t）; } else 0 1 0 1 0 1 0 0 1 1 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 v1 v5 v4 v3 v2 2 4 ^ 1 4 4 5 ^ 5 ^ 1 2 3 ^ 2 3 ^
可南广播电视大学现黄中心 return (NULL) ）/CopyTree*/ 2、参考容案1 int BTreeLeafCount (struct BTreeNode*BT) if (BT--NULL)return 0: else if (BT->left=NULL BT->right=NULL)return 1: else return BTreeLeafCount (BT->left)+BTreeLeafCount (BT->right) 六、完成：实验3一一找、队列、递归程序设计 实验4一图的存储方式和应用 根据实验要求（见数材P)认真完成本实险，并提交实险报告， 第6项共6页 版权所有河南电大现教中心范额，都箱p恒国
河南广播电视大学现教中心 第6页 共6页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn return（NULL）; }/*CopyTree*/ 2、 参考答案： int BTreeLeafCount（struct BTreeNode* BT） { if（BT==NULL） return 0; else if（BT->left==NULL && BT->right==NULL） return 1; else return BTreeLeafCount（BT->left）+BTreeLeafCount（BT->right）; } 六、完成：实验 3――栈、队列、递归程序设计 实验 4——图的存储方式和应用 根据实验要求（见教材 P203）认真完成本实验，并提交实验报告