《2013河南省数据要领入门》由会员分享，可在线阅读，更多相关《2013河南省数据要领入门（5页珍藏版）》请在金锄头文库上搜索。
1、1、#define maxsize 栈空间容量 void InOutS(int smaxsize) /s是元素为整数的栈，本算法进行入栈和退栈操作。 int top=0; /top为栈顶指针，定义top=0时为栈空。 for(i=1; i=n; i+) /n个整数序列作处理。 scanf(“%d”,&x); /从键盘读入整数序列。 if(x!=-1) / 读入的整数不等于-1时入栈。 if(top=maxsize-1)printf(“栈满n”);exit(0);else s+top=x; /x入栈。 else /读入的整数等于-1时退栈。 if(top=0)printf(“栈空n”);exit
2、(0); else printf(“出栈元素是%dn”,stop-)； /算法结2、我们可用“破圈法”求解带权连通无向图的一棵最小代价生成树。所谓“破圈法”就是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算法。注：圈就是回路。3、有一个带头结点的单链表，每个结点包括两个域，一个是整型域info，另一个是指向下一个结点的指针域next。假设单链表已建立，设计算法删除单链表中所有重复出现的结点，使得info域相等的结点只保留一个。#include typedef char dat
3、atype;typedef struct node datatype data; struct node * next; listnode;typedef listnode* linklist;/*-*/* 删除单链表中重复的结点 */*-*/linklist deletelist(linklist head) listnode *p,*s,*q; p=head-next; while(p) s=p; q=p-next; while(q) if(q-data=p-data) s-next=q-next;free(q); q=s-next; else s=q; /*找与P结点值相同的结点*/ q
4、=q-next; p=p-next; return head; 4、二部图（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为结点个数）。请在程序中加必要的注释。若有必要可直接利用堆栈或队列操作。【5、矩阵中元素按行和按列都已排序，要求查找时间
5、复杂度为O（m+n），因此不能采用常规的二层循环的查找。可以先从右上角（i=a,j=d）元素与x比较，只有三种情况：一是Ai,jx， 这情况下向j 小的方向继续查找；二是Ai,jx，下步应向i大的方向查找；三是Ai,j=x，查找成功。否则，若下标已超出范围，则查找失败。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=c) if(Aij=x) flag=1;break; else if
6、(Aijx) j-; else i+; if(flag) printf(“A%d%d=%d”,i,j,x); /假定x为整型. else printf(“矩阵A中无%d 元素”，x)； 算法search结束。算法讨论算法中查找x的路线从右上角开始，向下（当xAi,j）或向左（当xAi,j）。向下最多是m，向左最多是n。最佳情况是在右上角比较一次成功，最差是在左下角（Ab,c），比较m+n次，故算法最差时间复杂度是O(m+n）。6、给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在
7、哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。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 (wik+wkjwij) wij=wik+wkj; m=MAXINT; /设定m为机器内最大整数。 for (i=1;i=n;i+) /求最长路径中最短的一条。 s=0; for (j=1;
8、j=n;j+) /求从某村庄i（1=is) s=wij; if (s=m) m=s; k=i;/在最长路径中，取最短的一条。m记最长路径，k记出发顶点的下标。 Printf(“医院应建在%d村庄，到医院距离为%dn”,i,m); /for/算法结束对以上实例模拟的过程略。各行中最大数依次是9，9，6，7，9，9。这几个最大数中最小者为6，故医院应建在第三个村庄中,离医院最远的村庄到医院的距离是6。1、对图1所示的连通网G，请用Prim算法构造其最小生成树（每选取一条边画一个图）。7、 连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边，最小生成树是边上权值之和最小的生成树。故可按权
9、值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，若不再连通，则将该边恢复。若仍连通，继续向下删；直到剩n-1条边为止。 void SpnTree (AdjList g) /用“破圈法”求解带权连通无向图的一棵最小代价生成树。typedef struct int i,j,wnode; /设顶点信息就是顶点编号，权是整型数 node edge; scanf( %d%d,&e,&n) ; /输入边数和顶点数。 for (i=1;i=e;i+) /输入e条边：顶点，权值。 scanf(%d%d%d ,&edgei.i ,&edgei.j ,&edgei
10、.w); for (i=2;i=e;i+) /按边上的权值大小，对边进行逆序排序。 edge0=edgei; j=i-1;while (edgej.w=n) /破圈，直到边数e=n-1. if (connect(k) /删除第k条边若仍连通。 edgek.w=0; eg-; /测试下一条边edgek，权值置0表示该边被删除k+; /下条边 /while /算法结束。 connect()是测试图是否连通的函数，可用图的遍历实现，8、因为后序遍历栈中保留当前结点的祖先的信息，用一变量保存栈的最高栈顶指针，每当退栈时，栈顶指针高于保存最高栈顶指针的值时，则将该栈倒入辅助栈中，辅助栈始终保存最长路径长
11、度上的结点，直至后序遍历完毕，则辅助栈中内容即为所求。void LongestPath(BiTree bt)/求二叉树中的第一条最长路径长度BiTree p=bt,l,s; /l, s是栈，元素是二叉树结点指针，l中保留当前最长路径中的结点 int i，top=0,tag,longest=0; while(p | top0) while(p) s+top=p；tagtop=0; p=p-Lc; /沿左分枝向下 if(tagtop=1) /当前结点的右分枝已遍历 if(!stop-Lc & !stop-Rc) /只有到叶子结点时，才查看路径长度if(toplongest) for(i=1;i0)
12、 tagtop=1; p=stop.Rc; /沿右子分枝向下 /while(p!=null|top0)/结束LongestPath9、设计一个尽可能的高效算法输出单链表的倒数第K个元素。10、给定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+)
