2016年下半年軟考程序員下午真題第二部分：

>>>點(diǎn)擊進(jìn)入軟考初級(jí)程序員歷年真題下載

試題三（共15分）

閱讀以下說(shuō)明和代碼，填補(bǔ)代碼中的空缺，將解答填入答題紙的對(duì)應(yīng)欄內(nèi)。

【說(shuō)明】

下面的程序利用快速排序中劃分的思想在整數(shù)序列中找出第k小的元素（即將元素從小到大排序后，取第k個(gè)元素）。

對(duì)一個(gè)整數(shù)序列進(jìn)行快速排序的方法是：在待排序的整數(shù)序列中取第一個(gè)數(shù)作為基準(zhǔn)值，然后根據(jù)基準(zhǔn)值進(jìn)行劃分，從而將待排序的序列劃分為不大于基準(zhǔn)值者（稱為左子序列）和大于基準(zhǔn)值者（稱為右子序列），然后再對(duì)左子序列和右子序列分別進(jìn)行快速排序，最終得到非遞減的有序序列。

例如，整數(shù)序列“19,12,30,11,7,53,78,25”的第3小元素為12。整數(shù)序列“19,12,7,30,11,11,7，53.78,25,7”的第3小元素為7。

函數(shù)partition（int a[],int low,int high）以a[low]的值為基準(zhǔn)，對(duì)a[low]、a[low+l]、…、a[high]進(jìn)行劃分，最后將該基準(zhǔn)值放入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）

{//對(duì)a[low..high]進(jìn)行劃分，使得a[low..i]中的元素都不大于a[i+1..high]中的元素。

int pivot=a[low]；//pivot表示基準(zhǔn)元素

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）；//基準(zhǔn)元素定位

return i；

}

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

{ //整數(shù)序列存儲(chǔ)在a[startldx..endldx]中，查找并返回第k小的元素。

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

return-1;//參數(shù)錯(cuò)誤

if(startIdx<endldx){

int loc=partition(a,startIdx,endldx)；∥進(jìn)行劃分，確定基準(zhǔn)元素的位置

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

return（3）；

if(k-l<loc)//繼續(xù)在基準(zhǔn)元素之前查找

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

else／／繼續(xù)在基準(zhǔn)元素之后查找

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)//計(jì)算序列中的元素個(gè)數(shù)

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分）

閱讀以下說(shuō)明和代碼，填補(bǔ)代碼中的空缺，將解答填入答題紙的對(duì)應(yīng)欄內(nèi)。

【說(shuō)明】

圖是很多領(lǐng)域中的數(shù)據(jù)模型，遍歷是圖的一種基本運(yùn)算。從圖中某頂點(diǎn)v出發(fā)進(jìn)行廣度優(yōu)先遍歷的過(guò)程是：

①訪問(wèn)頂點(diǎn)v；

②訪問(wèn)V的所有未被訪問(wèn)的鄰接頂點(diǎn)W1,W₂,..,W_k；

③依次從這些鄰接頂點(diǎn)W₁,W₂,..,W_k出發(fā)，訪問(wèn)其所有未被訪問(wèn)的鄰接頂點(diǎn)；依此類推，直到圖中所有訪問(wèn)過(guò)的頂點(diǎn)的鄰接頂點(diǎn)都得到訪問(wèn)。

顯然，上述過(guò)程可以訪問(wèn)到從頂點(diǎn)V出發(fā)且有路徑可達(dá)的所有頂點(diǎn)。對(duì)于從v出發(fā)不可達(dá)的頂點(diǎn)u，可從頂點(diǎn)u出發(fā)再次重復(fù)以上過(guò)程,直到圖中所有頂點(diǎn)都被訪問(wèn)到。

例如，對(duì)于圖4-1所示的有向圖G，從a出發(fā)進(jìn)行廣度優(yōu)先遍歷，訪問(wèn)頂點(diǎn)的一種順序?yàn)閍、b、c、e、f、d。

設(shè)圖G采用數(shù)組表示法（即用鄰接矩陣arcs存儲(chǔ)），元素arcs[i][j]定義如下：

圖4-1的鄰接矩陣如圖4-2所示，頂點(diǎn)a~f對(duì)應(yīng)的編號(hào)依次為0~5.因此，訪問(wèn)頂點(diǎn)a的鄰接頂點(diǎn)的順序?yàn)閎，c，e。

函數(shù)BFSTraverse(Graph G)利用隊(duì)列實(shí)現(xiàn)圖G的廣度優(yōu)先遍歷。

相關(guān)的符號(hào)和類型定義如下：

#define MaxN：50／*圖中最多頂點(diǎn)數(shù)*／

typedef int AdjMatrix[MaxN][MaxN]；

typedef struct{

int vexnum，edgenum;／*圖中實(shí)際頂點(diǎn)數(shù)和邊（?。?shù)*／

AdjMatrix arcs；／*鄰接矩陣*／

)Graph；

typedef int QElemType；

enum{ERROR=0;OK=l};

代碼中用到的隊(duì)列運(yùn)算的函數(shù)原型如表4-1所述，隊(duì)列類型名為QUEUE。

【代碼】

int BFSTraverse(Graph G)

{ //圖G進(jìn)行廣度優(yōu)先遍歷，圖采用鄰接矩陣存儲(chǔ)

unsigned char*visited；//visited[]用于存儲(chǔ)圖G中各頂點(diǎn)的訪問(wèn)標(biāo)志，0表示未訪問(wèn)

int v，w；u；

QUEUEQ Q;

//申請(qǐng)存儲(chǔ)頂點(diǎn)訪問(wèn)標(biāo)志的空間，成功時(shí)將所申請(qǐng)空間初始化為0

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

If(（1）)

retum ERROR;

（2）；//初始化Q為空隊(duì)列

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

if(!visited[v]){//從頂點(diǎn)v出發(fā)進(jìn)行廣度優(yōu)先遍歷

printf("%d”，v)；//訪問(wèn)頂點(diǎn)v并將其加入隊(duì)列

visited[v]=l；

（3）；

while(！isEmpty(Q)){

（4）；//出隊(duì)列并用u表示出隊(duì)的元素

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

if（G.arcs[u][w]!=0&&（5）){//w是u的鄰接頂點(diǎn)且未訪問(wèn)過(guò)

printf("%d”，w)；//訪問(wèn)頂點(diǎn)w

visited[w]=1；

EnQueue(&Q,w);

}

}

}

}

free(visited);

return OK;

)//BFSTraverse