2021年數(shù)據(jù)結(jié)構(gòu)考試題庫(kù)含答案_第1頁(yè)
2021年數(shù)據(jù)結(jié)構(gòu)考試題庫(kù)含答案_第2頁(yè)
2021年數(shù)據(jù)結(jié)構(gòu)考試題庫(kù)含答案_第3頁(yè)
2021年數(shù)據(jù)結(jié)構(gòu)考試題庫(kù)含答案_第4頁(yè)
2021年數(shù)據(jù)結(jié)構(gòu)考試題庫(kù)含答案_第5頁(yè)
已閱讀5頁(yè),還剩25頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

第四章串一、選取題1.下面關(guān)于串論述中,哪一種是不對(duì)的?()【北方交通大學(xué)一、5(2分)】A.串是字符有限序列B.空串是由空格構(gòu)成串C.模式匹配是串一種重要運(yùn)算D.串既可以采用順序存儲(chǔ),也可以采用鏈?zhǔn)酱鎯?chǔ)2若串S1=‘ABCDEFG’,S2=‘9898’,S3=‘###’,S4=‘012345concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’其成果為()【北方交通大學(xué)1999一、5(25/7分)】A.ABC###G0123B.ABCD###2345C.ABC###G2345D.ABC###2345E.ABC###G1234F.ABCD###1234G.ABC###012343.設(shè)有兩個(gè)串p和q,其中q是p子串,求q在p中初次浮現(xiàn)位置算法稱(chēng)為()A.求子串B.聯(lián)接C.匹配D.求串長(zhǎng)【北京郵電大學(xué)二、4(20/8分)】【西安電子科技大學(xué)1996一、1(2分)】4.已知串S=‘a(chǎn)aab’,其N(xiāo)ext數(shù)組值為()?!疚靼搽娮涌萍即髮W(xué)1996一、7(2分)】A.0123B.1123C.1231D.12115.串‘a(chǎn)babaaababaa’next數(shù)組為()?!局猩酱髮W(xué)1999一、7】A.B.C.D.56.字符串‘a(chǎn)babaabab’nextval為()A.(0,1,0,1,04,1,0,1)B.(0,1,0,1,0,2,1,0,1)C.(0,1,0,1,0,0,0,1,1)D.(0,1,0,1,0,1,0,1,1)【北京郵電大學(xué)1999一、1(2分)】7.模式串t=‘a(chǎn)bcaabbcabcaabdab’,該模式串next數(shù)組值為(),nextval數(shù)組值為()。A.01112211123456712B.01112121123456112C.01110013101100701D.01112231123456712E.01100111011001701F.01102131011021701【北京郵電大學(xué)1998二、3(2分)】8.若串S=’software’,其子串?dāng)?shù)目是()?!疚靼搽娮涌萍即髮W(xué)應(yīng)用一、2(2分)】A.8B.37C.36D.99.設(shè)S為一種長(zhǎng)度為n字符串,其中字符各不相似,則S中互異非平凡子串(非空且不同于S自身)個(gè)數(shù)為()?!局锌圃河?jì)算所1997】A.2n-1B.n2C.(n2/2)+(n/2)D.(n2/2)+(n/2)-1E.(n2/2)-(n/2)-1F.其她狀況10.串長(zhǎng)度是指()【北京工商大學(xué)=1\*CHINESENUM3一、6(3分)】A.串中所含不同字母?jìng)€(gè)數(shù)B.串中所含字符個(gè)數(shù)C.串中所含不同字符個(gè)數(shù)D.串中所含非空格字符個(gè)數(shù)二、判斷題1.KMP算法特點(diǎn)是在模式匹配時(shí)批示主串指針不會(huì)變小。()【北京郵電大學(xué)一、4(1分)】2.設(shè)模式串長(zhǎng)度為m,目的串長(zhǎng)度為n,當(dāng)n≈m且解決只匹配一次模式時(shí),樸素匹配(即子串定位函數(shù))算法所花時(shí)間代價(jià)也許會(huì)更為節(jié)約。()【長(zhǎng)沙鐵道學(xué)院1998一、1(1分)】3.串是一種數(shù)據(jù)對(duì)象和操作都特殊線(xiàn)性表。()【大連海事大學(xué)1、L(1分)】二、填空題1.空格串是指__(1)__,其長(zhǎng)度等于___(2)__?!疚靼搽娮涌萍即髮W(xué)軟件一、4(2分)】2.構(gòu)成串?dāng)?shù)據(jù)元素只能是________?!局猩酱髮W(xué)1998=1\*CHINESENUM3一、5(1分)】3.一種字符串中________稱(chēng)為該串子串?!救A中理工大學(xué)一、3(1分)】4.INDEX(‘DATASTRUCTURE’,‘STR’)=________。【福州大學(xué)1998二、4(2分)】5.設(shè)正文串長(zhǎng)度為n,模式串長(zhǎng)度為m,則串匹配KMP算法時(shí)間復(fù)雜度為_(kāi)_______?!局貞c大學(xué)=1\*CHINESENUM3一、4】6.模式串P=‘a(chǎn)baabcac’next函數(shù)值序列為_(kāi)_______?!疚靼搽娮涌萍即髮W(xué)軟件一、6(2分)】7.字符串’ababaaab’nextval函數(shù)值為_(kāi)_______。【北京郵電大學(xué)二、4(2分)】8.設(shè)T和P是兩個(gè)給定串,在T中尋找等于P子串過(guò)程稱(chēng)為_(kāi)_(1)__,又稱(chēng)P為_(kāi)_(2)__?!疚靼搽娮涌萍即髮W(xué)1998二、5(16/6分)】9.串是一種特殊線(xiàn)性表,其特殊性體當(dāng)前__(1)__;串兩種最基本存儲(chǔ)方式是__(2)__、__(3)__;兩個(gè)串相等充分必要條件是__(4)__?!局腥A人民共和國(guó)礦業(yè)大學(xué)一、3(4分)】10.兩個(gè)字符串相等充分必要條件是_______?!疚靼搽娮涌萍即髮W(xué)1999軟件一、1(2分)】11.知U=‘xyxyxyxxyxy’;t=‘xxy’;ASSIGN(S,U);ASSIGN(V,SUBSTR(S,INDEX(s,t),LEN(t)+1));ASSIGN(m,‘ww’)求REPLACE(S,V,m)=________。【東北大學(xué)1997一、1(5分)】12.實(shí)現(xiàn)字符串拷貝函數(shù)strcpy為:voidstrcpy(char*s,char*t)/*copyttos*/{while(________)}【浙江大學(xué)1999一、5(3分)】13.下列程序判斷字符串s與否對(duì)稱(chēng),對(duì)稱(chēng)則返回1,否則返回0;如f("abba")返回1,f("abab")返回0;intf((1)________){inti=0,j=0;while(s[j])(2)________;for(j--;i<j&&s[i]==s[j];i++,j--);return((3)_______)}【浙江大學(xué)1999一、6(3分)】14.下列算法實(shí)現(xiàn)求采用順序構(gòu)造存儲(chǔ)串s和串t一種最長(zhǎng)公共子串。程序(a)PROCEDUREmaxcomstr(VARs,t:orderstring;VARindex,length:integer);VARi,j,k,length1:integer;con:boolean;BEGINindex:=0;length:=0;i:=1;WHILE(i<=s.len)DO[j:=1;WHILE(j<=t.len)DO[IF(s[i]=t[j])THEN[k:=1;length1:=1;con:=true;WHILEconDOIF(1)__THEN[length1:=length1+1;k:=k+1;]ELSE(2)_;IF(length1>length)THEN[index:=i;length:=length1;](3)____;]ELSE(4)____;](5)___;]END;程序(b)voidmaxcomstr(orderstring*s,*t;intindex,length){inti,j,k,length1,con;index=0;length=0;i=1;while(i<=s.len){j=1;while(j<=t.len){if(s[i]==t[j]){k=1;length1=1;con=1;while(con)if(1)_{length1=length1+1;k=k+1;}else(2)__;if(length1>length){index=i;length=length1;}(3)____;}else(4)___;}(5)__}}【上海大學(xué)=1\*CHINESENUM3一、2(10分)】15.完善算法:求KMP算法中next數(shù)組。PROCget_next(t:string,VARnext:ARRAY[1..t.len]OFinteger);BEGINj:=1;k:=(1)__;next[1]:=0;WHILEj<t.lenDOIFk=0ORt.ch[j]=t.ch[k]THENBEGINj:=j+1;k:=k+1;next[j]:=k;ENDELSEk:=(2)___;END;【中山大學(xué)1998=4\*CHINESENUM3四、1(4分)】16.下面函數(shù)index用于求t與否為s子串,若是返回t第一次出當(dāng)前s中序號(hào)(從1開(kāi)始計(jì)),否則返回0。例如:s=‘a(chǎn)bcdefcdek’,t=‘cde’,則indse(s,t)=3,index(s,’aaa’)=0。已知t,s串長(zhǎng)分別是mt,msFUNCindex(s,t,ms,mt);i:=1;j:=1;WHILE(i<ms)AND(j<mt)DOIFs[i]=t[j]THEN[(1)__;(2)__]ELSE[(3)___;(4)_]IFj>mtTHENreturn(5)____;ELSEreturn(6)__ENDF;【南京理工大學(xué)1999三、2(6分)】17.閱讀下列程序闡明和pascal程序,把應(yīng)填入其中()處字句寫(xiě)在答題紙上。程序闡明:本程序用于鑒別輸入字符串與否為如下形式字符串:W&M$其中,子字符串M是子字符串W字符反向排列,在此假定W不具有字符&和字符$,字符&用作W與M分隔符,字符$用作字符串輸入結(jié)束符。例如,對(duì)輸入字符串a(chǎn)b&ba$、11&12$、ab&dd$、&$,程序?qū)⒎謩e輸出Ok.(是),No.(不是)。程序PROGRAMaccept(input,output);CONSTmidch=’&’;endch=’$’;VARan:boolean;ch:char;PROCEDUREmatch(VARanswer:boolean);VARch1,ch2:char;f:boolean;BEGINread(ch1);IFch1<>endchTHENIF(1)__THENBEGINmatch(f);IFfTHENBEGINread(ch2);answer:=(2)_ENDELSEanswer:=falseENDELSE(3)___ELSE(4)___END;BEGINwriteln(‘EnterString:’);match(an);IFanTHENBEGIN(5)__IF(6)_THENwriteln(‘Ok.’)ELSEwriteln(‘No.’)ENDELSEwriteln(‘No.’)END.【上海海運(yùn)學(xué)院1998七(15分)】18.試運(yùn)用下列棧和串基本操作完畢下述填空題。initstack(s)置s為空棧;push(s,x)元素x入棧;pop(s)出棧操作;gettop(s)返回棧頂元素;sempty(s)判??蘸瘮?shù);setnull(st)置串st為空串;length(st)返回串st長(zhǎng)度;equal(s1,s2)判串s1和s2與否相等函數(shù);concat(s1,s2)返回聯(lián)接s1和s2之后串;sub(s,i,1)返回s中第i個(gè)字符;empty(st)判串空函數(shù)FUNCinvert(pre:string;VARexp:string):boolean;{若給定表達(dá)式前綴式pre對(duì)的,本過(guò)程求得和它相應(yīng)表達(dá)式exp并返回“true”,否則exp為空串,并返回“false”。已知原表達(dá)式中不包括括弧,opset為運(yùn)算符集合。}VARs:stack;i,n:integer;succ:boolean;ch:char;BEGINi:=1;n:=length(pre);succ:=true;(1)__;(2)__;WHILE(i<n)ANDsuccDOBEGINch:=sub(pre,i,l);IF(3)_THEN(4)__ELSEIF(5)__THEN(6)_ELSEBEGINexp:=concat((7)___,(8)____);exp:=concat((9)___,(10)___);(11)__;END;i:=i+1END;IF(12)___THENBEGINexp:=concat(exp,sub(pre,n,1));invert:=trueENDELSEBEGINsetnull(exp);invert:=falseENDEND;注意:每個(gè)空格只填一種語(yǔ)句?!厩迦A大學(xué)1996八】=4\*CHINESENUM3四、應(yīng)用題1.名詞解釋?zhuān)捍敬筮B海事1996一、10(1分)】【河海大學(xué)1998=2\*CHINESENUM3二、5(3分)】2.描述如下概念區(qū)別:空格串與空串?!敬筮B海事大學(xué)1996三、2、(1)(2分)】3.兩個(gè)字符串S1和S2長(zhǎng)度分別為m和n。求這兩個(gè)字符串最大共同子串算法時(shí)間復(fù)雜度為T(mén)(m,n)。估算最優(yōu)T(m,n),并簡(jiǎn)要闡明理由?!颈本┕I(yè)大學(xué)1996一、5(6分)】4.設(shè)主串S=‘xxyxxxyxxxxyxyx’,模式串T=‘xxyxy’。請(qǐng)問(wèn):如何用至少比較次數(shù)找到T在S中浮現(xiàn)位置?相應(yīng)比較次數(shù)是多少?【大連海事大學(xué)四(8分)】5.KMP算法(字符串匹配算法)較Brute(樸素字符串匹配)算法有哪些改進(jìn)?【大連海事大學(xué)1996三、1((2分)】6.已知模式串t=‘a(chǎn)bcaabbabcab’寫(xiě)出用KMP法求得每個(gè)字符相應(yīng)next和nextval函數(shù)值?!颈本┼]電大學(xué)1997三(10分)】7.給出字符串‘a(chǎn)bacabaaad’在KMP算法中next和nextval數(shù)組。【北京郵電大學(xué)三、1(5分)】8.令t=‘a(chǎn)bcabaa’,求其next函數(shù)值和nextval函數(shù)值?!颈狈浇煌ù髮W(xué)1994一(6分)】9.已知字符串‘cddcdececdea’,計(jì)算每個(gè)字符next和nextval函數(shù)值?!灸暇┼]電大學(xué)=1\*CHINESENUM3一2】10.試運(yùn)用KMP算法和改進(jìn)算法分別求p1=‘a(chǎn)baabaa’和p2=‘a(chǎn)abbaab’next函數(shù)和nextval函數(shù)。【東南大學(xué)1999一、6(8分)】11.已知KMP串匹配算法中子串為babababaa,寫(xiě)出next數(shù)組改進(jìn)后next數(shù)組信息值(規(guī)定寫(xiě)出數(shù)組下標(biāo)起點(diǎn))?!疚髂辖煌ù髮W(xué)=2\*CHINESENUM3二、2】12.求模式串T=‘a(chǎn)bcaabbac'失敗函數(shù)Next(j)值?!疚靼步煌ù髮W(xué)1996四、4(5分)】13.字符串模式匹配KMP算法中,失敗函數(shù)(NEXT)是如何定義?計(jì)算模式串p=‘a(chǎn)abaabaaabc’中各字符失敗函數(shù)值.【石油大學(xué)1998一、2(10分)】14.設(shè)字符串S=‘a(chǎn)abaabaabaac',P=‘a(chǎn)abaac'(1)給出S和Pnext值和nextval值;(2)若S作主串,P作模式串,試給出運(yùn)用BF算法和KMP算法匹配過(guò)程。【北方交通大學(xué)1998二(15分)】15.設(shè)目的為t=‘a(chǎn)bcaabbabcabaacbacba’,模式為p=‘a(chǎn)bcabaa’(1)計(jì)算模式pnaxtval函數(shù)值;(5分)(2)不寫(xiě)出算法,只畫(huà)出運(yùn)用KMP算法進(jìn)行模式匹配時(shí)每一趟匹配過(guò)程。(5分)【清華大學(xué)1998八(10分)】16.模式匹配算法是在主串中迅速尋找模式一種有效辦法,如果設(shè)主串長(zhǎng)度為m,模式長(zhǎng)度為n,則在主串中尋找模式KMP算法時(shí)間復(fù)雜性是多少?如果,某一模式P=’abcaacabaca’,請(qǐng)給出它NEXT函數(shù)值及NEXT函數(shù)修正值NEXTVAL之值?!旧虾=煌ù髮W(xué)=1\*CHINESENUM3一(5分)】17.設(shè)目的為S=‘a(chǎn)bcaabbcaaabababaabca’,模式為P=‘babab’,(1)手工計(jì)算模式Pnextval數(shù)組值;(5分)(2)寫(xiě)出運(yùn)用求得nextval數(shù)組,按KMP算法對(duì)目的S進(jìn)行模式匹配過(guò)程。(5分)【清華大學(xué)1997四(10分)】18.用無(wú)回溯模式匹配法(KMP法)及迅速無(wú)回溯模式匹配法求模式串Tnext[j]值,添入下面表中:j1234567taabbaabkmp法求得next[j]值迅速無(wú)回溯法求得next[j]值【北京郵電大學(xué)1992三、1(25/4分)】19.在改進(jìn)了(無(wú)回溯)字符串模式匹配中,要先求next數(shù)組值。下面是求nextval值算法。TYPESAR=ARRAY[1..m]OFINTEGER;PTY=ARRAY[1..m]OFCHAR;PROCEDUREnext2(P:PTY;VARNEXTVAL:SAR);{在模式P中求nextval數(shù)組值}BEGINJ:=1;NEXTVAL[1]:=0;K:=0REPEATIF(K=0)OR(P[J]=P[K])THEN[J:=J+1;K:=K+1;IFP[J]=P[K]THENNEXTVAL[J]:=NEXTVAL[K]ELSENEXTVAL[J]:=K]ELSEK:=NEXTVAL[K]UNTILJ=mEND;算法中第4行有P[J]=P[K],第六行中也有P[J]=P[K]。兩處比較語(yǔ)句相似。請(qǐng)分析闡明此兩處比較語(yǔ)句含義是什么?分析此算法在最壞狀況下時(shí)間復(fù)雜度是多少?【北京郵電大學(xué)1993二、2(6分)】20.在字符串模式匹配KMP算法中,求模式next數(shù)組值定義如下:next[j]=請(qǐng)問(wèn):(1)當(dāng)j=1時(shí),為什么要取next[1]=0?(2)為什么要取max{K},K最大是多少?(3)其他狀況是什么狀況,為什么取next[j]=1?【北京郵電大學(xué)1994二(8分)】21.給出KMP算法中失敗函數(shù)f定義,并闡明運(yùn)用f進(jìn)行串模式匹配規(guī)則,該算法技術(shù)特點(diǎn)是什么?【東南大學(xué)1993一、3(9分)1997一、2(8分)一、6(6分)】22.在模試匹配KMP算法中所用失敗函數(shù)f定義中,為什么規(guī)定p1p2……pf(j)為p1p2……pj兩頭匹配真子串?且為最大真子串?【東南大學(xué)1996一、3(7分)】23.如果兩個(gè)串具有相等字符,能否說(shuō)它們相等?【西安電子科技大學(xué)軟件一、3(5分)】24.設(shè)S1,S2為串,請(qǐng)給出使S1//S2=S2//S1成立所有也許條件(//為連接符)?!鹃L(zhǎng)沙鐵道學(xué)院1997三、5(3分)】【國(guó)防科技大學(xué)1999=1\*CHINESENUM3一】25.已知:s='(xyz)+*',t='(x+z)*y'。試運(yùn)用聯(lián)結(jié)、求子串和置換等基本運(yùn)算,將s轉(zhuǎn)化為t?!颈狈浇煌ù髮W(xué)1996一、3(5分)】【山東科技大學(xué)=1\*CHINESENUM3一、6(5分)】第=5\*CHINESENUM3五某些、算法設(shè)計(jì)1.設(shè)s、t為兩個(gè)字符串,分別放在兩個(gè)一維數(shù)組中,m、n分別為其長(zhǎng)度,判斷t與否為s子串。如果是,輸出子串所在位置(第一種字符),否則輸出0。(注:用程序?qū)崿F(xiàn))【南京航空航天大學(xué)1997九(10分)】2.輸入一種字符串,內(nèi)有數(shù)字和非數(shù)字字符,如:ak123x45617960?302gef4563,將其中持續(xù)數(shù)字作為一種整體,依次存儲(chǔ)到一數(shù)組a中,例如123放入a[0],456放入a[1],……。編程記錄其共有多少個(gè)整數(shù),并輸出這些數(shù)?!旧虾4髮W(xué)1998=1\*CHINESENUM3一(13分)】3.以順序存儲(chǔ)構(gòu)造表達(dá)串,設(shè)計(jì)算法。求串S中浮現(xiàn)第一種最長(zhǎng)重復(fù)子串及其位置并分析算法時(shí)間復(fù)雜度?!緰|南大學(xué)五(15分)】類(lèi)似本題此外論述有:(1)如果字符串一種子串(其長(zhǎng)度不不大于1)各個(gè)字符均相似,則稱(chēng)之為等值子串。試設(shè)計(jì)一算法,輸入字符串S,以“!”作為結(jié)束標(biāo)志。如果串S中不存在等值子串,則輸出信息“無(wú)等值子串”,否則求出(輸出)一種長(zhǎng)度最大等值子串。例如:若S=“abc123abc123!”,則輸出“無(wú)等值子串”;若S=“abceebccadddddaaadd!”,則輸出“ddddd”?!救A中科技大學(xué)】4.假設(shè)串存儲(chǔ)構(gòu)造如下所示,編寫(xiě)算法實(shí)現(xiàn)串置換操作。【清華大學(xué)1995五(15分)】TYPEstrtp=RECORDch:ARRAY[1..maxlen]OFchar;curlen:0..maxlenEND;5.函數(shù)voidinsert(char*s,char*t,intpos)將字符串t插入到字符串s中,插入位置為pos。請(qǐng)用c語(yǔ)言實(shí)現(xiàn)該函數(shù)。假設(shè)分派給字符串s空間足夠讓字符串t插入。(闡明:不得使用任何庫(kù)函數(shù))【北京航空航天大學(xué)六(10分)】6.設(shè)計(jì)一種二分檢索算法,在一組字符串中找出給定字符串,假設(shè)所有字符串長(zhǎng)度為4。(1)簡(jiǎn)述算法重要思想;(3分)(2)用PASCAL語(yǔ)言分別對(duì)算法中用到類(lèi)型和變量作出闡明;(3分)(3)用類(lèi)PASCAL語(yǔ)言或自然語(yǔ)言寫(xiě)算法非遞歸過(guò)程;(8分)(4)分析該算法最大檢索長(zhǎng)度;(3分)(5)必要處加上中文注釋。(3分)【山東工業(yè)大學(xué)1995八(20分)】7.設(shè)計(jì)一PASCAL或C語(yǔ)言函數(shù)atoi(x).其中X為字符串,由0--9十個(gè)數(shù)字符和表達(dá)正負(fù)數(shù)‘-’構(gòu)成,返回值為整型數(shù)值?!菊憬髮W(xué)1994二(7分)】8.已知字符串S1中存儲(chǔ)一段英文,寫(xiě)出算法format(s1,s2,s3,n),將其按給定長(zhǎng)度n格式化成兩端對(duì)齊字符串S2,其多余字符送S3?!臼锥冀?jīng)貿(mào)大學(xué)1998三、8(15分)】9.串以靜態(tài)存儲(chǔ)構(gòu)造存儲(chǔ),構(gòu)造如下所述,試實(shí)現(xiàn)串操作equal算法.CONSTmaxlen=串被確認(rèn)最大長(zhǎng)度TYPEstrtp=RECORDch:ARRAY[1..maxlen]OFchar;curlen:0..maxlenEND;(以一維數(shù)組存儲(chǔ)串值,并設(shè)批示器curlen批示當(dāng)前串長(zhǎng))【北京輕工業(yè)大學(xué)1998=1\*CHINESENUM3一(12分)】10.編寫(xiě)程序,記錄在輸入字符串中各個(gè)不同字符浮現(xiàn)頻度并將成果存入文獻(xiàn)(字符串中合法字符為A-Z這26個(gè)字母和0-9這10個(gè)數(shù)字)?!疚鞅贝髮W(xué)四(10分)】11.寫(xiě)一種遞歸算法來(lái)實(shí)現(xiàn)字符串逆序存儲(chǔ),規(guī)定不另設(shè)串存儲(chǔ)空間?!疚髂辖煌ù髮W(xué)=3\*CHINESENUM3三、2】12.已知三個(gè)字符串分別為s=’ab…abcaabcbca…a’,s’=’caab’,s’’=’bcb’。運(yùn)用所學(xué)字符串基本運(yùn)算函數(shù)得到成果串為:s’’’=’caabcbca…aca…a’,規(guī)定寫(xiě)出得到上成果串S’’’所用函數(shù)及執(zhí)行算法?!緰|北大學(xué)1998一、1(10分)】13.S=“S1S2…Sn”是一種長(zhǎng)為N字符串,存儲(chǔ)在一種數(shù)組中,編程序?qū)改造之后輸出:(1)將S所有第偶數(shù)個(gè)字符按照其本來(lái)下標(biāo)從大到小順序放在S后半某些;(2)將S所有第奇數(shù)個(gè)字符按照其本來(lái)下標(biāo)從小到大順序放在S前半某些;例如:S=‘ABCDEFGHIJKL’則改造后S為‘ACEGIKLJHFDB’?!局锌圃河?jì)算所1995】14.編一程序,對(duì)輸入一表達(dá)式(字符串),輸出其TOKEN表達(dá)。表達(dá)式由變量A,B,C,常數(shù)(數(shù)字)0,1,…,9,運(yùn)算符+,*和括號(hào)“(”,“)”構(gòu)成。一方面定義符號(hào)類(lèi)碼:符號(hào)變量常量*+()類(lèi)碼012345另一方面定義符號(hào)TOKEN表達(dá):其中NAMEL是變量名表(不容許有相似名),CONST是常量表(不容許有相似數(shù))。例如,假設(shè)有表達(dá)式(A+A*2)+2*B*3#,則將生成如下TOKENL:【吉林大學(xué)1995一(20分)】第四章串一、選取題

