第4章 字符串 例题精讲

1. 字符串"abc321ABCD"的子串是（A）。

A. "21ABC"

B.  "abcABCD"

C.  abcD

D.  "321a"

2. 数组a经初始化char a[ ]="English";a[1]中存放的是（A）。

A. 字符n

B. 字符E

C.  "n"

D.  "E"

注： "n"代表字符串，需要2个字符（以'\0'为结束符），选项C如果是 'n' 则正确。

3. 数组a经初始化char a[ ]="English";a[7]中存放的是（A）。

A. 字符串的结束符

B. 字符h

C.  "h"

D.  h

4. 设主串为"ABcCDABcdEFaBc"，以下模式串能与主串成功匹配的是（A）。

A.  aBc

B.  BCd

C.  ABC

D.  Abc

5. "a" 和 'a' 在计算机中存储时各占 两个和1个 字节。子串"acd"在主串"abdcacdefac"中的位置是  5  。

6. 设主串长为a，子串长为b，在简单定位匹配算法中，当主串直到在第 a-b+1 个位置开始都未能与子串匹配成功，则匹配失败。

7. 程序段

        char a[ ]="English";

        char *p=a; int n=0;

        while(*p!='\0'){n++;p++;}

结果中n的值是（D）。

A.  6

B.  8

C.  9

D.  7

8. 字符串a1="AEIJING"，a2="AEI"，a3="AEFANG"，a4="AEFI"中最大的是（A）。

A.  a1

B.  a2

C.  a3

D.  a4

9. 以下程序段的结果中c的值为（A）。

        char *a[5]={"1245","123","1236","123","2238"};

        int i,c=0;

        for(i=0;i<5;i++){

             if(StrCmp(a[i],"123")==0){

                      c++;

             }

        }

A.  2

B.  5

C.  0

D.  123

10. 设模式串第 j 个字符的next函数值next(j)=k，则当匹配中，模式串第 j 个字符与主串的第i个字符失配时，应让子串的第  k  个字符与主串的第i个字符对位，继续匹配。

11. 模式串的next函数值（A）。

A.  仅与模式串本身有关

B.  仅与主串本身有关

C. 与模式串本身和主串都有关

D. 与模式串本身和主串都无关

12. 设模式串t="ABAABC"，j 为 t 中字符的位置，利用next函数的定义，试求t中第j个字符的next函数值，填于下表。

j	1	2	3	4	5	6
next(j)	0	1	1	2	2	3

视频演示：

解析：

（1）根据next函数的定义：

        j=1时，next(j)=0

        j=2时，next(j)=1

（2）j=5时：

j	1	2	3	4	5	6
next (j)	0	1
	■	■	■		↓
j=5	A	B	A	A	B	C
		●	●	●
●子系列A等于子系列A,相等的子序列长度为1 ●子系列（A,B）不等于子系列(A,A),相等的子序列长度为0 ●子系列（A,B,A）不等于子系列(B,A,A),相等的子序列长度为0 比较结束，最大相等的子序列长度为1 next(5)=1+1=2

（3）j=6时：

j	1	2	3	4	5	6
next (j)	0	1
	■	■	■	■		↓
j=6	A	B	A	A	B	C
		●	●	●	●
●子系列A不等于子系列B,相等的子序列长度为0 ●子系列（A,B）等于子系列(A,B),相等的子序列长度为2 ●子系列（A,B,A）不等于子系列(A,A,B),相等的子序列长度为0 ●子系列（A,B,A,A）不等于子系列(B,A,A,B),相等的子序列长度为0 比较结束，最大相等的子序列长度为2 next(6)=2+1=3

（4）j=4时：

j	1	2	3	4	5	6
next (j)	0	1
	■	■		↓
j=4	A	B	A	A	B	C
		●	●
●子系列A等于子系列A,相等的子序列长度为1 ●子系列（A,B）不等于(B,A),相等的子序列长度为0   比较结束，最大相等的子序列长度为1 next(4)=1+1=2

（5）j=3时：

j	1	2	3	4	5	6
next (j)	0	1
	■		↓
j=3	A	B	A	A	B	C
		●
●子系列A不等于子系列B,相等的子序列长度为0 比较结束，最大相等的子序列长度为0 next(3)=0+1=1

注：左边的子序列由第一个位置向右依次推进到 j-2 的位置结束（红色标记处）；

        右边的子序列由 j-1 的位置向左依次推进。

        然后分别比较两个子序列是否相等，如果相等，则计算序列中元素的个数。                   

13. 设模式串t="BCBBCD", j 为 t 中字符的位置，利用求next函数值的递推算法试求第j个字符的next函数值，填于下表。

j	1	2	3	4	5	6
next(j)	0	1	1	2	2	3

视频演示：

解析：

（1）根据next函数的定义：

         j=1时，next(j)=0；

         j=2时，next(j)=1；

（2）用递推算法计算j=2时，next(j)的值        

j	1	2	3	4	5	6
next(j)	0
模式(t)	B	C	B	B	C	D
	■	↑

求next(2)：

以序号1所对应的字符'B'作为比较对象

因为next(1)=0，

所以next(2)=next(1)+1=0+1=1

（3）用递推算法计算j=3时，next(j)的值        

j	1	2	3	4	5	6
next(j)	0	1
模式(t)	B	C	B	B	C	D
		■	↑

求next(3)：

以序号2所对应的字符'C'作为比较对象

由next(2)=1，以序号1所对应的字符'B'与其比较，不相等。

由next(1)=0

所以next(3)=next(1)+1=0+1=1

（4）用递推算法计算j=4时，next(j)的值        

j	1	2	3	4	5	6
next(j)	0	1	1
模式(t)	B	C	B	B	C	D
			■	↑

求next(4)：

以序号3所对应的字符'B'作为比较对象

由next(3)=1，以序号1所对应的字符'B'与其比较，相等。

所以next(4)=next(3)+1=1+1=2

（5）用递推算法计算j=5时，next(j)的值        

j	1	2	3	4	5	6
next(j)	0	1	1	2
模式(t)	B	C	B	B	C	D
				■	↑

求next(5)：

以序号4所对应的字符'B'作为比较对象

由next(4)=2，以序号2所对应的字符'C'与其比较，不相等。

由next(2)=1，以序号1所对应的字符'B'与其比较，相等。

所以next(5)=next(2)+1=1+1=2

（6）用递推算法计算j=6时，next(j)的值        

j	1	2	3	4	5	6
next(j)	0	1	1	2	2
模式(t)	B	C	B	B	C	D
					■	↑

求next(6)：

以序号5所对应的字符'C'作为比较对象

由next(5)=2，以序号2所对应的字符'C'与其比较，相等。

所以next(6)=next(5)+1=2+1=3