1 / 7
文档名称:

2021年上半年(下午)《软件设计师》真题.docx

格式:docx   大小:883KB   页数:7页
下载后只包含 1 个 DOCX 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

2021年上半年(下午)《软件设计师》真题.docx

上传人:住在山区的Jack 2022/2/14 文件大小:883 KB

下载得到文件列表

2021年上半年(下午)《软件设计师》真题.docx

相关文档

文档介绍

文档介绍:2021年上半年(下午)《软件设计师》真题
注意:图片可根据实际需要调整大小
卷面总分:6分
答题时间:240分钟
试卷题量:6题
练****次数:0次


问答VkVN,两个子多边形V1,V2,…,Vk和Vk,Vk+1,…VN,得到一个最优的剖分方案,则该最优剖分方案应该包含这两个子凸边形的最优剖分方案。用m[i][j]表示带你Vi-1,Vi,…Vj构成的凸多边形的最优剖分方案的权重,S[i][j]记录剖分该凸多边形的k值。
其中:
Wj,i-1分别为该三角形三条边的权重。求解凸多边形的最优剖分方案,即求解最小剖分的权重及对应的三角形集。
[C代码]
#include
#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
temp=m[i][k]+m[k+1][j]+ge_triangle_ weight(i-1,k,j);
if((3)){/*判断是否最小值*/ //temp
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表示)。


正确答案:
本题解析:
问题1: