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