发布时间 : 星期二 文章数据结构课程 课后习题答案更新完毕开始阅读
练习题及参考答案 4. 算法设计题
（1）已知一棵二叉树按顺序方式存储在数组A[1..n]中。设计一个算法求出离下标分别为i和j（0 解：由二叉树顺序存储结构特点，可得到以下求离i和j的两个结点最近的公共祖先结点的算法： ElemType Ancestor(ElemType A[],int i,int j) { } int p=i,q=j; while (p!=q) if (p>q) p=p/2; else q=q/2; return A[p]; （2）已知一棵二叉树采用顺序方式存储在数组A[1..n]中。设计一个先序遍历的递归算法。 解：先序遍历树中结点的递归算法如下： void PreOrder1(ElemType A[],int i,int n) { } if (i if (A[i]!='#') { } //不为空结点时 //访问根结点 //遍历左子树 //遍历右子树 printf(\ PreOrder1(A,2*i,n); PreOrder1(A,2*i+1,n); （3）假设二叉树采用二叉链存储结构。设计一个算法求一棵非空二叉树中的最大结点 值。 解：求一个二叉树中的最大结点值的递归模型如下： f(bt)=bt->data 只有一个结点时 其他情况 f(bt)=Max{f(bt->lchild),f(bt->rchild),bt->data} 对应的算法如下： ElemType MaxNode(BTNode *bt) { ElemType max,max1,max2; if (bt->lchild==NULL && bt->rchild==NUL) { } return bt->data; max1=MaxNode(bt->lchild); //求左子树的最大结点值 max2=MaxNode(bt->rchild); //求右子树的最大结点值 max=bt->data; if (max1>max) max=max1; if (max2>max) max=max2; return(max); //求最大值 //返回最大值 else 37 数据结构简明教程 } （4）假设含有n个结点的二叉树采用二叉链存储结构。设计一个算法输出中序遍历序列中的第k（1≤i≤n）个结点值。 解：对应的算法如下： int i=0; { } //i为全局变量 void Trav(BTNode *bt,int k) if (bt!=NULL) { } Trav(bt->lchild,k); i++; if (i==k) { } Trav(bt->rchild,k); //遍历右子树 printf(\return; //遍历左子树 （5）假设二叉树采用二叉链存储结构，设计一个算法Level()求二叉树中结点值为x 的结点的层数。 解：对应的递归算法如下： int Level(BTNode *bt,ElemType x,int h) //调用h对应的实参置初值1 { } int l; if (bt==NULL) { } return 0; return h; l=Level(bt->lchild,x,h+1); if (l!=0) return l; //在左子树中未找到,再在右子树中查找 return(Level(bt->rchild,x,h+1)); else //在左子树中查找 else if (bt->data==x) else 上机实验题6 假设一棵二叉树采用二叉链存储结构，其中所有结点值均不相同。设计一个算法求从根结点到值为x的结点的路径。并用相关数据进行测试。 解：采用递归和层次遍历两种求解方法，对应的程序如下： #include 练习题及参考答案 void Path1(BTNode *bt,ElemType x,ElemType path[],int pathlen) { } void Path2(BTNode *bt,ElemType x) { BTNode *p; ElemType path[MaxSize]; int i,d; struct { BTNode *s; int parent; //存放结点指针 //存放其双亲结点在qu中的下标 //qu存放队中元素 //队头队尾指针 //根结点进队 //根结点没有双亲,其parent置为-1 //队不空循环 //出队一个结点*p,它在qu中的下标为front //找到值为x的结点 int i; if (bt!=NULL) { } if (bt->data==x) { } else { } path[pathlen]=bt->data; pathlen++; //将当前结点放入路径中 //path中元素个数增1 //找到值为x的结点 printf(\从根结点到%c结点的路径: \for (i=0;i printf(\→\printf(\return; Path1(bt->lchild,x,path,pathlen); //递归遍历左子树 Path1(bt->rchild,x,path,pathlen); //递归遍历右子树 } qu[MaxSize]; rear++; qu[rear].s=bt; int front=-1,rear=-1; qu[rear].parent=-1; while (front!=rear) { front++; p=qu[front].s; if (p->data==x) { printf(\从根结点到%c结点的路径: \d=0; path[d]=p->data; i=qu[front].parent; while (i!=-1) { } printf(\for (i=d-1;i>=0;i--) d++; path[d]=qu[i].s->data; i=qu[i].parent; 39 数据结构简明教程 } void main() { } BTNode *bt; ElemType path[MaxSize],x='I'; CreateBTree(bt,\//建立图6.14的二叉链 printf(\括号表示法:\printf(\解法1:\\n\Path1(bt,x,path,0); printf(\解法2:\\n\Path2(bt,x); } } if (p->lchild!=NULL) { } if (p->rchild!=NULL) { } rear++; qu[rear].s=p->rchild; qu[rear].parent=front; //右孩子的双亲为qu[front]结点 //*p有右孩子,将右孩子进队 rear++; qu[rear].s=p->lchild; qu[rear].parent=front; //左孩子的双亲为qu[front]结点 //*p有左孩子,将左孩子进队 printf(\→%c\ printf(\ 练习题7 1. 单项选择题 （1）在一个图中，所有顶点的度数之和等于图的边数的（ ）倍。 A.1/2 B.1 C.2 D.4 答：C （2）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。 A.1/2 B.1 C.2 答：B （3）有8个顶点的无向图最多有（ ）条边。 A.14 答：B B.28 C.56 D.4 D.112