数据结构-C语言版-第二版(严蔚敏)-第5章--树和二叉树-答案.doc
《数据结构-C语言版-第二版(严蔚敏)-第5章--树和二叉树-答案.doc》由会员分享,可在线阅读,更多相关《数据结构-C语言版-第二版(严蔚敏)-第5章--树和二叉树-答案.doc(9页珍藏版)》请在咨信网上搜索。
第5章 树和二叉树 1.选择题 (1)把一棵树转换为二叉树后,这棵二叉树的形态是( )。 A.唯一的 B.有多种 C.有多种,但根结点都没有左孩子 D.有多种,但根结点都没有右孩子 答案:A 解释:因为二叉树有左孩子、右孩子之分,故一棵树转换为二叉树后,这棵二叉树的形态是唯一的。 (2)由3个结点可以构造出多少种不同的二叉树?( ) A.2 B.3 C.4 D.5 答案:D 解释:五种情况如下: (3)一棵完全二叉树上有1001个结点,其中叶子结点的个数是( )。 A.250 B. 500 C.254 D.501 答案:D 解释:设度为0结点(叶子结点)个数为A,度为1的结点个数为B,度为2的结点个数为C,有A=C+1,A+B+C=1001,可得2C+B=1000,由完全二叉树的性质可得B=0或1,又因为C为整数,所以B=0,C=500,A=501,即有501个叶子结点。 (4)一个具有1025个结点的二叉树的高h为( )。 A.11 B.10 C.11至1025之间 D.10至1024之间 答案:C 解释:若每层仅有一个结点,则树高h为1025;且其最小树高为 ëlog21025û + 1=11,即h在11至1025之间。 (5)深度为h的满m叉树的第k层有( )个结点。(1=<k=<h) A.mk-1 B.mk-1 C.mh-1 D.mh-1 答案:A 解释:深度为h的满m叉树共有mh-1个结点,第k层有mk-1个结点。 (6)利用二叉链表存储树,则根结点的右指针是( )。 A.指向最左孩子 B.指向最右孩子 C.空 D.非空 答案:C 解释:利用二叉链表存储树时,右指针指向兄弟结点,因为根节点没有兄弟结点,故根节点的右指针指向空。 (7)对二叉树的结点从1开始进行连续编号,要求每个结点的编号大于其左、右孩子的编号,同一结点的左右孩子中,其左孩子的编号小于其右孩子的编号,可采用( )遍历实现编号。 A.先序 B. 中序 C. 后序 D. 从根开始按层次遍历 答案:C 解释:根据题意可知按照先左孩子、再右孩子、最后双亲结点的顺序遍历二叉树,即后序遍历二叉树。 (8)若二叉树采用二叉链表存储结构,要交换其所有分支结点左、右子树的位置,利用( )遍历方法最合适。 A.前序 B.中序 C.后序 D.按层次 答案:C 解释:后续遍历和层次遍历均可实现左右子树的交换,不过层次遍历的实现消耗比后续大,后序遍历方法最合适。 (9)在下列存储形式中,( )不是树的存储形式? A.双亲表示法 B.孩子链表表示法 C.孩子兄弟表示法 D.顺序存储表示法 答案:D 解释:树的存储结构有三种:双亲表示法、孩子表示法、孩子兄弟表示法,其中孩子兄弟表示法是常用的表示法,任意一棵树都能通过孩子兄弟表示法转换为二叉树进行存储。 (10)一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反,则该二叉树一定满足( )。 A.所有的结点均无左孩子 B.所有的结点均无右孩子 C.只有一个叶子结点 D.是任意一棵二叉树 答案:C 解释:因为先序遍历结果是“中左右”,后序遍历结果是“左右中”,当没有左子树时,就是“中右”和“右中”;当没有右子树时,就是“中左”和“左中”。则所有的结点均无左孩子或所有的结点均无右孩子均可,所以A、B不能选,又所有的结点均无左孩子与所有的结点均无右孩子时,均只有一个叶子结点,故选C。 (11)设哈夫曼树中有199个结点,则该哈夫曼树中有( )个叶子结点。 A.99 B.100 C.101 D.102 答案:B 解释:在哈夫曼树中没有度为1的结点,只有度为0(叶子结点)和度为2的结点。设叶子结点的个数为n0,度为2的结点的个数为n2,由二叉树的性质n0=n2+1,则总结点数n= n0+n2=2*n0-1,得到n0=100。 (12)若X是二叉中序线索树中一个有左孩子的结点,且X不为根,则X的前驱为( )。 A.X的双亲 B.X的右子树中最左的结点 C.X的左子树中最右结点 D.X的左子树中最右叶结点 答案:C (13)引入二叉线索树的目的是( )。 A.加快查找结点的前驱或后继的速度 B.为了能在二叉树中方便的进行插入与删除 C.为了能方便的找到双亲 D.使二叉树的遍历结果唯一 答案:A (14)设F是一个森林,B是由F变换得的二叉树。若F中有n个非终端结点,则B中右指针域为空的结点有( )个。 A.n−1 B.n C.n + 1 D.n + 2 答案:C (15)n(n≥2)个权值均不相同的字符构成哈夫曼树,关于该树的叙述中,错误的是( )。 A.该树一定是一棵完全二叉树 B.树中一定没有度为1的结点 C.树中两个权值最小的结点一定是兄弟结点 D.树中任一非叶结点的权值一定不小于下一层任一结点的权值 答案:A 解释:哈夫曼树的构造过程是每次都选取权值最小的树作为左右子树构造一棵新的二叉树,所以树中一定没有度为1的结点、两个权值最小的结点一定是兄弟结点、任一非叶结点的权值一定不小于下一层任一结点的权值。 2.应用题 (1)试找出满足下列条件的二叉树 ① 先序序列与后序序列相同 ②中序序列与后序序列相同 ③ 先序序列与中序序列相同 ④中序序列与层次遍历序列相同 答案:先序遍历二叉树的顺序是“根—左子树—右子树”,中序遍历“左子树—根—右子树”,后序遍历顺序是:“左子树—右子树―根",根据以上原则有 ① 或为空树,或为只有根结点的二叉树 ② 或为空树,或为任一结点至多只有左子树的二叉树. ③ 或为空树,或为任一结点至多只有右子树的二叉树. ④ 或为空树,或为任一结点至多只有右子树的二叉树 (2)设一棵二叉树的先序序列: A B D F C E G H ,中序序列: B F D A G E H C ①画出这棵二叉树。 ②画出这棵二叉树的后序线索树。 ③将这棵二叉树转换成对应的树(或森林)。 答案: A B F D ③ C E H G ① ② (3) 假设用于通信的电文仅由8个字母组成,字母在电文中出现的频率分别为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。 ① 试为这8个字母设计赫夫曼编码。 ② 试设计另一种由二进制表示的等长编码方案。 ③ 对于上述实例,比较两种方案的优缺点。 答案:方案1;哈夫曼编码 先将概率放大100倍,以方便构造哈夫曼树。 w={7,19,2,6,32,3,21,10},按哈夫曼规则:【[(2,3),6], (7,10)】, ……19, 21, 32 (100) (40) (60) 19 21 32 (28) (17) (11) 7 10 6 (5) 2 3 0 1 0 1 0 1 19 21 32 0 1 0 1 0 1 7 10 6 0 1 2 3 方案比较: 字母编号 对应编码 出现频率 1 000 0.07 2 001 0.19 3 010 0.02 4 011 0.06 5 100 0.32 6 101 0.03 7 110 0.21 8 111 0.10 字母编号 对应编码 出现频率 1 1100 0.07 2 00 0.19 3 11110 0.02 4 1110 0.06 5 10 0.32 6 11111 0.03 7 01 0.21 8 1101 0.10 方案1的WPL=2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61 方案2的WPL=3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3 结论:哈夫曼编码优于等长二进制编码 (4)已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8,11,试填写出其对应哈夫曼树HT的存储结构的初态和终态。 答案: 初态: weight parent lchild rchild 1 3 0 0 0 2 12 0 0 0 3 7 0 0 0 4 4 0 0 0 5 2 0 0 0 6 8 0 0 0 7 11 0 0 0 8 0 0 0 9 0 0 0 10 0 0 0 11 0 0 0 12 0 0 0 13 0 0 0 终态: weight parent lchild rchild 1 3 8 0 0 2 12 12 0 0 3 7 10 0 0 4 4 9 0 0 5 2 8 0 0 6 8 10 0 0 7 11 11 0 0 8 5 9 5 1 9 9 11 4 8 10 15 12 3 6 11 20 13 9 7 12 27 13 2 10 13 47 0 11 12 3.算法设计题 以二叉链表作为二叉树的存储结构,编写以下算法: (1)统计二叉树的叶结点个数。 [题目分析]如果二叉树为空,返回0,如果二叉树不为空且左右子树为空,返回1,如果二叉树不为空,且左右子树不同时为空,返回左子树中叶子节点个数加上右子树中叶子节点个数。 [算法描述] int LeafNodeCount(BiTree T) { if(T==NULL) return 0; //如果是空树,则叶子结点个数为0 else if(T->lchild==NULL&&T->rchild==NULL) return 1; //判断结点是否是叶子结点(左孩子右孩子都为空),若是则返回1 else return LeafNodeCount(T->lchild)+LeafNodeCount(T->rchild); } (2)判别两棵树是否相等。 [题目分析]先判断当前节点是否相等(需要处理为空、是否都为空、是否相等),如果当前节点不相等,直接返回两棵树不相等;如果当前节点相等,那么就递归的判断他们的左右孩子是否相等。 [算法描述] int pareTree(TreeNode* tree1, TreeNode* tree2) //用分治的方法做,比较当前根,然后比较左子树和右子树 {bool tree1IsNull = (tree1==NULL); bool tree2IsNull = (tree2==NULL); if(tree1IsNull != tree2IsNull) { return 1; } if(tree1IsNull && tree2IsNull) {//如果两个都是NULL,则相等 return 0; }//如果根节点不相等,直接返回不相等,否则的话,看看他们孩子相等不相等 if(tree1->c != tree2->c) { return 1; } return (pareTree(tree1->left,tree2->left)&pareTree(tree1->right,tree2->right)) (pareTree(tree1->left,tree2->right)&pareTree(tree1->right,tree2->left)); }//算法结束 (3)交换二叉树每个结点的左孩子和右孩子。 [题目分析]如果某结点左右子树为空,返回,否则交换该结点左右孩子,然后递归交换左右子树。 [算法描述] void ChangeLR(BiTree &T) { BiTree temp; if(T->lchild==NULL&&T->rchild==NULL) return; else { temp = T->lchild; T->lchild = T->rchild; T->rchild = temp; }//交换左右孩子 ChangeLR(T->lchild); //递归交换左子树 ChangeLR(T->rchild); //递归交换右子树 } (4)设计二叉树的双序遍历算法(双序遍历是指对于二叉树的每一个结点来说,先访问这个结点,再按双序遍历它的左子树,然后再一次访问这个结点,接下来按双序遍历它的右子树)。 [题目分析]若树为空,返回;若某结点为叶子结点,则仅输出该结点;否则先输出该结点,递归遍历其左子树,再输出该结点,递归遍历其右子树。 [算法描述] void DoubleTraverse(BiTree T) { if(T == NULL) return; else if(T->lchild==NULL&&T->rchild==NULL) cout<<T->data; //叶子结点输出 else { cout<<T->data; DoubleTraverse(T->lchild); //递归遍历左子树 cout<<T->data; DoubleTraverse(T->rchild); //递归遍历右子树 } } (5)计算二叉树最大的宽度(二叉树的最大宽度是指二叉树所有层中结点个数的最大值)。 [题目分析] 求二叉树高度的算法见上题。求最大宽度可采用层次遍历的方法,记下各层结点数,每层遍历完毕,若结点数大于原先最大宽度,则修改最大宽度。 [算法描述] int Width(BiTree bt)//求二叉树bt的最大宽度 {if (bt==null) return (0); //空二叉树宽度为0 else {BiTree Q[];//Q是队列,元素为二叉树结点指针,容量足够大 front=1;rear=1;last=1; //front队头指针,rear队尾指针,last同层最右结点在队列中的位置 temp=0; maxw=0; //temp记局部宽度, maxw记最大宽度 Q[rear]=bt; //根结点入队列 while(front<=last) {p=Q[front++]; temp++; //同层元素数加1 if (p->lchild!=null) Q[++rear]=p->lchild; //左子女入队 if (p->rchild!=null) Q[++rear]=p->rchild; //右子女入队 if (front>last) //一层结束, {last=rear; if(temp>maxw) maxw=temp; //last指向下层最右元素, 更新当前最大宽度 temp=0; }//if }//while return (maxw); }//结束width (6)用按层次顺序遍历二叉树的方法,统计树中具有度为1的结点数目。 [题目分析] 若某个结点左子树空右子树非空或者右子树空左子树非空,则该结点为度为1的结点 [算法描述] int Level(BiTree bt) //层次遍历二叉树,并统计度为1的结点的个数 {int num=0; //num统计度为1的结点的个数 if(bt){QueueInit(Q); QueueIn(Q,bt);//Q是以二叉树结点指针为元素的队列 while(!QueueEmpty(Q)) {p=QueueOut(Q); cout<<p->data; //出队,访问结点 if(p->lchild && !p->rchild ||!p->lchild && p->rchild)num++; //度为1的结点 if(p->lchild) QueueIn(Q,p->lchild); //非空左子女入队 if(p->rchild) QueueIn(Q,p->rchild); //非空右子女入队 } // while(!QueueEmpty(Q)) }//if(bt) return(num); }//返回度为1的结点的个数 (7)求任意二叉树中第一条最长的路径长度,并输出此路径上各结点的值。 [题目分析]因为后序遍历栈中保留当前结点的祖先的信息,用一变量保存栈的最高栈顶指针,每当退栈时,栈顶指针高于保存最高栈顶指针的值时,则将该栈倒入辅助栈中,辅助栈始终保存最长路径长度上的结点,直至后序遍历完毕,则辅助栈中内容即为所求。 [算法描述] void LongestPath(BiTree bt)//求二叉树中的第一条最长路径长度 {BiTree p=bt,l[],s[]; //l, s是栈,元素是二叉树结点指针,l中保留当前最长路径中的结点 int i,top=0,tag[],longest=0; while(p || top>0) {while(p) {s[++top]=p;tag[top]=0; p=p->Lc;} //沿左分枝向下 if(tag[top]==1) //当前结点的右分枝已遍历 {if(!s[top]->Lc && !s[top]->Rc) //只有到叶子结点时,才查看路径长度 if(top>longest) {for(i=1;i<=top;i++) l[i]=s[i]; longest=top; top--;} //保留当前最长路径到l栈,记住最高栈顶指针,退栈 } else if(top>0) {tag[top]=1; p=s[top].Rc;} //沿右子分枝向下 }//while(p!=null||top>0) }//结束LongestPath (8)输出二叉树中从每个叶子结点到根结点的路径。 [题目分析]采用先序遍历的递归方法,当找到叶子结点*b时,由于*b叶子结点尚未添加到path中,因此在输出路径时还需输出b->data值。 [算法描述] void AllPath(BTNode *b,ElemType path[],int pathlen) {int i; if (b!=NULL) {if (b->lchild==NULL && b->rchild==NULL) //*b为叶子结点 {cout << " " << b->data << "到根结点路径:" << b->data; for (i=pathlen-1;i>=0;i--) cout << endl; } else {path[pathlen]=b->data; //将当前结点放入路径中 pathlen++; //路径长度增1 AllPath(b->lchild,path,pathlen); //递归扫描左子树 AllPath(b->rchild,path,pathlen); //递归扫描右子树 pathlen--; //恢复环境 } }// if (b!=NULL) }//算法结束- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 语言版 第二 严蔚敏 二叉 答案
咨信网温馨提示:
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,个别因单元格分列造成显示页码不一将协商解决,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【w****g】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【w****g】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,个别因单元格分列造成显示页码不一将协商解决,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【w****g】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【w****g】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。
关于本文