资源描述：
《第6章 树和二叉树习题课》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、幻灯片1第6章树和二叉树习题课中北大学信息与通信工程学院主讲：金永副教授幻灯片2选择题1、已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为()A．-A+B*C/DEB.-A+B*CD/EC．-+*ABC/DED.-+A*BC/DE2、设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。A．M1B．M1+M2C．M3D．M2+M33、有关二叉树下列说法正确的是（）A．二叉树的度为2B．一棵二叉树的度可以小于2C．二叉树中至少有一个结点的度为2D．二叉树中任何一个结点的度
2、都为2幻灯片34、二叉树的第I层上最多含有结点数为（）A．2IB．2I-1-1C．2I-1D．2I-15、一个具有1025个结点的二叉树的高h为（）A．11B．10C．11至1025之间D．10至1024之间6、高度为K的二叉树最大的结点数为（）。A．2kB．2k-1C．2k-1D．2k-1-17、利用二叉链表存储树，则根结点的右指针是（）。A．指向最左孩子B．指向最右孩子C．空D．非空8、对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用()次序的遍历实现编号。A．先序B.中序C.后序D.从根
3、开始按层次遍历幻灯片49、某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E则先序序列是：A．E,G,F,A,C,D,BB．E,A,C,B,D,G,FC．E,A,G,C,F,B,DD．上面的都不对10、上题的二叉树对应的森林包括多少棵树（）A．lB．2C．3D．概念上是错误的11、一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）A．所有的结点均无左孩子B．所有的结点均无右孩子C．只有一个叶子结点D．是任意一棵二叉树12、在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（）A．都不相同 B．完全相同C．先
4、序和中序相同，而与后序不同 D．中序和后序相同，而与先序不同幻灯片513、在完全二叉树中，若一个结点是叶结点，则它没()。A．左子结点B．右子结点 C．左子结点和右子结点D．左子结点，右子结点和兄弟结点14、n个结点的线索二叉树上含有的线索数为（）A．2nB．n－lC．n＋lD．n15、下述编码中哪一个不是前缀码（）。A．（00，01，10，11）B．（0，1，00，11）C．（0，10，110，111）D．（1，01，000，001）16、在下述结论中，正确的是（）①只有一个结点的二叉树的度为0;②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或
5、等于深度相同的满二叉树。A．①②③B．②③④C．②④D．①④幻灯片617、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9B．11C．15D．不确定18、具有10个叶结点的二叉树中有（）个度为2的结点A．8B．9C．10D．1l19、一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）A．250B．500C．254D．50120、有n个叶子的哈夫曼树的结点总数为（）。A．不确定B．2nC．2n+1D．2n-121、二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历:HFIEJKG。该二叉树根的右子树的根是（）。A、EB、F C
6、、G D、H幻灯片722、设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（）A．m-nB．m-n-1C．n+1D．条件不足，无法确定23、用一维数组存储二叉树时，总是以（）遍历顺序存储结点A．先序B.中序C.后序D.按层次遍历24、对一棵二叉树进行层次遍历时，应借助于一个（）。A．顺序表B.数组C.栈D.队列25、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。A．空或只有一个结点B．任一结点无左子树C．高度等于其结点数D．任一结点无右子树幻灯片826、设树T的度为4，其中度为1，2，3和4的结点个数分别为
7、4，2，1，1则T中的叶子数为（）A．5B．6C．7D．827、将一棵树t转换为孩子—兄弟链表表示的二叉树h，则t的后根序遍历是h的（）A．先序遍历B．中序遍历C．后序遍历28、某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号为1，2，…，n，且有如下性质：T中任一结点V，其编号等于左子树上的最小编号减1，而V的右子树的结点中，其最小编号等于V左子树上结点的最大编号加1。这时是按()编号的。A.中序遍历序列B.先序遍历序列C.后序遍历序列D
