第6章-树和二叉树习题课ppt课件.ppt

《第6章-树和二叉树习题课ppt课件.ppt》由会员分享，可在线阅读，更多相关《第6章-树和二叉树习题课ppt课件.ppt（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第6章 树和二叉树习题课中北大学信息与通信工程学院主讲：金永 副教授第6章 树和二叉树习题课算法与数据结构我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物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、设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ）。AM1 BM1+M2 CM3

2、 DM2+M33、有关二叉树下列说法正确的是（ ）A二叉树的度为2 B一棵二叉树的度可以小于2C二叉树中至少有一个结点的度为2 D二叉树中任何一个结点的度都为2选择题第6章 树和二叉树习题课算法与数据结构我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物4、二叉树的第I层上最多含有结点数为（ ）A2I B 2I-1-1 C 2I-1 D2I -15、一个具有1025个结点的二叉树的高h为（ ）A11 B10 C11至1025之间 D10至1024之间6、高度为 K的二叉树最大的结点数为（ ）。A2k B2k-

3、1 C2k -1 D2k-1-1 7、利用二叉链表存储树，则根结点的右指针是（）。A指向最左孩子 B指向最右孩子 C空 D非空8、对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。A先序 B. 中序 C. 后序 D. 从根开始按层次遍历第6章 树和二叉树习题课算法与数据结构我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物9、某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A

4、,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上面的都不对 10、上题的二叉树对应的森林包括多少棵树（ ）Al B2 C3 D概念上是错误的 11、一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）A所有的结点均无左孩子B所有的结点均无右孩子C只有一个叶子结点 D是任意一棵二叉树12、在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（ ）A都不相同B完全相同 C先序和中序相同，而与后序不同D中序和后序相同，而与先序不同第6章 树和二叉树习题课算法与数据结构我吓了一跳，蝎子是

5、多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物13、在完全二叉树中，若一个结点是叶结点，则它没( )。 A左子结点 B右子结点 C左子结点和右子结点 D左子结点，右子结点和兄弟结点14、n个结点的线索二叉树上含有的线索数为（ ）A2n Bnl Cnl Dn 15、下述编码中哪一个不是前缀码（ ）。A（00，01，10，11） B（0，1，00，11） C（0，10，110，111） D（1，01，000，001）16、在下述结论中，正确的是（ ）只有一个结点的二叉树的度为0; 二叉树的度为2； 二叉树的左右子树可任意交换;

6、深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A B C D第6章 树和二叉树习题课算法与数据结构我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物17、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ） A9 B11 C15 D不确定 18、具有10个叶结点的二叉树中有（ ）个度为2的结点 A8 B9 C10 D1l19、一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）A 250 B 500 C254 D50120、有n个叶子的哈夫曼树的结点总数为（

7、 ）。A不确定 B2n C2n+1 D2n-121、二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中序遍历: HFIEJKG 。该二叉树根的右子树的根是（ ） 。A、 E B、 F C、 G D、 H 第6章 树和二叉树习题课算法与数据结构我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物22、设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ ）Am-n Bm-n-1 Cn+1 D条件不足，无法确定 23、用一维数组存储二叉树时，总是以（

8、）遍历顺序存储结点A先序 B. 中序 C. 后序 D. 按层次遍历24、对一棵二叉树进行层次遍历时，应借助于一个（）。A顺序表 B. 数组 C. 栈 D.队列25、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。A空或只有一个结点 B任一结点无左子树 C高度等于其结点数 D任一结点无右子树第6章 树和二叉树习题课算法与数据结构我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物26、设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ）A5 B6 C7

9、D827、将一棵树t 转换为孩子兄弟链表表示的二叉树h，则t的后根序遍历是h 的（ ） A先序遍历 B中序遍历 C后序遍历28、某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号为1，2， ，n，且有如下性质：T中任一结点V，其编号等于左子树上的最小编号减1，而V的右子树的结点中，其最小编号等于V左子树上结点的最大编号加1。这时是按( )编号的。A.中序遍历序列 B.先序遍历序列 C.后序遍历序列 D.层次顺序 第6章 树和二叉树习题课算法与数据结构我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的

10、生物1、从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。 树的孩子兄弟链表表示法和二叉树二叉链表表示法，本质是一样的，只是解释不同，也就是说树（森林的特例）可用二叉树唯一表示，并可使用二叉树的一些算法去解决树和森林中的问题。树和二叉树的区别有：一是二叉树的度至多为2，树无此限制；二是二叉树有左右子树之分，即使在只有一个分枝的情况下， 也必须指出是左子树还是右子树，树无此限制。应用题第6章 树和二叉树习题课算法与数据结构我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测

