正文

2021年下半年软件设计师下午真题答案及解析(代码片段)

ZhangJun  ZhangJun  2022-11-23  684

关键词：

生物学上通常采用编辑距离来定义两个物种DNA序列的相似性，从而刻画物种之间的进化关系。具体来说，编辑距离是指将一个字符串变换为另一个字符串所需要的最小操作次数。操作有三种，分别为：插入一个字符、删除一个字符以及将一个字符修改为另一个字符。用字符数组str1和str2分别表示长度分别为len1和len2的字符串，定义二维数组d记录求解编辑距离的子问题最优解，则该二维数组可以递归定义为：

【C代码】
下面是算法的C语言实现。

常量和变量说明
A，B：两个字符数组
d：二维数组
i，j：循环变量
temp：临时变量
C程序

#include <stdio.h>
#define N 100
char A[N]="CTGA";
char B[N]="ACGCTA";
int d[N][N];
int min(int a, int b) 
	return a <b ? a: b;

int editdistance(char *str1, int len1, char *str2, int len2) 
	int i, j;
	int diff;
	int temp;
	for(i=0; i<=len1; i++) 
		d[i][0]=i;
	
	for(j=0; j<=len2; j++)	
		(1);
	
	for(i=1;i<=len1;i++)	
		for(j=1; j<=len2; j++)	
			if((2)) 
				d[i][j]=d[i-1][j-1];
			else 
				temp=min(d[i-1][j]+1, d[i][j-1]+1);
				d[i][j]=min(temp, (3));
			
		
	
	return (4);

【问题1】(8分)
根据说明和C代码，填充C代码中的空(1)~(4)。
【问题2】(4分)
根据说明和C代码，算法采用了(5)设计策略，时间复杂度为(6)(用O符号表示，两个字符串的长度分别用m和n表示)。
【问题3】(3分)
已知两个字符串A="CTGA"和B=“ACGCTA”，根据说明和C代码，可得出这两个字符串的编辑距离为(7)。
参考答案：
问题1：
(1) d[0][j]=j
(2) str1[i-1]==str2[j-1]
(3) d[i-1][j-1] +1
(4) d[len1][len2]
问题2：
（5）动态规划法（6）O(mn)
问题3：
（7）4
答案解析：

动态规划法离不开一个关键词，拆分，就是把求解的问题分解成若干个子阶段，前一问题的结果就是求解后一问题的子结构。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。

适用性
适用动态规划的问题必须满足最优化原理和无后效性。

最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。

将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。

解题思路

