數(shù)據(jù)結(jié)構(gòu) 習(xí)題 第四章 串 答案

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)習(xí)題第四章串答案第四章串

一、選擇題1.B2.E3.C4.A5.C6.A7.1D7.2F8.B注9.D10.B注：子串的定義是：串中任意個連續(xù)的字符組成的子序列，并規(guī)定空串是任意串的子串，任意串是其自身的子串。若字符串長度為n（n>0），長為n的子串有1個，長為n-1的子串有2個，長為n-2的子串有3個，??，長為1的子串有n個。由于空串是任何串的子串，所以此題的答案為：8*（8+1）/2+1=37。應(yīng)選B。但某些教科書上認(rèn)為“空串是任意串的子串〞無意義，所以認(rèn)為選C。為避免考試中的二意性，編者認(rèn)為第9題出得好。二、判斷題

1.√2.√3.√

三．填空題

1．(1)由空格字符（ASCII值32）所組成的字符串(2)空格個數(shù)2．字符3．任意個連續(xù)的字符組成的子序列4．55.O(m+n)6．011223127．010104218．(1)模式匹配(2)模式串

9．(1)其數(shù)據(jù)元素都是字符(2)順序存儲(3)和鏈?zhǔn)酱鎯?4)串的長度相等且兩串中對應(yīng)位置的字符也相等

10．兩串的長度相等且兩串中對應(yīng)位置的字符也相等。11．’xyxyxywwy’12．*s++=*t++或（*s++=*t++）!=‘\\0’13．（1）chars[](2)j++(3)i>=j

14．[題目分析]此題算法采用順序存儲結(jié)構(gòu)求串s和串t的最大公共子串。串s用i指針（1midch//當(dāng)讀入不是分隔符

while(i<=m-nj++;}//對應(yīng)字符相等，指針后移。

else{i=i-j+1;j=0;}//對應(yīng)字符不相等，I回溯，j仍為0。if(i<=m-nreturn(i-n+1);}//匹配成功

elsereturn(0);//匹配失敗}//算法index終止main()//主函數(shù)

{chars[],t[];intm,n,i;

scanf(“%d%d〞,//輸入兩字符串的長度scanf(“%s〞,s);//輸入主串scanf(“%s〞,t);//輸入子串i=index(s,t,m,n);}//程序終止

[程序探討]因用C語言實現(xiàn)，一維數(shù)組的下標(biāo)從0開始，m-1是主串最終一個字符的下標(biāo)，n-1是t串的最終一個字符的下標(biāo)。若匹配成功，最正確狀況是s串的第0到第n-1個字符與t匹配，時間繁雜度為o（n）；匹配成功的最差狀況是，每次均在t的最終一個字符才失敗，直到s串的第m-n個字符成功，其時間繁雜度為o（（m-n）*n），即o（m*n）。失敗的狀況是s串的第m-n個字符比t串某字符對比失敗，時間繁雜度為o（m*n）。之所以串s的指針i最大到m-n，是由于在m-n之后,所剩子串長度已經(jīng)小于子串長度n，故不必再去對比。算法中未探討輸入錯誤（如s串長小于t串長）。

另外，根據(jù)子串的定義，返回值i-n+1是子串在主串中的位置，子串在主串中的下標(biāo)是i-n。

2.［問題分析］在一個字符串內(nèi)，統(tǒng)計含多少整數(shù)的問題，核心是如何將數(shù)從字符串中分開出來。從左到右掃描字符串，初次碰見數(shù)字字符時，作為一個整數(shù)的開始。然后進行拼數(shù)，即將連續(xù)出現(xiàn)的數(shù)字字符拼成一個整數(shù)，直到碰見非數(shù)字字符為止，一個整數(shù)拼完，存入數(shù)組，再準(zhǔn)備下一整數(shù)，如此下去，直至整個字符串掃描到終止。intCountInt（）

//從鍵盤輸入字符串，連續(xù)的數(shù)字字符算作一個整數(shù)，統(tǒng)計其中整數(shù)的個數(shù)。｛inti=0，a[]；//整數(shù)存儲到數(shù)組a，i記整數(shù)個數(shù)scanf（“％c〞，&ch）；//從左到右讀入字符串while（ch!=‘#’）//‘#’是字符串終止標(biāo)記if（isdigit（ch））//是數(shù)字字符｛num=０；//數(shù)初始化

while（isdigit（ch）&&ch!=‘#’）//拼數(shù)｛num=num＊10+‘ch’-‘０’；scanf（“％c〞，&ch）；｝

a[i]=num；i++；if（ch!