1.B2.E3.C4.A5.C6.A7.1D7.2F8.B注9.D10.B

注:子串定義是:串中任意個(gè)持續(xù)字符構(gòu)成子序列,并規(guī)定空串是任意串子串,任意串是其自身子串。若字符串長(zhǎng)度為n(n>0),長(zhǎng)為n子串有1個(gè),長(zhǎng)為n-1子串有2個(gè),長(zhǎng)為n-2子串有3個(gè),……,長(zhǎng)為1子串有n個(gè)。由于空串是任何串子串,因此本題答案為:8*(8+1)/2+1=37。故選B。但某些教科書(shū)上以為“空串是任意串子串”無(wú)意義,因此以為選C。為避免考試中二意性,編者以為第9題出得好。二、判斷題1.√2.√3.√

三.填空題1.(1)

由空格字符(ASCII值32)所構(gòu)成字符串

(2)空格個(gè)數(shù)

2.字符3.任意個(gè)持續(xù)字符構(gòu)成子序列

4.5

5.O(m+n)6.01122312

7.01010421

8.(1)模式匹配

(2)模式串9.(1)其數(shù)據(jù)元素都是字符(2)順序存儲(chǔ)(3)和鏈?zhǔn)酱鎯?chǔ)(4)串長(zhǎng)度相等且兩串中相應(yīng)位置字符也相等10.兩串長(zhǎng)度相等且兩串中相應(yīng)位置字符也相等。11.’xyxyxywwy’

