计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编6(总分：88.00，做题时间：90分钟)一、单项选择题(总题数：33，分数：66.00)1.一棵完全二叉树又是一棵( )。
【华中科技大学2006一、7(2分)】A.平衡二叉树B.堆√C.二叉排序树D.哈夫曼(Huffman)树完全二叉树的叶子至多在下面两层上，且一个结点若无左子树，绝不能有右子树。
平衡二叉树任何结点的左右子树的高度差的绝对值不超过1，但其结点的值符合二叉排序树的定义。
平衡二叉树(包括二叉排序树)的树形不一定是完全二叉树。
堆是一个序列，有大堆和小堆，编号为i的结点，其父结点、左右子女结点之间位置的关系，符合完全二叉树父结点、左右子女结点之间的关系，从这点上说，可以把堆看成完全二叉树。
哈夫曼树是二叉树，但树形不一定满足完全二叉树的定义。
2.一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是( )。
【合肥工业大学1999一、5(2分)】A.不确定B.0C.1D.2 √左子树为空的二叉树的根结点的左线索为空(无前驱)，先序序列的最后结点的右线索为空(无后继)，共2个空链域。
3.一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是( )。
【合肥工业大学2000一、5(2分)】A.0B.1 √C.2D.不确定4.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为( )。
【南京理工大学1996一、6(2分)】A.X的双亲B.X的右子树中最左的结点C.X的左子树中最右结点√D.X的左子树中最右叶结点5.引入二叉线索树的目的是( )。
【南京理工大学1998一、5(2分)】A.加快查找结点的前驱或后继的速度√B.为了能在二叉树中方便地进行插入与删除C.为了能方便地找到双亲D.使二叉树的遍历结果唯一6.线素二叉树是一种( )结构。
【西安电子科技大学1996一、9(2分)】A.逻辑B.逻辑和存储C.物理√D.线性7.甩个结点的线索二叉树上含有的线索数为( )。
【中山大学1998二、8(2分)】B.n-1C.n+1 √D.n线索二叉树是利用二叉树的空链域加上线索，n个结点的二叉树有n+1个空链域。
8.( )的遍历仍需要栈的支持。
【中科院计算所1999一、1(2分)】A.前序线索树B.中序线索树C.后序线索树√9.二叉树在线素化后，仍不能有效求解的问题是( )。
【北方交通大学2003一、4(2分)】A.先序线索二又树中求先序后继B.中序线索二叉树中求中序后继C.中序线索二叉树中求中序前驱D.后序线索二叉树中求后序后继√答案应选D。
其实，先序线索二叉树求先序前驱也不能有效求解。
10.在线索二叉树中，下面说法不正确的是( )。
【南京理工大学2004一、8(1分)】A.在中序线索树中，若某结点有右孩子，则其后继结点是它的右子树的左支末端结点B.线索二叉树是利用二叉树的n+1个空指针来存放结点前驱和后继信息的C.每个结点通过线索都可以直接找到它的前驱和后继√D.在中序线索树中，若某结点有左孩子，则其前驱结点是它的左子树的右支末端结点11.采用双亲表示法表示树，则具有n个结点的树至少需要( )个指向双亲的指针。
【中山大学2004】A.nB.n+1C.n-1 √D.2n树的双亲表示法除根结点外，每个结点都有一个指向双亲的指针。
12.树用孩子兄弟表示法，每个结点有两个指针域，分别指向“第一个孩子”和“下一个兄弟”。
若指向“下一个兄弟”的指针有n个为空，则该树有( )个非终端结点。
【哈尔滨工程大学2004】A.[n／2]B.n-1 √C.nD.n+113.设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个数为n，森林F中第一棵树的结点个数是( )。
【南京理工大学2000一、17(1．5分)】A.m-n √B.m-n-1C.n+lD.条件不足，无法确定14.设森林F中有三棵树，第一、第二、第三棵树的结点个数分别为M1、M2和M3。
与森林F对应的二叉树根结点的右子树上的结点个数是( )。
【北方交通大学2001一、16(2分)】A.M1B.M1+M2C.M3D.M2+M3 √15.设F是一个森林，B是由F变换得的二叉树。
若F中有n个非终端结点，则B中右指针域为空的结点有( )个。
【西安电子科技大学1998一、10(2分)】A.n-1B.nC.n+1 √16.如果T 2是由有序树T转换而来的二叉树，那么T中结点的后序就是T 2中结点的( )。
【西安电子科技大学1996一、2(2分)】【电子科技大学2005一、7(1分)】A.先序B.中序√C.后序D.层次序17.由3个结点可以构造出多少种不同的有向树?( )【北方交通大学2001一、6(2分)】A.2 √B.3C.4D.5n(n>0)个结点可以构造出1／(n+1)木(2n)!／(n!) 2种不同的二叉树。
n个结点构造的不同的树的数量等于n一1个结点可以构造出的不同的二叉树的数量。
18.含有4个结点的二叉树有( )种树型。
【北京邮电大学2005一、5(2分)】A.4B.5C.10D.14 √19.由3个结点可以构造出多少种不同的二叉树?( )【北方交通大学2001一、7(2分)】A.2B.3C.4D.5 √20.一棵共有n个结点的树，其中所有分支结点的度均为k 2则该树中叶子结点的个数为( )。
【华南理工大学2005一、1(2分)】A.n(k-1)／kB.n／kC.(n+1)／kD.(nk-n+1)／k √21.下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序( )。
【中国科技大学1998二、8(2分)】【中科院计算所1998二、8(2分)】【北京工业大学2005一、5(2分)】【电子科技大学2005一、1(1分)】【南京理工大学2004一、10(1分)】A.二叉排序树B.哈夫曼树C.AVL树D.堆√22.具有n个结点，其路径长度最短的二叉树是( )。
【电子科技大学2005一、3(1分)】A.哈夫曼树√B.完全二叉树C.AVL树D.二叉排序树23.在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树，该说法( )。
【中国科技大学1998二、10(2分)】【中科院计算所1998二、10(2分)】A.正确B.错误√24.设二叉树只有度为0和2的结点，其结点个数是15，则该二叉树最大深度为( )。
【北京理工大学2007一、8(1分)】A.4C.8 √D.925.一棵Huffman树共有215个结点，对其进行Huffrnan编码，共能得到( )个不同的码字。
【北京邮电大学2005一、6(2分)】A.107B.108 √C.214D.21526.设哈夫曼编码的长度不超过4，若已对两个字符编码为1和01，则还可以对( )字符编码。
【哈尔滨工程大学2005】A.2B.3C.4 √D.5因为哈夫曼编码长度不超过4，且已有两个字符编码为1和01，则还可以最多为4个字符编码，这4个字符的编码分别为0000，0001，0010，0011。
27.若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为( )。
【中科院计算所：1999一、2(2分)】A.n-1B.[n／m]一1C.[(n-1)／(m-1)] √D.[n／(m-1)]一1E.[(n+1)／(m+1)]一128.下述编码中哪一个不是前缀码? ( )【中科院计算所2000一、2(2分)】A.(00，01，10，11)B.(0，1，00，11) √C.(0，10，1 10，111)D.(1，01，000，001)29.下述编码哪一组不是前缀码?( )【哈尔滨工业大学2004二、1(1分)2005二、1(1分)】A.{00，01，10，11)B.{0，1，00，11) √C.{0，10，110，111)D.{000．001，010，101)30.下列编码中，( )不是前缀码。
【湖南大学2003】A.{00，01，10，11}B.{0，1，00，11) √C.{0，10，110，111)D.{10，110，1110，1111)31.有5个字符，根据其使用频率设计对应的哈夫曼编码，以下( )是可能的哈夫曼编码。
【武汉大学2006】A.000，001，010，011，1 √B.0000，0001，001，01，1 √C.000，001，01，10，11 √D.00，100，101，110，111D之所以错误，是因为若有编码00，至少必须有编码01，否则只一个结点不可能构成双亲。
32.现有一“遗传”关系，设x是y的父亲，则x可以把它的属性遗传给y，表示该遗传关系最适合的数据结构为( )。
【中国科学院2006】A.向量B.树√D.二叉树33.一棵深度为7的满二叉树共有( )非终端结点。
【北京邮电大学2007】A.3 1B.63 √C.127D.255二、填空题(总题数：11，分数：22.00)34.在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是__________。
【厦门大学2002六、3(4分)】__________________________________________________________________________________________ 正确答案：(正确答案：用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加“虚结点”。
设编号为i和j的结点在顺序存储中的下标为s和t，则结点i和j在同一层上的条件是[log 2 s]=[log 2 t]。
)35.一棵有n个结点的满二叉树有(1)个度为1的结点、有(2)个分支(非终端)结点和(3)个叶子，该满二叉树的深度为(4)。
【华中理工大学2000一、6(3分)】__________________________________________________________________________________________ 正确答案：(正确答案：(1)0 (2)(n—1)／2或[n／2] (3)(n+1)／2 (4)log 2 (n+1))36.设只含根结点的二又树的高度为0，则高度为尼的二又树的最大结点数为__________，最小结点数为__________。
【北京大学1997一、1(4分)】__________________________________________________________________________________________ 正确答案：(正确答案：(1)2 k+1一1 (2)k+1)37.完全二叉树结点的平衡因子取值只可能为__________。
【电子科技大学2008二、1(1分)】__________________________________________________________________________________________ 正确答案：(正确答案：1，0，一1)38.高度为K的完全二叉树至少有——个叶子结点。