2015年江西省数据大纲

2015年江西省数据大纲

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(i<n-1)

{while(i<n-1 && b[i]==b[i+1]) i++;

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

i++; j=i; } //新平台起点

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

}// Platform

2、设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给出构造过程。

3、给出折半查找的递归算法，并给出算法时间复杂度性分析。