专业软件设计师网站|培训机构|服务商（加客服微信:cnitpm或QQ：947530340进软件设计师学霸群）
用户登录:登录 注册 QQ客服
地区

软题库 培训课程

软件设计师
当前位置：信管网 >> 软件设计师 >> 每日一练 >> 文章内容
软件设计师案例分析每日一练试题（2022/7/12）
来源：信管网 2022年07月13日 【所有评论】 分享到微信

软件设计师案例分析当天每日一练试题地址：www.cnitpm.com/exam/ExamDayAL.aspx?t1=4

往期软件设计师每日一练试题汇总：www.cnitpm.com/class/27/e4_1.html

软件设计师案例分析每日一练试题（2022/7/12）在线测试：www.cnitpm.com/exam/ExamDayAL.aspx?t1=4&day=2022/7/12

点击查看：更多软件设计师习题与指导

软件设计师案例分析每日一练试题内容（2022/7/12）

阅读下列说明和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
#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表示)。


信管网试题答案与解析：www.cnitpm.com/st/455048357.html

信管网考友试题答案分享：

信管网yiren：
1、r＜=n 2、int j=i+r-1 3、temp＜m[i][j] 4、s[i][j]+1,j 5、动态规划 6、o（n^2） 7、o（n^2）

信管网cnitpm509362975264：
问题1： 1: r＜=n 2: j ＝ i+r-1 3: temp ＜s[i][j] 4:s[i][j]+1,j 问题2： 动态规划法 o（nlog（n）） o（n）

信管网cnitpm464882268830：
1. （1）r＜=n （2）int j=i+r-1 （3） temp＜m[i][j] （4） 2. 动态规划 o（n2） o（nlogn）

信管网试题答案与解析：www.cnitpm.com/st/455048357.html
扫码关注公众号

温馨提示：因考试政策、内容不断变化与调整，信管网网站提供的以上信息仅供参考，如有异议，请以权威部门公布的内容为准！

信管网致力于为广大信管从业人员、爱好者、大学生提供专业、高质量的课程和服务，解决其考试证书、技能提升和就业的需求。

信管网软考课程由信管网依托10年专业软考教研倾力打造，官方教材参编作者和资深讲师坐镇，通过深研历年考试出题规律与考试大纲，深挖核心知识与高频考点，为学员考试保驾护航。面授、直播＆录播，多种班型灵活学习，满足不同学员考证需求，降低课程学习难度，使学习效果事半功倍。

上一篇：软件设计师每日一练试题（2022/7/

相关内容

软件设计师每日一练试题（2022/7/12）

典型及新一代信息技术与应用试题：云计算中心提供的虚

未指定试题：theprocessof（）sched

计算题试题：下图是某项目的进度网络图，则在保障不会

项目合同管理试题：《合同法》第六十一条明确规定，对

信息化与信息系统试题：某企业是某个供应链的成员，同

贵州专业技术类职业资格与职称对应目录2022年版发

软件设计师职称有学历资历要求吗？

软考职称有学历资历要求吗？

如果软考成绩马上发布，你知道如何查询吗

发表评论  查看完整评论  
考试介绍
报考指南 报名时间 报名流程 考试时间 考试大纲 考试教程 成绩查询 证书领取 真题下载
免费领取学习资料
考试新手指南 学习计划攻略 精华备考资料 案例论文干货 章节模拟试题 免费试听课程
一键领取
软考题库
推荐文章
各省市软考报名简章
信管网APP下载

考试信息推送

免费在线答题

优惠报班活动

直播录播辅导
推荐内容
PMP学习网 | 软题库 | 网考网 | 注册消防考试网