12.*s++=*t++

或(*s++=*t++)!=‘\013.(1)char

s[]

(2)j++

(3)i>=j14.[題目分析]本題算法采用順序存儲(chǔ)構(gòu)造求串s和串t最大公共子串。串s用i指針(1<=i<=s.len)。t串用j指針(1<=j<=t.len)。算法思想是對(duì)每個(gè)i(1<=i<=s.len,即程序中第一種WHILE循環(huán)),來(lái)求從i開(kāi)始持續(xù)字符串與從j(1<=j<=t.len,即程序中第二個(gè)WHILE循環(huán))開(kāi)始持續(xù)字符串最大匹配。程序中第三個(gè)(即最內(nèi)層)WHILE循環(huán),是當(dāng)s中某字符(s[i])與t中某字符(t[j])相等時(shí),求出局部公共子串。若該子串長(zhǎng)度不不大于已求出最長(zhǎng)公共子串(初始為0),則最長(zhǎng)公共子串長(zhǎng)度要修改。程序(a):(1)(i+k<=s.len)AND(j+k<=t.len)AND(s[i+k]=t[j+k])

//如果在s和t長(zhǎng)度內(nèi),相應(yīng)字符相等,則指針k

后移(加1)。

(2)con:=false

//s和t相應(yīng)字符不等時(shí)置標(biāo)記退出

