搜档网
当前位置:搜档网 › 2015年上半年全国JAVA最新版本高级

2015年上半年全国JAVA最新版本高级

1、证明由二叉树的中序序列和后序序列,也可以唯一确定一棵二叉树。
当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}可唯一确定二叉树的右子树 。

2、 连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边,最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序,然后从大到小将边删除。每删除一条当前权值最大的边后,就去测试图是否仍连通,若不再连通,则将该边恢复。若仍连通,继续向下删;直到剩n-1条边为止。
void SpnTree (AdjList g)
//用“破圈法”求解带权连通无向图的一棵最小代价生成树。
{typedef struct {int i,j,w}node; //设顶点信息就是顶点编号,权是整型数
node edge[];
scanf( "%d%d",&e,&n) ; //输入边数和顶点数。
for (i=1;i<=e;i++) //输入e条边:顶点,权值。
scanf("%d%d%d" ,&edge[i].i ,&edge[i].j ,&edge[i].w);
for (i=2;i<=e;i++) //按边上的权值大小,对边进行逆序排序。
{edge[0]=edge[i]; j=i-1;
while (edge[j].wedge[j+1]=edge[0]; }//for
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()是测试图是否连通的函数,可用图的遍历实现,

3、设指针变量p指向双向链表中结点A,指针变量q指向被插入结点B,要求给出在结点A的后面

插入结点B的操作序列(设双向链表中结点的两个指针域分别为llink和rlink)。
4、证明由二叉树的中序序列和后序序列,也可以唯一确定一棵二叉树。
当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}可唯一确定二叉树的右子树 。

5、数组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]while(iwhile(j>=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

6、设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)__;
}}}}

7、设有一组初始记录关键字为(45,80,48,40,22,78),要求构造一棵二叉排序树并给出构造过程。
8、设一棵二叉树的结点结构为 (LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针,p和q分别为指向该二叉树中任意两个结点的指针,试编写一算法ANCESTOR(ROOT,p,q,r),该算法找到p和q的最近共同祖先结点r。
9、二路插入排序是将待排关键字序列r[1..n]中关键字分二路分别按序插入到辅助向量d[1..n]前半部和后半部(注:向量d可视为循环表),其原则为,先将r[l]赋给d[1],再从r[2] 记录开始分二路插入。编写实现二路插入排序算法。
10、后序遍历最后访问根结点,即在递归算法中,根是压在栈底的。采用后序非递归算法,栈中存放二叉树结点的指针,当访问到某结点时,栈中所有元素均为该结点的祖先。本题要找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);//q、p无公共祖先
}//结束Ancestor

11、我们可用“破圈法”求解带权连通无向图的一棵最小代价生成树。所谓“破圈法”就是“任取一圈,去掉圈上权最大的边”,反复执行这一步骤,直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法,并用程序实现你所给出的算法。注:圈就是回路。
12、若第n件物品能放入背包,则问题变为能否再从n-1件物品中选出若干件放入背包(这时背包可放入物品的重量变为s-w[n])。若第n件物品不能放入背包,则考虑从n-1件物品选若干件放入背包(这时背包可放入物品仍为s)。若最终s=0,则有一解;否则,若s<0或虽然s>0但物品数n<1,则无解。
(1)s-w[n],n-1 //Knap(s-w[n],n-1)=true
(2)s,n-1 // Knap←Knap(s,n-1)

13、二部图(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为结点个数)。请在程序中加必要的注释。若有必要可直接利用堆栈或队列操作。【

14、4、 void LinkList_reverse(Linklist &L)
//链表的就地逆置;为简化算法,假设表长大于2
{
p=L->next;q=p->next;s=q->next;p->next=NULL;
while(s->next)
{
q->next=p;p=q;
q=s;s=s->next; //把L的元素逐个插入新表表头
}
q->next=p;s->next=q;L->next=s;
}//LinkList_reverse

15、我们用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(iif(i-j+1>l) {l=i-j+1;k=j;} //局部最长平台
i++; j=i; } //新平台起点
printf(“最长平台长度%d,在b数组中起始下标为%d”,l,k);
}// Platform

16、4、 void LinkList_reverse(Linklist &L)
//链表的就地逆置;为简化算法,假设表长大于2
{
p=L->next;q=p->next;s=q->next;p->next=NULL;
while(s->next)
{
q->next=p;p=q;
q=s;s=s->next; //把L的元素逐个插入新表表头
}
q->next=p;s->next=q;L->next=s;
}//LinkList_reverse

