数据结构复习题(附答案)

更新时间：2024-07-04 03:43:01 阅读量：综合文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

数据结构题库及答案推荐度：
相关推荐

一、算法设计题（每题15分，共60分）

答题要求：

①用自然语言说明所采用算法的思想；

②给出每个算法所需的数据结构定义，并做必要说明； ③写出对应的算法程序，并做必要的注释。

1、有一个带头结点的单链表，每个结点包括两个域，一个是整型域info，另一个是指向下一个结点的指针域next。假设单链表已建立，设计算法删除单链表中所有重复出现的结点，使得info域相等的结点只保留一个。

3、约瑟夫环问题（Josephus问题）是指编号为1、2、…，n的n（n>0）个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，…，如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法，模拟此过程。

4、编程实现单链表的就地逆置。

23．在数组 A[1..n]中有n个数据，试建立一个带有头结点的循环链表，头指针为h，要求链中数据从小到大排列，重复的数据在链中只保存一个.

5、设计一个尽可能的高效算法输出单链表的倒数第K个元素。

3、假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。（15分）

（1）下面所示的序列中哪些是合法的？

A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO

（2）通过对（1）的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。

5、设从键盘输入一整数的序列：a1, a2, a3，?，an,试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。

设有一个背包可以放入的物品重量为S，现有n件物品，重量分别为W1，W2，...，Wn。问能否从这n件物品中选择若干件放入背包，使得放入的重量之和正好是S。设布尔函数Knap(S，n)表示背包问题的解，Wi(i=1,2,...，n)均为正整数，并已顺序存储地在数组W中。请在下列算法的下划线处填空，使其正确求解背包问题。

Knap(S，n) 若S=0

则Knap←true

否则若（S<0）或(S>0且n<1)

则Knap←false

否则若Knap(1) , _=true

则print(W[n])；Knap ←true

否则 Knap←Knap(2) _ , _

设有一个顺序栈S，元素s1, s2, s3, s4, s5, s6依次进栈，如果6个元素的出栈顺序为s2, s3, s4,

s6, s5, s1，则顺序栈的容量至少应为多少？画出具体进栈、出栈过程。

假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如：

str1 s t r i str2 b e n g

设str1和str2是分别指向两个单词的头结点，请设计一个尽可能的高效算法，找出两个单词共同后缀的起始位置，分析算法时间复杂度。

将n(n>1)个整数存放到一维数组R中。设计一个尽可能高效（时间、空间）的算

法，将R中保存的序列循环左移p（0

8. 给定nxm矩阵A[a..b,c..d],并设A[i,j]≤A[i,j+1](a≤i≤b,c≤j≤d-1)和A[i,j]≤A[i+1,j](a≤i≤b-1,c≤j≤d).设计一算法判定X的值是否在A中,要求时间复杂度为O(m+n)。【

22. 给定有m个整数的递增有序数组a[1..m]和有n个整数的递减有序数组b[1..n]，试写出算法:将数组a和b归并为递增有序数组c[l..m+n]。(要求：算法的时间复杂度为O(m+n))

4、要求二叉树按二叉链表形式存储，（15分）

（1）写一个建立二叉树的算法。（2）写一个判别给定的二叉树是否是完全二叉树的算法。

3、已知一棵二叉树的中序遍历结果为：DBFEAGHCI，后序遍历结果为：DFEBHGICA。（1）画出这棵二叉树，并写出它的前序遍历结果；（2）将这棵二叉树转换成等价的森林或树。

24.将二叉树bt中每一个结点的左右子树互换的C语言算法如下，其中ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分别为进队，出队和判别队列是否为空的函数，请填写算法中得空白处，完成其功能。

typedef struct node

{int data ; struct node *lchild, *rchild; }btnode; void EXCHANGE(btnode *bt) {btnode *p, *q;

if (bt){ADDQ(Q,bt);

while(!EMPTY(Q))

{p=DELQ(Q); q=(1)___; p->rchild=(2)___; (3)___=q;

if(p->lchild) (4)___; if(p->rchild) (5)___; }

} }

