| 数据结构(C语言)第二版 第五章课后答案 | 您所在的位置：网站首页 › 数据结构第五章总结 › 数据结构(C语言)第二版 第五章课后答案 |
数据结构(C语言)第二版 第五章课后答案
|
数据结构(C语言)第二版 第五章课后答案
1~5 A D D C A 6~10 C C B D C 11~15 B C A C A 1．选择题（1）把一棵树转换为二叉树后，这棵二叉树的形态是（A） 。 A．唯一的Ｂ．有多种 C．有多种，但根结点都没有左孩子Ｄ．有多种，但根结点都没有右孩子 因为二叉树有左孩子、右孩子之分，故一棵树转换为二叉树后，这棵二叉树的形态是唯一的。 （2）由3 个结点可以构造出多少种不同的二叉树？（D） A． 2 B ． 3 C ． 4 D ．5 五种情况如下： （3）一棵完全二叉树上有1001 个结点，其中叶子结点的个数是（D） 。 A． 250 B ． 500 C ． 254 D ． 501 设度为0 结点（叶子结点）个数为n0，度为1 的结点个数为n1，度为2 的结点个数为n2，有n0=n2+1，n0+n1+n2=1001 由完全二叉树的性质可得n1=0 或1，即有501 个叶子结点。 （4）一个具有1025 个结点的二叉树的高h 为（C） 。 A． 11． 10 C ． 11 至1025 之间D． 10 至1024 之间 若每层仅有一个结点，则树高h 为1025 ；且其最小树高为log 2 1025 + 1=11 ，即h 在11 至1025 之间。 （5）深度为h 的满m叉树的第k 层有（A）个结点。(1= // 用分治的方法做，比较当前根，然后比较左子树和右子树 bool tree1IsNull = (tree1==NULL); bool tree2IsNull = (tree2==NULL); if(tree1IsNull != tree2IsNull) return 1; if(tree1IsNull && tree2IsNull) return 0; if(tree1->c != tree2->c) return 1; return (compareTree(tree1->left,tree2->left)&compareTree(tree1->right,tree2->right)) (compareTree(tree1->left,tree2->right)&compareTree(tree1->right,tree2->left)); } 3）交换二叉树每个结点的左孩子和右孩子。 [ 题目分析] 如果某结点左右子树为空，返回，否则交换该结点左右孩子，然后递归交换左右子树。 [ 算法描述] void ChangeLR(BiTree &T){ BiTree temp; if(T->lchild==NULL&&T->rchild==NULL) return; else{ temp = T->lchild; T->lchild = T->rchild; T->rchild = temp; } ChangeLR(T->lchild); // 递归交换左子树 ChangeLR(T->rchild); //递归交换右子树 }（4）设计二叉树的双序遍历算法（双序遍历是指对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树） 。 [ 题目分析] 若树为空，返回；若某结点为叶子结点，则仅输出该结点；否则先输出该结点，递归遍历其左子树，再输出该结点，递归遍历其右子树。 [ 算法描述] void DoubleTraverse(BiTree T){ if(T == NULL) return; else if(T->lchild==NULL&&T->rchild==NULL) cout if (bt==null) return (0); // 空二叉树宽度为0 else{ BiTree Q[]; front=1;rear=1;last=1; temp=0; maxw=0; Q[rear]=bt; // 根结点入队列 while(front last=rear; if(temp>maxw) maxw=temp; //last 指向下层最右元素, 更新当前最大宽度 temp=0; } } return (maxw); } }（6）用按层次顺序遍历二叉树的方法，统计树中具有度为1 的结点数目。 [ 题目分析] 若某个结点左子树空右子树非空或者右子树空左子树非空，则该结点为度为1的结点 [ 算法描述] int Level(BiTree bt) { int num=0; if(bt){ QueueInit(Q); QueueIn(Q,bt); while(!QueueEmpty(Q)){ p=QueueOut(Q); coutlchild && !p->rchild ||!p->lchild && p->rchild) num++; if(p->lchild) QueueIn(Q,p->lchild); if(p->rchild) QueueIn(Q,p->rchild); } } return(num); }（7）求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值。 [ 题目分析] 因为后序遍历栈中保留当前结点的祖先的信息，用一变量保存栈的最高栈顶指针，每当退栈时，栈顶指针高于保存最高栈顶指针的值时，则将该栈倒入辅助栈中，辅助栈始终保存最长路径长度上的结点，直至后序遍历完毕，则辅助栈中内容即为所求。 [ 算法描述] int Depth(BiTree T)/* 深度 */ { if(T==NULL) return(0); return 1+(Depth(T->lchild)>Depth(T->rchild)? Depth(T->lchild):Depth(T->rchild)); //选择左右孩子深度高的然后加上根节点这一层就是深度 } void Long(BiTree T) { if(T!=NULL)//在T不为空的情况下 { visit(T->data);//访问节点 if(Depth(T->lchild)>Depth(T->rchild))//判断往左走还是往右走 Long(T->lchild); else Long(T->rchild); } }（8）输出二叉树中从每个叶子结点到根结点的路径。 [ 题目分析] 采用先序遍历的递归方法， 当找到叶子结点b 时， 由于b 叶子结点尚未添加到path 中，因此在输出路径时还需输出b->data 值。 [ 算法描述] void AllPath(BTNode *b,ElemType path[],int pathlen){ int i; if (b!=NULL){ if (b->lchild==NULL && b->rchild==NULL) { //*b 为叶子结点 cout |
【本文地址】