树和图的习题1课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《树和图的习题1课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 习题 课件
- 资源描述:
-
1、2005考研试题考研试题 所有分支结点的度为所有分支结点的度为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
2、;return(FormalTree(t-lchild)&(FormalTree(t-rchild);2005考研试题从空的平衡二叉排序树开始,按以下顺序插入关键从空的平衡二叉排序树开始,按以下顺序插入关键字,请给出最终的平衡二叉树。假设字,请给出最终的平衡二叉树。假设6 6个关键字的查找个关键字的查找概率相等,求该树的平均查找长度。概率相等,求该树的平均查找长度。27,31,49,38,41,6727,31,49,38,41,676731274927314938413127413849RR调整调整LR调整调整RR调整调整2005考研试题从空的平衡二叉排序树开始,按以下顺序插入关键从空的平衡二
3、叉排序树开始,按以下顺序插入关键字,请给出最终的平衡二叉树。假设字,请给出最终的平衡二叉树。假设6 6个关键字的查找个关键字的查找概率相等,求该树的平均查找长度。概率相等,求该树的平均查找长度。27,31,49,38,41,6727,31,49,38,41,67673127413849RR调整调整413149386727ASL=(3ASL=(3*3+23+2*2+12+1*1)/6 1)/6=14/6=14/62006考研试题下面不能唯一确定一棵二叉树的两个遍历序列是下面不能唯一确定一棵二叉树的两个遍历序列是_。A)A)先序序列和中序序列先序序列和中序序列 B)B)先序序列和后序序列先序序列和
4、后序序列C)C)后序序列和中序序列后序序列和中序序列 C)C)都不能都不能在树的孩子兄弟表示法中,二叉链表的左指针指向在树的孩子兄弟表示法中,二叉链表的左指针指向_,右指针指向,右指针指向_。B)先序序列和后序序列先序序列和后序序列第一个孩子第一个孩子下一个兄弟下一个兄弟在二叉链表的每个结点中添加一个域在二叉链表的每个结点中添加一个域int depthint depth,表示,表示以该结点为根的子树的深度,即:以该结点为根的子树的深度,即:typedef struct BiTNode typedef struct BiTNode /结点结构结点结构 TElemType data;TElemTy
5、pe data;struct BiTNode struct BiTNode*lchild,lchild,*rchild;/rchild;/左右孩子指针左右孩子指针 int depth;/int depth;/以该结点为根的子树的深度以该结点为根的子树的深度 BiTNode,BiTNode,*BiTree;BiTree;a.a.试编写一递归函数试编写一递归函数BiTreeDepth(BiTree T)BiTreeDepth(BiTree T),计算二叉树计算二叉树T T中每个结点的中每个结点的depthdepth值,函数的返回值为值,函数的返回值为树树T T的深度。的深度。b.b.在在a a的基
6、础上(即已求出二叉树中每个结点的的基础上(即已求出二叉树中每个结点的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-rchi
7、ld);if(ldepth=rdepth)T-depth=ldepth+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=-
8、1)&(BiTreeBalance(T-lchild)&BiTreeBalance(T-rchild)return TRUE;return FALSE;?2007考研试题考研试题 在中序线索二叉树中,若结点的左指针在中序线索二叉树中,若结点的左指针lchildlchild不是线索,则该结点的前驱结点应是遍历其左子树时不是线索,则该结点的前驱结点应是遍历其左子树时_;_;若结点的右指针若结点的右指针rchildrchild不是不是线索,则该结点的后继结点应是遍历其右子树时线索,则该结点的后继结点应是遍历其右子树时_。最后访问的一个结点;最后访问的一个结点;最先访问的一个结点最先访问的一个结点20
9、07考研试题如果两棵二叉树的形状相同,并且相应结点中的如果两棵二叉树的形状相同,并且相应结点中的数据也相同,则这两棵二叉树相等。试用二叉链表做数据也相同,则这两棵二叉树相等。试用二叉链表做存贮结构,编写判断两棵二叉树是否相等的递归算法存贮结构,编写判断两棵二叉树是否相等的递归算法,要求函数的原型为:,要求函数的原型为: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)&Equal
10、BTree(T1-lchild,T2-lchild)&EqualBTree(T1-rchild,T2-rchild);?2008考研试题在在5 5阶阶B-B-树中,非终端根结点至少有树中,非终端根结点至少有_个孩子结个孩子结点,除根之外的所有非终端结点至少有点,除根之外的所有非终端结点至少有_孩子结点。孩子结点。23若一棵二叉树有若一棵二叉树有126个节点,在第个节点,在第7层(根结点在第层(根结点在第1层)至多有()个结点。层)至多有()个结点。A32 B64 C63 D不存在第不存在第7层层C)63 对于有对于有10001000个结点的完全二叉树从个结点的完全二叉树从0 0开始编号(从开始
11、编号(从上到下逐层编号,每层从左到右编号),结点上到下逐层编号,每层从左到右编号),结点174174的双的双亲结点编号为亲结点编号为_,结点,结点499499的右孩子结的右孩子结点编号为点编号为_。(174+1)/2-1=86没有没有(2*500+1-1=1000)试编写先根遍历树的递归算法试编写先根遍历树的递归算法PreOrderTree(T,visit),其中其中T为要遍历的树,为要遍历的树,visit为访问函数,树的存储结构为访问函数,树的存储结构采用孩子兄弟表示法,其类型定义如下:采用孩子兄弟表示法,其类型定义如下:typedef struct TreeNode ElementType
12、 data;struct TreeNode*FirstChild;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);?树和二叉树树和二叉树20092009试题试题 给定二叉树如下图所示。设给定二叉树如下图所示。设N N代表二叉树的根,代表二叉树的根,L L代表代表根结点的左子树,根结
13、点的左子树,R R代表根结点的右子树。若遍历后的代表根结点的右子树。若遍历后的结点序列为结点序列为3,1,7,5,6,2,43,1,7,5,6,2,4,则其遍历方式是,则其遍历方式是A ALRNLRNB BNRLNRLC CRLNRLND DRNLRNLDRNLC1113215476已知一棵完全二叉树的第已知一棵完全二叉树的第6 6层(设根为第层(设根为第1 1层)有层)有8 8个叶个叶结点,则该完全二叉树的结点个数最多是结点,则该完全二叉树的结点个数最多是A A3939B B5252C C111111D D119119树和二叉树树和二叉树20092009试题试题下列二叉排序树中,满足平衡二叉
展开阅读全文