确定最优子结构:比如我们要求的结果F(X)的最优子结构可能为F(X-1)和F(X-2）
列转移方程:根据最优子结构可以列出转移方程F(X)=F(X-1)+F(X-2)
确定边界值:确定问题的边界，即当F(n)有可以确定的具体的值

时间复杂度

算法效率分析分为两种：第一种是时间效率，第二种是空间效率。时间效率被称为时间复杂度，而空间效率被称作空间复杂度。时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间，在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

常见的时间复杂度量级有：

常数阶O(1)
对数阶O(logN)
线性阶O(n)
线性对数阶O(nlogN)
平方阶O(n²)
立方阶O(n³)
K次方阶O(n^k)
指数阶(2^n)

动态规划算法一般是n步叠代计算局部最优解，每一步叠代需要计算m个子项，那么时间复杂度就是O(m*n)。如果只保存一步叠代的结果，空间复杂度就是O(m)；如果需要保存k步叠代结果，空间复杂度就是O(m*k)

2021年下半年软件设计师下午真题答案及解析(代码片段)

生物学上通常采用编辑距离来定义两个物种DNA序列的相似性，从而刻画物种之间的进化关系。具体来说，编辑距离是指将一个字符串变换为另一个字符串所需要的最小操作次数。操作有三种，分别为：插入一个字... 查看详情

2021年下半年软件设计师下午真题答案及解析(代码片段)

2021年上半年软件设计师下午真题及答案解析(代码片段)

阅读下列说明和Java代码，将应填入（n）处的字句写在答题纸的对应栏内。【说明】层叠菜单是窗口风格的软件系统中经常采用的一种系统功能组织方式。层叠菜单中包含的可能是一个菜单项（直接对应某个功能&#... 查看详情

2021年上半年软件设计师下午真题及答案解析(代码片段)

【说明】某社区蔬菜团购网站，为规范商品收发流程，便于查询客户订单情况，需要开发个信息系统。请根据下述需求描述完成该系统的数据库设计。【需求描述】（1）记录蔬菜供应商的信息，包括供应... 查看详情

2021年上半年软件设计师下午真题及答案解析(代码片段)

【说明】某停车场运营方为了降低运营成本，减员增效，提供良好的停车体验，欲开发无人值守停车系统，该系统的主要功能是∶1、信息维护。管理人员对车位（总数、空余车位数等）计费规则等基础信... 查看详情

2021年下半年软件设计师下午真题答案及解析

回答问题1至问题4，将解答填入答题纸的对应栏内【说明】某汽车维修公司为了便于管理车辆的维修情况，拟开发一套汽车维修管理系统，请根据下述需求描述完成该系统的数据库设计。【需求描述】（1）客... 查看详情

2021年下半年软件设计师下午真题答案及解析

阅读下列说明和图，回答问题1至问题3，将解答填入答题纸的对应栏内。【说明】某游戏公司欲开发一款吃金币游戏。游戏的背景为一种回廊式迷宫(Maze)，在迷宫的不同位置上设置有墙。迷宫中有两种类型的机器人(Rob... 查看详情

2021年下半年软件设计师下午真题答案及解析

阅读下列说明和图，回答问题1至问题4，将解答填入答题纸的对应栏内。【说明】某现代农业种植基地为进一步提升农作物种植过程的智能化，欲开发智慧农业平台，集管理和销售于一体，该平台的主要功能有... 查看详情

2021年下半年软件设计师下午真题答案及解析

2021年上半年软件设计师下午真题及答案解析(代码片段)

阅读下列说明和C代码，回答问题1和问题2，将解答填入答题纸的对应栏内。[说明]凸多边形是指多边形的任意两点的连线均落在多边形的边界或者内部。相邻的点连线落在多边形边上，称为边，不相邻的点连线落... 查看详情

2021年上半年软件设计师下午真题及答案解析

阅读下列说明和图，回答问题1至问题3，将解答填入答题纸的对应栏内。【说明】某中医医院拟开发一套线上抓药APP，允许患者凭借该医院医生开具的处方线上抓药，并提供免费送药上门服务。该系统的主要功能... 查看详情

2021年下半年系统架构设计师下午真题及答案解析

试题一(共25分) 某公司拟开发一套机器学习应用开发平台，支持用户使用浏览器在线进行基于机器学习的智能应用开发活动。该平台的核心应用场景是用户通过拖拽算法组件灵活定义机器学习流程，采用自助方式进行... 查看详情

2022年下半年软件设计师下午真题及答案解析

试题一（共15分）随着新能源车数量的迅猛增长，全国各地电动汽车配套充电桩急速增长，同时也带来了充电桩计量准确性的问题。充电桩都需要配备相应的电能计量和电费计费功能，需要对充电计量准确性强... 查看详情

2018年下半年软件设计师下午真题及答案解析

试题一（15分）某房产中介连锁企业欲开发一个基于Web的房屋中介信息系统，以有效管理房源和客户，提高成交率。该系统的主要功能是:1.房源采集与管理。系统自动采集外部网站的潜在房源信息，保存为潜在... 查看详情

2021年下半年软件设计师上午真题答案及解析(代码片段)

51、已知一个文件中出现的各字符及其对应的频率如下表所示。采用Huffman编码，则该文件中字符a和c的码长分别为(1)。若采用Huffman编码，则字序列“110001001101”的编码应为(2)。(1)A、1和3B、1和4C、3和3D、3和4(2)A、faceB、baceC... 查看详情