第4—5章自測卷答案

1、1第4～5章串和數(shù)組串和數(shù)組自測卷答案自測卷答案姓名姓名班級班級題號題號一二三四五總分總分題分題分2015201530100得分得分一、填空題一、填空題（每空（每空1分，共分，共20分）分）1.不包含任何字符（長度為0）的串稱為空串；由一個或多個空格（僅由空格符）組成的串稱為空白串。2.設(shè)S=“AdocumentMary.doc”，則strlen(s)=20“”的字符定位的位置為3。4.子串的定位運(yùn)算稱為串的模式匹配；被匹配的主串稱為目

2、標(biāo)串，子串稱為模式。5.設(shè)目標(biāo)T=”abccdcdccbaa”，模式P=“cdcc”，則第6次匹配成功。6.若n為主串長，m為子串長，則串的古典（樸素）匹配算法最壞的情況下需要比較字符的總次數(shù)為(nm1)m。7.假設(shè)有二維數(shù)組A68，每個元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。已知A的起始存儲位置（基地址）為1000，則數(shù)組A的體積（存儲量）為288B；末尾元素A57的第一個字節(jié)地址為1282；若按行存儲時，元素A14的第一個字節(jié)地

3、址為(84)61000=1072；若按列存儲時，元素A47的第一個字節(jié)地址為(67＋4)6＋1000）＝1276。(注：數(shù)組是從0行0列還是從1行1列計(jì)算起呢？由末單元為A57可知，是從0行0列開始！)8.設(shè)數(shù)組a[1…601…70]的基地址為2048，每個元素占2個存儲單元，若以列序?yàn)橹餍蝽樞虼鎯?，則元素a[3258]的存儲地址為8950。答：不考慮答：不考慮0行0列，利用列優(yōu)先公式：列，利用列優(yōu)先公式：LOC(aij)=LOC(ac

4、1，c2)[(jc2)(d1c11)ic1)]L得：LOC(a3258)=2048[(581)(6011)321]]2＝89509.三元素組表中的每個結(jié)點(diǎn)對應(yīng)于稀疏矩陣的一個非零元素，它包含有三個數(shù)據(jù)項(xiàng)，分別表示該元素的行下標(biāo)、列下標(biāo)和元素值。10.求下列廣義表操作的結(jié)果：（1）GetHead【((ab)(cd))】===(ab)頭元素不必加括號（2）GetHead【GetTail【((ab)(cd))】】===(cd)（3）GetHe

5、ad【GetTail【GetHead【((ab)(cd))】】】===b（4）GetTail【GetHead【GetTail【((ab)(cd))】】】===（d）二、單選題二、單選題（每小題（每小題1分，共分，共15分）分）（B）1.串是一種特殊的線性表，其特殊性體現(xiàn)在：Ａ可以順序存儲Ｂ數(shù)據(jù)元素是一個字符Ｃ可以鏈?zhǔn)酱鎯Γ臄?shù)據(jù)元素可以是多個字符（B）2.設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作：3答案：ABCD=121039

6、三、簡答題（每小題三、簡答題（每小題5分，共分，共15分）分）1.KMP算法的設(shè)計(jì)思想是什么？它有什么優(yōu)點(diǎn)？算法的設(shè)計(jì)思想是什么？它有什么優(yōu)點(diǎn)？答：其設(shè)計(jì)思想是，利用已利用已經(jīng)部分匹配的部分匹配的結(jié)果來加快模式串的滑果來加快模式串的滑動速度速度。主要優(yōu)點(diǎn)有二：一是在模式與主串已經(jīng)部分匹配的情況下，可以大大加快匹配速度；二是主串指針不回溯，可以使外設(shè)文件邊讀入邊匹配。2.已知二維數(shù)組Amm采用按行優(yōu)先順序存放，每個元素占K個存儲單元，并且

7、第一個元素的存儲地址為Loc(a11)，請寫出求Loc(aij)的計(jì)算公式。如果采用列優(yōu)先順序存放呢？解：按行存儲的元素地址公式是：Loc(aij)=Loc(a11)[(i1)m(j1)]K按列存儲的元素地址公式是：Loc(aij)=Loc(a11)[(j1)m(i1)]K3.遞歸算法比非遞歸算法花費(fèi)更多的時間，對嗎？為什么？答：不一定。時間復(fù)雜度與樣本個數(shù)答：不一定。時間復(fù)雜度與樣本個數(shù)n有關(guān)，是指最深層的執(zhí)行語句耗費(fèi)時間，而遞歸算法

8、與非遞歸算有關(guān)，是指最深層的執(zhí)行語句耗費(fèi)時間，而遞歸算法與非遞歸算法在最深層的語句執(zhí)行上是沒有區(qū)別的，循環(huán)的次數(shù)也沒有太大差異。僅僅是確定循環(huán)是否繼續(xù)的方式法在最深層的語句執(zhí)行上是沒有區(qū)別的，循環(huán)的次數(shù)也沒有太大差異。僅僅是確定循環(huán)是否繼續(xù)的方式不同，遞歸用棧隱含循環(huán)次數(shù)，非遞歸用循環(huán)變量來顯示循環(huán)次數(shù)而已。不同，遞歸用棧隱含循環(huán)次數(shù)，非遞歸用循環(huán)變量來顯示循環(huán)次數(shù)而已。四、計(jì)算題（每題四、計(jì)算題（每題5分，共分，共20分）分）1.設(shè)s

9、=’IAMASTUDENT’t=’GOOD’q=’WKER’求Replace(s’STUDENT’q)和Concat(SubString(s62)Concat(tSubString(s78)))。解：①Replace(s’STUDENT’q)＝’IAMAWKER’②因?yàn)镾ubString(s62)＝‘A’；SubString(s78)＝‘STUDENT’Concat(tSubString(s78))＝’GOODSTUDENT’所以Con

10、cat(SubString(s62)Concat(tSubString(s78)))＝‘AGOODSTUDENT’2.已知主串s=’ADBADABBAABADABBADADA’模式串pat=’ADABBADADA’。寫出模式串的nextval函數(shù)值，并由此畫出KMP算法匹配的全過程。解：nextval函數(shù)值為0102101040在第12個字符處發(fā)現(xiàn)匹配！s=’ADBADABBAABADABBADADA’pat=’ADABBADADA’3