数据结构复习(6树习题)ppt课件.ppt

上传人:飞****2 文档编号:31374971 上传时间:2022-08-07 格式:PPT 页数:34 大小:237.50KB
返回 下载 相关 举报
数据结构复习(6树习题)ppt课件.ppt_第1页
第1页 / 共34页
数据结构复习(6树习题)ppt课件.ppt_第2页
第2页 / 共34页
点击查看更多>>
资源描述

《数据结构复习(6树习题)ppt课件.ppt》由会员分享,可在线阅读,更多相关《数据结构复习(6树习题)ppt课件.ppt(34页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、2022-8-71数据结构复习(习题)22022-8-7第六章 树和二叉树(选择题)1已知一算术表达式的中缀形式为 A+B*C-D/E,后缀形式为ABC*+DE/-,其前缀形式为( )A-A+B*C/DE B. -A+B*CD/E C-+*ABC/DE D. -+A*BC/DE2算术表达式a+b*(c+d/e)转为后缀表达式后为( )Aab+cde/* Babcde/+*+ Cabcde/*+ Dabcde*/+32022-8-73. 设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1 则T中的叶子数为( )A5 B6 C7 D84. 在下述结论中,正确的是( )只有一个结点

2、的二叉树的度为0; 二叉树的度为2; 二叉树的左右子树可任意交换; 深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A B C D因为每个结点都有一条枝指向它,分支数为1*4+2*2*3*1+4*1所有结点数为分支数+1,所以1*4+2*2*3*1+4*1=4+2+1+1+x x=842022-8-76若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是( )A9 B11 C15 D不确定7. 设森林F对应的二叉树为B,它有m个结点,B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是( )Am-n Bm-n-1 Cn+1 D条件不足,无法确定8

3、设森林F中有三棵树,第一,第二,第三棵树的结点个数分别为M1,M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是( )。AM1 BM1+M2 CM3 DM2+M3 森林转换得到的二叉树中,其左子树加根为森林的第一棵树52022-8-79一棵完全二叉树上有1001个结点,其中叶子结点的个数是( )A 250 B 500 C254 D50110. 设给定权值总数有n 个,其哈夫曼树的结点总数为( ) A不确定 B2n C2n+1 D2n-1完全二叉树中度为1的结点最多只有1个,由二叉树的度和结点的关系n=n0+n1+n2 n=n1+2n2+1 得n=2n0+n1-1哈夫曼树中没有度为1的

4、节点,叶子节点个数为n62022-8-711. 有关二叉树下列说法正确的是( )A二叉树的度为2 B一棵二叉树的度可以小于2 C二叉树中至少有一个结点的度为2 D二叉树中任何一个结点的度都为212. 一个具有1025个结点的二叉树的高h为( )A11 B10 C11至1025之间 D10至1024之间13一棵二叉树高度为h,所有结点的度或为0,或为2,则这棵二叉树最少有( )结点A2h B2h-1 C2h+1 Dh+1 完全二叉树和单枝树之间72022-8-714对于有n 个结点的二叉树, 其高度为( )Anlog2n Blog2n Clog2n|+1 D不确定15. 一棵具有 n个结点的完全

5、二叉树的树高度(深度)是( )Alogn+1 Blogn+1 Clogn Dlogn-1 16深度为h的满m叉树的第k层有( )个结点。(1=k=lchild=null & p-rchlid=null 12202022-8-74在完全二叉树中,编号为i和j的两个结点处于同一层的条件是5在顺序存储的二叉树中,编号为i和j的两个结点处在同一层的条件是 。6一棵有n个结点的满二叉树有_ _个度为1的结点、有_ _个分支 (非 终端)结点和_ _个叶子,该满二叉树的深度为_ _ 。 log2i=log2j log2s=log2t 用顺序存储二叉树时,要按完全二叉树的形式存储,非完全二叉树存储时,要加“

6、虚结点”。设编号为i和j的结点在顺序存储中的下标为s 和t ,则结点i和j在同一层上的条件是log2s=log2t。0(n-1)/2(n+1)/2log2n+1212022-8-77设有N个结点的完全二叉树顺序存放在向量A1:N中,其下标值最大的分支结点为_。8高度为K的完全二叉树至少有_ _个叶子结点。 9已知二叉树有50个叶子结点,则该二叉树的总结点数至少是_。10一个有2001个结点的完全二叉树的高度为_。11如果结点A有 3个兄弟,而且B是A的双亲,则B的度是_。 N/22k-299114222022-8-712设F是由T1,T2,T3三棵树组成的森林,与F对应的二叉树为B,已知T1,

7、T2,T3的结点数分别为n1,n2和n3则二叉树B的左子树中有_ _个结点,右子树中有_ _个结点13对于一个具有n个结点的二元树,当它为一棵_ _二元树时具有最小高度,当它为一棵_ _ 时,具有最大高度。 14含4个度为2的结点和5个叶子结点的二叉树,可有_ _个度为1的结点。n1-1n2+n3完全二叉树 单枝树 0至多个 任意二叉树,度为的结点个数没限制。只有完全二叉树,度为的结点个数才至多为1。232022-8-715利用树的孩子兄弟表示法存储,可以将一棵树转换为_ _ 16有一份电文中共使用 6个字符:a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9,试构造一棵哈夫曼

8、树,则其加权路径长度WPL为_ _,字符c的编码是_ _。17将二叉树bt中每一个结点的左右子树互换的C语言算法如下,其中 ADDQ(Q,bt), DELQ(Q),EMPTY(Q)分别为进队,出队和判别队列是否为空的函数,请填写算法中得空白处,完成其功能。 80二叉树001242022-8-7typedef struct node int data ; struct node *lchild, *rchild; btnode; void EXCHANGE(btnode *bt)btnode *p, *q; if (bt)ADDQ(Q,bt); while(!EMPTY(Q) p=DELQ(Q)

9、; q= _ _; p-rchild=(2)_ _ (3)_ _=q; if(p-lchild) (4)_ _; if(p-rchild) (5) _; / p-rchild p-lchild p-lchild ADDQ(Q,p-lchild) ADDQ(Q,p-rchild) 252022-8-718设t是给定的一棵二叉树,下面的递归程序count(t)用于求得:二叉树t中具有非空的左,右两个儿子的结点个数N2;只有非空左儿子的个数NL;只有非空右儿子的结点个数NR和叶子结点个数N0。N2、NL、NR、N0都是全局量,且在调用count(t)之前都置为0.typedef struct nod

10、eint data; struct node *lchild,*rchild;node;int N2,NL,NR,N0;void count(node *t) if (t-lchild!=NULL) if (1)_ _ N2+; else NL+;else if (2)_ _ NR+; else (3) _ ;if(t-lchild!=NULL)(4)_ _ _; if (t-rchild!=NULL) (5)_ _; t-rchild!=null t-rchild!=null N0+ count(t-lchild)count(t-rchild)262022-8-719下面是求二叉树高度的类C

11、写的递归算法试补充完整 说明 二叉树的两指针域为lchild与rchild, 算法中p为二叉树的根,lh和rh分别为以p为根的二叉树的左子树和右子树的高,hi为以p为根的二叉树的高,hi最后返回。height(p)if (1)_ _) if(p-lchild=null) lh=(2)_; else lh=(3)_ _; if(p-rchild=null) rh=(4)_; else rh=(5)_ _; if (lhrh) hi=(6) _;else hi=(7)_; else hi=(8)_; return hi;/ p!=null0height(p-lchild)0height(p-rch

12、ild)lh+1rh+10272022-8-720下列是先序遍历二叉树的非递归子程序,请阅读子程序填充空格,使其成为完整的算法。void example(b) btree *b; btree *stack20, *p; int top; if (b!=null) top=1; stacktop=b; while (top0) p=stacktop; top-; printf(“%d”,p-data); if (p-rchild!=null)(1)_ _; (2)_ _; if (p-lchild!=null) (3)_ ; (4) _; top+stacktop=p-rchildtop+sta

13、cktop=p-lchild282022-8-7第六章 树和二叉树(应用题)1按下面要求解下图中二叉树的有关问题: (1)对此二叉树进行后序后继线索化 ;(2)将此二叉树变换为森林;(3)用后根序遍历该森林,;写出遍历后的结点序列。 LJGIABEFKCDHMONP292022-8-7ABECFDKIGLJHMONP后续遍历二叉树: DCBIJHGFLPONMKEA302022-8-7MKLNPOIGEFHJCABD后续遍历森林:BDCAIFJGHELOPMNK312022-8-72设有正文AADBAACACCDACACAAD,字符集为A,B,C,D,设计一套二进制编码,使得上述正文的编码最短

14、。字符A,B,C,D出现的次数为9,1,5,3。其哈夫曼编码如下A:0,B:100,C:11,D:101 322022-8-7第六章 树和二叉树(算法题)1二叉树采用二叉链表存储:(1)编写计算整个二叉树高度的算法(二叉树的高度也叫二叉树的深度)。(2)编写计算二叉树最大宽度的算法(二叉树的最大宽度是指二叉树所有层中结点个数的最大值)。332022-8-7int Height(btre bt)/求二叉树bt的深度int hl,hr;if (bt=null) return(0);else hl=Height(bt-lch); hr=Height(bt-rch);if(hlhr) return (

15、hl+1); else return(hr+1); 342022-8-7int 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记最大宽度 Qrear=bt; /根结点入队列 while(frontlchild!=null) Q+rear=p-lchild; /左子女入队 if (p-rchild!=null) Q+rear=p-rchild; /右子女入队 if (frontlast) /一层结束, last=rear; if(tempmaxw) maxw=temp;/last指向下层最右元素, 更新当前最大宽度 temp=0; /if /while return (maxw);/结束width

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 教育专区 > 教案示例

本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

工信部备案号:黑ICP备15003705号© 2020-2023 www.taowenge.com 淘文阁