数据结构复习(6树习题)教材课件

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构复习(习题),9/1/2024,1,数据结构复习(习题)9/8/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/DE,2算术表达式a+b*（c+d/e）转为后缀表达式后为（ ）,Aab+cde/* Babcde/+*+ Cabcde/*+,Dabcde*/+,9/1/2024,2,第六章 树和二叉树(选择题)1已知一算术表达式的中缀形式为,3. 设树T的度为4，其中度为1，2，3和4的结点个数分别为,4，2，1，1 则T中的叶子数为（ ）,A5 B6 C7 D8,4. 在下述结论中，正确的是（ ）只有一个结点的二叉树,的度为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=8,9/1/2024,3,3. 设树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,森林转换得到的二叉树中，其左子树加根为森林的第一棵树,9/1/2024,4,6若一棵二叉树具有10个度为2的结点，5个度为1的结点，,9一棵完全二叉树上有1001个结点，其中叶子结点的个数,是（ ）,A 250 B 500 C254 D501,10. 设给定权值总数有n 个，其哈夫曼树的结点总数为( ),A不确定 B2n C2n+1 D2n-1,完全二叉树中度为1的结点最多只有1个，由二叉树的度和结点的关系,n=n0+n1+n2 n=n1+2n2+1 得n=2n0+n1-1,哈夫曼树中没有度为1的节点，叶子节点个数为n,9/1/2024,5,9一棵完全二叉树上有1001个结点，其中叶子结点的个数完全,11. 有关二叉树下列说法正确的是（ ）,A二叉树的度为2 B一棵二叉树的度可以小于2,C二叉树中至少有一个结点的度为2,D二叉树中任何一个结点的度都为2,12. 一个具有1025个结点的二叉树的高h为（ ）,A11 B10 C11至1025之间 D10至1024之间,13一棵二叉树高度为h,所有结点的度或为0，或为2，则这,棵二叉树最少有( )结点,A2h B2h-1 C2h+1 Dh+1,完全二叉树和单枝树之间,9/1/2024,6,11. 有关二叉树下列说法正确的是（ ）完全二叉树,14对于有n 个结点的二叉树, 其高度为（ ）,Anlog,2,n Blog,2,n C,log,2,n,|+1 D不确定,15. 一棵具有 n个结点的完全二叉树的树高度（深度）是,（ ）,A,logn,+1 Blogn+1 C,logn,Dlogn-1,16深度为h的满m叉树的第k层有（ ）个结点。(1=k=lchild=null & p-rchlid=null,12,9/1/2024,19,第六章 树和二叉树(填空题)1二叉树由,4在完全二叉树中，编号为i和j的两个结点处于同一层的条,件是,5在顺序存储的二叉树中，编号为i和j的两个结点处在同一,层的条件是,。,6一棵有n个结点的满二叉树有,_ _,个度为1的结点、有,_ _,个分支 （非 终端）结点和,_ _,个叶子，该满二叉树的深度为,_ _,。,log,2,i,=,log,2,j,log,2,s,=,log,2,t,用顺序存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加“虚结点”。设编号为i和j的结点在顺序存储中的下标为s 和t ,则结点i和j在同一层上的条件是,log,2,s,=,log,2,t,。,0,(n-1)/2,(n+1)/2,log,2,n+1,9/1/2024,20,4在完全二叉树中，编号为i和j的两个结点处于同一层的条l,7设有N个结点的完全二叉树顺序存放在向量A1:N中，其,下标值最大的分支结点为,_,。,8高度为K的完全二叉树至少有,_,_,个叶子结点。,9已知二叉树有50个叶子结点，则该二叉树的总结点数至,少是,_,。,10一个有2001个结点的完全二叉树的高度为,_,。,11如果结点A有 3个兄弟，而且B是A的双亲，则B的度是,_,。,N/2,2,k-2,99,11,4,9/1/2024,21,7设有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-1,n2+n3,完全二叉树,单枝树,0至多个,任意二叉树，度为的结点个数没限制。只有完全二叉树，度为的结点个数才至多为1。,9/1/2024,22,12设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,二叉树,001,9/1/2024,23,15利用树的孩子兄弟表示法存储，可以将一棵树转换为_80,typedef 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),9/1/2024,24,typedef struct nodep-rchild p,18设t是给定的一棵二叉树，下面的递归程序count(t)用于,求得:二叉树t中具有非空的左,右两个儿子的结点个数N2;只有,非空左儿子的个数NL;只有非空右儿子的结点个数NR和叶子,结点个数N0。N2、NL、NR、N0都是全局量，且在调用,count(t)之前都置为0.,typedef struct node,int 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),9/1/2024,25,18设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!=null,0,height(p-lchild),0,height(p-rchild),lh+1,rh+1,0,9/1/2024,26,19下面是求二叉树高度的类C写的递归算法试补充完整p!=n,20下列是先序遍历二叉树的非递归子程序，请阅读子程序,填充空格，使其成为完整的算法。,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-rchild,top+,stacktop=p-lchild,9/1/2024,27,20下列是先序遍历二叉树的非递归子程序，请阅读子程序top,第六章 树和二叉树(应用题),1按下面要求解下图中二叉树的有关问题：,(1)对此二叉树进行后序后继线索化 ；(2)将此二叉树变换为,森林；(3)用后根序遍历该森林，；写出遍历后的结点序列。,L,J,G,I,A,B,E,F,K,C,D,H,M,O,N,P,9/1/2024,28,第六章 树和二叉树(应用题)1按下面要求解下图中二叉树的有,后续遍历二叉树: DCBIJHGFLPONMKEA,9/1/2024,29,后续遍历二叉树: DCBIJHGFLPONMKEA9/8/2,M,K,L,N,P,O,I,G,E,F,H,J,C,A,B,D,后续遍历森林:BDCAIFJGHELOPMNK,9/1/2024,30,MKLNPOIGEFHJCAB,2设有正文AADBAACACCDACACAAD,字符集为A,B,C,D,设计一套二进制编码，使得上述正文的编码最短。,字符A，B，C，D出现的次数为9,1,5,3。其哈夫曼编码如下,A:0，B:100，C:11，D:101,9/1/2024,31,2设有正文AADBAACACCDACACAAD,字符集为A,第六章 树和二叉树(算法题),1二叉树采用二叉链表存储：,（1）编写计算整个二叉树高度的算法（二叉树的高度也叫二叉树的深度）。,（2）编写计算二叉树最大宽度的算法（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。,9/1/2024,32,第六章 树和二叉树(算法题)1二叉树采用二叉链表存储：9/,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);,9/1/2024,33,int 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);/结束width,9/1/2024,34,int Width(BiTree bt)/求二叉树bt的最,