数据结构与算法上机作业

数据结构与算法上机作业第三章树一、选择题1、在一棵树中,如果结点A有3个兄弟,B就是A得双亲,则B得度为D A、1 B、2 C、3 D、42、深度为h得完全二叉树至少有D个结点,至多有B个结点 A、2h B、2h-1 C、2h+1 D、2h-13、具有n个结点得满二叉树有C个叶结点。 A、n/2 B、(n-1)/2 C、(n+1)/2 D、n/2+14、一棵具有25个叶结点得完全二叉树最多有C个结点。 A、48 B、49 C、50 D、515、已知二叉树得先根遍历序列就是ABCDEF,中根遍历序列就是CBAEDF,则后根遍历序列就是A。 A、CBEFDA B、FEDCBA C、CBEDFA D、不定6、具有10个叶结点得二叉树中有B个度为2得结点。 A、8 B、9 C、10 D、117、一棵非空二叉树得先序遍历序列与后序遍历序列正好相反,则该二叉树一定满足B。 A、所有非叶结点均无左孩子 B、所有非叶结点均无右孩子 C、只有一个叶子结点 D、A与B同时成立8、在线索二叉树中,t所指结点没有左子树得充要条件就是D。 A、t->left=NULL B、t->ltag=TRUE C、t->ltag=TRUE且t->left=NULL D、以上都不对9、n个结点得线索二叉树上含有得线索数为C。 A、2n B、n-1 C、n+1 D、n10、二叉树按照某种顺序线索化后,任一结点都有指向其前驱与后继得线索,这种说法B。 A、正确 B、错误 C、不确定 D、都有可能11、具有n(n>1)个结点得完全二叉树中,结点i(2i>n)得左孩子结点就是D。 A、2i B、2i+1 C、2i-1 D、不存在12、具有64个结点得完全二叉树得深度为C。 A、5 B、6 C、7 D、813、将一颗有100个结点得完全二叉树从上到下、从左到右一次对结点进行编号,根结点得编号为1,则编号为45得结点得右孩子得编号为D。 A、46 B、47 C、90 D、9114、在结点数为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、n B、「log2n C、「log2(n+1) D、n+117、以下说法错误得就是B。 A、存在这样得二叉树,对其采用任何次序得遍历其结点访问序列均相同 B、二叉树就是树得特殊情形 C、由树转换成二叉树,其根结点得右子树总就是空得 D、在二叉树中只有一棵子树得情形下,也要指出就是左子树还就是右子树18、设F就是一个森林,B就是由F变换得到得二叉树。若F中有n个非终端结点,则B中没有右孩子得结点有C个。 A、n-1 B、n C、n+1 D、n+219、将一棵树T转换为二叉树B,则T得后根序列就是B得B。 A、先根序列 B、中根序列 C、后根序列 D、层次序列20、将一棵树转换为二叉树后,这颗二叉树得形态就是B。 A、唯一得,根结点没有左孩子 B、唯一得,根结点没有右孩子 C、有多种,根结点都没有左孩子 D、有多种,根结点都没有右孩子21、设树T得度为4,其中度为1,2,3,4得结点个数分别为4,2,1,1,则T中得叶结点得个数为D。 A、5 B、6 C、7 D、822、设森林F中有三棵树,第一、第二、第三棵树得结点个数分别为M1,M2,M3。与森林F对应得二叉树根结点得右子树上得结点个数为D。 A、M1-1 B、M1+M2 C、M2 D、M2+M323、若以二叉树得任一结点出发到根得路径上所经过得结点序列按其关键字有序,则该二叉树就是C。 A、二叉排序树 B、哈夫曼树 C、堆 D、线索二叉树24、用5个权值{3,2,4,5,1}构造得哈夫曼树得带权路径长度就是C。 A、32 B、33 C、34 D、15二、填空题1、一棵二叉树有67个结点,结点得度就是0与2。问这棵二叉树中度为2得结点有33个。2、含A,B,C三个结点得不同形态得二叉树有0棵。3、含有4个度为2得结点与5个叶子结点得完全二叉树,有1个度为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-*+e/f-。13、设F就是由T1、T2、T3三棵树组成得森林,与F对应得二叉树为B。已知T1,T2,T3得结点数分别为n1,n2与n3,则二叉树B得左子树中有n1-1个结点,二叉树B得右子树中有n2+n3个结点。14、设二叉树得中根序列为ABCDEFG,后根序列为BDCAFGE。则该二叉树得先根序列为EGCBDGF。该二叉树对应得森林中包含2棵树。15、先根次序遍历森林等同于按先根遍历对应得二叉树,后根次序遍历森林等同与按中根遍历对应得二叉树。16、一棵哈夫曼树有19个结点,则其叶子结点得个数为10。17、设有数据WG={7,19,2,6,32,3,21,10}叶节点权重集合,则所构建哈夫曼树得高就是6,带权路径长度WPL为261。18、设有一份电文中共使用6个字符a,b,c,d,e,f,其中出现频率依次为2,3,4,7,8,19,则字符c得哈夫曼编码就是001,电文编码得总长度为96。20、在有n个结点得哈夫曼树中,叶子结点总数为(n+1)/2,非叶结点得总数为(n-1)/2。三、试分别画出具有4个结点得二叉树得所有不同形态。四、已知一棵二叉树得中根序列与后根序列分别就是BDCEAHFG与DECBHGFA,请画出此二叉树。五、已知非空二叉树T,写一个算法,求度为2得结点得个数。要求: 1、定义二叉树得抽象数据类型与型BTREE,并定义基本操作。 2、编写函数count2(BTREET),返回度为2得节点得个数。 3、在主函数中,构建一个二叉树,并验证所编写得算法。六、用递归方法写一个算法,求二叉树得叶子结点数intleafnum(BTREET)。要求:定义二叉树得抽象数据类型与型BTREE,并定义基本操作。编写函数leafnum(BTREET),返回树T得叶子节点得个数。在主函数中,构建一个二叉树,并验证所编写得算法。七、画出下图所表示得二叉树得中序线索二叉树与先序线索二叉树。八、已知二叉树得先根序列就是AEFBGCDHIKJ,中根序列就是EFAGBCHKIJD,画出此二叉树,并画出后序线索二叉树。九、在中序线索二叉树中插入一个结点Q作为树中某个结点P得左孩子,试给出相应得算法。要求:定义中序线索二叉树得型THTREE以及基本操作。定义函数voidLInsert(THTREEP,THTREEQ);实现题目要求得操作。在主函数中,利用操作RInsert与LInsert构造一个线索二叉树,并中序输出二叉树得结点得元素,验证结果。十、假设现在有如下得元素:7、16、49、82、5、31、6、2、44。画出将每一个元素插入堆中以后得最大堆。要求:利用基本操作Insert得基本原理,先用第一个元素7构成一个二叉树,然后将第二个元素16插入该二叉树中,再将第三个元素49插入堆中,……,直到最后一个元素插入为止。上述过程要求画图完成。十一、编写一个函数,在最大堆中查找任意元素,并分析其时间复杂度。要求:定义最大堆得型HEAP及其基本操作。定义函数intFind(HEAPH,Elementtypee),查找e就是否为堆得元素,如果就是,返回该元素在堆中得位置,如果不就是,返回0。(提示:利用最大堆得元素特点进行查找,可降低复杂度)在主函数中首先构建一个二叉树,然后验证所构造得函数。十二、给定叶子结点得权值集合{15,3,14,2,6,9,16,17},构造相应得哈夫曼树,并计算其带权路径长度。十三、已知n=9与一组等价关系:1≡5、6≡8、7≡2、9≡8、3≡7、4≡2、9≡3 试应用抽象数据类型MFSET设计一个算法,按输入得等价关系进行等价分类。十四、画出下图所示得森林经转换后所对应得二叉树,并指出在二叉树中某结点为叶子结点时,所对应得森林中结点应满足得条件。十五、已知森林F得先根序列为:ABCDEFGHIJKL,后根序列为:CBEFDGAJIKLH,试画出森林F。提示:先画出森林F所对应得二叉树B,然后再将B转换为森林。十六、画出表达式(A+B*C/D)*E+F*G所对应得树结构,并写出该表达式得波兰表示式与逆波兰表示式。十七、利用逆波兰表达式求一个四则混合元算得值。具体要求:定义二叉树得型BTREE与位置得型position。实现二叉树得基本操作。实现将一个四则混合运算转换成二叉树得函数:BTREEconvert(char*express),其中参数express为四则混合运算表达式,返回值为生成得树。实现计算四则混合运算得值得函数:doubleputer(BTREEbt),其中,参数bt为四则运算所对应得树,返回值为计算结果。提示:先求树得得波兰表达式,然后利用栈结构计算表达式得值。在主函数中进行测试,求2+3*(5+8)/4-5得值。要求:1、上述作业要求在单独完成;2、完成后,于规定期限内提交到ftp服务器得相应目录中中,注意,在提交时将所编写得程序统一拷贝到一个Word文件中,文件名格式为“学号+姓名”三ABCDABABCDABCDABCDABCDABCDABCDAABCDABCABCDABCDABCDABCDABCDABCDABCDABCD四BBCAFEDGH五、六代码#include<iostream>usingnamespacestd;typedefchardatatype;structnode{ node*lchild; datatypedata; node*rchild;};typedefnode*BTREE;voidCreateBTREE(BTREE&BT,char*&str)//先根输入树{ charch; ch=*str++; if(ch=='#') BT=NULL; else { BT=newnode; BT->data=ch; CreateBTREE(BT->lchild,str); CreateBTREE(BT->rchild,str); }}voidEmpty(BTREEBT){ BT=NULL;}boolIsEmpty(BTREEBT)//判断就是否为空{ if(BT==NULL) returntrue; else returnfalse;}BTREECreateBT(datatypev,BTREEltree,BTREErtree)//用左右子树建立二叉树{ BTREEroot; root=newnode; root->data=v; root->lchild=ltree; root->rchild=rtree; returnroot;}BTREELchild(BTREEBT)//返回左子树{ returnBT->lchild;}BTREERchild(BTREEBT)//返回右子树{ returnBT->rchild;}datatypeData(BTREEBT)//返回节点元素值{ returnBT->data;}voidvisit(datatypedt){ cout<<dt;}voidPreOrder(BTREEBT)//先根顺序遍历{ if(!IsEmpty(BT)) { visit(Data(BT)); PreOrder(Lchild(BT)); PreOrder(Rchild(BT)); }}voidInOrder(BTREEBT)//中根顺序遍历{ if(!IsEmpty(BT)) { PreOrder(Lchild(BT)); visit(Data(BT)); PreOrder(Rchild(BT)); }}voidPostOrder(BTREEBT)//后根顺序遍历{ if(!IsEmpty(BT)) { PreOrder(Lchild(BT)); PreOrder(Rchild(BT)); visit(Data(BT)); }}intcount2(BTREEBT){ if(BT==NULL) return0; else { if((BT->lchild)&&(BT->rchild)) return1+count2(Lchild(BT))+count2(Rchild(BT)); if((BT->lchild)&&(BT->rchild==NULL)) returncount2(Lchild(BT)); if((BT->lchild==NULL)&&(BT->rchild)) returncount2(Rchild(BT)); }}intleafnum(BTREEBT){ staticintcount=0; if(BT->lchild==NULL&&BT->rchild==NULL) return++count; else { leafnum(Lchild(BT)); leafnum(Rchild(BT)); }}intmain(){ BTREEBT=NULL; char*str="abc##d##ef##g##"; CreateBTREE(BT,str); cout<<"度为2得节点得个数:"<<count2(BT)<<endl; cout<<"叶子节点个数:"<<leafnum(BT)<<endl;}七headhead中序线索二叉树798653421798653421先序线索二叉树6689735124head八二叉树BBGAEFCDHJIK后序线索二叉树BBGAEFCDHJIKHead九#include<iostream>usingnamespacestd;typedefchardatatype;structnode{ node*lchild; node*rchild; boolltag; boolrtag; datatypedata;};typedefnode*THTREE;THTREEInPre(THTREEP)//求中序前驱(右子树得最左节点){ THTREEQ=P->lchild; if(P->ltag==true) while(Q->rtag==true) Q=Q->rchild; returnQ;}THTREEInNext(THTREEP)//求中序后继(左子树得最右节点){ THTREEQ=P->rchild; if(P->rtag==true) while(Q->ltag==true) Q=Q->lchild; returnQ;}//二叉树中插入一个结点Q作为树中某个结点P得左孩子voidLInsert(THTREEP,THTREEQ){ THTREEW; Q->lchild=P->lchild; Q->ltag=P->ltag; Q->rchild=P; Q->rtag=false; P->lchild=Q; P->ltag=true; if(Q->ltag==true)//如果P节点有左孩子 { W=InPre(Q); W->rchild=Q; }}voidRInsert(THTREEP,THTREEQ){ THTREEW; Q->rchild=P->rchild; Q->rtag=P->rtag; Q->lchild=P; Q->ltag=false; P->rchild=Q; P->rtag=true; if(Q->rtag==true)//如果P节点有右孩子 { W=InNext(Q); W->lchild=Q; }}voidThInOrder(THTREEHEAD){ THTREEtemp; temp=HEAD; do{ temp=InNext(temp); if(temp!=HEAD) cout<<(temp->data); }while(temp!=HEAD); }intmain(){ node*HEAD=newnode; node*A=newnode; HEAD->data='!'; A->data='A'; HEAD->lchild=A; HEAD->rchild=HEAD; HEAD->ltag=true; HEAD->rtag=true; A->lchild=HEAD; A->rchild=HEAD; A->ltag=false; A->rtag=false; node*B=newnode; B->data='B'; node*C=newnode; C->data='C'; node*D=newnode; D->data='D'; node*E=newnode; E->data='E'; node*F=newnode; F->data='F'; node*G=newnode; G->data='G'; LInsert(A,B); RInsert(A,C); LInsert(B,D); RInsert(B,E); LInsert(C,F); RInsert(C,G); ThInOrder(HEAD);}十1616744263158249744263158249716263158249716631582497163158249716582497168249716491677十一#include<iostream>#defineMaxSize200usingnamespacestd;typedefstruct{ intdata;}Elementtype;typedefstruct{ Elementtypeelements[MaxSize]; intn;}HEAP;voidMaxHeap(HEAP&heap)//创建一个空堆{ heap、n=0;}boolHeapEmpty(HEAPheap)//判断就是否为空堆{ return(!heap、n);}boolHeapFull(HEAPheap)//判断就是否满堆{ return(heap、n==MaxSize-1);}voidInsert(HEAP&heap,Elementtypeelement)//最大堆插入一个元素{ inti; if(!HeapFull(heap)) { i=++heap、n; while(i!=1&&(element、data>heap、elements[i/2]、data)) { heap、elements[i]=heap、elements[i/2]; i/=2; } } heap、elements[i]=element;}ElementtypeDeleteMax(HEAP&heap)//删除堆中得最大元素{ intparent=1,child=2; Elementtypeelement,tmp; if(!HeapEmpty(heap)) { element=heap、elements[1]; tmp=heap、elements[heap、n--]; while(child<=heap、n) { if((child<heap、n)&&(heap、elements[child]、data<heap、elements[child+1]、data)) child++; if(tmp、data>=heap、elements[child]、data) break; heap、elements[parent]=heap、elements[child]; parent=child; child*=2; } heap、elements[parent]=tmp; returnelement; }}intFind(HEAP&H,Elementtypee)//查找e就是否为堆中元素{ inti=H、n,j; if(e、data==H、elements[1]、data) return1; if(i!=0) { if(e、data==H、elements[i]、data) returni; elseif((e、data<H、elements[i/2]、data)&&(e、data<H、elements[i/4]、data)) { j=i/4+1; while(j<i) { if(e、data==H、elements[j]、data) returnj; j++; } return0; } else i/=4; }}intmain(){ HEAPH; H、n=0; Elementtypeelement; intdata[]={7,16,49,82,5,31,6,2,44}; for(inti=0;i<9;i++) { element、data=data[i]; Insert(H,element); } cout<<"最大堆元素为:"<<endl; for(inti=1;i<=9;i++) { cout<<H、elements[i]、data<<"\t"; } cout<<endl; cout<<"请输入要查找得元素"<<endl; cin>>element、data; cout<<"该元素在堆中得位置为"<<Find(H,element)<<endl;}292923651191415161733208249十二WPL=(16+17)*2+(9+14+15)*3+6*4+(2+3)*5=229WPL=(16+17)*2+(9+14+15)*3+6*4+(2+3)