最新中級(jí)軟件設(shè)計(jì)師下半下午試題和答案(編輯修改稿)
2025-07-21 05:46 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 代碼，回答問(wèn)題 1 至問(wèn)題 3，將解答寫(xiě)在答題紙的對(duì)應(yīng)欄內(nèi)。【說(shuō)明】計(jì)算兩個(gè)字符串 x 和 y 的最長(zhǎng)公共子串（Longest Common Substring）。假設(shè)字符串 x 和字符串 y 的長(zhǎng)度分別為 m 和 n，用數(shù)組 c 的元素 c[i][j]記錄 x 中前 i個(gè)字符和 y 中前 j 個(gè)字符的最長(zhǎng)公共子串的長(zhǎng)度。c[i][j]滿(mǎn)足最優(yōu)子結(jié)構(gòu)，其遞歸定義為：計(jì)算所有 c[i][j](0 ≤i ≤ m，0 ≤j ≤ n)的值，值最大的 c[i][j]即為字符串x 和 y 的最長(zhǎng)公共子串的長(zhǎng)度。根據(jù)該長(zhǎng)度即 i 和 j,+確定一個(gè)最長(zhǎng)公共子串?！綜 代碼】(1)常量和變量說(shuō)明x，y：長(zhǎng)度分別為 m 和 n 的字符串c[i][j]：記錄 x 中前 i 個(gè)字符和 y 中前 j 個(gè)字符的最長(zhǎng)公共子串的長(zhǎng)度max：x 和 y 的最長(zhǎng)公共子串的長(zhǎng)度maxi, maXj：分別表示 x 和 y 的某個(gè)最長(zhǎng)公共子串的最后一個(gè)字符在 x 和 y 中的位置（序號(hào)）(2)C程序include include int c［50］［50］。 int maxi。int maxj。int lcs(char *x, int m, char *y, int n) {int i, j。int max= 0。maxi= 0。maxj = 0。for ( i=0。 i=m 。 i++) c［i］［0］ = 0。 for (i =1。 i= n。 i++) c［i］［0］=0。for (i =1。 i= m。 i++) {for (j=1。 j= n。 j++) {If ( (1) ) {c[il[j] = c[i l][j i] + 1。 if(maxc[il[j] {(2) :maxi = i。 maxj =j。}}else (3) 。}}retum max。}void printLCS(int max, char *x) { int i= 0。if (max = 0) retum。For （ (4) ； i maxi。 i++)}void main（）{Char* x= ABCADAB。Char*y= BDCABA。 int max= o。int m = strlen(x)。 int n = strlen(y)。 Max=lcs(x,m,y,n)printLCS（max，x）}【問(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)表示）?！締?wèn)題 3】（3 分）根據(jù)題干說(shuō)明和以上 C 代碼，輸入字符串 x= ABCADAB’，39。y=BDCABA,則輸出為 （7）。從下列的 2 道試題（試題五至試題六）中任選 1 道解答。請(qǐng)?jiān)诖痤}紙上的指定位置處將所選擇試題的題號(hào)框涂黑。若多涂或者未涂題號(hào)框，則對(duì)題號(hào)最
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1