17、题目中要求矩阵两行元素的平均值按递增顺序排序,由于每行元素个数相等,按平均值排列与按每行元素之和排列是一个意思。所以应先求出各行元素之和,放入一维数组中,然后选择一种排序方法,对该数组进行排序,注意在排序时若有元素移动,则与之相应的行中各元素也必须做相应变动。
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{min=*(p+i); k=i; //初始设第i行元素之和最小.
for(j=i+1;jif(i!=k) //若最小行不是当前行,要进行交换(行元素及行元素之和)
{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(n2).

18、 二叉树的层次遍历序列的第一个结点是二叉树的根。实际上,层次遍历序列中的每个结点都是“局部根”。确定根后,到二叉树的中序序列中,查到该结点,该结点将二叉树分为“左根右”三部分。若左、右子树均有,则层次序列根结点的后面应是左右子树的根;若中序序列中只有左子树或只有右子树,则在层次序列的根结点后也只有左子树的根或右子树的根。这样,定义一个全

局变量指针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; iif (in[i]==level[0]) break;
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);
}//算法结束

19、设有一个数组中存放了一个无序的关键序列K1、K2、…、Kn。现要求将Kn放在将元素排序后的正确位置上,试编写实现该功能的算法,要求比较关键字的次数不超过n。
51. 借助于快速排序的算法思想,在一组无序的记录中查

找给定关键字值等于key的记录。设此组记录存放于数组r[l..h]中。若查找成功,则输出该记录在r数组中的位置及其值,否则显示“not find”信息。请编写出算法并简要说明算法思想。

20、 将顶点放在两个集合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); }//是二部图
[算法讨论] 题目给的是连通无向图,若非连通,则算法要修改。

21、证明由二叉树的中序序列和后序序列,也可以唯一确定一棵二叉树。
29. ① 试找出满足下列条件的二叉树
1)先序序列与后序序列相同 2)中序序列与后序序列相同
3)先序序列与中序序列相同 4)中序序列与层次遍历序列相同

22、后序遍历最后访问根结点,即在递归算法中,根是压在栈底的。采用后序非递归算法,栈中存放二叉树结点的指针,当访问到某结点时,栈中所有元素均为该结点的祖先。本题要找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);//q、p无公共祖先
}//结束Ancestor

23、给定n个村庄之间的交通图,若村庄i和j之间有道路,则将顶点i和j用边连接,边上的Wij表示这条道路的长度,现在要从这n个村庄中选择一个村庄建一所医院,问这所医院应建在哪个村庄,才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法,并应用该算法解答如图所示的实例。(20分)
24、已知有向图G=(V,E),其中V={V1,V2,V3,V4,V5,V6,V7},E={,,,,,,,,}
写出G的拓扑排序的结果。
G拓扑排序的结果是:V1、V2、V4、V3、V5、V6、V7


25、二部图(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为结点个数)。请在程序中加必要的注释。若有必要可直接利用堆栈或队列操作。【

26、给定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]m=MAXINT; //设定m为机器内最大整数。
for (i=1;i<=n;i++) //求最长路径中最短的一条。
{s=0;
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算法构造其最小生成树(每选取一条边画一个图)。

27、设T是一棵满二叉树,编写一个将T的先序遍历序列转换为后序遍历序列的递归算法。
28、设指针变量p指向双向链表中结点A,指针变量q指向被插入结点B,要求给出在结点A的后面插入结点B的操作序列(设双向链表中结点的两个指针域分别为llink和rlink)。
29、假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)。(注:图中不存在顶点到自己的弧)
有向图判断回路要比无向图复杂。利用深度优先遍历,将顶点分成三类:未访问;已访问但其邻接点未访问完;已访问且其邻接点已访问完。下面用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

30、已知有向图G=(V,E),其中V={V1,V2,V3,V4,V5,V6,V7},E={,,,,,,,,}
写出G的拓扑排序的结果。
G拓扑排序的结果是:V1、V2、V4、V3、V5、V6、V7


31、根据二叉排序树中序遍历所得结点值为增序的性质,在遍历中将当前遍历结点与其前驱结点值比较,即可得出结论,为此设全局指针变量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算法结束


