工大数据结构第三章作业复习过程.doc

学习资料数据结构与算法上机作业第三章 树一、选择题1、在一棵树中，如果结点A有3个兄弟，B是A的双亲，则B的度为 D A. 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. 2i B. 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+1 14、在结点数为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(BTREE T)，返回度为2的节点的个数。 3、在主函数中，构建一个二叉树，并验证所编写的算法。六、用递归方法写一个算法，求二叉树的叶子结点数int leafnum(BTREE T)。要求：1、 定义二叉树的抽象数据类型和型BTREE，并定义基本操作。2、 编写函数leafnum(BTREE T)，返回树T的叶子节点的个数。在主函数中，构建一个二叉树，并验证所编写的算法。七、 画出下图所表示的二叉树的中序线索二叉树和先序线索二叉树。 八、已知二叉树的先根序列是AEFBGCDHIKJ，中根序列是EFAGBCHKIJD，画出此二叉树，并画出后序线索二叉树。九、在中序线索二叉树中插入一个结点Q作为树中某个结点P的左孩子，试给出相应的算法。要求：1、 定义中序线索二叉树的型THTREE以及基本操作。2、 定义函数void LInsert(THTREE P, THTREE Q); 实现题目要求的操作。在主函数中，利用操作RInsert和LInsert构造一个线索二叉树，并中序输出二叉树的结点的元素，验证结果。#include#include#include#include#includeusing namespace std;typedef int elementtype;struct node/节点的型 node* lchild;node* rchild;bool ltag;bool rtag;elementtype element;typedef node* head;/指向树根roottypedef node* tree;/指向线索树的根节点 void makeNull(head& h)/将线索二叉树置空 h-lchild=h;h-ltag=false;h-rchild=h;h-rtag=true; head pointTotree(head& h,tree& t)/令head指向tree,注意head指向的并不是根节点，tree指向根节点 h-lchild=t;h-rchild=h;h-ltag=true;h-rtag=true; return h; /中根遍历的下一个节点node* inNext(node* p)node* q=p-rchild;if(p-rtag=true)/如果有右子树，找出右子树的最左节点 while(q-ltag=true)q=q-lchild;return q; /中根遍历的上一个节点 node* inPre(node* p)node *q= p-lchild; if(p-ltag=true)/如果P的左子树存在，则其前驱结点为左子树的最右结点while(q-rtag=true) q=q-rchild; return q;/左子树的最右结点/中序遍历 void thInOrder(head h)node* temp;temp=h;dotemp=inNext(temp);if(temp!=h)coutelementrchild=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指向的是原来节点s w=inNext(r);w-lchild=r;/插入左孩子void lInsert(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; int main()head h=new node;node* root=new node;node* lc=new node;node* rc=new node;node* c=new node;root-element=1;lc-element=2;rc-element=3;c-element=4;h-rchild=root;h-lchild=h;h-ltag=true;h-rtag=true;root-lchild=h;root-rchild=h;root-ltag=false;root-rtag=false;/构造线索树213 lInsert(root,lc);rInsert(root,rc);thInOrder(h);coutheap.elementsi/2.data) heap.elementsi=heap.elementsi/2; i/=2; Heap.n+; Heap.elementsi=element; Elementtype DeleteMax(HEAP&heap)/删除堆中最大元素 int paraent=1,child=2; Elementtype element,tmp; If(!HeapEmpty(heap) Element=heap.elements1; Tmp=heap.elementsheap.n-; While(child=heap.n) If(childheap.n)&(heap.elementschild.data=heap.elementschild.data)break; Heap.elementsparaent=heap.elementschild; Paraent=child; Child*=2; Heap.elementsparaent=tmp; Return element; Int Find(HEAP,datatype x) int m=1; While(mH.n)&(H.elementsm.data!=x) If(H.elementsm.data=x) m+; else return 0; else m+; if(m=H.n)return m; else return 0; Int main() HEAP H; Elementtype element; Int data=1,3,5,7,9,11,13; H.n=0; For(int i=0;i7;i+) element.key=i+1; Element.data=datai; Insert(H,element); for(int i;i=H.n;i+)coutH.elementsi.dataendl; DeleteMax(H); For(int i=1;i=H.n;i+)coutH.elementsi.data; Cout,endl; Coutx; CoutFind(H,x)endl;十二、给定叶子结点的权值集合15, 3,14, 2, 6, 9, 16, 17，构造相应的哈夫曼树，并计算其带权路径长度。十三、已知n=9和一组等价关系： 15、68、72、98、37、42、93 试应用抽象数据类型MFSET设计一个算法，按输入的等价关系进行等价分类。#include#definen9 /MEFSET元素个数 /MFSET抽象数据型structmfnodeintfather;/指向父节点的链intcount;/树结点个数;typedefmfnodeMFSETn+1;voidUnion(intA,intB,MFSETC)/合并A和Bif(CA.countCB.count)CB.father=A;/B并入ACA.count+=CB.count;elseCA.father=B;/A并入BCB.count+=CA.count;intFind(intx,MFSETC)/求包含元素x的树的根intf;f=x;while(Cf.father!=0)/未到根f=Cf.father;returnf;voidInitial(intA,MFSETC)/集合A只包含元素ACA.father=0;CA.count=1;/等价分类voidEquivalence(MFSETS)inti,j,m,k;for(i=1;ii;cinj;while(!(i=0&j=0)/输入0,0结束等价分类k=Find(i,S);m=Find(j,S);if(k!=m)Union(k,m,S);cini;cinj;voidprint_MFSET(MFSETS)/输出等价类intrn+1n+1=0,k;for(inti=1;i=n;i+)k=Find(i,S);rk0+;rkrk0=i;for(i=1;i0)cout;for(intj=1;jri0;j+)coutrij,;coutriri0endl;voidmain()MFSETS;Equivalence(S);print_MFSET(S);十四、画出下图所示的森林经转换后所对应的二叉树，并指出在二叉树中某结点为叶子结点时，所对应的森林中结点应满足的条件。十五、已知森林F的先根序列为：ABCDEFGHIJKL，后根序列为：CBEFDGAJIKLH，试画出森林F。提示：先画出森林F所对应的二叉树B，然后再将B转换为森林。十六、画出表达式(A+B*C/D)*E+F*G所对应的树结构，并写出该表达式的波兰表示式和逆波兰表示式。十七、利用逆波兰表达式求一个四则混合元算的值。具体要求：1、 定义二叉树的型BTREE和位置的型position。2、 实现二叉树的基本操作。3、 实现将一个四则混合运算转换成二叉树的函数：BTREE convert(char *express)，其中参数express为四则混合运算表达式，返回值为生成的树。4、 实现计算四则混合运算的值的函数：double computer(BTREE bt)，其中，参数bt为四则运算所对应的树，返回值为计算结果。提示：先求树的的波兰表达式，然后利用栈结构计算表达式的值。在主函数中进行测试，求2+3*（5+8）/4-5的值。#include./stack.cpp#include#include#define MAXSIZE 30using namespace std;char match= =;char opera=+-*/();const char& Match(const char &ch1,const char &ch2)int i=0,j=0;while(operai!=ch1) i+;while(operaj!=ch2) j+;return matchi*7+j;class TNodepublic:TNode(string str=,int b=0,TNode *l=NULL,TNode *r=NULL,TNode *p=NULL)strcpy(id,str.c_str();bit=b;left=l;right=r;parent=p;TNode(const char ch,TNode *l=NULL,TNode *r=NULL,TNode *p=NULL)id0=ch;id1=0;bit=0;left=l;right=r;parent=p;const TNode& operator=(const TNode& tn)strcpy(id,tn.id);bit=tn.bit;left=tn.left;right=tn.right;parent=tn.parent;char idMAXSIZE;int bit;TNode *parent,*left,*right;int ReadExpr(char *str,char *expr,int start,int bit,int &length)length=0;if(strstart=0)expr0=0;return 0;else if(strstart=*|strstart=/|strstart=(|strstart=)|strstart=)expr0=strstart;expr1=0;length=1;return 2;else if(bit|isdigit(strstart)|strstart=.) /read a digit stringint b=0;int k=0; /index for exprwhile(strstart=+|strstart=-) /read signif(strstart=-) b+;start+;length+;if(b%2) exprk+=-;while(isdigit(strstart)|strstart=.)exprk+=strstart+;length+;exprk=0;return 1;else if(strstart=+|strstart=-) /read a oper + or -int b=0;while(strstart=+|strstart=-)if(strstart=-) b+;start+;length+;if(b%2) expr0=-;else expr0=+;expr1=0;return 2;else return -1; /errorTNode *Translate(const string &str) /translate a expression string to a expression treechar substrMAXSIZE;Stack cstk;Stack tstk;char *tempstr=new charstr.length()+2;int start=0,bit=1;int t,length;strcpy(tempstr,str.c_str();tempstrstr.length()=;tempstrstr.length()+1=0;cstk.push();t=ReadExpr(tempstr,substr,start,bit,length);while(cstk.top()!=|substr0!=)if(t=1) /is a digit stringTNode *np=new TNode(substr,1);tstk.push(np);bit=0;else if(t=2) /is a operif(substr0=() bit=1;else bit=0;char tch=cstk.top();if(Match(tch,substr0)=)TNode *right=tstk.top();tstk.pop();TNode *left=tstk.top();tstk.pop();TNode *np=new TNode(tch,left,right);left-parent=np;right-parent=np;tstk.push(np);cstk.pop();continue;else if(Match(tch,substr0)=left)print(root-left);print(root-right);coutid;else coutid;void prints(TNode*);double solve(TNode*);void printExpr(string str)TNode *root=Translate(str);cout后缀式:;print(root);coutendl; cout中缀式:;prints(root);cout=solve(root)left=NULL) coutid; /is a leafelse if(root-parent=NULL)prints(root-left);coutid;prints(root-right);else if(root-parent-left=root&Match(root-id0,root-parent-id0)=)prints(root-left);coutid;prints(root-right);else if(root-parent-right=root)if(Match(root-parent-id0,root-id0)=parent-id0=+)prints(root-left); coutid; prints(root-right);elsecout(; prints(r