目前，2021年下半年軟件設計師真題答案已公布，為幫助廣大考生考后估分，信管網(wǎng)現(xiàn)已整理發(fā)布了真題答案及解析供考生免費查看，點擊下方鏈接即可！

2021年下半年軟件設計師上午真題答案（基礎知識） 

2021年下半年軟件設計師下午真題答案（應用技術）

試題四、

生物學上通常采用編輯距離來定義兩個物種DNA序列的相似性,從而刻畫物種之間的進化關系。具體來說，編輯距離是指將首將一個字符串變換為另- 一個字符所需要的最小操作次數(shù)。操作有三種,分別為:插入-一個字符、刪除一一個字符以及將一個字符修改為另 -一個字符。用字符數(shù)組str1和str2分別表示長度分別為len1和len2的字符串,義二維數(shù)組d記錄求解編輯距離的子問題最優(yōu)解,則該二維數(shù)組可以遞歸定義為:

【問題1】 (8分)

根據(jù)說明扣C代器，填充C代期中的空(1)~(4)的。

【問題2】 (4分)

根據(jù)說明和C代碼，算法采用了(5)設計策略,時間復雜度為(6)(用0符號表示，兩個字符串的長度分別用m和n表示)。

【問題3】 (3分)

已知兩個字符串A="CTGA"和B="ACGCTA",根據(jù)說明和C代碼，可得出這兩個字符串的編輯距離為(7)。

信管網(wǎng)參考答案：

【問題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)動態(tài)規(guī)劃法

(6)0(m*n)

【問題3】

(7)4

查看解析：www.jazzmuze.com/st/459582835.html