2. 从业资格
  3. 生物学上通常采用编辑距离来定义两个物种DNA序列的相似性,从而刻画物种之间的进化

生物学上通常采用编辑距离来定义两个物种DNA序列的相似性,从而刻画物种之间的进化

最全题库2022-08-02  39
问题 生物学上通常采用编辑距离来定义两个物种DNA序列的相似性,从而刻画物种之间的进化关系。具体来说，编辑距离是指将首一个字符串变换为另一个字符所需要的最小操作次数。操作有三种,分别为:插入一个字符、删除一个字符以及将一个字符修改为另 一个字符。用字符数组str1和str2分别表示长度分别为len1和len2的字符串,定义二维数组d记录求解编辑距离的子问题最优解,则该二维数组可以递归定义为:C代码下面是算法的C语言实现。(1)常量和变更说明  A,B:两个字符数组  d:二维数组  i,j:循环变量  temp:临时变量(2)C程序#include＜stdio.h>#define N 100return (  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][i-1]
(4) d[len1][len2]
【问题2】
(5)动态规划法
(6)0(m*n)
【问题3】
(7)4
转载请注明原文地址:https://www.tihaiku.com/congyezige/2410698.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)