試題四(共15分)

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

[說(shuō)明]

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

[問(wèn)題1] (8分)

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

[問(wèn)題2] (4分)

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

[問(wèn)題3] (3分)

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