(3)j:=j+k

//在t串中,從第j+k字符再與s[i]比較

(4)j:=j+1

//t串取下一字符(5)i:=i+1

//s串指針i后移(加1)。程序(b):(1)i+k<=s.len&&j+k<=t.len&&s[i+k]==t[j+k]

//所有注釋同上(a)

(2)con=0

(3)j+=k

(4)j++

(5)i++15.(1)0

(2)next[k]16.(1)i:=i+1

(2)j:=j+1

(3)i:=i-j+2

(4)j:=1;

(5)i-mt(或i:=i-j+1)

(6)017.程序中遞歸調(diào)用

(1)ch1<>midch

//當(dāng)讀入不是分隔符&和輸入結(jié)束符$時(shí),繼續(xù)讀入字符

(2)ch1=ch2

//讀入分隔符&后,判ch1與否等于ch2,得出真假結(jié)論。

(3)answer:=true

(4)answer:=false

(5)read(ch)

(6)ch=endch18.(1)initstack(s)

//棧s初始化為空棧。

(2)setnull(exp)

//串exp初始化為空串。(3)chinopset

//判取出字符與否是操作符。

(4)push(s,ch)

//如ch是運(yùn)算符,則入運(yùn)算符棧s。

(5)sempty(s)

//判棧s與否為空。

