数据结构复习题(附答案) 下载本文

PreToPost(pre,post,l1+half+1,h1,l2+half,h2-1) //将右子树先序序列转为后序序列

} }//PreToPost

32. .[题目分析]叶子结点只有在遍历中才能知道,这里使用中序递归遍历。设置前驱结点指针pre,初始为空。第一个叶子结点由指针head指向,遍历到叶子结点时,就将它前驱的rchild指针指向它,最后叶子结点的rchild为空。

LinkedList head,pre=null; //全局变量 LinkedList InOrder(BiTree bt)

//中序遍历二叉树bt,将叶子结点从左到右链成一个单链表,表头指针为head {if(bt){InOrder(bt->lchild); //中序遍历左子树

if(bt->lchild==null && bt->rchild==null) //叶子结点

if(pre==null) {head=bt; pre=bt;} //处理第一个叶子结点 else{pre->rchild=bt; pre=bt; } //将叶子结点链入链表 InOrder(bt->rchild); //中序遍历左子树 pre->rchild=null; //设置链表尾 }

return(head); } //InOrder

时间复杂度为O(n),辅助变量使用head和pre,栈空间复杂度O(n)

33.[题目分析]两棵空二叉树或仅有根结点的二叉树相似;对非空二叉树,可判左右子树是否相似,采用递归算法。

int Similar(BiTree p,q) //判断二叉树p和q是否相似 {if(p==null && q==null) return (1);

else if(!p && q || p && !q) return (0); else return(Similar(p->lchild,q->lchild) && Similar(p->rchild,q->rchild))

}//结束Similar

34. .[题目分析]对二叉树的某层上的结点进行运算,采用队列结构按层次遍历最适宜。 int LeafKlevel(BiTree bt, int k) //求二叉树bt 的第k(k>1) 层上叶子结点个数 {if(bt==null || k<1) return(0);

BiTree p=bt,Q[]; //Q是队列,元素是二叉树结点指针,容量足够大 int front=0,rear=1,leaf=0; //front 和rear是队头和队尾指针, leaf是叶子结点数

int last=1,level=1; Q[1]=p; //last是二叉树同层最右结点的指针,level 是二叉树的层数

while(front<=rear) {p=Q[++front];

if(level==k && !p->lchild && !p->rchild) leaf++; //叶子结点 if(p->lchild) Q[++rear]=p->lchild; //左子女入队 if(p->rchild) Q[++rear]=p->rchild; //右子女入队

if(front==last) {level++; //二叉树同层最右结点已处理,层数增1 last=rear; } //last移到指向下层最右一元素 if(level>k) return (leaf); //层数大于k 后退出运行 }//while }//结束LeafKLevel

35. .[题目分析] 二叉树的层次遍历序列的第一个结点是二叉树的根。实际上,层次遍历

序列中的每个结点都是“局部根”。确定根后,到二叉树的中序序列中,查到该结点,该结点将二叉树分为“左根右”三部分。若左、右子树均有,则层次序列根结点的后面应是左右子树的根;若中序序列中只有左子树或只有右子树,则在层次序列的根结点后也只有左子树的根或右子树的根。这样,定义一个全局变量指针R,指向层次序列待处理元素。算法中先处理根结点,将根结点和左右子女的信息入队列。然后,在队列不空的条件下,循环处理二叉树的结点。队列中元素的数据结构定义如下:

typedef struct { int lvl; //层次序列指针,总是指向当前“根结点”在层次序列中的位

int l,h; //中序序列的下上界

int f; //层次序列中当前“根结点”的双亲结点的指针 int lr; // 1—双亲的左子树 2—双亲的右子树 }qnode;

BiTree Creat(datatype in[],level[],int n)

//由二叉树的层次序列level[n]和中序序列in[n]生成二叉树。 n是二叉树的结点数 {if (n<1) {printf(“参数错误\\n”); exit(0);}

qnode s,Q[]; //Q是元素为qnode类型的队列,容量足够大 init(Q); int R=0; //R是层次序列指针,指向当前待处理的结点 BiTree p=(BiTree)malloc(sizeof(BiNode)); //生成根结点 p->data=level[0]; p->lchild=null; p->rchild=null; //填写该结点数据

for (i=0; i

if (i==0) //根结点无左子树,遍历序列的1—n-1是右子树 {p->lchild=null;

s.lvl=++R; s.l=i+1; s.h=n-1; s.f=p; s.lr=2; enqueue(Q,s); }

else if (i==n-1) //根结点无右子树,遍历序列的1—n-1是左子树

{p->rchild=null;

s.lvl=++R; s.l=1; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s); }

else //根结点有左子树和右子树

{s.lvl=++R; s.l=0; s.h=i-1; s.f=p; s.lr=1;enqueue(Q,s);//左子树有关信

息入队列

s.lvl=++R; s.l=i+1;s.h=n-1;s.f=p; s.lr=2;enqueue(Q,s);//右子树有关信

息入队列

}

while (!empty(Q)) //当队列不空,进行循环,构造二叉树的左右子树 { s=delqueue(Q); father=s.f; for (i=s.l; i<=s.h; i++)

if (in[i]==level[s.lvl]) break;

p=(bitreptr)malloc(sizeof(binode)); //申请结点空间 p->data=level[s.lvl]; p->lchild=null; p->rchild=null; //填写该结点数据 if (s.lr==1) father->lchild=p;

else father->rchild=p; //让双亲的子女指针指向该结点

if (i==s.l)

{p->lchild=null; //处理无左子女

s.lvl=++R; s.l=i+1; s.f=p; s.lr=2; enqueue(Q,s); }

else if (i==s.h)

{p->rchild=null; //处理无右子女

s.lvl=++R; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s);

}

else{s.lvl=++R; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s);//左子树有关信息入队列

s.lvl=++R; s.l=i+1; s.f=p; s.lr=2; enqueue(Q,s); //右子树有关信

息入队列

}

}//结束while (!empty(Q)) return(p); }//算法结束

