数据结构复习（6树习题）课件

数据结构复习(习题)6/17/20241数据结构复习(习题)8/10/20231第六章 树和二叉树(选择题)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*/+6/17/20242第六章 树和二叉树(选择题)1已知一算术表达式的中缀形式为3.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（）A5 B6 C7 D84.在下述结论中，正确的是（）只有一个结点的二叉树的度为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=86/17/202433.设树T的度为4，其中度为1，2，3和4的结点个数分别为6若一棵二叉树具有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设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。AM1 BM1+M2 CM3 DM2+M3 森林转换得到的二叉树中，其左子树加根为森林的第一棵树6/17/202446若一棵二叉树具有10个度为2的结点，5个度为1的结点，9一棵完全二叉树上有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的节点，叶子节点个数为n6/17/202459一棵完全二叉树上有1001个结点，其中叶子结点的个数完全11.有关二叉树下列说法正确的是（）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 完全二叉树和单枝树之间6/17/2024611.有关二叉树下列说法正确的是（）完全二叉树14对于有n 个结点的二叉树,其高度为（）Anlog2n Blog2n Clog2n|+1 D不确定15.一棵具有 n个结点的完全二叉树的树高度（深度）是（）Alogn+1 Blogn+1 Clogn Dlogn-1 16深度为h的满m叉树的第k层有（）个结点。(1=k=lchild=null&p-rchlid=null 126/17/202419第六章 树和二叉树(填空题)1二叉树由 4在完全二叉树中，编号为i和j的两个结点处于同一层的条件是5在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是 。6一棵有n个结点的满二叉树有_ _个度为1的结点、有_ _个分支（非 终端）结点和_ _个叶子，该满二叉树的深度为_ _ 。log2i=log2j log2s=log2t 用顺序存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加“虚结点”。设编号为i和j的结点在顺序存储中的下标为s 和t,则结点i和j在同一层上的条件是log2s=log2t。0(n-1)/2(n+1)/2log2n+16/17/2024204在完全二叉树中，编号为i和j的两个结点处于同一层的条l7设有N个结点的完全二叉树顺序存放在向量A1:N中，其下标值最大的分支结点为_。8高度为K的完全二叉树至少有_ _个叶子结点。9已知二叉树有50个叶子结点，则该二叉树的总结点数至少是_。10一个有2001个结点的完全二叉树的高度为_。11如果结点A有 3个兄弟，而且B是A的双亲，则B的度是_。N/22k-2991146/17/2024217设有N个结点的完全二叉树顺序存放在向量A1:N中，其12设F是由T1,T2,T3三棵树组成的森林,与F对应的二叉树为B,已知T1,T2,T3的结点数分别为n1,n2和n3则二叉树B的左子树中有_ _个结点，右子树中有_ _个结点13对于一个具有n个结点的二元树，当它为一棵_ _二元树时具有最小高度，当它为一棵_ _ 时，具有最大高度。14含4个度为2的结点和5个叶子结点的二叉树，可有_ _个度为1的结点。n1-1n2+n3完全二叉树 单枝树 0至多个 任意二叉树，度为的结点个数没限制。只有完全二叉树，度为的结点个数才至多为1。6/17/20242212设F是由T1,T2,T3三棵树组成的森林,与F对应的二15利用树的孩子兄弟表示法存储，可以将一棵树转换为_ _ 16有一份电文中共使用 6个字符:a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9，试构造一棵哈夫曼树，则其加权路径长度WPL为_ _，字符c的编码是_ _。17将二叉树bt中每一个结点的左右子树互换的C语言算法如下，其中 ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分别为进队，出队和判别队列是否为空的函数，请填写算法中得空白处，完成其功能。80二叉树0016/17/20242315利用树的孩子兄弟表示法存储，可以将一棵树转换为_80typedef 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);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)6/17/202424typedef struct nodep-rchild p18设t是给定的一棵二叉树，下面的递归程序count(t)用于求得:二叉树t中具有非空的左,右两个儿子的结点个数N2;只有非空左儿子的个数NL;只有非空右儿子的结点个数NR和叶子结点个数N0。N2、NL、NR、N0都是全局量，且在调用count(t)之前都置为0.typedef struct nodeint 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)6/17/20242518设t是给定的一棵二叉树，下面的递归程序count(t)19下面是求二叉树高度的类C写的递归算法试补充完整 说明 二叉树的两指针域为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-rchild)lh+1rh+106/17/20242619下面是求二叉树高度的类C写的递归算法试补充完整p!=n20下列是先序遍历二叉树的非递归子程序，请阅读子程序填充空格，使其成为完整的算法。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+stacktop=p-lchild6/17/20242720下列是先序遍历二叉树的非递归子程序，请阅读子程序top第六章 树和二叉树(应用题)1按下面要求解下图中二叉树的有关问题：(1)对此二叉树进行后序后继线索化；(2)将此二叉树变换为森林；(3)用后根序遍历该森林，；写出遍历后的结点序列。LJGIABEFKCDHMONP6/17/202428第六章 树和二叉树(应用题)1按下面要求解下图中二叉树的有后续遍历二叉树:DCBIJHGFLPONMKEA6/17/202429后续遍历二叉树:DCBIJHGFLPONMKEA8/10/MKLNPOIGEFHJCABD后续遍历森林:BDCAIFJGHELOPMNK6/17/202430MKL NPOI GEFHJ CAB2设有正文AADBAACACCDACACAAD,字符集为A,B,C,D,设计一套二进制编码，使得上述正文的编码最短。字符A，B，C，D出现的次数为9,1,5,3。其哈夫曼编码如下A:0，B:100，C:11，D:101 6/17/2024312设有正文AADBAACACCDACACAAD,字符集为A第六章 树和二叉树(算法题)1二叉树采用二叉链表存储：（1）编写计算整个二叉树高度的算法（二叉树的高度也叫二叉树的深度）。（2）编写计算二叉树最大宽度的算法（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。6/17/202432第六章 树和二叉树(算法题)1二叉树采用二叉链表存储：8/int Height(btre bt)/求二叉树bt的深度int hl,hr;if(bt=null)return(0);else hl=Height(bt-lch);hr=Height(bt-rch);if(hlhr)return(hl+1);else return(hr+1);6/17/202433int Height(btre bt)/求二叉树bt的深度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记最大宽度 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);/结束width6/17/202434int Width(BiTree bt)/求二叉树bt的最