四章

一、選擇題

1．下面關于串的的敘述中，哪一個是不正確的？(????)【北方交通大學?2001?一、5(2分)】

a．串是字符的有限序列??????????b．空串是由空格構成的串

c．模式匹配是串的一種重要運算??d．串既可以采用順序存儲，也可以采用鏈式存儲

2??若串s1=‘abcdefg’,?s2=‘9898’?,s3=‘###’,s4=‘012345’,執行

concat(replace(s1,substr(s1,length(s2),length(s3)),s3),substr(s4,index(s2,‘8’),length(s2)))

其結果為(????)【北方交通大學????1999????一、5????(25/7分)】

a．abc###g0123??b．abcd###2345??c．abc###g2345??d．abc###2345

e．abc###g1234??f．abcd###1234??g．abc###01234

3．設有兩個串p和q，其中q是p的子串，求q在p中首次出現的位置的算法稱為(????)

a．求子串???????b．聯接???????c．匹配?????????d．求串長

【北京郵電大學?2000?二、4(20/8分)】【西安電子科技大學?1996?一、1?(2分)】

4．已知串s=‘aaab’,其next數組值為(????)?！疚靼搽娮涌萍即髮W?1996?一、7?(2分)】

a．0123????????b．1123?????????c．1231???????????d．1211

5．串?‘ababaaababaa’?的next數組為(????)。【中山大學?1999?一、7】

a．012345678999???b．012121111212???c．011234223456????d．0123012322345

6．字符串‘ababaabab’?的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?)

【北京郵電大學?1999??一、1(2分)】

7．模式串t=‘abcaabbcabcaabdab’，該模式串的next數組的值為(??)，nextval數組的值為??(?)。

a．0?1?1?1?2?2?1?1?1?2?3?4?5?6?7?1?2????b．0?1?1?1?2?1?2?1?1?2?3?4?5?6?1?1?2

c．0?1?1?1?0?0?1?3?1?0?1?1?0?0?7?0?1????d．0?1?1?1?2?2?3?1?1?2?3?4?5?6?7?1?2

e．0?1?1?0?0?1?1?1?0?1?1?0?0?1?7?0?1????f．0?1?1?0?2?1?3?1?0?1?1?0?2?1?7?0?1

【北京郵電大學?1998?二、3?(2分)】

8．若串s=’software’,其子串的數目是(????)?！疚靼搽娮涌萍即髮W?2001應用?一、2(2分)】

a．8??????b．37??????????c．36??????????d．9

9．設s為一個長度為n的字符串，其中的字符各不相同，則s中的互異的非平凡子串(非空且不同于s本身)的個數為(????)?！局锌圃河嬎闼?1997?】

a．2n-1????b．n2??????c．(n2/2)+(n/2)???d．(n2/2)+(n/2)-1???e.?(n2/2)-(n/2)-1??f.其他情況

10．串的長度是指(????)【北京工商大學?2001??一、6?(3分)】

a．串中所含不同字母的個數??????b．串中所含字符的個數

c．串中所含不同字符的個數??????d．串中所含非空格字符的個數? 來源:-計算機三級考試

7．字符串’ababaaab’的nextval函數值為________。?【北京郵電大學?2001?二、4?(2分)】

8．設t和p是兩個給定的串，在t中尋找等于p的子串的過程稱為__(1)__，又稱p為__(2)__。

【西安電子科技大學?1998?二、5?(16/6分)】

9．串是一種特殊的線性表，其特殊性表現在__(1)__；串的兩種最基本的存儲方式是__(2)__、__(3)__；兩個串相等的充分必要條件是__(4)__。?【中國礦業大學?2000?一、3?(4分)】

10．兩個字符串相等的充分必要條件是_______。?【西安電子科技大學?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)=?________。?【東北大學?1997?一、1??(5分)】

12．實現字符串拷貝的函數?strcpy為：

void?strcpy(char?*s?,?char?*t)?/*copy?t?to?s*/

{?while??(________)

}???【浙江大學?1999?一、5?(3分)】

13．下列程序判斷字符串s?是否對稱，對稱則返回1，否則返回0；如?f("abba")返回1，f("abab")返回0；

int?f((1)________)

{int???i=0,j=0;

while?(s[j])(2)________;

for(j--;?i

return((3)_______)

}???【浙江大學?1999?一、6?(3分)】

14．下列算法實現求采用順序結構存儲的串s和串t的一個最長公共子串。

程序(a)

procedure??maxcomstr(var?s,t?:?orderstring;?var?index,length?:?integer);

var?i,j,k,length1:integer;??con:boolean;

begin

index?:=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;

while??con??do

if?(1)__then?[length1:=length1+1;k:=k+1;]?else(2)?_;

if?(length1>length)?then?[index:=i;?length:=length1;?]

(3)____;

]

else?(4)____;

]

(5)?___;

]

end;

程序(b)

void??maxcomstr(orderstring?*s,*t;?int?index,?length)

{int?i,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)?__

}??}??【上海大學?2000?一、2?(10分)】來源:-計算機三級考試

15．完善算法：求kmp算法中next數組。

proc?get?_next(t:string,var?next:array[1..t.len]?of?integer);

begin

j:=1;?k:=(1)__;??next[1]:=0;

while?j

if?k=0?or?t.ch[j]=t.ch[k]?then?begin?j:=j+1;?k:=k+1;?next[j]:=k;end

else?k:=(2)___;

end;

【中山大學?1998?四、1?(4分)】

16．下面函數index用于求t是否為s的子串，若是返回t第一次出現在s中的序號(從1開始計)，否則返回0。

例如:s=‘abcdefcdek’，t=‘cde’,則indse(s,t)=3,?index(s,’aaa’)=0?。已知t，s的串長分別是mt,ms

func?index(s,t,ms,mt);

i:=1;j:=1;

