1、下图所示的4棵二叉树中，不是完全二叉树的是（）2、二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法（）。
A 、正确B 、错误C 、不一定3、已知某二叉树的后序遍历序列是dabec ，中序遍历序列是debac ，它的前序遍历序列是（）。
A 、acbedB 、decabC 、deabcD 、cedba4、如果T2是由有序树T 转换而来的二叉树，那么T 中结点的后序就是T2中结点的（）。
A 、前序B 、中序C 、后序D 、层次序5、深度为5的二叉树至多有（）个结点。
A 、16B 、32C 、31D 、106、在一个非空二叉树的中序遍历序列中，根结点的右边（）。
A 、只有右子树上的所有结点B 、只有右子树上的部分结点C 、只有左子树上的部分结点D 、只有左子树上的所有结点7、树最适合用来表示（）。
A 、有序数据元素B 、无序数据元素C 、元素之间具有分支层次关系的数据D 、元素之间无联系的数据。
8、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）。
A 、不发生改变B 、发生改变C 、不能确定D 、以上都不对9、实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用（）存储结构。
A 、二叉链表B 、广义表存储结构C 、三叉链表D 、顺序存储结构10、对一个满二叉树，m 个树叶，n 个结点，深度为h ，则（）。
A 、n=m+hB 、h+m=2nC 、m=h-1D 、n=2h -111、设n ，m 为二叉树上的两个结点，在中序遍历时，n 在m 前的条件是（）。
A 、n 在m 右方B 、n 是m 祖先C 、n 在m 左方D 、n 是m 子孙12．已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/-，ABC D其前缀形式为( )A ．-A+B*C/DE B. -A+B*CD/E C ．-+*ABC/DE D. -+A*BC/DE 13.设有一表示算术表达式的二叉树（见右图），它所表示的算术表达式是（）A. A*B+C/(D*E)+(F-G) C. (A*B+C)/(D*E+（F-G ）) D. A*B+C/D*E+F-G14.在下述结论中，正确的是（）①只有一个结点的二叉树的度为0; ②二叉树的度为2；③二叉树的左右子树可任意交换; ④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。
A ．①②③B ．②③④C ．②④D ．①④15.设森林F 对应的二叉树为B ，它有m 个结点，B 的根为p,p 的右子树结点个数为n,森林F 中第一棵树的结点个数是（）A ．m-nB ．m-n-1C ．n+1D ．条件不足，无法确定16．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A ．9B ．11C ．15D ．不确定17．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）A ． 250B ．500C ．254D ．505E ．以上答案都不对18. 一个具有1025个结点的二叉树的高h 为（）A ．11B ．10C ．11至1025之间D ．10至1024之间19．深度为h 的满m 叉树的第k 层有（）个结点。
(1=<k=<h)A ．m k-1B ．m k -1C ．m h-1D ．m h -120.利用二叉链表存储树，则根结点的右指针是（）。
A ．指向最左孩子B ．指向最右孩子C ．空D ．非空21．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。
A ．先序 B. 中序 C. 后序 D. 从根开始按层次遍历22．若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( )遍历方法最合适。
A ．前序B ．中序C ．后序D ．按层次23．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）A．所有的结点均无左孩子B．所有的结点均无右孩子C．只有一个叶子结点D．是任意一棵二叉树24. 若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为( )A.X的双亲B.X的右子树中最左的结点C.X的左子树中最右结点D.X的左子树中最右叶结点25.线索二叉树是一种（）结构。
A．逻辑B．逻辑和存储C．物理D．线性26．n个结点的线索二叉树上含有的线索数为（）A．2n B．n－l C．n＋l D．n27．下面几个符号串编码集合中，不是前缀编码的是（）。
A．{0,10,110,1111} B．{11,10,001,101,0001}C．{00,010,0110,1000} D．{b,c,aa,ac,aba,abb,abc}28.当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组A[l..n]中时，数组中第i个结点的左孩子为（）A．A[2i](2i=<n) B. A[2i+1](2i+1=< n) C．A[i/2] D．无法确定29、高度为h的完全二叉树至少有多少个结点?至多有多少个结点?解：高度为h的完全二叉树至少有2h-1个结点，至多有2h-1个结点(也就是满二叉树)。
30、在什么样的情况下，等长编码是最优的前缀码?答：在每个字符的使用概率相同的情况下，也即在哈夫曼树中每片叶子的权重相等的时候，等长编码是最优的前缀码。
31.假设在树中，结点x是结点y的双亲时,用(x,y)来表示树边。
已知一棵树边的集合为{(i,m),(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)}用图表示出此树，并回答下列问题：(1)哪个是根结点? (2)哪些是叶结点? (3)哪个是g的双亲? (4)哪些是g的祖先?(5)哪些是g的孩子? (6)哪些是e的子孙? (7)哪些是e的兄弟?哪些是f的兄弟?(8)结点b和n的层次各是多少? (9)树的深度是多少? (10)以结点c为根的子树的深度是多少? (11) 树的度数是多少?答：这是测试我们对树的基本概念的掌握情况。
a是根结点；mndfjkl是叶结点；c是g的双亲；c,a是g的祖先；j,k是g的孩子；imn是e的子孙；d是e的兄弟，g,h是f的兄弟；b的层次是2，n的层次是5；树的深度是5；以c为根的子树深度是3；树的度数是3。
32、试找出分别满足下面条件的所有二叉树：(1)前序序列和中序序列相同；(2)中序序列和后序序列相同；(3)前序序列和后序序列相同；(4)前序、中序、后序序列均相同。
答：(1) 前序序列和中序序列相同的二叉树是：没有左子树的二叉树(右单支树)。
(2) 中序序列和后序序列相同的二叉树是：没有右子树的二叉树(左单支树)。
(3) 前序序列和后序序列相同的二叉树是：只有根结点的二叉树。
(4) 前序、中序、后序序列均相同的二叉树：只有根结点的二叉树。
33、对二叉树中的结点进行按层次顺序(每一层自左至右)的访问操作称为二叉树的层次遍历，遍历所得到的结点序列称为二叉树层次序列。
现已知一棵二叉树的层次序列为ABCDEFGHIJ,中序序列为DBGEHJACIF，请画出此二叉树。
解：A/ \BC/ \ \D E F/ \ /GHI\J34、对下图所示的森林：(1)求各树的前序序列和后序序列；(2)求森林的前序序列和后序序列；(3)将此森林转换为相应的二叉树；(4)给出(a)所示树的以双亲链表表示、孩子链表表示、双亲孩子链表表示及孩子兄弟链表表示等四种存储结构，并指出哪些存储结构易于求指定结点的祖先，哪些易于求指定结点的后代?解：(1) (a)的前序序列：ABCDEF 后序序列：BDEFCA(b)的前序序列：GHIJK 后序序列：IJKHG(c)的前序序列：LMPQRNO 后序序列：QRPMNOL(2) 此森林的前序序列：ABCDEFGHIJKLMPQRNO此森林的后序序列：BDEFCAIJKHGQRPMNOL(3)略(4)略35．完全二叉树中，结点个数为n，则编号最大的分支结点的编号为。
答：⎣n/2⎦36．二叉树结点的对称序序列为A,B,C,D,E,F,G,后序序列为B,D,C,A,F,G,E,则该二叉树结点的前序序列为(1),则该二叉树对应的树林包括(2)棵树。
答：(1)EACBDGF （2）237．具有n个结点的满二叉树，其叶结点的个数是______。
答：(n+1)/2设内部节点数为a，叶节点数为b，明显有a+b=n (1)，非空满二叉树中所有节点的出度正好等于入度，每个内部节点出度为2，叶节点出度为0，所有节点的出度和为2a；根节点入度为0，其他节点的入度为1，所有节点的入度和为a+b-1;因此有2a=a+b-1 (2)。
由(1)(2)得b=(n+1)/2，a=(n-1)/2。
另外可得b=a+1，也就是说，非空满二叉树的叶节点数正好比内部节点数多1。
38．设一棵后序线索树的高是50，结点x是树中的一个结点，其双亲是结点y,y 的右子树高度是31，x是y的左孩子。
则确定x的后继最多需经过______中间结点（不含后继及x本身）答：31（x的后继是经x的双亲y的右子树中最左下的叶结点）39．有一份电文中共使用6个字符:a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9，试构造一棵哈夫曼树，则其加权路径长度WPL为(1)，字符c的编码是(2)。
答：(1)80 (2)001（不唯一）40．下面是求二叉树高度的类C写的递归算法，试补充完整。
[说明]二叉树的两指针域为lchild与rchild, 算法中p为二叉树的根，lh和rh分别为以p为根的二叉树的左子树和右子树的高，hi为以p为根的二叉树的高，hi最后返回。
height(p){if ((1)){if(p->lchild==null) lh=(2); else lh=(3);if(p->rchild==null) rh=(4); else rh=(5);if (lh>rh) hi=(6)；else hi=(7);}else hi=(8);return hi;}//答：(1)p (2)0 (3)height(p->lchild) (4)0(5)height(p->rchild) (6)lh+1 (7)rh+1 (8)041．已知一棵满二叉树的结点个数为20到40之间的素数，此二叉树的叶子结点有多少个？答：结点个数在20到40的满二叉树且结点数是素数的数是31，其叶子数是16。
42．用一维数组存放的一棵完全二叉树；ABCDEFGHIJKL。