数据结构课堂习题2

《数据结构课堂习题2》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第6章树和二叉树6.1设树T的度为4，其中度为1，2，3和4的结点个数分别为4,2，1，1则1屮的叶子数为(D)A.5B.6C.7D.86.2在下述结论中，正确的是(D)①只冇一个结点的二叉树的度为0;②二叉树的度为2;③二叉树的左右了树可任意交换；④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A.①②③B.②③④C.②④D.①④6.3设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林E中第一棵树的结点个数是(A)A.m-nB.m-n-1C.n+1D.条件不足，无法确定1.如果结点A是结点B的双亲，而且结点B有4个兄弟，则结点A的度是(

2、D)A)2B)3C)4D)52.设有一棵二叉树，其1度结点有m个，2度结点有n个，则该二叉树的结点总数为(D)A)m+nB)2*m+nC)m+2*nD)m+2*n+l3.没奋一棵二义树，其先序遍历序列是：ABCDEFG,中序遍历序列是：CBDAFEG,则该二义树的后序遍历序列是(A)A)CDBFGEAB)CDFGBEAC)CDBAEGED)CDBFEGA4.设有13个值，由它们组成一棵哈夫曼树，则该哈夫受树中结点个数共有(D)。A)13B)12C)26D)255.设电文中出现的字母为A、B、C、D和E，每个字母在电文屮出现的次数分别为：6,23,3,5和12，按哈夫曼编码，则字母C

3、的编码应是(C)A)10B)110C)1110D)1116.已知一棵二叉树的先序遍历序列为EFHTGJK,屮序遍历序列为HFTEJGK,则该二叉树根的右子树的根是(G)A)EB)FC)GD)J7.设结点A有左孩子结点B,右孩子结点C，则在先序遍历、屮序遍历、后序遍历这三种基本遍历序列中B—定定C的(A)A)前驱B)后继C)相邻结点D)不ffl邻结点四.填空题1.采用二叉链式存储结构，具柯n个结点的二叉树屮，一共柯2n个指针域,K屮ri+1个指针域力空。2.-•棵非空的二叉树，其第i层上最多有_2iH个结点。3.满二叉树是一棵深度为k的且恰好有_2k-l个结点的二叉树。4.将一棵完全

4、二叉树按层次编号，对任一编号为i的结点有：如该结点有左孩子，则其编号为2i;如该结点有右孩子，则-K编号为2i+l。5.设一棵二义树屮只侖叶子结点和左、右子树都非空的结点，如果叶子结点的个数足m，贝IJ左、右子树都非空的结点个数是_m-l6.设有一棵树(如图6-5所示)，请回答下列问题：根结点是_A;叶子结点有_DHIJFK；E的双亲是_g;F的祖先是CA；G的孩子是g;D的孩•了•是无;E的了孙冉HIJ;D的兄弟足E__:B的兄弟足_[结点H的层数是_1_;树的深度是_1_;E为根的子树深度是_么这棵树的度是3。1.现冇一表达式(a+b)*c-d/e,写出该表达式的波兰式_-*+

5、abc/de，以及逆波兰式_ab+c*de/-o6.4—棵深度为H的满k叉树有如下性质：第H层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果按层次顺序从1开始对全部结点编号，问：(1)总结点数目是多少？(2)编号为p的结点的父结点(若存在)的编号是多少？(3)编号为p的结点的第i个儿子结点(若存在)的编号是多少？解：⑴(kH-l)/(k-l)(2)如果p是双亲的最小的孩子(右孩子)，则P减去根结点的一个结点，应是k的整数倍，该整数即为所在的组数，每一组为一棵满k叉树，正好应为双亲结点的编号。如災pS其双亲的敁人的孩子(左孩子)，则p+k-1为其最小的弟弟，洱减去一个

6、根结点，除以k，即为其双亲结点的编号。综合來说，对于P是左孩子的怙况，i=(p+k-2)/k:对于p是右孩子的惜况，i=(p-l)/k(3)结点p的右孩子的编号为kp+1,左孩子的编号为kp+l-(k-l)=k(p-i)+2，第i个孩子的编号为k(p-l)+2+i~l=kp-k+i+lc6.5已知一棵度为k的树中有％个度为1的结点，久个度为2的结点，…，久个度为k的结点，问该树中有多少个叶子结点？解：根据树的定义，在一颗树屮，除树根结点外，毎个结点有且仅有一个前驱结点，也就是说，毎个结点与指h'd它的一个分支一一对应，所以除树根结点之外的结点数等于所有结点的分支数，即度数，从而可得

7、树中的结点数等于所有结点的度数加1。总结点数为1+77,4-2n2+3n3+…+knk而度为o的结点数就应为总结点数减去度不为o的结点数的总和，即k；2()=1+/?,+2n2+3h3+...+knk-(h,+n2+n3++)=1+^(/-l)n(i=l6.8证明：一棵满k叉树上的叶子结点数n()和非叶子结点数％之间满足以下关系：n^=(k-l)n,4-1kh-lk-"o♦6.19((b)