2023年湖南省数据分析深入

1、设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。2、我们用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中最长平台的长度。 /局部最长平台i++;j=i新平台起点。

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

3、矩阵中元素按行和按列都已排序，要求查找时间复杂度为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中。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]）或向左（当x4、给定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++)求最长路径中最短的一条。//在最长路径中，取最短的一条。

m记最长路径，k记出发顶点的下标。

printf(“医院应建在%d村庄，到医院距离为%d”,i,m);}for}//算法结束。

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

1、对图1所示的连通网g，请用prim算法构造其最小生成树（每选取一条边画一个图）。

2023年湖南省数据分析深入

2023年湖南省数据分析深入

2023年湖南省数据分析深入

2023年湖南省星级酒店经营数据分析

其他用户还读了