32、 连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边,最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序,然后从大到小将边删除。每删除一条当前权值最大的边后,就去测试图是否仍连通,若不再连通,则将该边恢复。若仍连通,继续向下删;直到剩n-1条边为止。
void SpnTree (AdjList g)
//用“破圈法”求解带权连通无向图的一棵最小代价生成树。
{typedef struct {int i,j,w}node; //设顶点信息就是顶点编号,权是整型数
node edge[];
scanf( "%d%d",&e,&n) ; //输入边数和顶点数。
for (i=1;i<=e;i++) //输入e条边:顶点,权值。
scanf("%d%d%d" ,&edge[i].i ,&edge[i].j ,&edge[i].w);
for (i=2;i<=e;i++) //按边上的权值大小,对边进行逆序排序。
{edge[0]=edge[i]; j=i-1;
while (edge[j].wedge[j+1]=edge[0]; }//for
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()是测试图是否连通的函数,可用图的遍历实现,

33、设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)__;
}}}}

34、已知有向图G=(V,E),其中V={V1,V2,V3,V4,V5,V6,V7},E={,,,,,,,,}
写出G的拓扑排序的结果。
G拓扑排序的结果是:V1、V2、V4、V3、V5、V6、V7


35、证明由二叉树

的中序序列和后序序列,也可以唯一确定一棵二叉树。
当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}可唯一确定二叉树的右子树 。

36、证明由二叉树的中序序列和后序序列,也可以唯一确定一棵二叉树。
当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}可唯一确定二叉树的右子树 。

37、冒泡排序算法是把大的元素向上移(

气泡的上浮),也可以把小的元素向下移(气泡的下沉)请给出上浮和下沉过程交替的冒泡排序算法。
48.有n个记录存储在带头结点的双向链表中,现用双向起泡排序法对其按上升序进行排序,请写出这种排序的算法。(注:双向起泡排序即相邻两趟排序向相反方向起泡)

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、后序遍历最后访问根结点,即在递归算法中,根是压在栈底的。采用后序非递归算法,栈中存放二叉树结点的指针,当访问到某结点时,栈中所有元素均为该结点的祖先。本题要找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);//q、p无公共祖先
}//结束Ancestor

40、设有两个集合A和集合B,要求设计生成集合C=A∩B的算法,其中集合A、B和C用链式存储结构表示。
typedef struct node {int data; struct node *next;}lklist;
void intersection(lklist *ha,lklist *hb,lklist *&hc)
{
lklist *p,*q,*t;
for(p=ha,hc=0;p!=0;p=p->next)
{ for(q=hb;q!=0;q=q->next) if (q->data==p->data) break;
if(q!=0){ t=(lklist *)malloc(sizeof(lklist)); t->data=p->data;t->next=hc; hc=t;}
}
}

41、因为后序遍历栈中保留当前结点的祖先的信息,用一变量保存栈的最高栈顶指针,每当退栈时,栈顶指针高于保存最高栈顶指针的值时,则将该栈倒入辅助栈中,辅助栈始终保存最长路径长度上的结点,直至后序遍历完毕,则辅助栈中内容即为所求。
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

42、证明由二叉树的中序序列和后序序列,也可以唯一确定一棵二叉树。
当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

,Sm}。由于后序遍历是“左子树—右子树—根结点”,所以{P1,P2,…,Pi-1}和{Pi,Pi+1,…Pm-1}是二叉树的左子树和右子树的后序遍历序列。因而由{S1,S2,…,Si-1}和{P1,P2,…,Pi-1}
可唯一确定二叉树的左子树,由{Si+1,Si+2,…,Sm}和
{Pi,Pi+1,…,Pm-1}可唯一确定二叉树的右子树 。

43、假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)。(注:图中不存在顶点到自己的弧)
有向图判断回路要比无向图复杂。利用深度优先遍历,将顶点分成三类:未访问;已访问但其邻接点未访问完;已访问且其邻接点已访问完。下面用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

44、4、 void LinkList_reverse(Linklist &L)
//链表的就地逆置;为简化算法,假设表长大于2
{
p=L->next;q=p->next;s=q->next;p->next=NULL;
while(s->next)
{
q->next=p;p=q;
q=s;s=s->next; //把L的元素逐个插入新表表头
}
q->next=p;s->next=q;L->next=s;
}//LinkList_reverse