25.设t是给定的一棵二叉树，下面的递归程序count(t)用于求得:二叉树t中具有非空的左,右两个儿子的结点个数N2;只有非空左儿子的个数NL;只有非空右儿子的结点个数NR和叶子结点个数N0。N2、NL、NR、N0都是全局量，且在调用count(t)之前都置为0. typedef struct node

{int data; struct node *lchild,*rchild;}node; int N2,NL,NR,N0; void count(node *t)

{if (t->lchild!=NULL) if (1)___ N2++; else NL++; else if (2)___ NR++; else (3)__ ;

if(t->lchild!=NULL)(4)____; if (t->rchild!=NULL) (5)____; }

26.树的先序非递归算法。 void example(b)

btree *b;

{ btree *stack[20], *p； int top; if (b!=null)

{ top=1; stack[top]=b; while (top>0)

{ p=stack[top]; top--; printf(“%d”,p->data); if (p->rchild!=null) {(1)___; (2)___; }

if (p->lchild!=null) (3)___; (4)__;

}}}}

27.由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序所缺的语句。

#define MAX 100 typedef struct Node

{char info; struct Node *llink, *rlink; }TNODE; char pred[MAX],inod[MAX]; main(int argc,int **argv)

{ TNODE *root;

if(argc<3) exit 0;

strcpy(pred,argv[1]); strcpy(inod,argv[2]); root=restore(pred,inod,strlen(pred)); postorder(root); }