(6)succ:=false

//若讀出ch是操作數(shù)且棧為空,則按出錯(cuò)解決。

(7)exp

(8)ch

//若ch是操作數(shù)且棧非空,則形成某些中綴表達(dá)式。

(9)exp

(10)gettop(s)//取棧頂操作符。

(11)pop(s)

//操作符取出后,退棧。(12)sempty(s)

//將pre最后一種字符(操作數(shù))加入到中綴式exp最后。

四.應(yīng)用題1.串是零個(gè)至各種字符構(gòu)成有限序列。從數(shù)據(jù)構(gòu)造角度講,串屬于線(xiàn)性構(gòu)造。與線(xiàn)性表特殊性在于串元素是字符。2.空格是一種字符,其ASCII碼值是32??崭翊怯煽崭駱?gòu)成串,其長(zhǎng)度等于空格個(gè)數(shù)??沾遣缓魏巫址?,即空串長(zhǎng)度是零。3.最優(yōu)T(m,n)是O(n)。串S2是串S1子串,且在S1中位置是1。開(kāi)始求出最大公共子串長(zhǎng)度恰是串S2長(zhǎng)度,普通狀況下,T(m,n)=O(m*n)。4.樸素模式匹配(Brute-Force)時(shí)間復(fù)雜度是O(m*n),KMP算法有一定改進(jìn),時(shí)間復(fù)雜度達(dá)到O(m+n)。本題也可采用從背面匹配辦法,即從右向左掃描,比較6次成功。另一種匹配方式是從左往右掃描,但是先比較模式串最后一種字符,若不等,則模式串后移;若相等,再比較模式串第一種字符,若第一種字符也相等,則從模式串第二個(gè)字符開(kāi)始,向右比較,直至相等或失敗。若失敗,模式串后移,再重復(fù)以上過(guò)程。按這種辦法,本題比較18次成功。5.KMP算法重要長(zhǎng)處是主串指針不回溯。當(dāng)主串很大不能一次讀入內(nèi)存且經(jīng)常發(fā)生某些匹配時(shí),KMP算法長(zhǎng)處更為突出.6.模式串next函數(shù)定義如下:next[j]=

依照此定義,可求解模式串tnext和nextval值如下:j1

2

3

4

5

6

7

8

9

101112t串a(chǎn)

b

c

a

a

b

b

a

b

c

a

bnext[j]0

1

1

1

2

2

3

1

2

3

4

5nextval[j]0

1

1

0

2

1

3

0

1

1

0

57.解法同上題6,其next和nextval值分別為和010422。8.解法同題6,t串next和nextval函數(shù)值分別為0111232和0110132。9.解法同題6,其next和nextval

值分別為和01101301。10.p1next和nextval值分別為:0112234和0102102;p2next和nextval值分別為:0121123和0021002。11.next數(shù)組值為

改進(jìn)后next數(shù)組信息值為。12.。13.next定義見(jiàn)題上面6和下面題20。串pnext函數(shù)值為:。14.(1)Snext與nextval值分別為和0000,pnext與nextval值分別為012123和00。

(2)運(yùn)用BF算法匹配過(guò)程:

運(yùn)用KMP算法匹配過(guò)程:

第一趟匹配:

aabaabaabaac

第一趟匹配:aabaabaabaac

aabaac(i=6,j=6)

aabaac(i=6,j=6)

第二趟匹配:

aabaabaabaac

第二趟匹配:aabaabaabaac

aa(i=3,j=2)

(aa)baac

第三趟匹配:

aabaabaabaac

第三趟匹配:aabaabaabaac

a(i=3,j=1)

(成功)(aa)baac第四趟匹配:

aabaabaabaac

aabaac(i=9,j=6)第五趟匹配:

aabaabaabaac

aa(i=6,j=2)第六趟匹配:

aabaabaabaac

a(i=6,j=1)第七趟匹配:

aabaabaabaac(成功)

aabaac(i=13,j=7)

15.(1)pnextval函數(shù)值為0110132。(pnext函數(shù)值為0111232)。(2)運(yùn)用KMP(改進(jìn)nextval)算法,每趟匹配過(guò)程如下:

第一趟匹配:

abcaabbabcabaacbacba

abcab(i=5,j=5)

第二趟匹配:

abcaabbabcabaacbacba

abc(i=7,j=3)

第三趟匹配:

abcaabbabcabaacbacba

a(i=7,j=1)

第四趟匹配:

abcaabbabcabaacbacba

(成功)

abcabaa(i=15,j=8)16.KMP算法時(shí)間復(fù)雜性是O(m+n)。pnext和nextval值分別為和0110220。17.(1)pnextval函數(shù)值為01010。(next函數(shù)值為01123)

(2)運(yùn)用所得nextval數(shù)值,手工模仿對(duì)s匹配過(guò)程,與上面16題類(lèi)似,為節(jié)約篇幅,故略去。18.模式串Tnext和nextval值分別為0121123和0021002。19.第4行p[J]=p[K]語(yǔ)句是測(cè)試模式串第J個(gè)字符與否等于第K個(gè)字符,如是,則指針J和K均增長(zhǎng)1,繼續(xù)比較。第6行p[J]=p[K]語(yǔ)句意義是,當(dāng)?shù)贘個(gè)字符在模式匹配中失配時(shí),若第K個(gè)字符和第J個(gè)字符不等,則下個(gè)與主串匹配字符是第K個(gè)字符;否則,若第K個(gè)字符和第J個(gè)字符相等,則下個(gè)與主串匹配字符是第K個(gè)字符失配時(shí)下一種(即NEXTVAL[K])。

該算法在最壞狀況下時(shí)間復(fù)雜度O(m2)。20.(1)當(dāng)模式串中第一種字符與主串中某字符比較不等(失配)時(shí),next[1]=0表達(dá)模式串中已沒(méi)有字符可與主串中當(dāng)前字符s[i]比較,主串當(dāng)前指針應(yīng)后移至下一字符,再和模式串中第一字符進(jìn)行比較。

(2)當(dāng)主串第i個(gè)字符與模式串中第j個(gè)字符失配時(shí),若主串i不回溯,則假定模式串第k個(gè)字符與主串第i個(gè)字符比較,k值應(yīng)滿(mǎn)足條件1<k<j并且‘p1…pk-1’=‘pj-k+1…pj-1

(3)在上面兩種狀況外,發(fā)生失配時(shí),主串指針i不回溯,在最壞狀況下,模式串從第1個(gè)字符開(kāi)始與主串第i個(gè)字符比較,以便不致丟失也許匹配。21.這里失敗函數(shù)f,即是普通講模式串next函數(shù),其定義見(jiàn)本章應(yīng)用題第6題。進(jìn)行模式匹配時(shí),若主串第i個(gè)字符與模式串第j個(gè)字符發(fā)生失配,主串指針i不回溯,和主串第i個(gè)字符進(jìn)行比較是模式串第next[j]個(gè)字符。模式串next函數(shù)值,只依賴(lài)于模式串,和主串無(wú)關(guān),可以預(yù)先求出。該算法技術(shù)特點(diǎn)是主串指針i不回溯。在經(jīng)常發(fā)生“某些匹配”和主串很大不能一次調(diào)入內(nèi)存時(shí),長(zhǎng)處特別突出。22.失敗函數(shù)(即next)值只取決于模式串自身,若第j個(gè)字符與主串第i個(gè)字符失配時(shí),假定主串不回溯,模式串用第k(即next[j])個(gè)字符與第i個(gè)相比,有‘

