數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題：第四章-串

數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題：第四章-串第二部分習(xí)題精選一、填空題1.稱為空串；稱為空白串。2.設(shè)S=“A;/document/Mary.doc”，則strlen(s)=,“/”的字符定位的位置為。3.子串的定位運算稱為串的模式匹配，稱為目標(biāo)串，稱為模式。4.設(shè)目標(biāo)T=”abccdcdccbaa”，模式P=“cdcc”，則第次匹配成功。5.若n為主串長，m為子串長，則串的古典（樸素）匹配算法最壞的情況下需要比較字符的總次數(shù)為。二、單選題（）1.串是一種特殊的線性表，其特殊性體現(xiàn)在：Ａ．可以順序存儲Ｂ．?dāng)?shù)據(jù)元素是一個字符Ｃ．可以鏈?zhǔn)酱鎯Γ模當(dāng)?shù)據(jù)元素可以是多個字符（）2.設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱作：Ａ．連接Ｂ．模式匹配Ｃ．求子串Ｄ．求串長數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題：第四章-串全文共3頁，當(dāng)前為第1頁。（）3.設(shè)串s1=’ABCDEFG’，s2=’PQRST’，函數(shù)con(x,y)返回x和y串的連接串，subs(s,i,j)返回串s的從序號i開始的j個字符組成的子串，len(s)返回串s的長度，則con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的結(jié)果串是：數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題：第四章-串全文共3頁，當(dāng)前為第1頁。Ａ．BCDEFＢ．BCDEFGＣ．BCPQRSTＤ．BCDEFEF三、計算題設(shè)s=’IAMASTUDENT’,t=’GOOD’,q=’WORKER’,求Replace(s,’STUDENT’,q)和Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)))。已知主串s=’ADBADABBAABADABBADADA’,模式串pat=’ADABBADADA’。寫出模式串的nextval函數(shù)值，并由此畫出KMP算法匹配的全過程。答案一、填空題1.不包含任何字符（長度為0）的串由一個或多個空格（僅由空格符）組成的串2.2033.被匹配的主串子串4.65.(n-m+1)*m二、單選題1.B2.B3.D四、計算題解：①Replace(s,’STUDENT’,q)＝’IAMAWORKER’數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題：第四章-串全文共3頁，當(dāng)前為第2頁。②因為SubString(s,6,2)＝‘A’；SubString(s,7,8)＝‘STUDENT數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題：第四章-串全文共3頁，當(dāng)前為第2頁。Concat(t,SubString(s,7,8))＝’GOODSTUDENT’所以Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)))＝‘AGOODSTUDENT’2.解：（由演示程序得知）nextval函數(shù)值為0102101040在第12個字符處發(fā)現(xiàn)匹配！s=’ADBAD