数据结构课程 课后习题答案

练习题及参考答案 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 #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