《数据结构复习(6树习题)解读》由会员分享，可在线阅读，更多相关《数据结构复习(6树习题)解读（34页珍藏版）》请在金锄头文库上搜索。
1、数据结构复习(习题) *1 第六章 树和二叉树(选择题) 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*/+ Date 2 3. 设树T的度为4，其中度为1，2，3和4的结点个数分别为 4，2，1，1 则T中的叶子数为（ ） A5 B6 C7 D8 4. 在下述结论中，正确的是（ ）只有一个结点的二叉树 的度
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 Date 3 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条件不足，无法
3、确定 8设森林F中有三棵树，第一，第二，第三棵树的结点个数 分别为M1，M2和M3。与森林F对应的二叉树根结点的右子 树上的结点个数是（ ）。 AM1 BM1+M2 CM3 DM2+M3 森林转换得到的二叉树中，其左子树加根为森林的第一棵树 Date 4 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-
4、1 哈夫曼树中没有度为1的节点，叶子节点个数为n Date 5 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 完全二叉树和单枝树之间 Date 6 14对于有n 个结点的二叉树, 其高度为（ ） Anlog2n Blog2n Clog2n|+1 D不
5、确定 15. 一棵具有 n个结点的完全二叉树的树高度（深度）是 （ ） Alogn+1 Blogn+1 Clogn Dlogn-1 16深度为h的满m叉树的第k层有（ ）个结点。(1=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) Date 24 18设t是给定的一棵二叉树，下面的递归程序count(t)用于 求得:二叉树t中具有非空的左,右两个儿子的结点个数N2;只有 非空左儿子的个数N
6、L;只有非空右儿子的结点个数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)_ _;
7、t-rchild!=null t-rchild!=null N0+ count(t-lchild) count(t-rchild) Date 25 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 (
8、lhrh) hi=(6) _；else hi=(7)_; else hi=(8)_; return hi; / p!=null 0height(p-lchild) 0 height(p-rchild) lh+1 rh+1 0 Date 26 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
9、); if (p-rchild!=null)(1)_ _; (2)_ _; if (p-lchild!=null) (3)_ ; (4) _; top+ stacktop=p-rchild top+stacktop=p-lchild Date 27 第六章 树和二叉树(应用题) 1按下面要求解下图中二叉树的有关问题： (1)对此二叉树进行后序后继线索化 ；(2)将此二叉树变换为 森林；(3)用后根序遍历该森林，；写出遍历后的结点序列。 L J G I A B E F K C D HM ON P Date 28 后续遍历二叉树: DCBIJHGFLPONMKEA Date 29 M K LN P
10、 O I G E FH J C A B D 后续遍历森林:BDCAIFJGHELOPMNK Date 30 2设有正文AADBAACACCDACACAAD,字符集为A,B,C,D, 设计一套二进制编码，使得上述正文的编码最短。 字符A，B，C，D出现的次数为9,1,5,3。其哈夫曼编码如下 A:0，B:100，C:11，D:101 Date 31 第六章 树和二叉树(算法题) 1二叉树采用二叉链表存储： （1）编写计算整个二叉树高度的算法（二叉树的高度也叫 二叉树的深度）。 （2）编写计算二叉树最大宽度的算法（二叉树的最大宽度 是指二叉树所有层中结点个数的最大值）。 Date 32 int H
11、eight(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); Date 33 int Width(BiTree bt)/求二叉树bt的最大宽度 if (bt=null) return (0); /空二叉树宽度为0 else BiTree Q;/Q是队列，元素为二叉树结点指针，容量足够大 front=1;rear=1;last=1;/front队头指针,rear队尾指针
12、,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 Date 34