45、 连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边,最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序,然后从大到小将边删除。每删除一条当前权值最大的边后,就去测试图是否仍连通,若不再连通,则将该边恢复。若仍连通,继续向下删;直到剩n-1条边为止。
void SpnTree (AdjList g)
//用“破圈法”求解带权连通无向图的一棵最小代价生成树。
{typedef struct {int i,j,w}node; //设顶点信息就是顶点编号,权是整型数
node edge[];
scanf( "%d%d",&e,&n) ; //输入边数和顶点数。
for (i=1;i<=e;i++) //输入e条边:顶点,权值。
scanf("%d%d%d" ,&edge[i].i ,&edge[i].j ,&edge[i].w);
fo

r (i=2;i<=e;i++) //按边上的权值大小,对边进行逆序排序。
{edge[0]=edge[i]; j=i-1;
while (edge[j].wedge[j+1]=edge[0]; }//for
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()是测试图是否连通的函数,可用图的遍历实现,

46、设有一个数组中存放了一个无序的关键序列K1、K2、…、Kn。现要求将Kn放在将元素排序后的正确位置上,试编写实现该功能的算法,要求比较关键字的次数不超过n。
51. 借助于快速排序的算法思想,在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组r[l..h]中。若查找成功,则输出该记录在r数组中的位置及其值,否则显示“not find”信息。请编写出算法并简要说明算法思想。

47、根据二叉排序树中序遍历所得结点值为增序的性质,在遍历中将当前遍历结点与其前驱结点值比较,即可得出结论,为此设全局指针变量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算法结束


48、本题应使用深度优先遍历,从主调函数进入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)
{i

f (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。



49、二路插入排序是将待排关键字序列r[1..n]中关键字分二路分别按序插入到辅助向量d[1..n]前半部和后半部(注:向量d可视为循环表),其原则为,先将r[l]赋给d[1],再从r[2] 记录开始分二路插入。编写实现二路插入排序算法。
50、假设K1,…,Kn是n个关键词,试解答:
试用二叉查找树的插入算法建立一棵二叉查找树,即当关键词的插入次序为K1,K2,…,Kn时,用算法建立一棵以LLINK / RLINK 链接表示的二叉查找树。

51、若第n件物品能放入背包,则问题变为能否再从n-1件物品中选出若干件放入背包(这时背包可放入物品的重量变为s-w[n])。若第n件物品不能放入背包,则考虑从n-1件物品选若干件放入背包(这时背包可放入物品仍为s)。若最终s=0,则有一解;否则,若s<0或虽然s>0但物品数n<1,则无解。
(1)s-w[n],n-1 //Knap(s-w[n],n-1)=true
(2)s,n-1 // Knap←Knap(s,n-1)

52、本题应使用深度优先遍历,从主调函数进入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。



53、证明由二叉树的中序序列和后序序列,也可以唯一确定一棵二叉树。
当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}可唯一确定二叉树的右子树 。

54、设一棵树T中边的集合为{(A,B),(A,C),(A,D),(B,E),(C,F),(C,G)},要求用孩子兄弟表示法(二叉链表)表示出该树的存储结构并将该树转化成对应的二叉树。
55、若第n件物品能放入背包,则问题变为能否再从n-1件物品中选出若干件放入背包(这时背包可放入物品的重量变为s-w[n])。若第n件物品不能放入背包,则考虑从n-1件物品选若干件放入背包(这时背包可放入物品仍为s)。若最终s=0,则有一解;否则,若s<0或虽然s>0但物品数n<1,则无解。
(1)s-w[n],n-1 //Knap(s-w[n],n-1)=true
(2)s,n-1 // Knap←Knap(s,n-1)

56、因为后序遍历栈中保留当前结点的祖先的信息,用一变量保存栈的最高栈顶指针,每当退栈时,栈顶指针高于保存最高栈顶指针的值时,则将该栈倒入辅助栈中,辅助栈始终保存最长路径长度上的结点,直至后序遍历完毕,则辅助栈中内容即为所求。
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

57、 连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边,最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序,然后从大到小将边删除。每删除一条当前权值最大的边后,就去测试图是否仍连通,若不再连通,则将该边恢复。若仍连通,继续向下删;直到剩n-1条边为止。
void SpnTree (AdjList g)
//用“破圈法”求解带权连通无向图的一棵最小代价生成树。
{typedef struct {int i,j,w}node; //设顶点信息就是顶点编号,权是整型数
node edge[];
scanf( "%d%d",&e,&n) ; //输入边数和顶点数。
for (i=1;i<=e;i++) //输入e条边:顶点,权值。
scanf("%d%d%d" ,&edge[i].i ,&edge[i].j ,&edge[i].w);
for (i=2;i<=e;i++) //按边上的权值大小,对边进行逆序排序。
{edge[0]=edge[i]; j=i-1;
while (edge[j].wedge[j+1]=edge[0]; }//for
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()是测试图是否连通的函数,可用图的遍历实现,

58、设有一组初始记录关键字序列(K1,K2,…,Kn),要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分,其中左半部分的每个关键字均小于Ki,右半部分的每个关键字均大于等于Ki。
void quickpass(int r[], int s, int t)
{
int i=s, j=t, x=r[s];
while(iwhile (ix) j=j-1; if (iwhile (i}
r[i]=x;
}

59、有一种简单的排序算法,叫做计数排序(count sorting)。这种排序算法对一个待排序的表(用数组表示)进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所有待排序的关键码互不相同,计数排序算法针对表中的每个记录,扫描待排序的表一趟,统计表中有多少个记录的关键码比该记录的关键码小,假设针对某一个记录,统计出的计数值为c,那么,这个记录在新的有序表中的合适的存放位置即为c。
(1) (3分)给出适用于计数排序的数据表定义;
(2) (7分)使用Pascal或C语言编写实现计数排序的算法;
(3) (4分)对于有n个记录的表,关键码比较次数是多少?
(4) (3分)与简单选择排序相比较,这种方法是否更好?为什么?

60、冒泡排序算法是把大的元素向上移(气泡的上浮),也可以把小的元素向下移(气泡的下沉)请给出

上浮和下沉过程交替的冒泡排序算法。
48.有n个记录存储在带头结点的双向链表中,现用双向起泡排序法对其按上升序进行排序,请写出这种排序的算法。(注:双向起泡排序即相邻两趟排序向相反方向起泡)

61、请编写一个判别给定二叉树是否为二叉排序树的算法,设二叉树用llink-rlink法存储。
62、设有两个集合A和集合B,要求设计生成集合C=A∩B的算法,其中集合A、B和C用链式存储结构表示。
typedef struct node {int data; struct node *next;}lklist;
void intersection(lklist *ha,lklist *hb,lklist *&hc)
{
lklist *p,*q,*t;
for(p=ha,hc=0;p!=0;p=p->next)
{ for(q=hb;q!=0;q=q->next) if (q->data==p->data) break;
if(q!=0){ t=(lklist *)malloc(sizeof(lklist)); t->data=p->data;t->next=hc; hc=t;}
}
}

63、两棵空二叉树或仅有根结点的二叉树相似;对非空二叉树,可判左右子树是否相似,采用递归算法。
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

64、对二叉树的某层上的结点进行运算,采用队列结构按层次遍历最适宜。
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

65、设T是一棵满二叉树,编写一个将T的先序遍历序列转换为后序遍历序列的递归算法。
66、对一般二叉树,仅根据一个先序、中序、后序遍历,不能确定另一个遍历序列。但对于满二叉树,任一结点的左右子树均含有数量相等的结点,根据此性质,可将任一遍历序列转为另一遍历序列(即任一遍历序列均可确定一棵二叉树)。
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)

67、二部图(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为结点个数)。请在程序中加必要的注释。若有必要可直接利用堆栈或队列操作。【

68、4、 void LinkList_reverse(Linklist &L)
//链表的就地逆置;为简化算法,假设表长大于2
{
p=L->next;q=p->next;s=q->next;p->next=NULL;
while(s->next)
{
q->next=p;p=q;
q=s;s=s->next; //把L的元素逐个插入新表表头
}
q->next=p;s->next=q;L->next=s;
}//LinkList_reverse

69、我们可用“破圈法”求解带权连通无向图的一棵最小代价生成树。所谓“破圈法”就是“任取一圈,去掉圈上权最大的边”,反复执行这一步骤,直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法,并用程序实现你所给出的算法。注:圈就是回路。
70、对二叉树的某层上的结点进行运算,采用队列结构按层次遍历最适宜。
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 是

相关主题