第6章树和二叉树(2)

第六章树和二叉树一、选择题1．算术表达式a+b*（c+d/e）转为后缀表达式后为（）A．ab+cde/*B．abcde/+*+C．abcde/*++D．abcde*/++2.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（）A．m-nB．m-n-1C．n+1D．条件不足，无法确定3．若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（）。A．n-1B．n/m-1C．(n-1)/(m-1)D．n/(m-1)-1E．(n+1)/(m+1)-14．深度为h的满m叉树的第k层有（）个结点。(1=k=h)A．mk-1B．mk-1C．mh-1D．mh-15.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为()A.X的双亲B.X的右子树中最左的结点C.X的左子树中最右结点D.X的左子树中最右叶结点6.引入二叉线索树的目的是（）A．加快查找结点的前驱或后继的速度B．为了能在二叉树中方便的进行插入与删除C．为了能方便的找到双亲D．使二叉树的遍历结果唯一7．由3个结点可以构造出多少种不同的二叉树？（）A．2B．3C．4D．58．下述编码中哪一个不是前缀码（）。A．（00，01，10，11）B．（0，1，00，11）C．（0，10，110，111）D．（1，01，000，001）二、判断题1.给定一棵树，可以找到唯一的一棵二叉树与之对应。2．将一棵树转成二叉树，根结点没有左子树；3.在中序线索二叉树中，每一非空的线索均指向其祖先结点。4.一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和。5．当一棵具有n个叶子结点的二叉树的WPL值为最小时，称其树为Huffman树，且其二叉树的形状必是唯一的。三、填空题1．一棵树T中，包括一个度为1的结点，两个度为2的结点，三个度为3的结点，四个度为4的结点和若干叶子结点，则T的叶结点数为______。【山东大学2001三、2(2分)】2．设二叉树中每个结点均用一个字母表示，若一个结点的左子树或右子树为空，用．表示，现前序遍历二叉树，访问的结点的序列为ABD.G...CE.H..F．．，则中序遍历二叉树时，访问的结点序列为(1)__;后序遍历二叉树时，访问的结点序列为(2)__。【南京理工大学1999二、3（4分）】3.在一棵存储结构为三叉链表的二叉树中，若有一个结点是它的双亲的左子女，且它的双亲有右子女，则这个结点在后序遍历中的后继结点是______。【中国人民大学2001一、4（2分）】4．具有n个结点的满二叉树，其叶结点的个数是______。【北京大学1994】5．有数据WG={7，19，2，6，32，3，21，10}，则所建Huffman树的树高是(1)__，带权路径长度WPL为(2)__。【南京理工大学1999三、6（4分）】6．有一份电文中共使用6个字符:a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9，试构造一棵哈夫曼树，则其加权路径长度WPL为(1)__，字符c的编码是(2)__。【中国矿业大学2000一、7（3分）】7．下面是中序线索树的遍历算法，树有头结点且由指针thr指向。树的结点有五个域，分别为数据域data，左、右孩子域lchild、rchild和左、右标志域ltag,rtag。规定，标志域为1是线索，O是指向孩子的指针。inordethread(thr){p=thr-lchild;while((1)______){while((2)_____)p=(3)___;printf(p-data);while((4)_________){p=(5)___；printf(p-data);}p=(6)_;}}【南京理工大学2000三、1（6分）】四、应用题1．从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。【西安电子科技大学2001软件二、1（5分）】2.由二叉树的中序序列及前序序列能唯一的建立二叉树，试问中序序列及后序序列是否也能唯一的建立二叉树，不能则说明理由，若能对中序序列DBEAFGC和后序序列DEBGFCA构造二叉树。【南京理工大学1998四、(3分)】3．对于二叉树T的两个结点n1和n2，我们应该选择树T结点的前序、中序和后序中哪两个序列来判断结点n1必定是结点n2的祖先,并给出判断的方法。不需证明判断方法的正确性。【复旦大学1999五(10分)】4．设二叉树BT的存储结构如下:12345678910Lchild00237580101DataJHFDBACEGIRchild0009400000其中BT为树根结点的指针，其值为6,Lchild,Rchild分别为结点的左、右孩子指针域,data为结点的数据域。试完成下列各题:（l）画出二叉树BT的逻辑结构;（2）写出按前序、中序、后序遍历该二叉树所得到的结点序列;（3）画出二叉树的后序线索树。【中国矿业大学2000二、(15分)】五、算法设计题1．设计算法返回二叉树T的先序序列的最后一个结点的指针，要求采用非递归形式，且不许用栈。2．设计算法：统计一棵二叉树中所有叶结点的数目及非叶结点的数目。【南开大学2000三、1】六，上机实验赫夫曼编/译码器要求：（1）建立赫夫曼树，生成赫夫曼编码，即实现算法6.12（2）实现编码，利用建立的赫夫曼树，对字符串“THISPROGRAMISMYFAVORITE”进行编码（3）实行译码，利用建立好的赫夫曼树，对上述编码进行译码。测试数据：字符集和频度字符频度空格186A64B13C22D32E103F21G15H47I57J1K5L32M20N57O63P15Q1R48S51T80U23V8W18X1Y16Z1