面向对象程序设计第9章复习题.pptVIP

第9章 习题;1、前缀表达式 + * 2 / 8 4 3 的值是_____。 2、设G是完全二元树，G有15个顶点，其中有8个叶子，则G有_____条边，G的总度数是_____。 3、设 是图，如果G是____并且____则G是树。 ; 4、后缀表达式 3 5 2 － * 7 + 4 / 的值是 ___。 5、已知一棵无向树T中有4度、3度和2度分支点各1个，其余顶点均为树叶，则T有 ___个树叶。 6、波兰符号表达式 * + 4 5 - / 8 2 1的值是 ___。 ; 7、5阶非同构的无向树有_______棵。 8、波兰符号法算式 + - * 3 2 * 2 3 / 6 – 4 2的值为_______。 9、设G是完全二元树，G有15个顶点，其中有8个叶子，则G有_____条边，G的总度数是_____。 ; 1、设图G是有6个顶点的连通图，总度数为20，则从G中至少删去_____条边后使之成为树。 A、10 B、5 C、3 D、2 ;3、下面编码_____不是前缀码。 A、11，00，10，01 B、01，11，011，1001 C、101，11，001，011，010 D、010，11，011，1011，1001，10101 4、5阶非同构的无向树有_____棵。 A、1 B、2 C、3 D、4 5、若T为树，以下叙述不正确的是_____。 A、T是连通的且不含回路 B、T的每对顶点之间有唯一的一条路径 C、T是连通的且每条边都是割边 D、T是连通的且每个点都是割点 ;6、设T是由n个顶点的完全二元正则树，则T的叶子数为_____。 A、 B、 C、 D、 7、6阶非同构的无向树有_____棵。 A、5 B、6 C、7 D、8 ;12、在下列选项中，关于n阶树(n1)的性质描述不正确的是_____。 A、在连通n阶图中，n阶树的边的数量最少 B、在n阶无回路图中，n阶树的边的数量最多 C、n阶树不一定是平面图 D、n阶树(n1)至少有两片树叶 13、T是正则二元树，有m条边和t片树叶，则m=_______。 A、 t B、2t C、2t-1 D、 2t-2;;; 3、求下图中的最小生成树，并计算它的权。; 4、设有7个字母在通信中出现的频率(%)如下： a: 35% b: 20%, c: 15%, d: 10%, e: 10%, f: 5%, g: 5% (1)以频率(或乘100)为权，求最优2元树． (2)利用所求最优2元树找出每个字母的前缀码． (3)求传输10000个按上述比例出现的字母需要多少个??进制数字？若用等长的 (长为3) 的码字传输需要多少个二进制数字?节约多少个二进制位？ ;5、设T=V, E是n阶非平凡的无向树，证明：T至少有两片树叶。 6、画出权为2、4、6、8、10、12、14的最优二元树，并计算其权值。