搜索
数据结构与算法上机作业第三章树一、选择题1、在一棵树中，如果结点A有3个兄弟，B是A的双亲，则B的度为DA.1B.2C.3D.42、深度为h的完全二叉树至少有D个结点，至多有B个结点A.2hB.2h-1C.2h+1D.2h-12^(h-1)-1+1=2^(h-1)前（n-1）层满，第h层只有一结点3、具有n个结点的满二叉树有C个叶结点。A.n/2B.(n-1)/2C.(n+1)/2D.n/2+1因为二叉树中，有这样一个性质，如果其终端结点数（也就是叶子节点）的个数为n1，度为2的结点数为n2，则n1=n2+1;假设叶子节点有x个，则度为2的个数为x-1：所以：2x-1=n;所以x=(n+1)/2(满二叉树)所以叶子节点个数为：(n+1)/2非终端结点为：(n+1)/2-14、一棵具有25个叶结点的完全二叉树最多有B个结点。A.48B.49C.50D.515、已知二叉树的先根遍历序列是ABCDEF，中根遍历序列是CBAEDF，则后根遍历序列是A。A.CBEFDAB.FEDCBAC.CBEDFAD.不定6、具有10个叶结点的二叉树中有B个度为2的结点。A.8B.9C.10D.117、一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足C。A.所有非叶结点均无左孩子B.所有非叶结点均无右孩子C.只有一个叶子结点D.A和B同时成立8、在线索二叉树中，t所指结点没有左子树的充要条件是B。A.t-left=NULLB.t-ltag=TRUEC.t-ltag=TRUE且t-left=NULLD.以上都不对9、n个结点的线索二叉树上含有的线索数为C。A.2nB.n-1C.n+1D.nn-1表示结点的左右子树，其余n-1指针为空线索取代原来的空链10、二叉树按照某种顺序线索化后，任一结点都有指向其前驱和后继的线索，这种说法B。A.正确B.错误C.不确定D.都有可能11、具有n(n1)个结点的完全二叉树中，结点i(2in)的左孩子结点是D。A.2iB.2i+1C.2i-1D.不存在12、具有64个结点的完全二叉树的深度为C。A.5B.6C.7D.813、将一颗有100个结点的完全二叉树从上到下、从左到右一次对结点进行编号，根结点的编号为1，则编号为45的结点的右孩子的编号为C。A.46B.47C.90D.912i举个简单的例子就可以看出来，比如7个节点时（也就是三层时），编号为1的左子树编号是2，编号2的左子树是4，编号3的左子树编号为6。。。。以此就可以看出来。左结点是2i,右结点才是2i+114、在结点数为n的堆中插入一个结点时，复杂度为C。A.O(n)B.O(n2)C.O(log2n)D.O(logn2)15、两个二叉树是等价的，则它们满足D。A.它们都为空B.它们的左右子树都具有相同的结构C.它们对应的结点包含相同的信息D.A、B和C16、包含n个元素的堆的高度为C。（符号「a表示取不小a最小整数）A.nB.「log2nC.「log2(n+1)D.n+117、以下说法错误的是B。A.存在这样的二叉树，对其采用任何次序的遍历其结点访问序列均相同B.二叉树是树的特殊情形C.由树转换成二叉树，其根结点的右子树总是空的D.在二叉树中只有一棵子树的情形下，也要指出是左子树还是右子树18、设F是一个森林，B是由F变换得到的二叉树。若F中有n个非终端结点，则B中没有右孩子的结点有C个。A.n-1B.nC.n+1D.n+219、将一棵树T转换为二叉树B，则T的后根序列是B的B。A.先根序列B.中根序列C.后根序列D.层次序列20、将一棵树转换为二叉树后，这颗二叉树的形态是A。A.唯一的，根结点没有左孩子B.唯一的，根结点没有右孩子C.有多种，根结点都没有左孩子D.有多种，根结点都没有右孩子树转换成二叉树，根节点是没有右孩子的，这由转换规则应该不难理解，且转换规则是唯一的，所以转换成的二叉树是唯一的21、设树T的度为4，其中度为1,2,3,4的结点个数分别为4,2,1,1，则T中的叶结点的个数为D。A.5B.6C.7D.822、设森林F中有三棵树，第一、第二、第三棵树的结点个数分别为M1,M2,M3。与森林F对应的二叉树根结点的右子树上的结点个数为D。A.M1-1B.M1+M2C.M2D.M2+M323、若以二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是C。A.二叉排序树B.哈夫曼树C.堆D.线索二叉树24、用5个权值{3,2,4,5,1}构造的哈夫曼树的带权路径长度是B。A.32B.33C.34D.15二、填空题1、一棵二叉树有67个结点，结点的度是0和2。问这棵二叉树中度为2的结点有33个。2、含A,B,C三个结点的不同形态的二叉树有5棵。3、含有4个度为2的结点和5个叶子结点的完全二叉树，有1或0个度为1的结点。4、具有100个结点的完全二叉树的叶子结点数为50。5、在用左右链表示的具有n个结点的二叉树中，共有2n个指针域，其中n-1个指针域用于指向其左右孩子，剩下的n+1个指针域是空的。6、如果一颗完全二叉树的任意一个非终结结点的元素都不小于其左儿子结点和右儿子结点(如果有的话)的元素，则称此完全二叉树为最大堆。7、堆是一种特殊形式的完全二叉树，对于最大堆而言，其根结点的元素的值应该是所有结点元素中最大的。8、二叉树的复制是指按照一棵已知的二叉树复制一个副本，使两者等价。复制二叉树最长用的方法是后根遍历递归算法。9、在定义堆时，通常采用结构体方式定义相应的二叉树，这样可以很容易实现其相关操作。10、在构建选择树时，根据孩子结点的获胜者确定他们双亲结点所得到的选择树称为胜者树。根据孩子结点的失败者确定他们双亲结点所得到的选择树称为败者树。11、树的表示方法包括数组、邻接表和左右链。12、表达式(a+b*(c-d))-e/f的波兰式(前缀式)是-+a*b-cd/ef，逆波兰式(后缀式)是abcd-*+ef/-。13、设F是由T1、T2、T3三棵树组成的森林，与F对应的二叉树为B。已知T1,T2,T3的结点数分别为n1,n2和n3，则二叉树B的左子树中有n1-1个结点，二叉树B的右子树中有n2+n3个结点。14、设二叉树的中根序列为ABCDEFG，后根序列为BDCAFGE。则该二叉树的先根序列为EACBDGF。该二叉树对应的森林中包含2棵树。15、先根次序遍历森林等同于按先根遍历对应的二叉树，后根次序遍历森林等同与按中根遍历对应的二叉树。16、一棵哈夫曼树有19个结点，则其叶子结点的个数为10。17、设有数据WG={7,19,2,6,32,3,21,10}叶节点权重集合，则所构建哈夫曼树的高是5，带权路径长度WPL为169。18、设有一份电文中共使用6个字符a,b,c,d,e,f，其中出现频率依次为2，3，4，7，8，19，则字符c的哈夫曼编码是001，电文编码的总长度为80。20、在有n个结点的哈夫曼树中，叶子结点总数为(n+1)/2，非叶结点的总数为(n-1)/2。三、试分别画出具有4个结点的二叉树的所有不同形态。四、已知一棵二叉树的中根序列和后根序列分别是BDCEAHFG和DECBHGFA，请画出此二叉树。五、已知非空二叉树T，写一个算法，求度为2的结点的个数。要求：1、定义二叉树的抽象数据类型和型BTREE，并定义基本操作。2、编写函数count2(BTREET)，返回度为2的节点的个数。3、在主函数中，构建一个二叉树，并验证所编写的算法。六、用递归方法写一个算法，求二叉树的叶子结点数intleafnum(BTREET)。要求：1、定义二叉树的抽象数据类型和型BTREE，并定义基本操作。2、编写函数leafnum(BTREET)，返回树T的叶子节点的个数。在主函数中，构建一个二叉树，并验证所编写的算法。七、画出下图所表示的二叉树的中序线索二叉树和先序线索二叉树。八、已知二叉树的先根序列是AEFBGCDHIKJ，中根序列是EFAGBCHKIJD，画出此二叉树，并画出后序线索二叉树。九、在中序线索二叉树中插入一个结点Q作为树中某个结点P的左孩子，试给出相应的算法。要求：1、定义中序线索二叉树的型THTREE以及基本操作。2、定义函数voidLInsert(THTREEP,THTREEQ);实现题目要求的操作。在主函数中，利用操作RInsert和LInsert构造一个线索二叉树，并中序输出二叉树的结点的元素，验证结果。#includeiostream#includeiomanip#includecmath#includecstdlib#includestringusingnamespacestd;typedefintelementtype;structnode{//节点的型node*lchild;node*rchild;boolltag;boolrtag;elementtypeelement;};typedefnode*head;//指向树根roottypedefnode*tree;//指向线索树的根节点voidmakeNull(head&h)//将线索二叉树置空{h-lchild=h;h-ltag=false;h-rchild=h;h-rtag=true;}headpointTotree(head&h,tree&t)//令head指向tree,注意head指向的并不是根节点，tree指向根节点{h-lchild=t;h-rchild=h;h-ltag=true;h-rtag=true;returnh;}//中根遍历的下一个节点node*inNext(node*p){node*q=p-rchild;if(p-rtag==true)//如果有右子树，找出右子树的最左节点while(q-ltag==true)q=q-lchild;returnq;}//中根遍历的上一个节点node*inPre(node*p){node*q=p-lchild;if(p-ltag==true)//如果P的左子树存在，则其前驱结点为左子树的最右结点while(q-rtag==true)q=q-rchild;returnq;//左子树的最右结点}//中序遍历voidthInOrder(headh){node*temp;temp=h;do{temp=inNext(temp);if(temp!=h)couttemp-element;}while(temp!=h);}//插入右孩子voidrInsert(node*s,node*r){node*w;r-rchild=s-rchild;r-rtag=s-rtag;r-lchild=s;r-ltag=false;//新插入的节点木有左子树，所以lchild指向的是父节点s-rchild=r;s-rtag=true;//原节点的右孩子为新插入的节点if(r-rtag==true){//这里是神马意思呢∑q|?Д?|p，就是如果被插节点s有右子树，//找出被插节点s的的next位置，即右子树中的最左节点，令其lchild指向新添加的节点r//因为插入前该最左节点的lchild指向的是原来节点sw=inNext(r);w-lchild=r;}}//插入左孩子voidlInsert(node*s,node*l){node*w;l-lchild=s-lchild;l-ltag=s-ltag;l-rchild=s;l-rtag=false;s-lchild=l;s-ltag=true;if(l-ltag==true){//与插入右孩子方法相似，只需把左右方向对调即可w=inPre(l);w-rchild=l;}}intmain(){headh=newnode;node*root=newnode;node*lc=newnode;node*rc=newnode;node*c=newnode;root-element=1;lc-element=2;rc-element=3;c-