当前位置:首页计算机类软件水平考试中级软件设计师->阅读下列说明和C代码,回答问题1和问题2,将解答填入答题纸的

阅读下列说明和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值。

中级软件设计师,历年真题,2021年上半年(下午)《软件设计师》真题

其中:

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:

(1)r<=N

(2)intj=i+r-1;

(3)temp<m[i][j]

(4)s[i][j]+1

问题2:

(5)动态规划

(6)O(n^3)

(7)O(n^2)

更新时间:2021-12-02 11:01

你可能感兴趣的试题

单选题

Advancements in ( )have contributed to the growth of the automotive industry through the creation and evolution of self-driving vehicles.

  • A.Artificial Intelligence
  • B.Cloud Computing
  • C.Internet of Things
  • D.Big Data
查看答案
单选题

In project human resource management , ( )is not a source of power for the project manager.

  • A.referent power
  • B.expert power
  • C.reward power
  • D.audit power
查看答案
单选题

At the project establishment stage , the feasibility study mainly includes techinical feasibility analysis , ( ), operation environment feasibility analysis and other aspects of feasibility analysis.

  • A.detail feasibility analysis
  • B.opportunity analysis
  • C.economic feasibility analysis
  • D.risk analysis
查看答案
单选题

( )is a grid that shows the project resources assigned to each work package.

  • A.Stakeholder engagement assessment matrix
  • B.Requirements traceability matrix
  • C.Probability and impact matrix
  • D.Responsibility assignment matrix
查看答案
单选题

Xinhua News Agency reported in January 2022,Chian will further promote the developmet of a digital economy during the 14th Five-Year Plan eriod(2021-2025). The plan also emphasized industrial ( )transformation.

  • A.digital
  • B.networking
  • C.intelligentize
  • D.informatization
查看答案
单选题

某公司投资一个使用寿命为5年的项目,第一年年初投入1000万元,从第1年到第5年每年年末都有净现金流量300万元。则项目的静态投资回收期为( )年。

  • A.2
  • B.2.5
  • C.3
  • D.3.3
查看答案
单选题

下图是某地的街区网络图(单位:)里),疫情防控期间,一辆消毒车从疾控中心出发,需要消杀所有的街道并返回疾控中心。该消毒车完成消杀工作至少需要运行( )公里 。

高级信息系统项目管理师,历年真题,2022年上半年(上午)《信息系统项目管理师》真题

  • A.43
  • B.45
  • C.46
  • D.48
查看答案
单选题

某公司有东部、中部、西部三个生产基地,生产的产品需要运送带甲、乙、丙、丁四个市场,从生产基地到各个市场的单位运价及产量和需求量如表所示,完成该运输任务所需的最小运费为( )。

高级信息系统项目管理师,历年真题,2022年上半年(上午)《信息系统项目管理师》真题

  • A.242
  • B.244
  • C.289
  • D.302
查看答案
单选题

某炼油厂每季度需供应合同单位汽油15吨,煤油12吨,重油12吨,该厂从甲乙两处运回原油提炼,已知两处炼油成分如表所示,从甲处采购原油价格为2000元/吨,乙处为2900元/吨,为了使成本最低,炼油厂应从甲处购15吨,乙处采购( )吨。

高级信息系统项目管理师,历年真题,2022年上半年(上午)《信息系统项目管理师》真题

  • A.20
  • B.25
  • C.30
  • D.35
查看答案
单选题

某炼油厂每季度需供应合同单位汽油15吨,煤油12吨,重油12吨,该厂从甲乙两处运回原油提炼,已知两处炼油成分如表所示,从甲处采购原油价格为2000元/吨,乙处为2900元/吨,为了使成本最低,炼油厂应从甲处购( )吨,乙处采购20吨。

高级信息系统项目管理师,历年真题,2022年上半年(上午)《信息系统项目管理师》真题

  • A.15
  • B.20
  • C.25
  • D.30
查看答案