【最详细】数据结构（C语言版 第2版）第五章课后习题答案 严蔚敏 等 编著 |
您所在的位置：网站首页 › 清华大学数据结构严蔚敏答案 › 【最详细】数据结构（C语言版 第2版）第五章课后习题答案 严蔚敏 等 编著 |
|
所有章节答案合集——>传送门
1．选择题 （ 1）把一棵树转换为二叉树后，这棵二叉树的形态是（） 。 A．唯一的 Ｂ．有多种 C．有多种，但根结点都没有左孩子 Ｄ．有多种，但根结点都没有右孩子 答案： A 解释：因为二叉树有左孩子、右孩子之分，故一棵树转换为二叉树后，这棵二叉树的 形态是唯一的。 （ 2）由 3 个结点可以构造出多少种不同的二叉树？（） A． 2 B ． 3 C ． 4 D ． 5 答案： D （ 3）一棵完全二叉树上有 1001 个结点，其中叶子结点的个数是（） 。 A． 250 B ． 500 C ． 254 D ． 501 答案： D 解释：设度为 0 结点（叶子结点）个数为 A，度为 1 的结点个数为 B，度为 2 的结点个数为 C，有A=C+1， A+B+C=1001 ，可得 2C+B=1000 ，由完全二叉树的性质可得 B=0 或 1，又因为 C 为整数，所以 B=0， C=500 ， A=501 ，即有 501 个叶子结点。 （ 4）一个具有 1025 个结点的二叉树的高 h 为（）。 A． 11 B ． 10 C ． 11 至 1025 之间 D． 10 至 1024 之间 答案： C 解释：若每层仅有一个结点，则树高 h 为 1025 ；且其最小树高为 log 2 1025 + 1=11 ， 即 h 在 11 至 1025 之间。 （ 5）深度为 h 的满 m叉树的第 k 层有（）个结点。 (1= bool tree1IsNull = (tree1==NULL); bool tree2IsNull = (tree2==NULL); if(tree1IsNull != tree2IsNull) { return 1; } if(tree1IsNull && tree2IsNull) {// 如果两个都是 NULL ，则相等 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[];//Q 是队列，元素为二叉树结点指针，容量足够大 front=1;rear=1;last=1; //front 队头指针 ,rear 队尾指针 ,last 同层最右结点在队列中的位置 temp=0; maxw=0; //temp 记局部宽度 , maxw 记最大宽度 Q[rear]=bt; // 根结点入队列 while(front last=rear; if(temp>maxw) maxw=temp; //last 指向下层最右元素 , 更新当前最大宽度 temp=0; }//if }//while return (maxw); } }// 结束 width（ 6）用按层次顺序遍历二叉树的方法，统计树中具有度为 1 的结点数目。 [题目分析 ] 若某个结点左子树空右子树非空或者右子树空左子树非空，则该结点为度为 1 的结点 [算法描述 ] int Level(BiTree bt) // 层次遍历二叉树，并统计度为 1 的结点的个数 { int num=0; //num 统计度为 1 的结点的个数 if(bt) { QueueInit(Q); QueueIn(Q,bt);//Q 是以二叉树结点指针为元素的队列 while(!QueueEmpty(Q)) { p=QueueOut(Q); coutlchild && !p->rchild ||!p->lchild && p->rchild) num++; // 度为 1 的结点 if(p->lchild) QueueIn(Q,p->lchild); // 非空左子女入队 if(p->rchild) QueueIn(Q,p->rchild); // 非空右子女入队 } //while(!QueueEmpty(Q)) }//if(bt) return(num); }// 返回度为 1 的结点的个数（ 7）求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值。 [ 题目分析 ] 因为后序遍历栈中保留当前结点的祖先的信息，用一变量保存栈的最高栈顶 指针，每当退栈时，栈顶指针高于保存最高栈顶指针的值时，则将该栈倒入辅助栈中，辅助 栈始终保存最长路径长度上的结点，直至后序遍历完毕，则辅助栈中内容即为所求。 [ 算法描述 ] void LongestPath(BiTree bt)// 求二叉树中的第一条最长路径长度 { BiTree p=bt,l[],s[]; //l, s 是栈，元素是二叉树结点指针， l 中保留当前最长路径中的结点 int i ， top=0,tag[],longest=0; while(p || top>0) { while(p) { s[++top]=p; tag[top]=0; p=p->Lc; } // 沿左分枝向下 if(tag[top]==1) // 当前结点的右分枝已遍历 { if(!s[top]->Lc && !s[top]->Rc) // 只有到叶子结点时，才查看路径长度 if(top>longest) { for(i=1;i0) {tag[top]=1; p=s[top].Rc;} // 沿右子分枝向下 }//while(p!=null||top>0) }// 结束 LongestPath（ 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 |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |