數(shù)據(jù)結(jié)構(gòu) 第4章 串練習題

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

一、選擇題

1．下面關(guān)于串的的表達中，哪一個是不正確的？（）

A．串是字符的有限序列B．空串是由空格構(gòu)成的串

C．模式匹配是串的一種重要運算D．串既可以采用順序存儲，也可以采用鏈式存儲2若串S1=‘ABCDEFG’,S2=‘9898’,S3=‘###’,S4=‘012345’,執(zhí)行concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2)))

其結(jié)果為（）A．ABC###G0123B．ABCD###2345C．ABC###G2345D．ABC###2345E．ABC###G1234F．ABCD###1234G．ABC###01234

3．設(shè)有兩個串p和q，其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法稱為（）A．求子串B．聯(lián)接C．匹配D．求串長

4．已知串S=‘a(chǎn)aab’,其Next數(shù)組值為（）。A．0123B．1123C．1231D．12115．串‘a(chǎn)babaaababaa’的next數(shù)組為（）。

A．012345678999B．012121111212C．011234223456D．01230123223456．字符串‘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)7．模式串t=‘a(chǎn)bcaabbcabcaabdab’，該模式串的next數(shù)組的值為（），nextval數(shù)組的值為（）。A．01112211123456712B．01112121123456112C．01110013101100701D．01112231123456712E．01100111011001701F．01102131011021701

8．若串S=’software’,其子串的數(shù)目是（）。

A．8B．37C．36D．9

9．設(shè)S為一個長度為n的字符串，其中的字符各不一致，則S中的互異的非平凡子串（非空且不同于S本身）的個數(shù)為（）。A．2n-1B．n2C．(n2/2)+(n/2)D．(n2/2)+(n/2)-1E.(n2/2)-(n/2)-1F.其他狀況

10．串的長度是指（）A．串中所含不同字母的個數(shù)B．串中所含字符的個數(shù)

C．串中所含不同字符的個數(shù)D．串中所含非空格字符的個數(shù)

二、判斷題

1．KMP算法的特點是在模式匹配時指示主串的指針不會變小。（）

2．設(shè)模式串的長度為m,目標串的長度為n，當n≈m且處理只匹配一次的模式時，簡樸的匹

配（即子串定位函數(shù)）算法所花的時間代價可能會更為節(jié)省。（）

3．串是一種數(shù)據(jù)對象和操作都特別的線性表。（）

二、填空題

1．空格串是指__(1)__，其長度等于___(2)__。2．組成串的數(shù)據(jù)元素只能是________。

3．一個字符串中________稱為該串的子串。4．INDEX（‘DATASTRUCTURE’，‘STR’）=________。5．設(shè)正文串長度為n，模式串長度為m，則串匹配的KMP算法的時間繁雜度為________。

6．模式串P=‘a(chǎn)baabcac’的next函數(shù)值序列為________。7．字符串’ababaaab’的nextval函數(shù)值為________。8．設(shè)T和P是兩個給定的串，在T中尋覓等于P的子串的過程稱為__(1)__，又稱P為__(2)__。9．串是一種特別的線性表，其特別性表現(xiàn)在__(1)__；串的兩種最基本的存儲方式是__(2)__、__(3)__；兩個串相等的充分必要條件是__(4)__。10．兩個字符串相等的充分必要條件是_______。

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）=________。12．實現(xiàn)字符串拷貝的函數(shù)strcpy為：

voidstrcpy(char*s,char*t)/*copyttos*/{while(________)

}

13．以下程序判斷字符串s是否對稱，對稱則返回1，否則返回0；如f(\返回1，f(\返回0；intf((1)________)

{inti=0,j=0;

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

for(j--;ilength)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(ilength){index=i;length=length1;}(3)____;}

else(4)___;}

(5)__

}}

15．完善算法：求KMP算法中next數(shù)組。

PROCget_next(t:string,VARnext:ARRAY[1..t.len]OFinteger);BEGIN

j:=1;k:=(1)__;next[1]:=0;WHILEjmtTHENreturn(5)____;ELSEreturn(6)__ENDF;

17．閱讀以下程序說明和pascal程序,把應(yīng)填入其中的（）處的字句寫在答題紙上。程序說明：

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

WCONSTmidch=’endch=’$’;VARan:boolean;ch:char;

PROCEDUREmatch(VARanswer:boolean);VARch1,ch2:char;f:boolean;BEGIN

read(ch1);IFch1endchTHENIF(1)__

THENBEGINmatch(f);IFfTHENBEGINread(ch2);answer:=(2)_ENDELSEanswer:=falseENDELSE(3)___ELSE(4)___END;BEGIN

writeln(‘EnterString:’);match(an);

IFanTHENBEGIN(5)__IF(6)_THENwriteln(‘Ok.’)ELSEwriteln(‘No.’)END

ELSEwriteln(‘No.’)

END.

18．試利用以下棧和串的基本操作完成下述填空題。initstack(s)置s為空棧；push(s,x)元素x入棧;

pop(s)出棧操作;

gettop(s)返回棧頂元素；sempty(s)判?？蘸瘮?shù)；setnull(st)置串st為空串；length(st)返回串st的長度；

equal(s1,s2)判串s1和s2是否相等的函數(shù)；concat(s1,s2)返回聯(lián)接s1和s2之后的串；sub(s,i,1)返回s中第i個字符；empty(st)判串空函數(shù)

FUNCinvert(pre:string;VARexp:string):boolean;

{若給定的表達式的前綴式pre正確，本過程求得和它相應(yīng)的表達式exp并返回“true〞，否則exp為空串，并返回“false〞。已知原表達式中不包含括弧，opset為運算符的集合。}VARs:stack;i,n:integer;succ:boolean;ch:char;BEGIN

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

WHILE(i<n)ANDsuccDOBEGINch:=sub（pre,i,l）;IF(3)_THEN(4)__ELSEIF(5)__THEN(6)_ELSEBEGIN

exp:=concat((7)___,(8)____);exp:=concat((9)___,(10)___);(11)__;END;i:=i+1END;

IF(12)___THEN

BEGINexp:=concat(exp,sub(pre,n,1));invert:=trueENDELSEBEGINsetnull(exp);invert:=falseENDEND;

注意：每個空格只填一個語句。

四、應(yīng)用題

1．名詞解釋：串2．描述以下概念的區(qū)別：空格串與空串。3．兩個字符串S1