p1…pk-1’=‘pj-k+1…pj-123.僅從兩串具有相等字符,不能鑒定兩串與否相等,兩串相等充分必要條件是兩串長(zhǎng)度相等且相應(yīng)位置上字符相似(即兩串串值相等)。24.(1)s1和s2均為空串;(2)兩串之一為空串;(3)兩串串值相等(即兩串長(zhǎng)度相等且相應(yīng)位置上字符相似)。(4)兩串中一種串長(zhǎng)是另一種串長(zhǎng)(涉及串長(zhǎng)為1僅有一種字符狀況)數(shù)倍,并且長(zhǎng)串就好象是由數(shù)個(gè)短串通過(guò)連接操作得到。25、題中所給操作含義如下://:連接函數(shù),將兩個(gè)串連接成一種串substr(s,i,j):取子串函數(shù),從串s第i個(gè)字符開(kāi)始,取持續(xù)j個(gè)字符形成子串replace(s1,i,j,s2):置換函數(shù),用s2串替代s1串中從第i個(gè)字符開(kāi)始持續(xù)j個(gè)字符本題有各種解法,下面是其中一種:(1)

s1=substr(s,3,1)

//取出字符:‘y’(2)

s2=substr(s,6,1)

//取出字符:‘+’(3)

s3=substr(s,1,5)

//取出子串:‘(xyz)’(4)

s4=substr(s,7,1)

//取出字符:‘*’(5)

s5=replace(s3,3,1,s2)//形成某些串:‘(x+z)’(6)

s=s5//s4//s1

//形成串t即‘(x+z)*y’

五、算法設(shè)計(jì)1、[題目分析]判斷字符串t與否是字符串s子串,稱(chēng)為串模式匹配,其基本思想是對(duì)串s和t各設(shè)一種指針i和j,i值域是0..m-n,j值域是0..n-1。初始值i和j均為0。模式匹配從s0和t0開(kāi)始,若s0=t0,則i和j指針增長(zhǎng)1,若在某個(gè)位置si!=tj,則主串指針i回溯到i=i-j+1,j仍從0開(kāi)始,進(jìn)行下一輪比較,直到匹配成功(j>n-1),返回子串在主串位置(i-j)。否則,當(dāng)i>m-n則為匹配失敗。int

index(char

s[],t[],int

m,n)//字符串s和t用一維數(shù)組存儲(chǔ),其長(zhǎng)度分別為m和n。本算法求字符串t在字符串s中第一次浮現(xiàn),如是,輸出子串在s中位置,否則輸出0。{int

i=0,j=0;

while

(i<=m-n&&j<=n-1)

if

(s[i]==t[j]){i++;j++;}

//相應(yīng)字符相等,指針后移。

else

{i=i-j+1;j=0;}

//相應(yīng)字符不相等,I回溯,j仍為0。

if(i<=m-n&&j==n){printf(“t在s串中位置是%d”,i-n+1);return(i-n+1);}//匹配成功else

return(0);//匹配失敗}//算法index結(jié)束main()//主函數(shù){char

s[],t[];

int

m,n,i;

scanf(“%d%d”,&m,&n);

//輸入兩字符串長(zhǎng)度

scanf(“%s”,s);

//輸入主串

scanf(“%s”,t);

//輸入子串

i=index(s,t,m,n);}//程序結(jié)束[程序討論]因用C語(yǔ)言實(shí)現(xiàn),一維數(shù)組下標(biāo)從0開(kāi)始,m-1是主串最后一種字符下標(biāo),n-1是t串最后一種字符下標(biāo)。若匹配成功,最佳狀況是s串第0到第n-1個(gè)字符與t匹配,時(shí)間復(fù)雜度為o(n);匹配成功最差狀況是,每次均在t最后一種字符才失敗,直到s串第m-n個(gè)字符成功,其時(shí)間復(fù)雜度為o((m-n)*n),即o(m*n)。失敗狀況是s串第m-n個(gè)字符比t串某字符比較失敗,時(shí)間復(fù)雜度為o(m*n)。之因此串s指針i最大到m-n,是由于在m-n之后,所剩子串長(zhǎng)度已經(jīng)不大于子串長(zhǎng)度n,故不必再去比較。算法中未討論輸入錯(cuò)誤(如s串長(zhǎng)不大于t串長(zhǎng))。此外,依照子串定義,返回值i-n+1是子串在主串中位置,子串在主串中下標(biāo)是i-n。2.[問(wèn)題分析]在一種字符串內(nèi),記錄含多少整數(shù)問(wèn)題,核心是如何將數(shù)從字符串中分離出來(lái)。從左到右掃描字符串,初次遇到數(shù)字字符時(shí),作為一種整數(shù)開(kāi)始。然后進(jìn)行拼數(shù),即將持續(xù)浮現(xiàn)數(shù)字字符拼成一種整數(shù),直到遇到非數(shù)字字符為止,一種整數(shù)拼完,存入數(shù)組,再準(zhǔn)備下一整數(shù),如此下去,直至整個(gè)字符串掃描到結(jié)束。int

CountInt()//

