試題四(共15分)

閱讀下列說明和C代碼,回答問題1至問題3.將解答寫答題紙的對應(yīng)欄內(nèi)。

[說明]

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

[問題1] (8分)

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

[問題2] (4分)

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

[問題3] (3分)

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