数据结构(c语言版)习题-树

《数据结构(c语言版)习题-树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、选择题1．一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为()A．-A+B*C/DEB.-A+B*CD/EC．-+*ABC/DED.-+A*BC/DE2．算术表达式a+b*（c+d/e）转为后缀表达式后为（）A．ab+cde/*B．abcde/+*+C．abcde/*++D．abcde*/++3.在一颗度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点。则树T的叶结点个数是()。A.41B.82C.113D.1224.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为（）A．5B．6C．7D

2、．85.在下述结论中，正确的是（）①只有一个结点的二叉树的度为0;②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A．①②③B．②③④C．②④D．①④6.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（）A．m-nB．m-n-1C．n+1D．条件不足，无法确定7．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9B．11C．15D．不确定8．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点

3、的右子树上的结点个数是（）。A．M1B．M1+M2C．M3D．M2+M39．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。A．250B．500C．254D．505E．以上答案都不对10.设给定权值总数有n个，其哈夫曼树的结点总数为()。A．不确定B．2nC．2n+1D．2n-111．若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（）。A．n-1B．ën/mû-1C．é(n-1)/(m-1)ùD．én/(m-1)ù-1E．é(n+1)/(m+1)ù-112.有关二叉树下列说法正确的是（）A．二叉树的度为2B．一棵二叉树的度可以小于2C．二叉树中至少有一个结点的度为2D

4、．二叉树中任何一个结点的度都为213．二叉树的第I层上最多含有结点数为（）A．2IB．2I-1-1C．2I-1D．2I-114.一个具有1025个结点的二叉树的高h为（）A．11B．10C．11至1025之间D．10至1024之间15．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有()结点A．2hB．2h-1C．2h+1D．h+116．对于有n个结点的二叉树,其高度为（）A．nlog2nB．log2nC．ëlog2nû

5、+1D．不确定17.一棵具有n个结点的完全二叉树的树高度（深度）是（）A．ëlognû+1B．logn+1C．ëlognûD．logn-118．深度为h的

6、满m叉树的第k层有（）个结点。(1=

7、其左孩子的编号小于其右孩子的编号，可采用()次序的遍历实现编号。A．先序B.中序C.后序D.从根开始按层次遍历24．树的后根遍历序列等同于该树对应的二叉树的().A.先序序列B.中序序列C.后序序列25．若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用()遍历方法最合适。A．前序B．中序C．后序D．按层次26．在下列存储形式中，哪一个不是树的存储形式？（）A．双亲表示法B．孩子链表表示法C．孩子兄弟表示法D．顺序存储表示法27．一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（）A．CABDEFGB．ABCDEFGC．DACEFBGD．ADCFEG28

8、.对n（n≥2）个权值均不相同的字符构成的哈夫曼树，关于该树的叙述，错误的是()。A.该树一定是一颗完全二叉树B.树中两个权值最小的结点一定是兄弟结点C.树中一定没有度为1的结点D.树中任一非叶结点的权值一定不小于下一层任一结点的权值29.已知一棵完全二叉树的第6层(设根为第1层)有8个叶结点,则完全二叉树的结点个数最多是()。(A)39(B)52(C)111(D)11930.某二叉树中序序列为A,B,C,D