《数据结构复习(6树习题)教材课件.ppt》由会员分享，可在线阅读，更多相关《数据结构复习(6树习题)教材课件.ppt（34页珍藏版）》请在三一办公上搜索。
1、2022/12/2,1,数据结构复习(习题),2,2022/12/2,第六章 树和二叉树(选择题),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*/+,3,2022/12/2,3. 设树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=8,4,2022/12/2,6若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）A9 B11 C15 D不确定7. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ ）Am-n Bm-n-1
3、 Cn+1 D条件不足，无法确定8设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ）。AM1 BM1+M2 CM3 DM2+M3,森林转换得到的二叉树中，其左子树加根为森林的第一棵树,5,2022/12/2,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
4、得n=2n0+n1-1,哈夫曼树中没有度为1的节点，叶子节点个数为n,6,2022/12/2,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,完全二叉树和单枝树之间,7,2022/12/2,14对于有n 个结点的二叉树, 其高度为（ ）Anlog2n Blog2n
5、 Clog2n|+1 D不确定15. 一棵具有 n个结点的完全二叉树的树高度（深度）是（ ）Alogn+1 Blogn+1 Clogn Dlogn-1 16深度为h的满m叉树的第k层有（ ）个结点。(1=k=h)Amk-1 Bmk-1 Cmh-1 Dmh-1,完全二叉树可以确定，一般二叉树不能确定,8,2022/12/2,17. 一棵树高为K的完全二叉树至少有（ ）个结点A2k 1 B. 2k-1 1 C. 2k-1 D. 2k18. 将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度（ ）A4 B5 C6 D7 19. 利用二叉链表存储树，则根结点的右指针是（ ）A指向最
6、左孩子 B指向最右孩子 C空 D非空,2k-1-1+1= 2k-1,h=log3n+1,9,2022/12/2,20对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。A先序 B. 中序 C. 后序 D. 从根开始按层次遍历21树的后根遍历序列等同于该树对应的二叉树的( ). A. 先序序列 B. 中序序列 C. 后序序列22一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ ） ACABDEFG BABCDEFG CDACEFBG DADCFEG,当该二叉树所有结
7、点的左子树为空时，先序遍历序列和中序遍历序列相同。,10,2022/12/2,23已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ ）。ACBEFDA B FEDCBA C CBEDFA D不定24. 某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则前序序列是：AE,G,F,A,C,D,B BE,A,C,B,D,G,F CE,A,G,C,F,B,D D上面的都不对 25. 上题的二叉树对应的森林包括多少棵树（ ）A1 B2 C3 D概念上是错误的,左孩子，右兄弟,11,2022/12/2,26二叉树的先序遍历和中
8、序遍历如下： 先序遍历：EFHIGJK；中序遍历: HFIEJKG 。该二叉树根的右子树的根是：A、 E B、 F C、 G D、 H 27. 某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号为1，2， ，n，且有如下性质：T中任一结点V，其编号等于左子树上的最小编号减1，而V的右子树的结点中，其最小编号等于V左子树上结点的最大编号加1。这时是按( )编号的。A.中序遍历序列 B.前序遍历序列 C.后序遍历序列 D.层次顺序,12,2022/12/2,28对于前序遍历与中序遍历结果相同的二叉树为（ 1）;对于前序遍历和后序遍历结果相同的二叉树为（ 2）。A一般二叉树 B只有根结
9、点的二叉树 C根结点无左孩子的二叉树 D根结点无右孩子的二叉树 E所有结点只有左子数的二叉树 F所有结点只有右子树的二叉树29一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）A所有的结点均无左孩子 B所有的结点均无右孩子C只有一个叶子结点 D是任意一棵二叉树,F,B,前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树，所以本题的A和B均对，单支树的特点是只有一个叶子结点,13,2022/12/2,30在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（ ）A都不相同 B完全相同 C先序和中序相同，而与后序不同 D中序和后序
10、相同，而与先序不同31某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。A空或只有一个结点 B任一结点无左子树 C高度等于其结点数 D任一结点无右子树,14,2022/12/2,32. 一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是：( )A不确定 B. 0 C. 1 D. 2 33. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：( )。A. 0 B. 1 C. 2 D. 不确定,左子树为空的二叉树的根结点的左线索为空（无前驱），先序序列的最后结点的右线索为空（无后继），共2个空链域,只有最后一个叶结点没有后继,15,2022/12/2,34.
11、 线索二叉树是一种（ ）结构。A 逻辑 B 逻辑和存储 C 物理 D线性35n个结点的线索二叉树上含有的线索数为（ ）A2n Bn1 Cn1 Dn 36. 设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ ）个。A n-1 Bn C n+1 D n+2,N个结点共有2n个指针域，二叉链表用了n-1个，剩下n+1个,每一个终端结点的孩子中都会贡献出一个空的右指针,16,2022/12/2,37下述编码中哪一个不是前缀码（ ）。A（00，01，10，11） B（0，1，00，11） C（0，10，110，111） D（1，01，000，001）38由3
12、个结点可以构造出多少种不同的二叉树？（ ）A2 B3 C4 D5 39. 引入二叉线索树的目的是（ ）A加快查找结点的前驱或后继的速度 B为了能在二叉树中方便的进行插入与删除C为了能方便的找到双亲 D使二叉树的遍历结果唯一,17,2022/12/2,第六章 树和二叉树(判断题),1. 二叉树的遍历结果不是唯一的. 2. 二叉树的遍历只是为了在应用中找到一种线性次序。 3采用二叉链表作存储结构，树的前序遍历和其相应的二叉树的前序遍历的结果是一样的。4完全二叉树中，若一个结点没有左孩子，则它必是树叶。,18,2022/12/2,5. 给定一棵树，可以找到唯一的一棵二叉树与之对应。6霍夫曼树的结点个
13、数不能是偶数。7哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。8. 线索二叉树的优点是便于是在中序下查找前驱结点和后继结点。9完全二叉树的存储结构通常采用顺序存储结构。,19,2022/12/2,第六章 树和二叉树(填空题),1二叉树由 三个基本单元组成。2在二叉树中，指针p所指结点为叶子结点的条件是 3已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有_个叶子结点。,根结点,左子树,右子树,p-lchild=null & p-rchlid=null,12,20,2022/12/2,4在完全二叉树中，编号为i和j的两个结点处于同一层的条件是5在顺
14、序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是 。6一棵有n个结点的满二叉树有_ _个度为1的结点、有_ _个分支 （非 终端）结点和_ _个叶子，该满二叉树的深度为_ _ 。,log2i=log2j,log2s=log2t,用顺序存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加“虚结点”。设编号为i和j的结点在顺序存储中的下标为s 和t ,则结点i和j在同一层上的条件是log2s=log2t。,0,(n-1)/2,(n+1)/2,log2n+1,21,2022/12/2,7设有N个结点的完全二叉树顺序存放在向量A1:N中，其下标值最大的分支结点为_。8高度为K的完
15、全二叉树至少有_ _个叶子结点。 9已知二叉树有50个叶子结点，则该二叉树的总结点数至少是_。10一个有2001个结点的完全二叉树的高度为_。11如果结点A有 3个兄弟，而且B是A的双亲，则B的度是_。,N/2,2k-2,99,11,4,22,2022/12/2,12设F是由T1,T2,T3三棵树组成的森林,与F对应的二叉树为B,已知T1,T2,T3的结点数分别为n1,n2和n3则二叉树B的左子树中有_ _个结点，右子树中有_ _个结点13对于一个具有n个结点的二元树，当它为一棵_ _二元树时具有最小高度，当它为一棵_ _ 时，具有最大高度。 14含4个度为2的结点和5个叶子结点的二叉树，可有
16、_ _个度为1的结点。,n1-1,n2+n3,完全二叉树,单枝树,0至多个,任意二叉树，度为的结点个数没限制。只有完全二叉树，度为的结点个数才至多为1。,23,2022/12/2,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)分别为进队，出队和判别队列是否为空的函数，请填写算法中得空白处，
17、完成其功能。,80,二叉树,001,24,2022/12/2,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-l
18、child),ADDQ(Q,p-rchild),25,2022/12/2,18设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+
19、; 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),26,2022/12/2,19下面是求二叉树高度的类C写的递归算法试补充完整 说明 二叉树的两指针域为lchild与rchild, 算法中p为二叉树的根，lh和rh分别为以p为根的二叉树的左子树和右子树的高，hi为以p为根的二叉树的高，hi最后返回。height(p)i
20、f (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,27,2022/12/2,20下列是先序遍历二叉树的非递归子程序，请阅读子程序填充空格，使其成为完整的算法。void example(b) btree *b; btree *
21、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,28,2022/12/2,第六章 树和二叉树(应用题),1按下面要求解下图中二叉树的有关问题： (1)对此二叉树进行后序后继线索化 ；(2)将此二叉树变换为森
22、林；(3)用后根序遍历该森林，；写出遍历后的结点序列。,29,2022/12/2,后续遍历二叉树: DCBIJHGFLPONMKEA,30,2022/12/2,后续遍历森林:BDCAIFJGHELOPMNK,31,2022/12/2,2设有正文AADBAACACCDACACAAD,字符集为A,B,C,D,设计一套二进制编码，使得上述正文的编码最短。字符A，B，C，D出现的次数为9,1,5,3。其哈夫曼编码如下A:0，B:100，C:11，D:101,32,2022/12/2,第六章 树和二叉树(算法题),1二叉树采用二叉链表存储：（1）编写计算整个二叉树高度的算法（二叉树的高度也叫二叉树的深度
23、）。（2）编写计算二叉树最大宽度的算法（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。,33,2022/12/2,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); ,34,2022/12/2,int Width(BiTree bt)/求二叉树bt的最大宽度 if (bt=null) return (0); /空二叉树宽度为0 else BiTre
24、e 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,
