《2011陕西省数据要领基础》由会员分享，可在线阅读，更多相关《2011陕西省数据要领基础（6页珍藏版）》请在金锄头文库上搜索。
1、1、我们用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(in-1)while(il) l=i-j+1;k=j; /局部最长平台i+; j=i; /新平台起点printf(“最长平台长度%d，在b数组中起始下标为%
2、d”，l，k)；/ Platform2、给定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
3、;j+) if (wik+wkjwij) wij=wik+wkj; m=MAXINT; /设定m为机器内最大整数。 for (i=1;i=n;i+) /求最长路径中最短的一条。 s=0; for (j=1;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，故医院应建在第三个村庄中,离医院最远的村庄到医院的距离
4、是6。1、对图1所示的连通网G，请用Prim算法构造其最小生成树（每选取一条边画一个图）。3、 将顶点放在两个集合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
5、 (i=1;i=n;i+) visitedi=0;si=0; /初始化，各顶点未确定属于那个集合 Q1=1; r=1; s1=1;/顶点1放入集合S1while(fr) v=Q+f; if (sv=1) jh=2; else jh=1;/准备v的邻接点的集合号 if (!visitedv) visitedv=1; /确保对每一个顶点，都要检查与其邻接点不应在一个集合中for (j=1,j0）个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法，模
6、拟此过程。#includetypedef int datatype;typedef struct nodedatatype data; struct node *next;listnode;typedef listnode *linklist;void jose(linklist head,int s,int m)linklist k1,pre,p; int count=1; pre=NULL; k1=head; /*k1为报数的起点*/ while (count!=s) /*找初始报数起点*/ pre=k1; k1=k1-next; count+; while(k1-next!=k1) /*
7、当循环链表中的结点个数大于1时*/ p=k1; /*从k1开始报数*/ count=1; while (count!=m) /*连续数m个结点*/ pre=p; p=p-next; count+; pre-next=p-next; /*输出该结点，并删除该结点*/ printf(%4d,p-data); free(p); k1=pre-next; /*新的报数起点*/ printf(%4d,k1-data); /*输出最后一个结点*/ free(k1);main()linklist head,p,r; int n,s,m,i; printf(n=); scanf(%d,&n); printf(
8、s=); scanf(%d,&s); printf(m=,&m); scanf(%d,&m); if (n1) printf(ndata=n; r=head; for (i=n-1;i0;i-) /*建立剩余n-1个结点*/ p=(linklist)malloc(sizeof(listnode); p-data=i; p-next=head; head=p; r-next=head; /*生成循环链表*/ jose(head,s,m); /*调用函数*/ 6、有一种简单的排序算法，叫做计数排序（count sorting）。这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到
9、另一个新的表中。必须注意的是，表中所有待排序的关键码互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小，假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c。 (1) (3分)给出适用于计数排序的数据表定义; (2) (7分)使用Pascal或C语言编写实现计数排序的算法； (3) (4分)对于有n个记录的表，关键码比较次数是多少? (4) (3分)与简单选择排序相比较，这种方法是否更好?为什么?7、给出折半查找的递归算法，并给出算法时间复杂度性分析。8、 连通图的生成树包括图中的全部n个顶点和足以
10、使图连通的n-1条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，若不再连通，则将该边恢复。若仍连通，继续向下删；直到剩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(
11、%d%d%d ,&edgei.i ,&edgei.j ,&edgei.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()是测试图是否连通的函数，可用图的遍历实现，9、设T是一棵满二叉树，编写一个将T的先序遍历序列转换为后序遍历序列的递归算法。10、设从键盘输入一整数的序列：a1, a2, a3，an,试编写算法实现：用栈结构存储输入的整数，当ai-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。设有一个背包可以放入的物品重量为S，现有n件物品，重量分别为W1，W2，.，Wn。问能否从这n件物品中选择若干件放入背包，使得放入的重量之和正好是S。设布尔函数Knap(S，n)表示背包问题的解，Wi(i=1,2,.，n)均为正整数
