树和图的习题.pptx
《树和图的习题.pptx》由会员分享,可在线阅读,更多相关《树和图的习题.pptx(25页珍藏版)》请在咨信网上搜索。
1、2005考研试题根据根据_可以唯一地确定一棵二叉树。可以唯一地确定一棵二叉树。A.A.先序遍历和后序遍历先序遍历和后序遍历 B.B.先序遍历和层次遍历先序遍历和层次遍历 C.C.中序遍历和层次遍历中序遍历和层次遍历 D.D.中序遍历和后序遍历中序遍历和后序遍历D.D.中序遍历和后序遍历中序遍历和后序遍历对于对于 m=4(4m=4(4阶阶)的的B-B-树,如果根的层次为第树,如果根的层次为第1 1层,则高度为层,则高度为2 2的的B-B-树最少要存储树最少要存储_个数据,最个数据,最多可以保存多可以保存_个数据。个数据。3152005考研试题考研试题 所有分支结点的度为所有分支结点的度为2 2的
2、二叉树称为正则二叉树,的二叉树称为正则二叉树,试用二叉链表做存储结构,编写一递归函数试用二叉链表做存储结构,编写一递归函数int int FormalTree(Bitree t)FormalTree(Bitree t),判断二叉树是否为正则二叉树。,判断二叉树是否为正则二叉树。int FormalTree(Bitree t)if(t=NULL)return 1;if(t-lchild=NULL)&(t-rchild=NULL)return 1;if(t-lchild=NULL)|(t-rchild=NULL)return 0;return(FormalTree(t-lchild)&(Forma
3、lTree(t-rchild);2005考研试题从空的平衡二叉排序树开始,按以下顺序插入关键从空的平衡二叉排序树开始,按以下顺序插入关键字,请给出最终的平衡二叉树。假设字,请给出最终的平衡二叉树。假设6 6个关键字的查找个关键字的查找概率相等,求该树的平均查找长度。概率相等,求该树的平均查找长度。27,31,49,38,41,6727,31,49,38,41,676731274927314938413127413849RR调整调整LR调整调整RR调整调整2005考研试题从空的平衡二叉排序树开始,按以下顺序插入关键从空的平衡二叉排序树开始,按以下顺序插入关键字,请给出最终的平衡二叉树。假设字,请
4、给出最终的平衡二叉树。假设6 6个关键字的查找个关键字的查找概率相等,求该树的平均查找长度。概率相等,求该树的平均查找长度。27,31,49,38,41,6727,31,49,38,41,67673127413849RR调整调整413149386727ASL=(3*3+2*2+1*1)/6 ASL=(3*3+2*2+1*1)/6=14/6=14/62006考研试题下面不能唯一确定一棵二叉树的两个遍历序列是下面不能唯一确定一棵二叉树的两个遍历序列是_。A)A)先序序列和中序序列先序序列和中序序列 B)B)先序序列和后序序列先序序列和后序序列C)C)后序序列和中序序列后序序列和中序序列 C)C)都
5、不能都不能在树的孩子兄弟表示法中,二叉链表的左指针指向在树的孩子兄弟表示法中,二叉链表的左指针指向_,右指针指向,右指针指向_。B)先序序列和后序序列先序序列和后序序列第一个孩子第一个孩子下一个兄弟下一个兄弟在二叉链表的每个结点中添加一个域在二叉链表的每个结点中添加一个域int depthint depth,表示,表示以该结点为根的子树的深度,即:以该结点为根的子树的深度,即:typedef struct BiTNode typedef struct BiTNode /结点结构结点结构 TElemType data;TElemType data;struct BiTNode*lchild,*r
6、child;/struct BiTNode*lchild,*rchild;/左右孩子指针左右孩子指针 int depth;/int depth;/以该结点为根的子树的深度以该结点为根的子树的深度 BiTNode,*BiTree;BiTNode,*BiTree;a.a.试编写一递归函数试编写一递归函数BiTreeDepth(BiTree T)BiTreeDepth(BiTree T),计算二叉树计算二叉树T T中每个结点的中每个结点的depthdepth值,函数的返回值为树值,函数的返回值为树T T的深度。的深度。b.b.在在a a的基础上(即已求出二叉树中每个结点的的基础上(即已求出二叉树中每
7、个结点的depthdepth值),编写一递归函数值),编写一递归函数BiTreeBalance(BiTree BiTreeBalance(BiTree T)T),判断二叉排序树,判断二叉排序树T T是否为平衡二叉树,如果是平衡是否为平衡二叉树,如果是平衡二叉树,则函数的返回值为真。二叉树,则函数的返回值为真。a.int BiTreeDepth(BiTree T)int ldepth,rdepth;if(!T )return-1;ldepth=BiTreeDepth(T-lchild);rdepth=BiTreeDepth(T-rchild);if(ldepth=rdepth)T-depth=l
8、depth+1;else T-depth=rdepth+1;return T-depth;?b.Status BiTreeBalance(BiTree T)int ldepth,rdepth;if(T=NULL)return TRUE;if(T-lchild)ldepth=T-lchild-depth;else ldepth=-1;if(T-rchild)rdepth=T-rchild-depth;else rdepth=-1;lrdepth=ldepth rdepth;if(lrdepth=0|lrdepth=1|lrdepth=-1)&(BiTreeBalance(T-lchild)&Bi
9、TreeBalance(T-rchild)return TRUE;return FALSE;?2007考研试题考研试题 在中序线索二叉树中,若结点的左指针在中序线索二叉树中,若结点的左指针lchildlchild不是线索,则该结点的前驱结点应是遍历其左子树时不是线索,则该结点的前驱结点应是遍历其左子树时_;_;若结点的右指针若结点的右指针rchildrchild不是不是线索,则该结点的后继结点应是遍历其右子树时线索,则该结点的后继结点应是遍历其右子树时_。最后访问的一个结点;最后访问的一个结点;最先访问的一个结点最先访问的一个结点2007考研试题如果两棵二叉树的形状相同,并且相应结点中的如果两
10、棵二叉树的形状相同,并且相应结点中的数据也相同,则这两棵二叉树相等。试用二叉链表做数据也相同,则这两棵二叉树相等。试用二叉链表做存贮结构,编写判断两棵二叉树是否相等的递归算法,存贮结构,编写判断两棵二叉树是否相等的递归算法,要求函数的原型为:要求函数的原型为:int EqualBTree(BiTree T1,BiTree T2)。int EqualBTree(BiTree T1,BiTree T2)if(!T1&!T2)return 1;if(!T1|!T2)return 0;return(T1-data=T2-data)&EqualBTree(T1-lchild,T2-lchild)&Equ
11、alBTree(T1-rchild,T2-rchild);?2008考研试题在在5 5阶阶B-B-树中,非终端根结点至少有树中,非终端根结点至少有_个孩子结个孩子结点,除根之外的所有非终端结点至少有点,除根之外的所有非终端结点至少有_孩子结点。孩子结点。23若一棵二叉树有若一棵二叉树有126个节点,在第个节点,在第7层(根结点在第层(根结点在第1层)至多有()个结点。层)至多有()个结点。A32 B64 C63 D不存在第不存在第7层层C)63 对于有对于有10001000个结点的完全二叉树从个结点的完全二叉树从0 0开始编号(从开始编号(从上到下逐层编号,每层从左到右编号),结点上到下逐层编
12、号,每层从左到右编号),结点174174的双的双亲结点编号为亲结点编号为_,结点,结点499499的右孩子结点的右孩子结点编号为编号为_。(174+1)/2-1=86没有没有(2*500+1-1=1000)试试编编写写先先根根遍遍历历树树的的递递归归算算法法PreOrderTree(T,visit),其其中中T为为要要遍遍历历的的树树,visit为为访访问问函函数数,树树的的存存储储结结构构采用孩子兄弟表示法,其类型定义如下:采用孩子兄弟表示法,其类型定义如下:typedef struct TreeNode ElementType data;struct TreeNode*FirstChild
13、;struct TreeNode*NextSibling;TreeNode,*Tree;void PreOrderTree(Tree T,void(*visit)(ElementType)if(!T)return;(*visit)(T-data);for(p=T-FirstChild;p;p=p-NextSibling )PreOrderTree(p,visit);?树和二叉树树和二叉树2009试题试题 给定二叉树如下图所示。设给定二叉树如下图所示。设N N代表二叉树的根,代表二叉树的根,L L代表代表根结点的左子树,根结点的左子树,R R代表根结点的右子树。若遍历后的代表根结点的右子树。若遍
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 习题
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【天****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【天****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。