单元练习5
一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳ ）
（ㄨ）（1）串是n个字母的有限序列。 （√）（2）串的数据元素是一个字符。
（ㄨ）（3）串的长度是指串中不同字符的个数。
（ㄨ）（4）如果两个串含有相同的字符，则说明它们相等。
（ㄨ）（5）如果一个串中所有的字母均在另一个串中出现，则说明前者是后者的子串。 （√）（6）串的堆分配存储是一种动态存储结构。 （ㄨ）（7）“DT”是“DATA”的子串。
（ㄨ）（8）串中任意个字符组成的子序列称为该串的子串。 （√）（9）子串的定位运算称为模式匹配。
（√）（10）在链串中为了提高存储密度，应该增大结点的大小。
二．填空题
（1） 由零个或多个字符组成的有限序列称为 字符串（或串） 。 （2） 字符串按存储方式可以分为：顺序存储、链接存储和 堆分配存储 。 （3） 串的顺序存储结构简称为 顺序串 。
（4） 串顺序存储非紧凑格式的缺点是： 空间利用率低 。 （5） 串顺序存储紧凑格式的缺点是对串的字符处理 效率低 。 （6） 串链接存储的优点是插入、删除方便，缺点的 空间利用率低 。 （7） 在C或C++语言中，以字符 \\0 表示串值的终结。 （8） 空格串的长度等于 空格的个数 。 （9） 在空串和空格串中，长度不为0的是 空格串 。
（10） 两个串相等是指两个串相长度等，且对应位置的 字符都相
同 。
（11） 设S=\\，则LenStr(s)= _ 8 。 （12） 两
个
字
符
串
分
别
为
：
S1=\
is\，
S2=\
July,2005\atStr(S1,S2)的结果是： Today is 30 July,2005 。
（13） 求子串函数SubStr(\is 30 July,2005\的结果是：
July 。
（14）在串的运算中，EqualStr(aaa,aab)的返回值为 <0 。 （15）在串的运算中，EqualStr(aaa,aaa)的返回值为 0 。
（16） 在子串的定位运算中，被匹配的主串称为目标串，子串称为 模式 。 （17） 模式匹配成功的起始位置称为： 有效位移 。
（18） 设S=\dccbaa\，T=\dcc\， 则第 6 次匹配成功。
（19） 设S=\，T= \，则字符定位的位置为 0 。 （20） 若n为主串长度，m为子串长度，且n>>m，则模式匹配算法最坏情况下的时间复
杂度为：
26
(n-m+1)*m 。
三．选择题
（1）串是一种特殊的线性表，其特殊性体现在（ B ）。
A.可以顺序存储 B．数据元素是一个字符 C.可以链接存储 D．数据元素可以是多个字符 （2）某串的长度小于一个常数，则采用（ B ）存储方式最节省空间。 A．链式 B．顺序 A．空串与空格串是相同的 C．空串是零个字符的串
C．堆结构
D．无法确定
（3）以下论述正确的是（ C ）。
B．\是\\的子串 D. 空串的长度等于1
B．\是\leptone\的子串 D. 空串的长度等于1
B．\是\的子串 D．\ B．模式匹配 D．串比较
C．找某字符在主串中第一次出现的位置 D．找某子串在主串中第一次出现的第一个字
（4）以下论述正确的是（ B ）。 A．空串与空格串是相同的 C．空格串是有空格的串
（5）以下论断正确的是( A )。 A．\是空串，\ \空格串 C．\ A. 串连接
（6）设有两个串S1和S2，则EqualStr(S1,S2)运算称作( D )。 C. 求子串
（7）串的模式匹配是指（ D ）。
A．判断两个串是否相等 B．对两个串比较大小 符位置
（8）若字符串\采用链式存储，假设每个字符占用1个字节，每个指针占用2个字节。则该字符串的存储密度为( D )。 A．20％ B．40％
C．50％ D．33．3％
（9）若字符串\采用链式存储，假设每个指针占用2个字节，若希望存储密度50％，则每个结点应存储( A )个字符。 A．2 B．3 A．\
C．4
D．5
（10）设串S1=\，S2=\ENT\则ConcatStr(S1,S2)=( B )。
B．\ENT\
D. \
C．\UDENT\
A．0
B．1
（11）设S=\，则LenStr（S）=（ A ）。
C．2 D．3
（12）设目标串T=\E\，模式P=\E\，则该模式匹配的有效位移为 ( A )。
A．0
B．1
C．2 D．3
（13）设目标串T=\EEFF\，模式P=\\，则该模式匹配的有效位
27
移为 ( D )。
A．2 行了( D )次。
A．1 B．9
C．4 D．5
C．0（m+n）
D．0（m*n）
（15）朴素模式匹配算法在最坏情况下的时间复杂度是( D )。 A．O（m） B．O（n）
A．\( A )。
A．\\
B．\
D．\
C．\\ ( B )。 A．\\
B．\ing\
C．\ D．\（19）设串S1=\EFG\，S2=\
则ConcatStr(SubStr(S1,2,LenStr(S2)),SubStr(S1,LenStr(S2),2))的结果串为( D )。
A．BCDEF B．BCDEFG C．BCPQRST D. BCDEFEF
（20）若串S=\，其子串的数目最多是：（ C ） 。 A．35 B．36 C．37 D．38 （8+7+6+5+4+3+2+1+1=37）
B．\
（16）S=\，执行求子串函数SubStr(S,2,2)后的结果为( B )。
C．\\ D．\
（17）S1=\，S2=\\，执行串连接函数ConcatStr(S1,S2)后的结果为
B．3 C．4 D. 5
（14）设目标串T=\aababaabaa\，模式P=\\朴素匹配算法的外层循环进
（18）S1=\，S2=\\，执行函数SubStr(S2,4,LenStr(S1))后的结果为
四．程序题填空
（1）下面程序是把两个串r1和r2首尾相连的程序，即：r1=r1+r2，试完成程序填空。
typedef Struct
{ char vec[MAXLEN]; // 定义合并后串的最大长度 int len; // len为串的长度 }St ;
void ConcatStr(Str *r1,Str *r2) // 字符串连接函数 { int i;
cout<
if(r1->len+r2->len> MAXLEN ) cout<<\两个串太长，溢出！\
else { for(i=0;i< r2->len ;i++) // 把r2连接到r1
r1->vec[ r1->len+i ]=r2->vec[i];
28
r1->vec[r1->len+i]= '\\0' ; // 添上字符串结束标记 r1->len= r1->len+r2->len ; // 修改新串长度
} }
（2）设x和y两个串均采用顺序存储方式，下面的程序是比较x 和y两个串是否相等的函数，试完成程序填空。
#define MAXLEN 100 typedef struct
{ char vec[MAXLEN]; len; } str; int same (x,y) str *x,*y; { int i=0,tag=1;
if (x->len != y->len) return (0); // (或 <> ) else
{ while ( i
{ if ( x->vec[i] != y->vec[i] ) tag=0 ; i++ ; （ 或 i=i+1 ） } return (tag); } }
（4） 下面算法是判断字符串是否为回文（即正读和倒读相同），试完成程序填空。
#include \typedef struct
{ char vec[MAXLEN]; int len; }str;
void Palindrome (str s) { int i=0;
ing j= s.len-1 ; while ( j-i>=1 )
{ if ( s.vec[i]== s.vec[j] )
{i++; j-- ;continue} // (或 j=j+1 ) else break; }
if ( j-i>=1 )
cout<<\
29
else
cout<<\}
五． 编程题
（1）设下面所用的串均采用顺序存储方式，其存储结构定义如下，请编写下列算法： #define MAXLEN 100 typedef struct { char vec[MAXLEN]; int len;
} str; ① 将串中r中所有其值为ch1的字符换成ch2的字符。 ② 将串中r中所有字符按照相反的次序仍存放在r中。 ③ 从串r中删除其值等于ch的所有字符。
④ 从串r1中第index个字符起求出首次与字符r2相同的子串的起始位置。 ⑤ 从串r中删除所有与串r3相同的子串（允许调用第（4）小题的函数）。 ⑥ 编写一个比较x 和y两个串是否相等的函数。 解：
①//算法思想：从头至尾扫描r串，对于值为ch1的元素直接替换成ch2即可。
str *trans(r,ch1,ch2) str *r;
char ch1,ch2; { int i;
for(i=0;i
if(r->vec[i]==ch1)
r-vec[i]=ch2;
return(r); }
②//算法思想是：将第一个元素与最后一个元素交换，第二个元素与倒数第二个元
素交换，依次类推，便将该串的所有字符反序了。
str *invert (r) str *r;
{ int i;
char x;
for(i=0;i<(r->len%2);i++) { x=r->vec[i];
r->vec[i]=r->[r->len-i+1]; r->vec[r->len-i+1]=x; } return (r );
}
③//算法思想：从头到尾扫描r串，对于值为ch的元素用移动的方式进行删除。 str *delall(r,ch)
str *r;
30