40．下面的说法中正确的是（ ）.
（1）任何一棵二叉树的叶子结点在三种遍历中的相对次序不变；
（2）按二叉树定义，具有三个结点的二叉树共有6种。
a．(1)(2) b．(1) c．(2) d．(1)、(2)都错 【南京理工大学 2001 一、10 （1.5分）】
41．对于前序遍历与中序遍历结果相同的二叉树为（1）;
对于前序遍历和后序遍历结果相同的二叉树为（2）。【中科院计算所 1999 一、4 （4分）】
a．一般二叉树 b．只有根结点的二叉树 c．根结点无左孩子的二叉树
d．根结点无右孩子的二叉树 e．所有结点只有左子数的二叉树 f．所有结点只有右子树的二叉树
42．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）
【南开大学 2000 一、2】
a．所有的结点均无左孩子b．所有的结点均无右孩子c．只有一个叶子结点d．是任意一棵二叉树
43．在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（ ）
a．都不相同 b．完全相同 c．先序和中序相同，而与后序不同
d．中序和后序相同，而与先序不同 【北方交通大学 2001 一、25 （2分）】
44．某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。【武汉大学2000二、4】
a．空或只有一个结点 b．任一结点无左子树 c．高度等于其结点数 d．任一结点无右子树
45．在完全二叉树中，若一个结点是叶结点，则它没（ ）。【北方交通大学 2001 一、22 （2分）】
a．左子结点 b．右子结点 c．左子结点和右子结点 d．左子结点，右子结点和兄弟结点
46．在下列情况中，可称为二叉树的是（ ）
a．每个结点至多有两棵子树的树 b. 哈夫曼树 c．每个结点至多有两棵子树的有序树
d. 每个结点只有一棵右子树 e．以上答案都不对 【西安交通大学 1996 三、4 (3分)】
47. 一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是：( )
a．不确定 b. 0 c. 1 d. 2 【合肥工业大学 1999 一、5 （2分）】
48. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：( )。
a. 0 b. 1 c. 2 d. 不确定 【合肥工业大学 2000 一、5 （2分）】
49. 若x是二叉中序线索树中一个有左孩子的结点，且x不为根，则x的前驱为( )
【南京理工大学1996 一、6 (2分)】
a.x的双亲 b.x的右子树中最左的结点 c.x的左子树中最右结点 d.x的左子树中最右叶结点
50. 引入二叉线索树的目的是（ ）
a．加快查找结点的前驱或后继的速度 b．为了能在二叉树中方便的进行插入与删除
c．为了能方便的找到双亲 d．使二叉树的遍历结果唯一【南京理工大学1998 一、5 （2分）】
51. 线索二叉树是一种（ ）结构。
a． 逻辑 b． 逻辑和存储 c． 物理 d．线性【西安电子科技大学1996 一、9 （2分）】
52．n个结点的线索二叉树上含有的线索数为（ ）
a．2n b．n－l c．n＋l d．n 【中山大学 1998 二、8 （2分）】
53．（ ）的遍历仍需要栈的支持.
a．前序线索树 b．中序线索树 c．后序线索树 【中科院计算所 1999 一、1 （2分）】
54．二叉树在线索后，仍不能有效求解的问题是（ ）。
a．前（先）序线索二叉树中求前（先）序后继 b．中序线索二叉树中求中序后继
c．中序线索二叉树中求中序前驱 d．后序线索二叉树中求后序后继 【武汉大学2000 二、3 二、5】
55. 设f是一个森林，b是由f变换得的二叉树。若f中有n个非终端结点，则b中右指针域为空的结点有（ ）个。
a． n-1 b．n c． n+1 d． n+2 【西安电子科技大学1998 一、10 （2分）】
56．如果t2是由有序树t转换而来的二叉树，那么t中结点的后序就是t2中结点的（ ）。
a．先序 b．中序 c．后序 d．层次序 【西安电子科技大学1996 一、2 （2分）】
57. 由3 个结点可以构造出多少种不同的有向树？（ ）
a．2 b．3 c．4 d．5 【北方交通大学 2001 一、6 （2分）】
58．由3 个结点可以构造出多少种不同的二叉树？（ ）
a．2 b．3 c．4 d．5 【北方交通大学 2001 一、7 （2分）】
59.下述二叉树中,哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序（）。
a．二叉排序树 b．哈夫曼树 c．avl树 d．堆
【中国科技大学1998二、8（2分）】【中科院计算所1998二、8(2分）】
60．在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树，该说法（ ）。
a．正确 b．错误 【中国科技大学1998 二、10（2分）】【中科院计算所1998 二、10（2分）】
61．最优二叉树（哈夫曼树）、最优查找树均为平均查找路径长度 最小的树，其中对最优二叉树，n表示（1），对最优查找树，n表示（2），构造这两种树均（3）。【中科院计算所1999一、3 (6分）】
a．结点数 b．叶结点数 c．非叶结点数 d．度为2的结点数 e．需要一张n个关键字的有序表
f．需要对n个关键字进行动态插入 g．需要n个关键字的查找概率表 h．不需要任何前提
62．下述编码中哪一个不是前缀码（ ）。【中科院计算所 2000 一、2 （2分）】
a．（00，01，10，11） b．（0，1，00，11） c．（0，10，110，111） d．（1，01，000，001）
63．下面几个符号串编码集合中，不是前缀编码的是（ ）。
a．{0,10,110,1111} b．{11,10,001,101,0001} c．{00,010,0110,1000}
d．{b,c,aa,ac,aba,abb,abc} 【西安电子科技大学2001 应用 一、6（2分）】
64. 当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组 a[l..n]中时，数组中第i个结点的左孩子为（ ）【南京理工大学 1999一、18(2分）】
a．a[2i](2i=
责任编辑：小草