11、没有错：表里边有一个活的生物 2、试找出满足下列条件的二叉树1）先序序列与后序序列相同；2）中序序列与后序序列相同；3）先序序列与中序序列相同；1)、既不含左子树，也不含右子树的二叉树。2)、不含右子树的二叉树。3)、不含左子树的二叉树。第6章 树和二叉树习题课算法与数据结构我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物3、已知一棵度为、已知一棵度为k的树中有的树中有n1个度为个度为1的结点，的结点，n2个个度为度为2的结点，的结点，nk个度为个度为k的结点，问该树中有的结点，问该树中有多少个叶子结点？多

12、少个叶子结点？根据树的定义，在一颗树中，除树根结点外，每个结点有且仅有一个前驱结点，也就是说，每个结点与指向它的一个分支一一对应，所以除树根结点之外的结点树等于所有结点的分支数，即度数，从而可得树中的结点数等于所有结点的度数加1。总结点数为而度为0的结点数就应为总结点数减去度不为0的结点数的总和，即kknnnn.321321kiikkninnnnknnnnn13213210) 1(1).(.321第6章 树和二叉树习题课算法与数据结构我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物4、将算术表达式 (a+b

13、)+c*(d+e)+f)*(g+h)转化为二叉树。 +*+fhg*+abc+de5、用一维数组存放的一棵完全二叉树如下图所示：ABCDEFGHIJKL写出后序遍历该二叉树时访问结点的顺序。HIDJKEBLFGCA 第6章 树和二叉树习题课算法与数据结构我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物6、对下图所示二叉树分别按先序、中序后序遍历，给出相应的结点序列，同时给二叉树加上中序线索。 （1）先序序列：ABDEHCFG（2）中序序列：DHEBAFCG（3）后序序列：HEDBFGCA ABCDFGEHnu

14、llnull第6章 树和二叉树习题课算法与数据结构我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物7、设一棵二叉树的先序、中序遍历序列分别为先序遍历序列： ABDFCEGH 中序遍历序列：BFDAGEHC（1）画出这棵二叉树。（2）将这棵二叉树转换成对应的树（或森林）AEDCBHGFABFDCEHG第6章 树和二叉树习题课算法与数据结构我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物BACEDFNPGHJMOLIKHGD

15、ACJIBFEMPONKL8、将森林转换成对应的二叉树第6章 树和二叉树习题课算法与数据结构我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物9、一棵二叉树的先序、中序、后序序列如下，其中一部分未标出，请构造出该二叉树。先序序列 ：_ _ C D E _ G H I _ K 中序序列 ：C B _ _ F A _ J K I G后序序列 ：_ E F D B _ J I H _ A ABCEDGIHFJK第6章 树和二叉树习题课算法与数据结构我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的

16、世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物10、设二叉树BT的存储结构如下: 12345678910Lchild 0 0 2 3 7 5 8 0 10 1DataJ H F D B A C E G IRchild 0 0 0 9 4 0 0 0 0 0其中BT为树根结点的指针，其值为6,Lchild,Rchild分别为结点的左、右孩子指针域,data为结点的数据域。试完成下列各题:（l）画出二叉树BT的逻辑结构;（2）写出按先序、中序、后序遍历该二叉树所得到的结点序列;（3）画出二叉树的后序线索树 。第6章 树和二叉树习题课算法与数据结构我吓了一跳，蝎子是多么丑恶和恐

17、怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物BACEDFGHIJ先序序列：J中序序列： E C B H F D J I G A后序序列： BACEDFGHIJnullnull第6章 树和二叉树习题课算法与数据结构我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物11、给定集合15,3,14,2,6,9,16,17，(1) 构造相应的huffman树，(2) 计算它的带权路径长度，(3) 写出它的huffman编码。16296170 11531401

18、1100001101wpl=(2+3)*5+6*4+(9+14+15)*3+(16+17)*2=229 编码为：15:111,3:10101,14:110,2:101006:10119:10016:0017:01 第6章 树和二叉树习题课算法与数据结构我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物12、已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8，11，试填写出其对应哈夫曼树HT的存储结构的初态和终态。 字符weightparentlchrch1A38002B1212003C710004D49005E28006F810007G111100859519911481015123611201397122713210134701112