2016年下半年程序员下午试卷案例

阅读以下说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏内。
【说明】
设有整数数组A[1：N]（N>1），其元素有正有负。下面的流程图在该数组中寻找连续排列的若干个元素，使其和达到最大值，并输出其起始下标K、元素个数L以及最大的和值M。
例如，若数组元素依次为3，-6，2，4，-2，3，-1，则输出K=3，L=4,M=7。该流程图中考察了A[1：N]中所有从下标i到下标j（j≥i）的各元素之和S，并动态地记录其最大值M。

问题：1.1 【流程图】

注：循环开始框内应给出循环控制变量的初值和终值，默认递增值为1，格式为：循环控制变量=初值，终值

阅读以下代码，回答问题1至问题3，将解答填入答题纸的对应栏内。
【代码1】

【代码2】

【代码3】

问题：2.1 写出代码1运行后的输出结果。

问题：2.2 写出代码2运行后的输出结果。

问题：2.3 代码3的功能与代码2完全相同，请补充3中的空缺，将解答写入答题纸的对应栏内。

阅读以下说明和代码，填补代码中的空缺，将解答填入答题纸的对应栏内。
【说明】
下面的程序利用快速排序中划分的思想在整数序列中找出第k小的元素（即将元素从小到大排序后，取第k个元素）。
对一个整数序列进行快速排序的方法是：在待排序的整数序列中取第一个数作为基准值，然后根据基准值进行划分，从而将待排序的序列划分为不大于基准值者（称为左子序列）和大于基准值者（称为右子序列），然后再对左子序列和右子序列分别进行快速排序，最终得到非递减的有序序列。
例如，整数序列“19,12,30,11,7,53,78,25"的第3小元素为12。整数序列“19,12,7,30,11,11,7,53,78,25,7"的第3小元素为7。
函数partition（int a[],int low,int high）以a[low]的值为基准，对a[low],a[low+1],…,a[high]进行划分，最后将该基准值放入a[i](low≤i≤high)，并使得a[low],a[low+1],...,a[i-1]都小于或等于a[i]，而a[i+1],a[i+2],...,a[high]都大于a[i]。
函教findkthElem(int a[],int startIdx,int endIdx,inr k)在a[startIdx],a[startIdx+1],...,a[endIdx]中找出第k小的元素。

问题：3.1 【代码】

阅读以下说明和代码，填补代码中的空缺，将解答填入答题纸的对应栏内。
【说明】
图是很多领域中的数据模型，遍历是图的一种基本运算。从图中某顶点v出发进行广度优先遍历的过程是：
①访问顶点v；
②访问V的所有未被访问的邻接顶点w1,w2,...,wk；
③依次从这些邻接顶点w1,w2,...,wk出发，访问其所有未被访问的邻接顶点；依此类推，直到图中所有访问过的顶点的邻接顶点都得到访问。
显然，上述过程可以访问到从顶点V出发且有路径可达的所有顶点。对于从v出发不可达的顶点u，可从顶点u出发再次重复以上过程,直到图中所有顶点都被访问到。
例如，对于图4-1所示的有向图G，从a出发进行广度优先遍历，访问顶点的一种顺序为a、b、c、e、f、d。