树和二叉树自测试题

经典word整理文档，仅参考，双击此处可删除页眉页脚。本资料属于网络整理，如有侵权，请联系删除，谢谢！第六章树1树27456891、________________XX是它的任一子树的根结点惟一的________。2、________B是AA是B3、一般的，二叉树有____________左子树____________4、i(i>=1)层上至多有_____5、k(k>=1)的二叉树至多有_____6、2n2，则叶子数_____。7、满二叉树上各层的节点数已达到了二叉树可以容纳的____________8、n个结点的完全二叉树的深度为______。9、ni(1<=i<=n)X1）若i=1,X______1,则XPARENT(X)__i/2____。2）若2i>nX_左孩子___________；否则，XLCHILD(X)__2i____。3）若2i+1>nX______XRCHILD(X)的编号为__为2i+1____。10.______链式_____11.每个二叉链表的访问只能从______12.对二叉链表的访问只能从______指针开始，若二叉树为空，则13.二叉链表中每个存储结点的每个指针域必须有一个值，这个值或者是___指向孩子的___________Null____。14.n个结点的二叉树中,__2n______,__n-1__________n+1____NULL。15．二叉树有不同的链式存储结构，其中最常用的是________________。16．可通过在非完全二叉树的“残缺”位置上增设“_______countleaf(bitreptrt,int*countleaf(t->lchild,&count);countleaf(t->rchild,&count);_}}18________________________19、R分别表示二叉树的三项子任务，限定“先左后右”，这样可能的次序有：________、________________三种，按这三种次序进行的遍历分别称为________________、________。20__________________________非终端节点________22Tn,……，npip1kinnlT进行分类的平均比较次数为________。1ii23的数组,令数组每个元素由四个域组成：的权值；rchild分别为结点的左、右孩子指针；struct{float/*权值指针域intparent,lchildrchild;hftree[2*n-1];k,floati,j,x,y;/*Wfloat{T[i].parent=-1;T[i].lchild=-1;T[i].rchild=-1;else}for(i=0;i<k-1;i++){for(j=0;j<k=i;j++)elseif((T[j].wt<n)&&(T[j].parint==-1)){n=T[j].wt;y=j;}}24________25_______***26n个结点的完全二叉树，若按层次从上到下、从左到右对其编，号（根结点为1号最大的分支结点序号是___________1______n______+1______。．二叉树的先根遍历序列中，除根结点外，任一结点均处在其双亲结点的__后面______。．先根遍历树和先根遍历与该树对应的二叉树，其结果________。．树与二叉树之间最主要的差别是：二叉树中各结点的子树要区分为______________，即使在结点只有一棵子树的情况下，也要明确指出该子树是_左子树_______________。***30______．哈夫曼树是带权路径度________的树，通常权值较大的结点离根________。m个叶子结点的哈夫曼树，其结点总数为__2m-1______。33_____A_________e,j,H_3_________4______5_______F的儿子结点是__j,k______，G的父结点是___c_____。．树的结点数目至少为__1_________0_____。35________2，而________2。．结点最少的树为________，结点最少的二叉树为________。37，则该二叉树中，左、右子树皆非空的结点个数为___n-1____。nm1_____n+1-2m___，问有___5_____________。．以数据集{456，7101218}__________165______。41m个叶子结点的哈夫曼树上的结点数是___2m-1_____。423213243__12______43T4123和4421和1T________。1．(1)③树形结构可以表达()(及一切树形结构)是一种""2(3)3(4)&&4(4)1nn56的二叉树最多有()(2)61(4(3))nn-1n5floor(log9k023**10.(4)2(1)11(4)2222122***13T4n1,n2,n3,n4,T转换成一棵二叉树后，且根结点的右子树上有（4n-11nnT4n1,n2,n3,n4,T一棵二叉树后，且根结点的左孩子上有（1n-11nn1123234112323415.2012．讨论树、森林和二叉树的关系，目的是为了（12.）17）18.dabec,deabc,4）**19.TTTT1）②2220TTTT2）2221abdgcefh,dgbaechf,（4）④22.323242252(1)(2)(2)26(275的二叉树至多有(3)28、在计算递归函数时，如不使用递归过程，则一般情况下必须借助于（129.(Heap)是(2)30(4)2222310h的满二叉树中的结点个数是（4）2h2h-12-12-1h+1h32、设二叉树结点的先根序列、中根序列和后根序列中，所有叶子结点的先后顺序(2)33(2)34(3)35(1)k的nk-12-1n-2kk-1k-136()37(3)1234(1)?(2)?(3)G?(4)G?(5)G?(6)E?(7)E?C的兄弟?(8)B和I?(9)?(10)G为根的子树的深度是多少?(11)556377-18a9.1）2（310和EDCBHGEA11．试分别画出图简答题121314157183325261281617及GDHBEACIJF188719632310，819201、以二叉链表为存储结构，分别实现二叉树的下列运算:1(BT,X)；2