关键词：
阅读下列说明和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分别为该三角形三条边的权重。求解凸多边形的最优剖分方案，即求解最小剖分的权重及对应的三角形集。
＃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为子问题规模*/
for(i=1;k<=N-r+1;i++)
（2）;
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))
/*判断是否最小值*/
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));
print(“V%d- -V%d- -V%d\\n“,i-1,S[i][j],j);
[问题1] (8分)
根据说明和C代码，填充C代码中的空(1) ~ (4)。
(1)i<=N
(2)j=i+r-1
(3)temp<m[i][j]
(4)s[i][j]+1,j
[问题2] (7分)
根据说明和C代码，该算法采用的设计策略为(5)，算法的时间复杂度为(6)，空间复杂度为(7) (用O表示)。
(5)动态规划法
(6)O(n3)
(7)O(n2)
答案解析：
本题算法难度较大，在没有理解算法过程的前提下，首先可以根据相关信息进行部分填空。
首先根据题干描述出现的将问题规模从k开始截断，此时其实就是“最优子结构”的说法，并且本题出现了递归式的应用，是典型的动态规划法的应用。
又根据题目中的代码，出现了三层嵌套for循环，此时代码的时间复杂度为O(n3)。
本题用到的辅助空间记录中间解有2个数组m[i][j]和S[i][j]，都是二维数组，空间复杂度的量级为O(n2)。
最后分析代码填空部分。
第（1）空，r表示的是子问题规模，规模划分已知从r=2开始，子问题最大应该能够取到N，因此本空填写r<=N或其等价表示形式。
第（2）空缺失的是j的初始化赋值，本空较难。代码计算前边界为i，链长为r的链的后边界取值，结果为i+r-1，即本题填写j=i+r-1或其等价表示形式。
第（3）空缺失判断条件，此时注释明确说明此处判断最小值，判断后，m[i][j]值进行修改并修改为temp，也就是意味着m[i][j]此时记录的不是最优解（最小值），需要进行修正改为最小，即填写temp<m[i][j] 或其等价表示形式（某一个数值比最小值还小，则修改最小值）。
第（4）空缺失的是打印参数，结合代码上下文进行分析，上文打印print_triangle(i,S[i][j]);即截断的前一部分编号，下面print_ triangle((4));打印的应该是截断的后一部分，即填写s[i][j]+1,j。
2021年上半年软件设计师下午真题及答案解析(代码片段)
【说明】某社区蔬菜团购网站，为规范商品收发流程，便于查询客户订单情况，需要开发个信息系统。请根据下述需求描述完成该系统的数据库设计。【需求描述】（1）记录蔬菜供应商的信息，包括供应... 查看详情
2021年上半年软件设计师下午真题及答案解析(代码片段)
【说明】某停车场运营方为了降低运营成本，减员增效，提供良好的停车体验，欲开发无人值守停车系统，该系统的主要功能是∶1、信息维护。管理人员对车位（总数、空余车位数等）计费规则等基础信... 查看详情
2021年上半年软件设计师下午真题及答案解析(代码片段)
阅读下列说明和C代码，回答问题1和问题2，将解答填入答题纸的对应栏内。[说明]凸多边形是指多边形的任意两点的连线均落在多边形的边界或者内部。相邻的点连线落在多边形边上，称为边，不相邻的点连线落... 查看详情
2021年下半年软件设计师下午真题答案及解析(代码片段)
阅读下列说明和Java代码，将应填入（n）处的字句写在题纸的对应栏内。【说明】享元（flyweight）模式主要用于减少创建对象的数量，以低内存占用，提高性能。现要开发一个网络围棋程序允许多个玩... 查看详情
2021年下半年软件设计师下午真题答案及解析(代码片段)
阅读下列说明和Java代码，将应填入（n）处的字句写在题纸的对应栏内。【说明】享元（flyweight）模式主要用于减少创建对象的数量，以低内存占用，提高性能。现要开发一个网络围棋程序允许多个玩... 查看详情
2021年上半年软件设计师下午真题及答案解析
阅读下列说明和图，回答问题1至问题3，将解答填入答题纸的对应栏内。【说明】某中医医院拟开发一套线上抓药APP，允许患者凭借该医院医生开具的处方线上抓药，并提供免费送药上门服务。该系统的主要功能... 查看详情
2021年下半年软件设计师下午真题答案及解析(代码片段)
生物学上通常采用编辑距离来定义两个物种DNA序列的相似性，从而刻画物种之间的进化关系。具体来说，编辑距离是指将一个字符串变换为另一个字符串所需要的最小操作次数。操作有三种，分别为：插入一个字... 查看详情
2021年下半年软件设计师下午真题答案及解析(代码片段)
生物学上通常采用编辑距离来定义两个物种DNA序列的相似性，从而刻画物种之间的进化关系。具体来说，编辑距离是指将一个字符串变换为另一个字符串所需要的最小操作次数。操作有三种，分别为：插入一个字... 查看详情
2021年下半年软件设计师下午真题答案及解析
回答问题1至问题4，将解答填入答题纸的对应栏内【说明】某汽车维修公司为了便于管理车辆的维修情况，拟开发一套汽车维修管理系统，请根据下述需求描述完成该系统的数据库设计。【需求描述】（1）客... 查看详情
2021年下半年软件设计师下午真题答案及解析
回答问题1至问题4，将解答填入答题纸的对应栏内【说明】某汽车维修公司为了便于管理车辆的维修情况，拟开发一套汽车维修管理系统，请根据下述需求描述完成该系统的数据库设计。【需求描述】（1）客... 查看详情
2021年下半年软件设计师下午真题答案及解析
阅读下列说明和图，回答问题1至问题3，将解答填入答题纸的对应栏内。【说明】某游戏公司欲开发一款吃金币游戏。游戏的背景为一种回廊式迷宫(Maze)，在迷宫的不同位置上设置有墙。迷宫中有两种类型的机器人(Rob... 查看详情
2021年下半年软件设计师下午真题答案及解析
阅读下列说明和图，回答问题1至问题3，将解答填入答题纸的对应栏内。【说明】某游戏公司欲开发一款吃金币游戏。游戏的背景为一种回廊式迷宫(Maze)，在迷宫的不同位置上设置有墙。迷宫中有两种类型的机器人(Rob... 查看详情
2021年下半年软件设计师下午真题答案及解析
阅读下列说明和图，回答问题1至问题4，将解答填入答题纸的对应栏内。【说明】某现代农业种植基地为进一步提升农作物种植过程的智能化，欲开发智慧农业平台，集管理和销售于一体，该平台的主要功能有... 查看详情
2021年下半年软件设计师下午真题答案及解析
阅读下列说明和图，回答问题1至问题4，将解答填入答题纸的对应栏内。【说明】某现代农业种植基地为进一步提升农作物种植过程的智能化，欲开发智慧农业平台，集管理和销售于一体，该平台的主要功能有... 查看详情
2022年上半年软件设计师下午真题及答案解析
试题一（15分）某公司欲开发一款外卖订餐系统，集多家外卖平台和商户为一体，为用户提供在线浏览餐品、订餐和配送等服务。该系统的主要功能是：1.入驻管理。用户注册，商户申请入驻，设置按时... 查看详情
2022年上半年软件设计师下午真题及答案解析
试题一（15分）某公司欲开发一款外卖订餐系统，集多家外卖平台和商户为一体，为用户提供在线浏览餐品、订餐和配送等服务。该系统的主要功能是：1.入驻管理。用户注册，商户申请入驻，设置按时... 查看详情
2021年上半年软件设计师上午真题及答案解析(代码片段)
11、通常使用（）为IP数据报文进行加密。A.IPSecB.PP2PC.HTTPSD.TLS参考答案：A答案解析：IPSec工作于网络层，为IP数据报文进行加密。PP2P工作于数据链路层，用于链路加密。HTTPS是HTTP与SSL的结合体，为传输... 查看详情
2021年上半年软件设计师上午真题及答案解析(代码片段)
51、如下图如下E-R图中，两个实体R1、R2之间有一个联系E，当E的类型为（）时必须将E转换成—个独立的关系模式？A.1:1B.1:*C.*:1D.*:*参考答案：D答案解析：E-R图转关系模式转换原则：实体必须单独转... 查看详情