2021年11月08日来源:信管网 作者:cnitpm
目前,2021年下半年软件设计师真题答案已公布,为帮助广大考生考后估分,信管网现已整理发布了真题答案及解析供考生免费查看,点击下方链接即可!
试题四、
生物学上通常采用编辑距离来定义两个物种DNA序列的相似性,从而刻画物种之间的进化关系。具体来说,编辑距离是指将首将一个字符串变换为另- 一个字符所需要的最小操作次数。操作有三种,分别为:插入-一个字符、删除一一个字符以及将一个字符修改为另 -一个字符。用字符数组str1和str2分别表示长度分别为len1和len2的字符串,义二维数组d记录求解编辑距离的子问题最优解,则该二维数组可以递归定义为:
【问题1】 (8分)
根据说明扣C代器,填充C代期中的空(1)~(4)的。
【问题2】 (4分)
根据说明和C代码,算法采用了(5)设计策略,时间复杂度为(6)(用0符号表示,两个字符串的长度分别用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][i-1]
(4) d[len1][len2]
【问题2】
(5)动态规划法
(6)0(m*n)
【问题3】
(7)4
查看解析:www.cnitpm.com/st/459582835.html
温馨提示:因考试政策、内容不断变化与调整,信管网提供的以上信息仅供参考,如有异议,请考生以权威部门公布的内容为准!
相关推荐