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

一、选择题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．算术表达式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. 41 B. 82 C. 113 D. 1224. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ）A．5 B．6 C．7 D．85. 在下述结论中，正确的是（ ）①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A．①②③ B．②③④ C．②④ D．①④6. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ ）A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定7．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）A．9 B．11 C．15 D．不确定8．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3与森林F对应的二叉树根结点的右子树上的结点个数是（ ）A．M1 B．M1+M2 C．M3 D．M2+M39．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）A． 250 B． 500 C．254 D．505 E．以上答案都不对 10. 设给定权值总数有n 个，其哈夫曼树的结点总数为( )A．不确定 B．2n C．2n+1 D．2n-111．若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（ ）。

A．n-1 B．ën/mû-1 C．é(n-1)/(m-1)ù D． én/(m-1)ù-1 E．é(n+1)/(m+1)ù-112. 有关二叉树下列说法正确的是（ ）A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为213．二叉树的第I层上最多含有结点数为（ ）A．2I B． 2I-1-1 C． 2I-1 D．2I -114. 一个具有1025个结点的二叉树的高h为（ ）A．11 B．10 C．11至1025之间 D．10至1024之间15．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点A．2h B．2h-1 C．2h+1 D．h+1 16．对于有n 个结点的二叉树, 其高度为（ ）A．nlog2n B．log2n C．ëlog2nû|+1 D．不确定17. 一棵具有 n个结点的完全二叉树的树高度（深度）是（ ）A．ëlognû+1 B．logn+1 C．ëlognû D．logn-118．深度为h的满m叉树的第k层有（ ）个结点。

1=

A．前序 B．中序 C．后序 D．按层次26．在下列存储形式中，哪一个不是树的存储形式？（ ）A．双亲表示法 B．孩子链表表示法 C．孩子兄弟表示法 D．顺序存储表示法27．一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ ）A．CABDEFG B．ABCDEFG C．DACEFBG D．ADCFEG 28. 对n（n≥2）个权值均不相同的字符构成的哈夫曼树，关于该树的叙述，错误的是( )A. 该树一定是一颗完全二叉树 B. 树中两个权值最小的结点一定是兄弟结点C. 树中一定没有度为1的结点 D. 树中任一非叶结点的权值一定不小于下一层任一结点的权值29. 已知一棵完全二叉树的第6层(设根为第1层)有8个叶结点,则完全二叉树的结点个数最多是( )A)39 (B)52 (C)111 (D)11930. 某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则前序序列是：A．E,G,F,A,C,D,B B．E,A,C,B,D,G,F C．E,A,G,C,F,B,D D．上面的都不对 31．二叉树的先序遍历：EFHIGJK；中序遍历: HFIEJKG 。

该二叉树根的右子树的根是（ ）A、 E B、 F　 C、 G　 D、 H 32．将一棵树t 转换为孩子—兄弟链表表示的二叉树h，则t的后根序遍历是h 的A．前序遍历 B．中序遍历 C．后序遍历（ ）33. 某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号为1，2，… ，n，且有如下性质：T中任一结点V，其编号等于左子树上的最小编号减1，而V的右子树的结点中，其最小编号等于V左子树上结点的最大编号加1这时是按( )编号的A.中序遍历序列 B.前序遍历序列 C.后序遍历序列 D.层次顺序34．下面的说法中正确的是（ ）.（1）任何一棵二叉树的叶子结点在三种遍历中的相对次序不变；（2）按二叉树定义，具有三个结点的二叉树共有6种A．(1)(2) B．(1) C．(2) D．(1)、(2)都错36．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）A．所有的结点均无左孩子B．所有的结点均无右孩子C．只有一个叶子结点D．是任意一棵二叉树37．在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（ ）A．都不相同　　B．完全相同 C．先序和中序相同，而与后序不同　 D．中序和后序相同，而与先序不同38．某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。

A．空或只有一个结点 B．任一结点无左子树 C．高度等于其结点数 D．任一结点无右子树39．在完全二叉树中，若一个结点是叶结点，则它没（ ） A．左子结点 B．右子结点　 C．左子结点和右子结点 D．左子结点，右子结点和兄弟结点40．在下列情况中，可称为二叉树的是（ ） A．每个结点至多有两棵子树的树 B. 哈夫曼树 C．每个结点至多有两棵子树的有序树 D. 每个结点只有一棵右子树 E．以上答案都不对41. 一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是：( )A．不确定 B. 0 C. 1 D. 242. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：( )A. 0 B. 1 C. 2 D. 不确定43. 若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为( ) A.X的双亲 B.X的右子树中最左的结点 C.X的左子树中最右结点 D.X的左子树中最右叶结点44. 引入二叉线索树的目的是（ ）A．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一45. 线索二叉树是一种（ ）结构。

A． 逻辑 B． 逻辑和存储 C． 物理 D．线性46．n个结点的线索二叉树上含有的线索数为（ ）A．2n B．n－l C．n＋l D．n 47．（ ）的遍历仍需要栈的支持.A．前序线索树 B．中序线索树 C．后序线索树 48．二叉树索后，仍不能有效求解的问题是（ ）A．前（先）序线索二叉树中求前（先）序后继 B．中序线索二叉树中求中序后继C．中序线索二叉树中求中序前驱 D．后序线索二叉树中求后序后继49. F是一森林，B是由F变换的二叉树若F中有n个非终端结点，则B中右指针域为空的结点有（ ）个A． n-1 B．n C． n+1 D． n+250．如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2中结点的（ ）A．先序 B．中序 C．后序 D．层次序51．由3 个结点可以构造出多少种不同的二叉树？（ ）A．2 。