while??(i

if?s[i]=t[j]?then??[?(1)__;?(2)__]

else?[?(3)___;?(4)_?]

if?j>mt?then??return?(5)____;?else??return?(6)__

endf;

【南京理工大學?1999?三、2?(6分)】

17．閱讀下列程序說明和pascal程序,把應填入其中的(??)處的字句寫在答題紙上。

程序說明：

本程序用于判別輸入的字符串是否為如下形式的字符串:

w&m$?其中,子字符串m是子字符串w的字符反向排列,在此假定w不含有字符&和字符$,字符&用作w與m的分隔符,字符$用作字符串的輸入結束符。

例如,對輸入字符串ab&ba$、11&12$、ab&dd$、&$,程序將分別輸出ok.(是),no.(不是)。

程序

program??accept(input,output);

const??midch=’&’;???endch=’$’;

var???an:boolean;????ch:char;

procedure??match(var??answer:?boolean);

var??ch1,ch2:char;???f:boolean;

begin

read(ch1);

if??ch1<>endch

then?if??(1)__

then?begin?match(f);

if?f?then?begin?read(ch2);?answer:=(2)_?end?else?answer:=false

end

else?(3)___

else?(4)___

end;

begin

writeln(‘enter??string:’);

match(an);

if??an??then?begin

(5)__?if?(6)_?then??writeln(‘ok.’)?else?writeln(‘no.’)

end

else???writeln(‘no.’)

end.?【上海海運學院?1998?七?(15分)】

18．試利用下列棧和串的基本操作完成下述填空題。

initstack(s)??????????置s為空棧；

push(s,x)?????????????元素x入棧;

pop(s)????????????????出棧操作;

gettop(s)?????????????返回棧頂元素；

sempty(s)?????????????判?？蘸瘮?#xff1b;

setnull(st)???????????置串st為空串；

length(st)????????????返回串st的長度；

equal(s1,s2)??????????判串s1和s2是否相等的函數；

concat(s1,s2)?????????返回聯接s1和s2之后的串；

sub(s,i,1)????????????返回s中第i個字符；

empty(st)?????????????判串空函數

func???invert(pre:string;?var??exp:string):boolean;

{若給定的表達式的前綴式pre正確，本過程求得和它相應的表達式exp并返回“true”，否則exp為空串，并返回“false”。已知原表達式中不包含括弧，opset為運算符的集合。}

var??s:stack;???i,n:integer;???succ:boolean;???ch:?char;

begin

i:=1;??n:=length(pre);???succ:=true;

(1)__;??(2)__;

while??(i

begin?ch:=sub(pre,i,l);

if?(3)_?then?(4)__

else?if?(5)__then?(6)_

else??begin

exp:=concat((7)___,(8)____);

exp:=concat((9)___,(10)___);

(11)__;

end;

i:=i+1

end;

if?(12)___then

begin?exp:=concat(exp,sub(pre,n,1));?invert:=true?end

else??begin?setnull(exp);?invert:=false??end

end;

注意：每個空格只填一個語句。?【清華大學?1996?八】??來源:-計算機三級考試

四、應用題

1．名詞解釋：串?【大連海事?1996?一、10??(1分)?】【河海大學?1998?二、5(3分)】

2．描述以下概念的區別：空格串與空串?！敬筮B海事大學?1996?三、2、(1)?(2分)】

3．兩個字符串s1和s2的長度分別為m和n。求這兩個字符串最大共同子串算法的時間復雜度為t(m,n)。估算最優的t(m,n)，并簡要說明理由。?【北京工業大學?1996?一、5?(6分)】

4．設主串s=‘xxyxxxyxxxxyxyx’，模式串t=‘xxyxy’。請問：如何用最少的比較次數找到t在s中出現的位置？相應的比較次數是多少？?【大連海事大學?2001?四??(8分)】

5．kmp算法(字符串匹配算法)較brute(樸素的字符串匹配)算法有哪些改進?【大連海事大學1996三、1((2分)】

6．已知模式串t=‘abcaabbabcab’寫出用kmp法求得的每個字符對應的next和nextval函數值。

【北京郵電大學?1997??三?(10分)】

7．給出字符串‘abacabaaad’在kmp算法中的next和nextval數組?！颈本┼]電大學?2000?三、1(5分)】

8．令t=‘abcabaa’,求其next?函數值和nextval函數值。?【北方交通大學?1994??一?(6分)】

9．已知字符串‘cddcdececdea’，計算每個字符的next和nextval函數的值。【南京郵電大學?2000?一?2】

10．試利用kmp算法和改進算法分別求p1=‘abaabaa’和p2=‘aabbaab’的next函數和nextval函數。

【東南大學?1999?一、6(8分)】

11．已知kmp串匹配算法中子串為babababaa,寫出next數組改進后的next數組信息值(要求寫出數組下標起點)?！疚髂辖煌ù髮W?2000?二、2】

12．求模式串t=‘abcaabbac’??的失敗函數next(j)值?！疚靼步煌ù髮W?1996?四、4?(5分)】

13．字符串的模式匹配kmp算法中,失敗函數(next)是如何定義的?計算模式串p=‘aabaabaaabc’中各字符的失敗函數值.【石油大學?1998??一、2?(10分)】

14．設字符串s=‘aabaabaabaac’，p=‘aabaac’

(1)給出s和p的next值和nextval值；

(2)若s作主串，p作模式串，試給出利用bf算法和kmp算法的匹配過程。

【北方交通大學1998二(15分)】

15．設目標為t=‘abcaabbabcabaacbacba’,模式為p=‘abcabaa’

(1)計算模式p的naxtval函數值；(5分)

(2)不寫出算法,只畫出利用kmp算法進行模式匹配時每一趟的匹配過程。(5分)

【清華大學?1998?八(10分)】

16．模式匹配算法是在主串中快速尋找模式的一種有效的方法，如果設主串的長度為m，模式的長度為n，則在主串中尋找模式的kmp算法的時間復雜性是多少？如果，某一模式?p=’abcaacabaca’，請給出它的next函數值及next函數的修正值nextval之值?！旧虾＝煌ù髮W?2000??一?(5分)】

17．設目標為s=‘abcaabbcaaabababaabca’，模式為p=‘babab’，

(1)手工計算模式p的nextval數組的值；(5分)

(2)寫出利用求得的nextval數組，按kmp算法對目標s進行模式匹配的過程。?(5分)

【清華大學?1997?四(10分)】

18．用無回溯的模式匹配法(kmp法)及快速的無回溯的模式匹配法求模式串t的next[j]值，添入下面表中：

j1???2???3???4???5???6???7

ta???a???b???b???a???a???b

kmp法求得的next[j]值

快速無回溯法求得的next[j]值

【北京郵電大學?1992??三、1(25/4分)】? 來源:-計算機三級考試

19．在改進了的(無回溯)字符串模式匹配中，要先求next數組的值。下面是求nextval值的算法。

type?sar=array[1..m]?of?integer;

pty=array[1..m]?of?char;

procedure?next2(p:pty;var?nextval:sar);

{在模式p中求nextval數組的值}

1??????begin

2??????j:=1;nextval[1]:=0;k:=0

3??????repeat

4????????if?(k=0)?or?(p[j]=p[k])

5??????????then?[?j:=j+1;k:=k+1;

6?????????????????if?p[j]=p[k]

7???????????????????then?nextval[j]:=nextval[k]

8???????????????????else?nextval[j]:=k?]

9??????????else?k:=nextval[k]

10?????until?j=m

11????end;

算法中第4行有p[j]=p[k],第六行中也有p[j]=p[k]。兩處比較語句相同。請分析說明此兩處比較語句的含義是什么？分析此算法在最壞情況下的時間復雜度是多少？【北京郵電大學?1993?二、2(6分)】

20．在字符串模式匹配的kmp算法中，求模式的next數組值的定義如下：

next［j］=

請問：

(1)當j=1時，為什么要取next[1]=0？

(2)為什么要取max{k},k最大是多少？

(3)其它情況是什么情況，為什么取next[j]=1??【北京郵電大學?1994??二(8分)】

21．給出kmp算法中失敗函數f的定義，并說明利用f進行串模式匹配的規則，該算法的技術特點是什么？

【東南大學?1993?一、3?(9分)?1997?一、2?(8分)?2001?一、6?(6分)】

22．?在模試匹配kmp算法中所用失敗函數f的定義中，為何要求p1p2……pf(j)為p1p2……pj兩頭匹配的真子串？且為最大真子串？?【東南大學?1996?一、3(7分)】

23．如果兩個串含有相等的字符，能否說它們相等？【西安電子科技大學?2000軟件?一、3?(5分)】

24．設s1,s2為串，請給出使s1//s2=s2//s1成立的所有可能的條件(//為連接符)。

【長沙鐵道學院?1997??三、5?(3分)】【國防科技大學??1999?一?】

25．已知：s?＝’(xyz)＋＊’，t?＝’(x＋z)＊y’。試利用聯結、求子串和置換等基本運算，將?s?轉化為?t?。

【北方交通大學?1996?一、3(5分)】【山東科技大學?2002?一、6?(5分)】

第五部分、算法設計

1．設s、t為兩個字符串，分別放在兩個一維數組中，m、n分別為其長度，判斷t是否為s的子串。如果是，輸出子串所在位置(第一個字符)，否則輸出0。(注：用程序實現)【南京航空航天大學?1997?九(10分)】

2．輸入一個字符串，內有數字和非數字字符，如：ak123x456?17960?302gef4563，將其中連續的數字作為一個整體，依次存放到一數組ａ中，例如123放入ａ［０］,456放入ａ［１］，…　…　。編程統計其共有多少個整數，并輸出這些數。【上海大學?1998?一?(13分)】

3．?以順序存儲結構表示串，設計算法。求串s中出現的第一個最長重復子串及其位置并分析算法的時間復雜度。【東南大學?2000?五?(15分)】

類似本題的另外敘述有：

(1)如果字符串的一個子串(其長度大于1)的各個字符均相同，則稱之為等值子串。試設計一算法，輸入字符串s，以“！”作為結束標志。如果串s中不存在等值子串，則輸出信息“無等值子串”，否則求出(輸出)一個長度最大的等值子串。

例如：若s=“abc123abc123!”，則輸出“無等值子串”；若s=“abceebccadddddaaadd!”，則輸出“ddddd”。

【華中科技大學?2001】

10．編寫程序，統計在輸入字符串中各個不同字符出現的頻度并將結果存入文件(字符串中的合法字符為a-z這26個字母和0-9這10個數字)。【西北大學?2000?四?(10分)】

11．寫一個遞歸算法來實現字符串逆序存儲，要求不另設串存儲空間。?【西南交通大學?2000?三、2】

12．已知三個字符串分別為s=’ab…abcaabcbca…a’，s’=’caab’,??s’’=’bcb’。利用所學字符串基本運算的函數得到結果串為：s’’’=’caabcbca…aca…a’，要求寫出得到上結果串s’’’所用的函數及執行算法。【東北大學?1998?一、1?(10分)】

13．s=“s1s2…sn”是一個長為n的字符串，存放在一個數組中，編程序將s改造之后輸出：

(1)將s的所有第偶數個字符按照其原來的下標從大到小的次序放在s的后半部分；

(2)將s的所有第奇數個字符按照其原來的下標從小到大的次序放在s的前半部分；

例如：

s=‘abcdefghijkl’

則改造后的s為‘acegikljhfdb’?！局锌圃河嬎闼?1995】來源:-計算機三級考試

總結

以上是生活随笔為你收集整理的计算机组成与设计第五版课后答案ch04,数据结构第4章例题与答案的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。