36. .[题目分析]因为后序遍历栈中保留当前结点的祖先的信息,用一变量保存栈的最高栈顶指针,每当退栈时,栈顶指针高于保存最高栈顶指针的值时,则将该栈倒入辅助栈中,辅助栈始终保存最长路径长度上的结点,直至后序遍历完毕,则辅助栈中内容即为所求。

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;i<=top;i++) l[i]=s[i]; longest=top; top--;}

//保留当前最长路径到l栈,记住最高栈顶指针,退栈 }

else if(top>0) {tag[top]=1; p=s[top].Rc;} //沿右子分枝向下 }//while(p!=null||top>0) }//结束LongestPath

2、假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)。(注:图中不存在顶点到自己的弧)

[题目分析]有向图判断回路要比无向图复杂。利用深度优先遍历,将顶点分成三类:未访问;已访问但其邻接点未访问完;已访问且其邻接点已访问完。下面用0,1,2表示这三种状态。前面已提到,若dfs(v)结束前出现顶点u到v的回边,则图中必有包含顶点v和u的回路。对应程序中v的状态为1,而u是正访问的顶点,若我们找出u的下一邻接点的状态为1,就可以输出回路了。

void Print(int v,int start ) //输出从顶点start开始的回路。 {for(i=1;i<=n;i++)

if(g[v][i]!=0 && visited[i]==1 ) //若存在边(v,i),且顶点i的状态为1。

{printf(“%d”,v);

if(i==start) printf(“\\n”); else Print(i,start);break;}//if

}//Print

void dfs(int v) {visited[v]=1;

for(j=1;j<=n;j++ )

if (g[v][j]!=0) //存在边(v,j)

if (visited[j]!=1) {if (!visited[j]) dfs(j); }//if else {cycle=1; Print(j,j);} visited[v]=2;

}//dfs

void find_cycle() //判断是否有回路,有则输出邻接矩阵。visited数组为全局变量。 {for (i=1;i<=n;i++) visited[i]=0;

for (i=1;i<=n;i++ ) if (!visited[i]) dfs(i); }//find_cycle

5、给定n个村庄之间的交通图,若村庄i和j之间有道路,则将顶点i和j用边连接,边上的Wij表示这条道路的长度,现在要从这n个村庄中选择一个村庄建一所医院,问这所医院应建在哪个村庄,才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法,并应用该算法解答如图所示的实例。20分 void Hospital(AdjMatrix w,int n)

//在以邻接带权矩阵表示的n个村庄中,求医院建在何处,使离医院最远的村庄到医院的路径最短。

{for (k=1;k<=n;k++) //求任意两顶点间的最短路径 for (i=1;i<=n;i++) for (j=1;j<=n;j++)

if (w[i][k]+w[k][j]

for (j=1;j<=n;j++) //求从某村庄i(1<=i<=n)到其它村庄的最长路径。 if (w[i][j]>s) s=w[i][j];

if (s<=m) {m=s; k=i;}//在最长路径中,取最短的一条。m记最长路径,k记出发顶点的下标。

Printf(“医院应建在%d村庄,到医院距离为%d\\n”,i,m); }//for

}//算法结束

对以上实例模拟的过程略。各行中最大数依次是9,9,6,7,9,9。这几个最大数中最小者为6,故医院应建在第三个村庄中,离医院最远的村庄到医院的距离是6。

1、对图1所示的连通网G,请用Prim算法构造其最小生成树(每选取一条边画一个图)。

4、已知有向图G=(V,E),其中V={V1,V2,V3,V4,V5,V6,V7},

E={,,,,,,,,} 写出G的拓扑排序的结果。

G拓扑排序的结果是:V1、V2、V4、V3、V5、V6、V7

37.[题目分析]本题应使用深度优先遍历,从主调函数进入dfs(v)时 ,开始记数,若退出dfs()前,已访问完有向图的全部顶点(设为n个),则有向图有根,v为根结点。将n个顶点从1到n编号,各调用一次dfs()过程,就可以求出全部的根结点。题中有向图的邻接表存储结构、记顶点个数的变量、以及访问标记数组等均设计为全局变量。建立有向图g的邻接表存储结构参见上面第2题,这里只给出判断有向图是否有根的算法。

int num=0, visited[]=0 //num记访问顶点个数,访问数组visited初始化。 const n=用户定义的顶点数;

AdjList g ; //用邻接表作存储结构的有向图g。 void dfs(v)

{visited [v]=1; num++; //访问的顶点数+1

if (num==n) {printf(“%d是有向图的根。\\n”,v); num=0;}//if p=g[v].firstarc; while (p)

{if (visied[p->adjvex]==0) dfs (p->adjvex);

p=p->next;} //while

visited[v]=0; num--; //恢复顶点v

}//dfs

void JudgeRoot()

//判断有向图是否有根,有根则输出之。 {static int i ;

for (i=1;i<=n;i++ ) //从每个顶点出发,调用dfs()各一次。 {num=0; visited[1..n]=0; dfs(i); } }// JudgeRoot

算法中打印根时,输出顶点在邻接表中的序号(下标),若要输出顶点信息,可使用g[i].vertex。