第6章 补充习题 2.docx

一、单选题1. 树最适合用来表示（ C ）。 A）有序数据元素B）无序数据元素C）元素之间具有分支层次关系的数据D）元素之间无联系的数据2. 设深度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至多为（ A ）。A）2h-1 B）2(h-1) C）2*h-1 D）2*h3. 在一棵二叉树中，第5层上的结点数最多有（ C ）。A）10 B）15 C）16 D）32 4. 下图所示的二叉树中，（ C ）不是完全二叉树。5. 有100个结点的完全二叉树,叶子结点的个数为:（ B ）。A）49 B）50 C）51 D）52说明:由完全二叉树的性质知:第100个结点的父结点为50，而且2*51100,即第51个结点无左孩子,为叶子结点,故叶子结点编号为:51- -100,叶子结点数为50。7. 具有100个结点的二叉树中，若用二叉链表存储，其指针域部分用来指向结点的左、右孩子，其中（ D ）个指针域为空。A）50 B）99 C）100 D）101说明:已知:n=n0+n1+n2,指针域为空个数:2*n0+n1=n0+n1+n2+1, 即n+1.8. 首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为（ C ）。 A）前序遍历 B）后序遍历 C）中序遍历 D）层次遍历9. 任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序（ A ）。A）不发生变化 B）发生变化C）不能确定 D）以上都不对10.某非空二叉树的前序序列和后序序列正好相反，则二叉树一定是（ B ）的二叉树。A）空或只有一个结点 B）高度等于其结点数C）任一结点无左孩子 D）任一结点无右孩子11.如果某二叉树的先序遍历序列是abdcef，中序遍历序列是dbaefc，则其后序遍历序列是（ D ）。A）dbafec B）fecdba C）efcdba D）dbfeca12.按照二叉树的定义，具有3个结点的二叉树形态有（C ）种。A）3 B）4 C）5 D）614.n个结点深度为h的二叉树的线索化所需的时间复杂度是（ C ）。A）O(1) B）O(hn) C）O(n) D）O(nlog2h)15.设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是（C ）。A）a是b祖先 B）a是b子孙 C）a在b左方 D）a在b右方16.关于二叉树的三种遍历，下列说法正确的是（ D ）。A）任意两种遍历序列都不可以唯一决定该二叉树B）任意两种遍历序列都可以唯一决定该二叉树C）先序遍历序列和后序遍历序列可以唯一决定该二叉树D）先序遍历序列和中序遍历序列可以唯一决定该二叉树18.已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是（ D ）。A）acbed B）decab C）deabc D）cedba19.前序遍历和中序遍历结果相同的二叉树为（ B ）。A）只有根结点的二叉树B）所有非叶子结点只有右子树的二叉树C）根结点无右孩子的二叉树D）根结点无左孩子的二叉树20.前序遍历和后序遍历结果相同的二叉树为（ A ）。A）只有根结点的二叉树B）所有非叶子结点只有右子树的二叉树C）根结点无右孩子的二叉树D）根结点无左孩子的二叉树21.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里我们把由树转化得到的二叉树叫做这棵树对应的二叉树。那么以下结论中，（ A ）是正确的。A）树的先根遍历序列与其对应的二叉树的先序遍历序列相同B）树的后根遍历序列与其对应的二叉树的后序遍历序列相同C）树的先根遍历序列与其对应的二叉树的中序遍历序列相同D）以上都不对22.若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是（ C ）。A）根结点无右子树的二叉树B）根结点无左子树的二叉树C）根结点可能有左二叉树和右二叉树D）各结点只有一个儿子的二叉树23.由分别带权为9,2,5,7的四个叶子结点构造一棵Huffman树，则该树的带权路径长度WPL为（ C ）。A）23 B）37 C）44 D）4624.有m个叶子结点的Huffman树所具有的结点总数为（ B ）。A）m+1 B）2m-1 C）2m D） 2m+126.若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过（B ）。A）n/2 B）n C）(n+1)/2 D）n+127.分别以下列序列构造二叉排序树，则与其它几个序列构造的结果不同的是（ C ）。A）（80，70，60，75，90，85，100，10）B）（80，90，85，70，60，10，75，100）C）（80，90，70，85，10，60，75，100）D）（80，90，100，70，85，60，10，75）28.若以二叉树的任一结点出发到根的路径上所经过的序列按其关键字有序,则该二叉树是（ C ）。A）二叉排序树 B）赫夫曼树 C）堆 D）线索二叉树29.以下说法错误的是（ B ）。A）存在这样的二叉树，对其采取任何次序的遍历其结点的访问序列均相同B）二叉树是树的特殊情形C）由树转化成二叉树，其根结点的右子树总是空的D）在二叉树只有一棵子树的情况下，也要指出是左子树还是右子树30.设F为一个森林，B为由F转换得到的二叉树，若F中有n个非终端结点，则B中右指针为空的结点有（ C ）。A）n-1 B）n C）n+1 D）n+2单选题参考答案：1. C 2.D 3.D 4.B 5.C 6.B 7.A 8.B 9.D 10.C11.A 12.C 13.B 14.B 15.A 16.D 17.D 18.A 19.C 20.C11.A 12.C 13.B 14.B 15.A 16.D 17.D 18.A 19.C 20.C二、判断题13.二叉树的后序遍历序列中，任意一个结点均处在其孩子结点的前面。( O )17.在某棵二叉树的一种序列中，如果发现其中每一结点的左孩子均是其前趋，则可判断定这种序列为中序序列。( O )25.用HUFFMAN算法求最优二叉树时,权越大的叶子离根越远。( O )( P ) ( O )三、计算题6. 已