TNODE *restore(char *ppos,char *ipos,int n) { TNODE *ptr； char *rpos; int k; if(n<=0) return NULL; ptr->info=(1)_______;

for((2)_______ ; rpos

ptr->llink=restore(ppos+1, (4)_______,k );

ptr->rlink=restore ((5)_______+k,rpos+1,n-1-k); return ptr; }

postorder(TNODE*ptr) { if(ptr=NULL) return;

postorder(ptr->llink); postorder(ptr->rlink); printf(“%c”,ptr->info); }

28. 证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。

29. ① 试找出满足下列条件的二叉树

1）先序序列与后序序列相同 2）中序序列与后序序列相同

3）先序序列与中序序列相同 4）中序序列与层次遍历序列相同

30. 设一棵二叉树的结点结构为 (LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针，p和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR（ROOT，p,q,r）,该算法找到p和q的最近共同祖先结点r。

31. 设T是一棵满二叉树，编写一个将T的先序遍历序列转换为后序遍历序列的递归算法。 32. 请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为head。二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。分析你的算法的时、空复杂度。

33. 设两棵二叉树的的根结点地址分别为p和q，采用二叉链表的形式存储这两棵树上所有的结点。请编写程序，判断它们是否相似。

34. 一棵二叉树以二叉链表来表示，求其指定的某一层k(k>1)上的叶子结点的个数。 35. 二叉树T的中序遍历序列和层次遍历序列分别是BAFDGCE和ABCDEFG，试画出该二叉树，并写出由二叉树的中序遍历序列和层次遍历序列确定二叉树的算法。 36. 设二叉树的结点结构是（Lc,data,Rc），其中Lc、Rc分别为指向左、右子树根的指针，data是字符型数据。试写出算法，求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值。

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

5、给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。（20分） 2 12 1 9 5 6 3 10 4 4 2 6 7 6 3 2 4 1、对图1 所示的连通网G，请用Prim算法构造其最小生成树（每选取一条边画一个图）。

图1 连通网G

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

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

37.在有向图G中，如果r到G中的每个结点都有路径可达，则称结点r为G的根结点。编写一个算法完成下列功能：（1）．建立有向图G的邻接表存储结构；（2）．判断有向图G是否有根，若有，则打印出所有根结点的值。

38．二部图（bipartite graph） G=（V，E）是一个能将其结点集V分为两不相交子集V 1和V2=V-V1的无向图，使得：V1中的任何两个结点在图G中均不相邻，V2中的任何结点在图G中也均不相邻。（1）．请各举一个结点个数为5的二部图和非二部图的例子。（2）．请用C或PASCAL编写一个函数BIPARTITE判断一个连通无向图G是否是二部图，并分析程序的时间复杂度。设G用二维数组A来表示，大小为n*n（n为结点个数）。请在程序中加必要的注释。若有必要可直接利用堆栈或队列操作。【

39．我们可用“破圈法”求解带权连通无向图的一棵最小代价生成树。所谓“破圈法”就是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算法。注：圈就是回路。

40. 请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink-rlink法存储。

S2 S1 S3 S1 S4 S1 S6 S5 S1 S5 S1 S1

①分别求出str1、str2的长度m、n

②将两个链表的表尾对齐。p、q两个指针。

③p、q两个指针同步移动，直到指向相同结点。

先将n个数据(前后对应交换)原地逆置，然后再将前n－p和后p个分别原地逆置。 Void reverse(int r[], int left, int right) {

int k=left, j=right, temp; while (k

temp=r[k]; r[k]=r[j]; r[j]=temp; k++;j--; } }

Void leftshift(int r[], int n, int p) {

if(p>0&&p

{ reverse(r,0,n-1)；reverse(r,0,n-p-1)；reverse(r,n-p,n-1)；} } 4. [题目分析]题目中要求矩阵两行元素的平均值按递增顺序排序，由于每行元素个数相等，按平均值排列与按每行元素之和排列是一个意思。所以应先求出各行元素之和，放入一维数组中，然后选择一种排序方法，对该数组进行排序，注意在排序时若有元素移动，则与之相应的行中各元素也必须做相应变动。

void Translation（float *matrix，int n）

//本算法对n×n的矩阵matrix，通过行变换，使其各行元素的平均值按递增排列。 {int i,j,k,l；

float sum，min； //sum暂存各行元素之和 float *p, *pi, *pk; for(i=0; i

{sum=0.0; pk=matrix+i*n; //pk指向矩阵各行第1个元素.

for (j=0; j

*(p+i)=sum; //将一行元素之和存入一维数组.

}//for i

for(i=0; i

for(j=i+1;j

{pk=matrix+n*k; //pk指向第k行第1个元素. pi=matrix+n*i; //pi指向第i行第1个元素. for(j=0;j

{sum=*(pk+j); *(pk+j)=*(pi+j); *(pi+j)=sum;}

sum=p[i]; p[i]=p[k]; p[k]=sum; //交换一维数组中元素之和. }//if }//for i

free(p); //释放p数组. }// Translation

[算法分析] 算法中使用选择法排序,比较次数较多,但数据交换(移动)较少.若用其它

排序方法,虽可减少比较次数,但数据移动会增多.算法时间复杂度为O(n). 7．[题目分析]我们用l代表最长平台的长度，用k指示最长平台在数组b中的起始位置（下标）。用j记住局部平台的起始位置，用i指示扫描b数组的下标，i从0开始，依次和后续元素比较，若局部平台长度（i-j）大于l时，则修改最长平台的长度k（l=i-j）和其在b中的起始位置（k=j），直到b数组结束，l即为所求。

void Platform (int b[ ], int N)

//求具有N个元素的整型数组b中最长平台的长度。 {l=1;k=0;j=0;i=0; while(i

{while(i

if(i-j+1>l) {l=i-j+1;k=j;} //局部最长平台 i++; j=i; } //新平台起点

printf(“最长平台长度%d，在b数组中起始下标为%d”，l，k)； }// Platform

8．[题目分析]矩阵中元素按行和按列都已排序，要求查找时间复杂度为O（m+n），因此不能采用常规的二层循环的查找。可以先从右上角（i=a,j=d）元素与x比较，只有三种情况：一是A[i,j]>x，这情况下向j 小的方向继续查找；二是A[i,j]

void search(datatype A[ ][ ], int a,b,c,d, datatype x)

//n*m矩阵A,行下标从a到b,列下标从c到d,本算法查找x是否在矩阵A中. {i=a; j=d; flag=0; //flag是成功查到x的标志 while(i<=b && j>=c)

if(A[i][j]==x) {flag=1;break;}

else if (A[i][j]>x) j--; else i++;

if(flag) printf(“A[%d][%d]=%d”,i,j,x); //假定x为整型. else printf(“矩阵A中无%d 元素”，x)； }算法search结束。

[算法讨论]算法中查找x的路线从右上角开始，向下（当x>A[i,j]）或向左（当x

22、[题目分析]数组A和B的元素分别有序，欲将两数组合并到C数组，使C仍有序，应将A和B拷贝到C，只要注意A和B数组指针的使用，以及正确处理一数组读完数据后将另一数组余下元素复制到C中即可。

void union(int A[],B[],C[],m,n)

//整型数组A和B各有m和n个元素，前者递增有序，后者递减有序，本算法将A和B归并为递增有序的数组C。

{i=0; j=n-1; k=0;// i，j，k分别是数组A,B和C的下标，因用C描述，下标从0开始

while(i=0)

if(a[i]=0) c[k++]=b[j--]; }算法结束

4、要求二叉树按二叉链表形式存储。15分

（1）写一个建立二叉树的算法。（2）写一个判别给定的二叉树是否是完全二叉树的算法。

BiTree Creat() //建立二叉树的二叉链表形式的存储结构 {ElemType x；BiTree bt;

scanf(“%d”,&x); //本题假定结点数据域为整型 if(x==0) bt=null; else if(x>0)

{bt=(BiNode *)malloc(sizeof(BiNode));

bt->data=x; bt->lchild=creat(); bt->rchild=creat(); }

else error(“输入错误”)； return(bt); }//结束 BiTree

int JudgeComplete(BiTree bt) //判断二叉树是否是完全二叉树,如是，返回1，否则，返回0

{int tag=0; BiTree p=bt, Q[]; // Q是队列，元素是二叉树结点指针，容量足够大

if(p==null) return (1);

QueueInit(Q); QueueIn(Q,p); //初始化队列，根结点指针入队 while (!QueueEmpty(Q))

{p=QueueOut(Q); //出队

if (p->lchild && !tag) QueueIn(Q,p->lchild); //左子女入队

else {if (p->lchild) return 0; //前边已有结点为空，

本结点不空

else tag=1; //首次出现结点为空 if (p->rchild && !tag) QueueIn(Q,p->rchild); //右子女入队 else if (p->rchild) return 0; else tag=1; } //while

return 1; } //JudgeComplete

3、已知一棵二叉树的中序遍历结果为：DBFEAGHCI，后序遍历结果为：DFEBHGICA。（1）画出这棵二叉树，并写出它的前序遍历结果；（2）将这棵二叉树转换成等价的森林或树。前序遍历结果为：ABDEFCGHI

24. (1)p->rchild (2)p->lchild (3)p->lchild (4)ADDQ(Q,p->lchild) (5)ADDQ(Q,p->rchild)

25. (1)t->rchild!=null (2)t->rchild!=null (3)N0++ (4)count(t->lchild) (5)count(t->rchild)

26. .(1)top++ (2) stack[top]=p->rchild (3)top++ (4)stack[top]=p->lchild

27. (1)*ppos // 根结点（2）rpos=ipos (3)rpos–ipos (4)ipos (5)ppos+1

28. 证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。

当n=1时，只有一个根结点，由中序序列和后序序列可以确定这棵二叉树。设当n=m-1时结论成立，现证明当n=m时结论成立。

设中序序列为S1，S2，?，Sm,后序序列是P1,P2,?，Pm。因后序序列最后一个元素Pm是根，则在中序序列中可找到与Pm相等的结点（设二叉树中各结点互不相同）Si(1≤i≤m)，因中序序列是由中序遍历而得，所以Si是根结点，S1，S2，?，Si-1是左子树的中序序列，而Si+1,Si+2,?,Sm是右子树的中序序列。

若i=1，则S1是根，这时二叉树的左子树为空，右子树的结点数是m-1,则{S2，S3，?，Sm}和{P1，P2，?，Pm-1}可以唯一确定右子树，从而也确定了二叉树。

若i=m,则Sm是根，这时二叉树的右子树为空，左子树的结点数是m-1，则{S1，S2，?，Sm-1}和{P1，P2，?，Pm-1}唯一确定左子树，从而也确定了二叉树。

最后，当1

可唯一确定二叉树的左子树，由{Si+1,Si+2,?，Sm}和 {Pi,Pi+1,?，Pm-1}可唯一确定二叉树的右子树。

29. 原则，本题解答如下：

（１）若先序序列与后序序列相同，则或为空树，或为只有根结点的二叉树

（２）若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树．（３）若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树．（４）若中序序列与层次遍历序列相同，则或为空树，或为任一结点至多只有右子树的二

叉树。

30. .[题目分析]后序遍历最后访问根结点，即在递归算法中，根是压在栈底的。采用后序非递归算法，栈中存放二叉树结点的指针，当访问到某结点时，栈中所有元素均为该结点的祖先。本题要找p和q 的最近共同祖先结点r ,不失一般性，设p在q的左边。后序遍历必然先遍历到结点p，栈中元素均为p的祖先。将栈拷入另一辅助栈中。再继续遍历到结点q时，将栈中元素从栈顶开始逐个到辅助栈中去匹配，第一个匹配（即相等）的元素就是结点p 和q的最近公共祖先。 typedef struct

{BiTree t;int tag;//tag=0 表示结点的左子女已被访问，tag=1表示结点的右子女已被访问 }stack;

stack s[],s1[];//栈，容量够大

BiTree Ancestor(BiTree ROOT,p,q,r)//求二叉树上结点p和q的最近的共同祖先结点r。 {top=0; bt=ROOT; while(bt!=null ||top>0)

{while(bt!=null && bt!=p && bt!=q) //结点入栈 {s[++top].t=bt; s[top].tag=0; bt=bt->lchild;} //沿左分枝向下

if(bt==p) //不失一般性，假定p在q的左侧,遇结点p时，栈中元素均为p的祖先结点

{for(i=1;i<=top;i++) s1[i]=s[i]; top1=top; }//将栈s的元素转入辅助栈s1 保存

if(bt==q) //找到q 结点。

for(i=top;i>0;i--)//；将栈中元素的树结点到s1去匹配 {pp=s[i].t;

for (j=top1;j>0;j--) if(s1[j].t==pp) {printf(“p 和q的最近共同的祖先已找到”)；return (pp);} ｝

while(top!=0 && s[top].tag==1) top--; //退栈

if (top!=0)｛s[top].tag=1;bt=s[top].t->rchild;｝ //沿右分枝向下遍历 }//结束while(bt!=null ||top>0) return(null);//ｑ、p无公共祖先｝//结束Ancestor

31. .[题目分析]对一般二叉树，仅根据一个先序、中序、后序遍历，不能确定另一个遍历序列。但对于满二叉树，任一结点的左右子树均含有数量相等的结点，根据此性质，可将任一遍历序列转为另一遍历序列（即任一遍历序列均可确定一棵二叉树）。

void PreToPost(ElemType pre[] ,post[],int l1,h1,l2,h2)

//将满二叉树的先序序列转为后序序列，l1,h1,l2,h2是序列初始和最后结点的下标。

{if(h1>=l1)

{post[h2]=pre[l1]; //根结点

half=(h1-l1)/2; //左或右子树的结点数

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

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

[题目分析]有向图判断回路要比无向图复杂。利用深度优先遍历，将顶点分成三类：未访问；已访问但其邻接点未访问完;已访问且其邻接点已访问完。下面用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。

38.[题目分析] 将顶点放在两个集合V1和V2。对每个顶点，检查其和邻接点是否在同一个集合中，如是，则为非二部图。为此，用整数1和2表示两个集合。再用一队列结构存放图中访问的顶点。

int BPGraph (AdjMatrix g)

//判断以邻接矩阵表示的图g是否是二部图。

{int s[]; //顶点向量，元素值表示其属于那个集合（值1和2表示两个集合） int Q[];//Q为队列，元素为图的顶点，这里设顶点信息就是顶点编号。

int f=0,r,visited[]; //f和r分别是队列的头尾指针,visited[]是访问数组 for (i=1;i<=n;i++) {visited[i]=0;s[i]=0;} //初始化，各顶点未确定属于那个集合

Q[1]=1; r=1; s[1]=1;//顶点1放入集合S1

while(f

{v=Q[++f]; if (s[v]==1) jh=2; else jh=1;//准备v的邻接点的集合号 if (!visited[v])

{visited[v]=1; //确保对每一个顶点，都要检查与其邻接点不应在一个集合中

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

if (g[v][j]==1){if (!s[j]) {s[j]=jh; Q[++r]=j;} //邻接点入队列 else if (s[j]==s[v]) return(0);} //非二部图 }//if (!visited[v]) }//while

return(1); }//是二部图

[算法讨论] 题目给的是连通无向图，若非连通，则算法要修改。

39．[题目分析] 连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，若不再连通，则将该边恢复。若仍连通，继续向下删；直到剩n-1条边为止。 void SpnTree (AdjList g)

//用“破圈法”求解带权连通无向图的一棵最小代价生成树。

{typedef struct {int i,j,w}node; //设顶点信息就是顶点编号，权是整型数 node edge[];

scanf( \输入边数和顶点数。

for (i=1;i<=e;i++) //输入e条边：顶点，权值。

scanf(\

for (i=2;i<=e;i++) //按边上的权值大小，对边进行逆序排序。 {edge[0]=edge[i]; j=i-1;

while (edge[j].w

k=1; eg=e;

while (eg>=n) //破圈，直到边数e=n-1. {if (connect(k)) //删除第k条边若仍连通。

{edge[k].w=0; eg--; }//测试下一条边edge[k]，权值置0表示该边被删除

k++; //下条边

}//while

}//算法结束。

connect()是测试图是否连通的函数，可用图的遍历实现，

40.根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论，为此设全局指针变量pre（初值为null）和全局变量flag，初值为true。若非二叉排序树，则置flag为false。

#define true 1 #define false 0

typedef struct node

{datatype data; struct node *llink,*rlink;} *BTree; void JudgeBST（BTree t,int flag）

// 判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag得出结论。 { if（t!=null && flag）

{ Judgebst（t->llink,flag）；// 中序遍历左子树

if（pre==null）pre=t；// 中序遍历的第一个结点不必判断

else if（pre->datadata）pre=t；//前驱指针指向当前结点 else{flag=flase；} //不是完全二叉树 Judgebst （t->rlink,flag）；// 中序遍历右子树 }//JudgeBST算法结束

41. 非递归建立二叉排序树，在二叉排序树上插入的结点都是叶子结点。 void Creat_BST（BiTree bst，datatype K[]，int n）

// 以存储在数组K中的n个关键字，建立一棵初始为空的二叉排序树。 {for（i=1；i≤n；i++）

{p=bst；f=null；//在调用Creat_BST时，bst=null while（p!=null）

if（p->dataRLINK； } // f是p的双亲 else if（p->data>K[i]）{ f=p；p=p->LLINK；}

s=（BiTree）malloc（sizeof （BiNode））；// 申请结点空间 s->data=K[i]；s->LLINK=null；s->RLINK=null； if（f==null）bst=s； //根结点 else if（s->datadata）f->LLINK=s；//左子女

else f->RLINK=s；//右子树根结点的值大于等于根结点的值 }//算法结束

42. int BinSrch（rectype r[ ]，int k，low，high）

//在长为n的有序表中查找关键字k，若查找成功，返回k所在位置，查找失败返回0。 {if（low≤high） //low和high分别是有序表的下界和上界 {mid=（low+high）/2；

if（r[mid].key==k）return （mid）；

else if（r[mid].key>k）return （BinSrch（r,k，mid+1，high））; else return （BinSrch（r,k，low，mid-1））; }

else return （0）；//查找失败。 }//算法结束

算法时间复杂度为O（logn）。

43. ．[题目分析] 用链地址法解决冲突的哈希表是一个指针数组，数组分量均是指向单链表的指针，（第i个）单链表结点有两个域，一个是哈希地址为i的关键字，另一个是指向同义词结点的指针。删除算法与单链表上删除算法类似。

typedef struct node {keytype key；

struct node *next； }HSNode；*HSList

typedef struct node *HLK；

void Delete（HLK HT[]，keytype K）

//用链地址法解决冲突，从哈希表中删去关键字为K的记录 {i=H（K）；//用哈希函数确定关键字K的哈希地址

if（HT[i]==null）{printf（“无被删除记录\\n”）；exit（0）；} HLK p,q; p=H[i]；q=p； //p指向当前记录（关键字），q是p的前驱 while（p && p->key！=k）{q=p；p=p->next；}

if（p==null）{printf（“无被删除记录”）；exit(0); } if（q==H[i]） //被删除关键字是链表中第一个结点 {HT[i]=HT[i].next；free（p）；} else{q->next=p->next；free（p）；}

}//结束Delete

44. ．[题目分析]首先计算关键字的散列地址，若该地址为空，则空操作；若该地址有关键字，但与给定值不等，则用解决冲突的方法去查找给定值；若该地址有关键字且与给定值相等，则实行删除。题目要求将所有可以前移的元素前移去填充被删除的空位，以保证探测序列不断裂。由于用线性探测解决冲突，设被删除元素的散列地址为i，则其余m-1（m为表长）个位置均可能是同义词。查找同义词的操作直到碰到空地址或循环一圈回到i才能结束。为了提高算法效率，减少数据移动，应将最后一个同义词前移填充被删除关键字。 void HsDelete（rectype HS[]，K）

//在以除余法为散列函数、线性探测解决冲突的散列表HS中，删除关键字K {i=K % P； // 以造表所用的除余法计算关键字K的散列地址

if（HS[i]==null）{printf（“散列表中无被删关键字”）；exit（0）；} // 此处null代表散列表初始化时的空值 switch

{case HS[i]==K：del(HS，i，i，K)；break；

case HS[i]!=K：di=1；j=(i+ di)%m； // m为表长

while（HS[j]!=null && HS[j]!=K && j!=i）// 查找关键字K {di=di+1；

j=(i+di)%m； }// m为表长

if（HS[j]==K）del(HS，i，j，K)； else {printf（“散列表中无被删关键字”）；exit（0）;}

}// switch }算法结束

void del（rectype HS[]，in i，int j，rectype K）

//在散列表HS中，删除关键字K，K的散列地址是i，因解决冲突而将其物理地置于表中j。算法查找关键字K的同义词，将其最后一个同义词移到位置j，并将其同义词的位置置空。

{di=1；last=j；x=(j+di)% m；// 探测地址序列，last记K的最后一个同义词的位置 while（x!=i） //可能要探测一圈

{if（HS[x]==null）break； // 探测到空位置，结束探测 else if（HS[x]%P==i）last=x；// 关键字K的同义词 di=di+1；x=(j+di) % m； // 取下一地址探测 }

HS[j]=HS[last]; HS[last]=null; //将哈希地址last的关键字移到哈希地址j

}

45. [题目分析] 因为二叉树各结点已标明了平衡因子b，故从根结点开始记树的层次。根结点的层次为1，每下一层，层次加1，直到层数最大的叶子结点，这就是平衡二叉树的高度。当结点的平衡因子b为0时，任选左右一分枝向下查找，若b不为0，则沿左（当b=1时）或右（当b=-1时）向下查找。 int Height（BSTree t） // 求平衡二叉树t的高度 {level=0；p=t； while（p）

{level++； // 树的高度增1

if（p->bf<0）p=p->rchild；//bf=-1 沿右分枝向下

//bf是平衡因子，是二叉树t结点的一个域，因篇幅所限，没有写出其存

储定义

else p=p->lchild； //bf>=0 沿左分枝向下

}//while

return （level）；//平衡二叉树的高度

} //算法结束

46. ．[题目分析]非零元素个数是100，负载因子取0.8，表长125左右，取p为127，散列地址为0到126。哈希函数用H(k)=(3*i+2*j) % 127，i，j为行值和列值。 #define m 127 typedef struct

{int i，j；datatype v;}triple； void CreatHT（triple H[m]）

//100个非零元素生成稀疏矩阵的哈希表，表中元素值均初始化为0。 {for（k=0；k<100；k++）

{scanf（&i,&j,&val）；//设元素值为整型 h=(3*i+2*j)% m； //计算哈希地址