《數(shù)據結構》習題集第4章 串

本文格式為Word版，下載可任意編輯——《數(shù)據結構》習題集第4章串數(shù)據結構課后練習題第4章串

第4章串

一、選擇題

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

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

A、正確B、錯誤

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

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.串是一種特別的線性表，其特別性表達在（）。

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

A、連接B、模式匹配C、求子串D、求串長6.下面關于串的的表達中，哪一個是不正確的？（）

A．串是字符的有限序列B．空串是由空格構成的串C．模式匹配是串的一種重要運算D．串既可以采用順序存儲，也可以采用鏈式存儲7.串的長度是指（）

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

二、判斷題

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

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

匹配。

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

三、填空題

1.2.3.4.5.6.

設s=’I_AM_A_TEACHER’，其長度為（）?？沾牵ǎ?，其長度為（）。

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

空格串是_________，其長度等于_________。

1/2

北京理工大學珠海學院計算機學院“數(shù)據結構〞課程組編制2023-3-1

數(shù)據結構課后練習題第4章串

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

四、簡答題

1.已知以下字符串（假設采用定長存儲結構）

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ù)會產生怎樣的輸出結果？

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.設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)))。

五、算法設計題

1.串s和t采用堆存儲，設計一個函數(shù)，求第一個在s而不在t中的字符的序號。2.采用堆存儲