《數(shù)據(jù)結(jié)構(gòu)》習(xí)題集第4章 串

本文格式為Word版，下載可任意編輯——《數(shù)據(jù)結(jié)構(gòu)》習(xí)題集第4章串?dāng)?shù)據(jù)結(jié)構(gòu)課后練習(xí)題第4章串

第4章串

一、選擇題

1.設(shè)串s1=’ABCDEFG’，s2=’PQRST’，函數(shù)Concat(x,y)返回x和y串的連接串，Substr(s,i,j)返回串s從序號(hào)i開始

的j個(gè)字符組成的子串，length(s)返回串s的長(zhǎng)度，則Concat(Substr(s1,2,length(s2)),Substr(s1,length(s2),2))的結(jié)果串是（）。A、BCDEFB、BCDEFGC、BCPQRSTD、BCDEFEF2.空串和空格是一致的。（）

A、正確B、錯(cuò)誤

3.若串S1=’ABCDEFG’，S2=’9898’，S3=’###’，S4=’012345，則執(zhí)行以下語(yǔ)句后，其結(jié)果為（）。

replace(s1,Substr(s1,4,length(s3)),s3)；

Concat(s1,Substr(s4,index(s2,’8’),length(s2)))A、ABC###G0123B、ABCD###2345C、ABC###G2345D、ABC###2345E、ABC###G1234F、ABCD###1234G、ABC###012344.串是一種特別的線性表，其特別性表達(dá)在（）。

A、可以順序存儲(chǔ)B、數(shù)據(jù)元素是一個(gè)字符C、可以鏈接存儲(chǔ)D、數(shù)據(jù)元素可以是多個(gè)字符5.設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱為（）。

A、連接B、模式匹配C、求子串D、求串長(zhǎng)6.下面關(guān)于串的的表達(dá)中，哪一個(gè)是不正確的？（）

A．串是字符的有限序列B．空串是由空格構(gòu)成的串C．模式匹配是串的一種重要運(yùn)算D．串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)7.串的長(zhǎng)度是指（）

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

二、判斷題

1.子串定位函數(shù)的時(shí)間繁雜度在最壞的狀況下為O（n*m），因此子串定位函數(shù)沒有實(shí)際利用價(jià)值。

2.設(shè)有兩個(gè)串p和q，其中q是p的子串，把q在p中首次出現(xiàn)的位置作為子串q在p中的位置的算法稱為

匹配。

3.KMP算法的最大特點(diǎn)是指示主串的指針不需要回朔。

三、填空題

1.2.3.4.5.6.

設(shè)s=’I_AM_A_TEACHER’，其長(zhǎng)度為（）?？沾牵ǎ?，其長(zhǎng)度為（）。

設(shè)S1=’GOOD’，S2=’’，S3=’BYE!’，則S1、S2和S3連接后的結(jié)果是（）。兩個(gè)串相等的充分必要條件是（）。串的兩種最基本的存儲(chǔ)方式是（）。

空格串是_________，其長(zhǎng)度等于_________。

1/2

北京理工大學(xué)珠海學(xué)院計(jì)算機(jī)學(xué)院“數(shù)據(jù)結(jié)構(gòu)〞課程組編制2023-3-1

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

7.設(shè)有兩個(gè)串q和p，求q在p中首次出現(xiàn)的算法叫_________。8.串的連接運(yùn)算不滿足_________，滿足_________。

四、簡(jiǎn)答題

1.已知以下字符串（假設(shè)采用定長(zhǎng)存儲(chǔ)結(jié)構(gòu)）

a=’this’,b=’’,c=’good’,

d=’ne’,

f=’asample’,g=’is’

順序執(zhí)行以下操作后，S、T、U、V、Length(s)、Index(v,g)、Index(u,g)各是什么？

S=Concat(a,concat(Substr(f,2,7),Concat(b,Substr(a,3,2))))T=Replace(f,Substr(f,3,6),c)U=Concat(Substr(c,3,1),d)

V=Concat(S,Concat(b,Concat(T,Concat(b,U))))2.2執(zhí)行以下函數(shù)會(huì)產(chǎn)生怎樣的輸出結(jié)果？

Voiddemonstrate(){

Strassign(s,’thisisabook’);

Replace(s,Substring(s,3,7),’eseare’);Strassign(t,Concat(s,’s’));Strassign(u,’xyxyxyxyxyxy’);Strassign(v,Substring(u,6,3));Strassign(w,’w’);

Printf(’t=’,t,’v=’,v,’u=’,Replace(u,v,w));}

3.設(shè)s=’Iamastudent’，t=’good’，q=’worker’。求strlength(s)，strlength(t)，substr(s,8,7)，substr(t,2,1)，

index(s,’a’)，index(s,t)，replace(s,’student’,q)，concat(substr(s,6,2),concat(t,substr(s,7,8)))。

五、算法設(shè)計(jì)題

1.串s和t采用堆存儲(chǔ)，設(shè)計(jì)一個(gè)函數(shù)，求第一個(gè)在s而不在t中的字符的序號(hào)。2.采用堆存儲(chǔ)