從鍵盤(pán)輸入字符串,持續(xù)數(shù)字字符算作一種整數(shù),記錄其中整數(shù)個(gè)數(shù)。{int

i=0,a[];

//

整數(shù)存儲(chǔ)到數(shù)組a,i記整數(shù)個(gè)數(shù)scanf(“%c”,&ch);//

從左到右讀入字符串while(ch!=‘#’)

//‘#’是字符串結(jié)束標(biāo)記if(isdigit(ch))//

是數(shù)字字符{num=0;

//

數(shù)初始化while(isdigit(ch)&&ch!=‘#’)//

拼數(shù){num=num*10+‘ch’-‘0’;scanf(“%c”,&ch);}a[i]=num;i++;if(ch!=‘#’)scanf(“%c”,&ch);

//

若拼數(shù)中輸入了‘#’,則不再輸入}//

結(jié)束while(ch?。健?’)printf(“共有%d個(gè)整數(shù),它們是:”i);for(j=0;j<i;j++){printf(“%6d”,a[j]);if((j+1)%10==0)printf(“\n”);}//

每10個(gè)數(shù)輸出在一行上}//

算法結(jié)束[算法討論]假定字符串中數(shù)均不超過(guò)32767,否則,需用長(zhǎng)整型數(shù)組及變量。3、[題目分析]設(shè)以字符數(shù)組s表達(dá)串,重復(fù)子串含義是由一種或各種持續(xù)相等字符構(gòu)成子串,其長(zhǎng)度用max表達(dá),初始長(zhǎng)度為0,將每個(gè)局部重復(fù)子串長(zhǎng)度與max相比,若比max大,則需要更新max,并用index記住其開(kāi)始位置。int

LongestString(char

s[],int

n)//串用一維數(shù)組s存儲(chǔ),長(zhǎng)度為n,本算法求最長(zhǎng)重復(fù)子串,返回其長(zhǎng)度。{int

index=0,max=0;

//index記最長(zhǎng)串在s串中開(kāi)始位置,max記其長(zhǎng)度

int

length=1,i=0,start=0;

//length記局部重復(fù)子串長(zhǎng)度,i為字符數(shù)組下標(biāo)

while(i<n-1)

if(s[i]==s[i+1]){i++;length++;}

else

//上一種重復(fù)子串結(jié)束

{if(max<length){max=length;index=start;}//當(dāng)前重復(fù)子串長(zhǎng)度大,則更新max

i++;start=i;length=1;

//初始化下一重復(fù)子串起始位置和長(zhǎng)度}printf(“最長(zhǎng)重復(fù)子串長(zhǎng)度為%d,在串中位置%d\n”,max,index);return(max);}//算法結(jié)束[算法討論]算法中用i<n-1來(lái)控制循環(huán)次數(shù),因C數(shù)組下標(biāo)從0

開(kāi)始,故長(zhǎng)度為n串,其最后一種字符下標(biāo)是n-1,當(dāng)i最大為n-2時(shí),條件語(yǔ)句中s[i+1]正好是s[n-1],即最后一種字符。子串長(zhǎng)度初值數(shù)為1,表達(dá)一種字符自然等于其身。算法時(shí)間復(fù)雜度為O(n),每個(gè)字符與其后繼比較一次。4、[題目分析]教材中簡(jiǎn)介串置換有兩種形式:第一種形式是replace(s,i,j,t),含義是將s串中從第i個(gè)字符開(kāi)始j個(gè)字符用t串替代,第二種形式是replace(s,t,v),含義是將s串中所有非重疊t串用v代替。咱們先討論第一種形式替代。由于已經(jīng)給定順序存儲(chǔ)構(gòu)造,咱們可將s串從第(i+j-1)到串尾(即s.curlen)移動(dòng)t.curlen-j絕對(duì)值個(gè)位置(以便將t串插入):若j>t.curlen,則向左移;若j<t.curlen,則向右移動(dòng);若j=t.curlen,則不必移動(dòng)。最后將t串復(fù)制到s串適當(dāng)位置上。固然,應(yīng)考慮置換后溢出問(wèn)題。int

replace(strtps,t,int

i,j)//s和t是用一維數(shù)組存儲(chǔ)串,本算法將s串從第i個(gè)字符開(kāi)始持續(xù)j個(gè)字符用t串置換,操作成功返回1,否則返回0表達(dá)失敗。{if(i<1||j<0||t.curlen+s.curlen-j>maxlen)

{printf(“參數(shù)錯(cuò)誤\n”);exit(0);}

//檢查參數(shù)及置換后長(zhǎng)度合法性。if(j<t.curlen)//若s串被替代子串長(zhǎng)度不大于t串長(zhǎng)度,則s串某些右移,

for(k=s.curlen-1;k>=i+j-1;k--)s.ch[k+t.curlen-j]=s.ch[k];

else

if

(j>t.curlen)

//s串中被替代子串長(zhǎng)度不大于t串長(zhǎng)度。

for(k=i-1+j;k<=s.curlen-1;k++)s.ch[k-(j-t.curlen)]=s.ch[k];

for(k=0;k<t.curlen;k++)s.ch[i-1+k]=t.ch[k];

//將t串復(fù)制到s串恰當(dāng)位置if(j>t.curlen)s.curlen=s.curlen-(j-t.curlen);else

s.curlen=s.curlen+(t.curlen-j);}//算法結(jié)束[算法討論]若容許使用另一數(shù)組,在檢查合法性后,可將s第i個(gè)(不涉及i)之前子串復(fù)制到另一子串如s1中,再將t串接到s1串背面,然后將s第i+j直到尾某些加到s1之后。最后將s1串復(fù)制到s。重要語(yǔ)句有:for(k=0;k<i;k++)s1.ch[k]=s.ch[k];//將s1第i個(gè)字符前子串復(fù)制到s1,這時(shí)k=i-1for(k=0;k<t.curlen;k++)s1.ch[i+k]=t.ch[k]//將t串接到s1尾部l=s.curlen+t.curlen-j-1;for(k=s.curlen-1;k>i-1+j;k--);//將子串第i+j-1個(gè)字符后來(lái)子串復(fù)制到s1

s1.ch[l--]=s.ch[k]for(k=0;k<s.curlen+t.curlen-j;k++)s.ch[k]=s1.ch[k];//將成果串放入s。下面討論replace(s,t,v)算法。該操作意義是用串v替代所有在串s中浮現(xiàn)和非空串t相等不重疊子串。本算法不指定存儲(chǔ)構(gòu)造,只使用串基本運(yùn)算。void

replace(strings,t,v)//本算法是串置換操作,將串s中所有非空串t相等且不重復(fù)子串用v代替。{i=index(s,t);//判斷s與否有和t相等子串

if(i!=0)//串s中包括和t相等子串

{creat(temp,”);

//creat操作是將串常量(此處為空串)賦值給temp。

m=length(t);n=length(s);

//求串t和s長(zhǎng)度

while(i!=0)

{assign(temp,concat(temp,substr(s,1,i-1),v));//用串v替代t形成某些成果

assign(s,substr(s,i+m,n-i-m+1));

//將串s中串后某些形成新s串

n=n-(i-1)-m;

//求串s長(zhǎng)度

i=index(s,t);

//在新s串中再找串t位置}assign(s,contact(temp,s));

//將串temp和剩余串s連接后再賦值給s}//if結(jié)束}//算法結(jié)束5、[題目分析]本題是字符串插入問(wèn)題,規(guī)定在字符串spos位置,插入字符串t。一方面應(yīng)查找字符串spos位置,將第pos個(gè)字符到字符串s尾子串向后移動(dòng)字符串t長(zhǎng)度,然后將字符串t復(fù)制到字符串s第pos位置后。

對(duì)插入位置pos要驗(yàn)證其合法性,不大于1或不不大于串s長(zhǎng)度均為非法,因題目假設(shè)給字符串s空間足夠大,故對(duì)插入不必判溢出。void

insert(char

*s,char

*t,int

pos)//將字符串t插入字符串s第pos個(gè)位置。{int

i=1,x=0;

char

*p=s,*q=t;

//p,q分別為字符串s和t工作指針

if(pos<1){printf(“pos參數(shù)位置非法\n”);exit(0);}while(*p!=’\0’

//若pos不大于串s長(zhǎng)度,則查到pos位置時(shí),i=pos。

if(*p=='/0'){printf("%d位置不不大于字符串s長(zhǎng)度",pos);exit(0);}

else

//查找字符串尾

while(*p!='/0'){p++;i++;}

//查到尾時(shí),i為字符‘\0’下標(biāo),p也指向‘\0

while(*q!='\0'){q++;x++;}

//查找字符串t長(zhǎng)度x,循環(huán)結(jié)束時(shí)q指向'\0'。

for(j=i;j>=pos;j--){*(p+x)=*p;p--;}//串spos后子串右移,空出串t位置。

q--;

//指針q回退到串t最后一種字符

for(j=1;j<=x;j++)*p--=*q--;

//將t串插入到spos位置上

[算法討論]

串s結(jié)束標(biāo)記('\0')也后移了,而串t結(jié)尾標(biāo)記不應(yīng)插入到s中。6.[題目分析]本題屬于查找,待查找元素是字符串(長(zhǎng)4),將查找元素存儲(chǔ)在一維數(shù)組中。二分檢索(即折半查找或?qū)Ψ植檎遥?,是一方面用一維數(shù)組“中間”元素與被檢索元素比較,若相等,則檢索成功,否則,依照被檢索元素不不大于或不大于中間元素,而在中間元素右方或左方繼續(xù)查找,直到檢索成功或失?。ū粰z索區(qū)間低端指針不不大于高品位指針)。下面給出類(lèi)C語(yǔ)言解法typedef

struct

node{char

data[4];//字符串長(zhǎng)4}node;非遞歸過(guò)程如下:int

binsearch(nodestring[];int

n;char

name[4])//在有n個(gè)字符串?dāng)?shù)組string中,二分檢索字符串name。若檢索成功,返回name在string中下標(biāo),否則返回-1。{int

low=0,high=n-1;//low和high分別是檢索區(qū)間下界和上界while(low<=high){mid=(low+high)/2;//取中間位置

if(strcmp(string[mid],name)==0)

return

(mid);//檢索成功

else

if(strcmp(string[mid],name)<0)low=mid+1;//到右半某些檢索else

high=mid-1;

//到左半某些檢索}return

0;//檢索失敗}//算法結(jié)束最大檢索長(zhǎng)度為log2n。7.[題目分析]設(shè)字符串存于字符數(shù)組X中,若轉(zhuǎn)換后數(shù)是負(fù)數(shù),字符串第一種字符必為

'-',取出數(shù)字字符,通過(guò)減去字符零('0')ASCII值,變成數(shù),先前取出數(shù)乘上10加上本次轉(zhuǎn)換數(shù)形成某些數(shù),直到字符串結(jié)束,得到成果。longatoi(char

X[])

//一數(shù)字字符串存于字符數(shù)組X中,本算法將其轉(zhuǎn)換成數(shù){longnum=0;int

i=1;//i

為數(shù)組下標(biāo)while

(X[i]!='\0')num=10*num+(X[i++]-'0');//當(dāng)字符串未到尾,進(jìn)行數(shù)轉(zhuǎn)換if(X[0]=='-')

return

(-num);

//返回負(fù)數(shù)else

return

((X[0]-'0')*10+num);//返回正數(shù),第一位若不是負(fù)號(hào),則是數(shù)字}//算法atoi結(jié)束[算法討論]如是負(fù)數(shù),其符號(hào)位必在前面,即字符數(shù)組x[0],因此在作轉(zhuǎn)換成數(shù)時(shí)下標(biāo)i從1

開(kāi)始,數(shù)字字符轉(zhuǎn)換成數(shù)使用X[i]-'0',即字符與'0'ASCII值相減。請(qǐng)注意對(duì)返回正整數(shù)解決。8.[題目分析]本題規(guī)定字符串s1拆提成字符串s2和字符串s3,規(guī)定字符串s2“按給定長(zhǎng)度n格式化成兩端對(duì)齊字符串”,即長(zhǎng)度為n且首尾字符不得為空格字符。算法從左到右掃描字符串s1,找到第一種非空格字符,計(jì)數(shù)到n,第n個(gè)拷入字符串s2字符不得為空格,然后將余下字符復(fù)制到字符串s3中。void

format(char

*s1,*s2,*s3)//將字符串s1拆提成字符串s2和字符串s3,規(guī)定字符串s2是長(zhǎng)n且兩端對(duì)齊{char

*p=s1,*q=s2;

int

i=0;

while(*p!='\0'&&*p=='')p++;//濾掉s1左端空格

if(*p=='\0'){printf("字符串s1為空串或空格串\n");exit(0);

}

while(*p!='\0'&&i<n){*q=*p;q++;p++;i++;}//字符串s1向字符串s2中復(fù)制

if(*p=='\0'){printf("字符串s1沒(méi)有%d個(gè)有效字符\n",n);exit(0);}

if(*(--q)=='')//若最后一種字符為空格,則需向后找到第一種非空格字符

{p--;

//p指針也后退

while(*p==''&&*p!='\0')p++;//往后查找一種非空格字符作串s2尾字符

if(*p=='\0'){printf("s1串沒(méi)有%d個(gè)兩端對(duì)齊字符串\n",n);exit(0);

}

*q=*p;

//字符串s2最后一種非空字符

*(++q)='\0';

//置s2字符串結(jié)束標(biāo)記

}

*q=s3;p++;

//將s1串別的某些送字符串s3。

while

(*p!='\0'){*q=*p;q++;p++;}

*q='\0';

//置串s3結(jié)束標(biāo)記}9.[題目分析]兩個(gè)串相等,其定義為兩個(gè)串值相等,即串長(zhǎng)相等,且相應(yīng)字符相等是兩個(gè)串相等充分必要條件。因而,一方面比較串長(zhǎng),在串長(zhǎng)相等前提下,再比較相應(yīng)字符與否相等。int

equal(strtps,strtpt)//本算法判斷字符串s和字符串t與否相等,如相等返回1,否則返回0{if

(s.curlen!=t.curlen)

return

(0);for

(i=0;i<s.curlen;i++)

//在類(lèi)C中,一維數(shù)組下標(biāo)從零開(kāi)始if

(s.ch[i]!=t.ch[i])return

(0);return

(1);

//兩串相等}//算法結(jié)束10.[問(wèn)題分析]由于字母共26個(gè),加上數(shù)字符號(hào)10個(gè)共36個(gè),因此設(shè)一長(zhǎng)36整型數(shù)組,前10個(gè)分量存儲(chǔ)數(shù)字字符浮現(xiàn)次數(shù),余下存儲(chǔ)字母浮現(xiàn)次數(shù)。從字符串中讀出數(shù)字字符時(shí),字符ASCII代碼值減去數(shù)字字符‘0’ASCII代碼值,得出其數(shù)值(0..9),字母ASCII代碼值減去字符‘A’void

Count()//記錄輸入字符串中數(shù)字字符和字母字符個(gè)數(shù)。{int

i,num[36];char

ch;for(i=0;i<36;i++)num[i]=0;//

初始化while((ch=getchar())!=‘#’)

//‘#’表達(dá)輸入字符串結(jié)束。if(‘0’<=ch<=‘9’){i=ch-48;num[i]++;}

//

數(shù)字字符

elseif(‘A’<=ch<=‘Z’){i=ch-65+10;num[i]++;}//

字母字符for(i=0;i<10;i++)

//

輸出數(shù)字字符個(gè)數(shù)printf(“數(shù)字%d個(gè)數(shù)=%d\n”,i,num[i]);for(i=10;i<36;i++)//

求出字母字符個(gè)數(shù)printf(“字母字符%c個(gè)數(shù)=%d\n”,i+55,num[i]);}//

算法結(jié)束。11.[題目分析]實(shí)現(xiàn)字符串逆置并不難,但本題“規(guī)定不另設(shè)串存儲(chǔ)空間”來(lái)實(shí)現(xiàn)字符串逆序存儲(chǔ),即第一種輸入字符最后存儲(chǔ),最后輸入字符先存儲(chǔ),使用遞歸可容易做到。

void

InvertStore(char

A[])//字符串逆序存儲(chǔ)遞歸算法。{

char

ch;static

int

i=0;//需要使用靜態(tài)變量scanf("%c",&ch);if

(ch!='.')

//規(guī)定'.'是字符串輸入結(jié)束標(biāo)志

{InvertStore(A);

A[i++]=ch;//字符串逆序存儲(chǔ)

}A[i]='\0';

//字符串結(jié)尾標(biāo)記}//結(jié)束算法InvertStore。12.

串s'''可以看作由如下兩某些構(gòu)成:'caabcbca...a'和

'ca...a',設(shè)這兩某些分別叫串s1和串s2,要設(shè)法從s,s'

和s''中得

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論