2016年下半年软考程序员下午真题第二部分：

>>>点击进入软考初级程序员历年真题下载

试题三（共15分）

阅读以下说明和代码，填补代码中的空缺，将解答填入答题纸的对应栏内。

【说明】

下面的程序利用快速排序中划分的思想在整数序列中找出第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+l]、…、a[high]进行划分，最后将该基准值放入a[i](low≤i≤high)，并使得a[low]、a[low+l]、，．．、A[i-1]都小于或等于a[i]，而a[i+l]、a[i+2]、．．、a[high]都大于a[i]。

函教findkthElem(int a[],int startIdx,int endIdx,inr k)在a[startIdx]、a[startIdx+1]、...、a[endIdx]中找出第k小的元素。

【代码】

#include<stdio.h>

#include<stdlib.h>

int partition（int a[]，int low,int high）

{//对a[low..high]进行划分，使得a[low..i]中的元素都不大于a[i+1..high]中的元素。

int pivot=a[low]；//pivot表示基准元素

int i=low,j=high;

while(（1）){

While(i<j&&a[j]>pivot)--j;

a[i]=a[j]

While(i<j&&a[i]>pivot)++i;

a[j]=a[i]

}

（2）；//基准元素定位

return i；

}

int findkthElem（int a[]，int startIdx，int endIdx,int k）

{ //整数序列存储在a[startldx..endldx]中，查找并返回第k小的元素。

if(startldx<0||endIdx<0||startIdx>endIdx||k<1||k-l>endIdx||k-1<startIdx)

return-1;//参数错误

if(startIdx<endldx){

int loc=partition(a,startIdx,endldx)；∥进行划分，确定基准元素的位置

if(loc==k-1)∥找到第k小的元素

return（3）；

if(k-l<loc)//继续在基准元素之前查找

return findkthElem(a，（4），k）；

else／／继续在基准元素之后查找

return findkthElem(a，（5），k);

}

return a[startIdx]；

}

int main()

{

int i,k;

int n;

int a[]={19,12,7,30,11,11,7,53,78,25,7};

n=sizeof(a)／sizeof(int)//计算序列中的元素个数

for(k=1;k＜n+1；k++){

for(i=0;i＜n;i++){

printf(“%d/t”,a[i]);

}

printf(“\n”);

printf(“elem%d=%d\n,k,findkthElem(a,0,n-1,k));//输出序列中第k小的元素

}

return 0；

}

试题四（共15分）

阅读以下说明和代码，填补代码中的空缺，将解答填入答题纸的对应栏内。

【说明】

图是很多领域中的数据模型，遍历是图的一种基本运算。从图中某顶点v出发进行广度优先遍历的过程是：

①访问顶点v；

②访问V的所有未被访问的邻接顶点W1,W₂,..,W_k；

③依次从这些邻接顶点W₁,W₂,..,W_k出发，访问其所有未被访问的邻接顶点；依此类推，直到图中所有访问过的顶点的邻接顶点都得到访问。

显然，上述过程可以访问到从顶点V出发且有路径可达的所有顶点。对于从v出发不可达的顶点u，可从顶点u出发再次重复以上过程,直到图中所有顶点都被访问到。

例如，对于图4-1所示的有向图G，从a出发进行广度优先遍历，访问顶点的一种顺序为a、b、c、e、f、d。

设图G采用数组表示法（即用邻接矩阵arcs存储），元素arcs[i][j]定义如下：

图4-1的邻接矩阵如图4-2所示，顶点a~f对应的编号依次为0~5.因此，访问顶点a的邻接顶点的顺序为b，c，e。

函数BFSTraverse(Graph G)利用队列实现图G的广度优先遍历。

相关的符号和类型定义如下：

#define MaxN：50／*图中最多顶点数*／

typedef int AdjMatrix[MaxN][MaxN]；

typedef struct{

int vexnum，edgenum;／*图中实际顶点数和边（弧）数*／

AdjMatrix arcs；／*邻接矩阵*／

)Graph；

typedef int QElemType；

enum{ERROR=0;OK=l};

代码中用到的队列运算的函数原型如表4-1所述，队列类型名为QUEUE。

【代码】

int BFSTraverse(Graph G)

{ //图G进行广度优先遍历，图采用邻接矩阵存储

unsigned char*visited；//visited[]用于存储图G中各顶点的访问标志，0表示未访问

int v，w；u；

QUEUEQ Q;

//申请存储顶点访问标志的空间，成功时将所申请空间初始化为0

visited=(char*)calloc(G.vexnum,sizeof(char));

If(（1）)

retum ERROR;

（2）；//初始化Q为空队列

for(v=0;v<G.vexnum;v++){

if(!visited[v]){//从顶点v出发进行广度优先遍历

printf("%d”，v)；//访问顶点v并将其加入队列

visited[v]=l；

（3）；

while(！isEmpty(Q)){

（4）；//出队列并用u表示出队的元素

for(v=0;v<G.vexnum;w++){

if（G.arcs[u][w]!=0&&（5）){//w是u的邻接顶点且未访问过

printf("%d”，w)；//访问顶点w

visited[w]=1；

EnQueue(&Q,w);

}

}

}

}

free(visited);

return OK;

)//BFSTraverse