為方便廣大考生考后估分對答案，希賽網特向廣大學員和網友搜集整理了相關真題信息，供大家參考。收集完整2021年上半年軟考軟件設計師真題答案后，希賽網的老師也將在考后第一時間進行真題答案解析，敬請廣大考友考后積極關注。

現在要推薦給大家的是文字版2021年上半年軟考軟件設計師考試下午真題及答案解析試題四。

試題四(共15分)

閱讀下列說明和C代碼，回答問題1和問題2，將解答填入答題紙的對應欄內。

[說明]

凸多邊形是指多邊形的任意兩點的連線均落在多邊形的邊界或者內部。相鄰的點連線落在多邊形邊上，稱為邊，不相鄰的點連線落在多邊形內部。稱為弦。假設任意兩點連線上均有權重，凸多邊形最優三幫劑分問題定義為：求將凸多邊形劃分為不相交的三角形集合，且各三角形權重之和最小的剖分方案。每個三角形的權重為三條邊權重之和。

假設N個點的凸多邊形點編號為V1,V2,……,VN,若在VK處將原凸多邊形劃分為一個三角形V1VkVN，兩個子多邊形V1,V2,…,Vk和Vk,Vk+1,…VN，得到一個最優的剖分方案，則該最優剖分方案應該包含這兩個子凸邊形的最優剖分方案。用m[i][j]表示帶你Vi-1,Vi,…Vj構成的凸多邊形的最優剖分方案的權重，S[i][j]記錄剖分該凸多邊形的k值。

則

其中：

Wj,i-1分別為該三角形三條邊的權重。求解凸多邊形的最優剖分方案，即求解最小剖分的權重及對應的三角形集。

[C代碼]

＃include＜stdio.h＞

＃define N 6                       

//凸多邊形規模

int m[N＋1] [N＋1];         //m[i][j]表示多邊形Vi-1到Vj最優三角剖分的權值

int S[N＋1] [N＋1]；        //S[i][j]記錄多邊形Vi-1 到Vj最優三角剖分的k值

int W[N＋1] [N＋1]；      //凸多邊形的權重矩陣，在main函數中輸入

/*三角形的權重a，b，c，三角形的頂點下標*/

int get_ triangle_weight（int a，int b，int c）{

return W[a][b]＋W[b][c]＋W[c][a];

}

/*求解最優值*/

void triangle_partition(){

int i,r,k,j;

int temp;

/*初始化*/

for(i=1;i<=N;i++){

m[i][i]=0;

}

/*自底向上計算m，S*/

for(r=2;（1）;r++){/*r為子問題規模*/                  //r<=N

for(i=1;k<=N-r+1;i++){

（2）;               //int j=i+r-1

m[i][j]= m[i][j]+m[i+1][j]+get_triangle_weight(i-1,i,j);     /*k=j*/

S[i][j]=i;

for(k=j+1;k<j;k++){/*計算 [i][j]的最小代價*/

temp=m[i][k]+m[k+1][j]+ge_triangle_ weight(i-1,k,j);

if((3)){/*判斷是否最小值*/    //temp<m[i][j]

m[i][j]=temp;

S[i][j]=k;

}

}

}

}

}

/*輸出剖分的三角形i，j：凸多邊形的起始點下標*/

void print_triangle(int i,int j){

if(i==j)       return;

print_triangle(i,S[i][j]);

print_

triangle((4));           //s[i][j]+1,j

print(“V%d- -V%d-

-V%d\n“,i-1,S[i][j],j);

}

[問題1] (8分)

根據說明和C代碼，填充C代碼中的空(1) ~ (4)。

[問題2] (7分)

根據說明和C代碼，該算法采用的設計策略為(5)，算法的時間復雜度為(6)，空間復雜度為(7) (用0表示)。

2021上半年軟件設計師下午真題及答案解析【完整版】請大家點擊下載附件查看，或-掃碼-看答案，提前估分！