第4章 字符串 单元测试

1 . 以下陈述中正确的是（   A  ）。

 A. 串是一种特殊的线性表

 B. 串的长度必须大于零

 C. 串中元素只能是字母

 D. 空串就是空格串

2 . 设有两个串p和q，其中q是p的子串，q在p中首次出现的位置的算法称为（ C ）。

 A. 求子串

 B. 连接

 C. 匹配

 D. 求串长

3 . 串是（   D  ）。

 A. 不少于一个字母的序列

 B. 任意个字母的序列

 C. 不少于一个字符的序列

 D. 有限个字符的序列

4 . 串的长度是指（ B    ）。

 A. 串中所含不同字母的个数

 B. 串中所含字符的个数

 C. 串中所含不同字符的个数

 D. 串中所含非空格字符的个数

5 . 在C语言中，存储字符串“ABCD”需占用（  C  ）字节。

 A. 4

 B. 2

 C. 5

 D. 3

6 . 下面关于串的叙述中，不正确的是（   B  ）。

 A. 串是字符的有限序列

 B. 空串是由空格构成的串

 C. 模式匹配是串的一种重要运算

 D. 串即可以采用顺序存储，也可以采用链式存储

7 . 串与普通的线性表相比较，它的特殊性体现在（  C  ）。

 A. 顺序的存储结构

 B. 链接的存储结构

 C. 数据元素是一个字符

 D. 数据元素可以任意

8 . 空串与空格串（   B    ）。

 A. 相同

 B. 不相同

 C. 可能相同

 D. 无法确定

9 . 两个字符串相等的条件是（  D  ）。

 A. 两串的长度相等

 B. 两串包含的字符相同

 C. 两串的长度相等，并且两串包含的字符相同

 D. 两串的长度相等，并且对应位置上的字符相同

1 0.在实际应用中，要输入多个字符串，且长度无法预定。则应该采用（    ）存储比较合适（  A   ）。

 A. 链式

 B. 顺序

 C. 堆结构

 D. 无法确定

1 1. 下列关于串的叙述中，不正确的是（ B  ）。

 A. 串是字符的有限序列

 B. 空串是由空格构成的串

 C. 模式匹配是串的一种重要运算

 D. 串既可以采用顺序存储，也可以采用链式存储

1 2. 串是一种特殊的线性表，其特殊性体现在（ B  ）。

 A. 可以顺序存储

 B. 数据元素是一个字符

 C. 可以链接存储

 D. 数据元素可以是多个字符

1 3. 串函数StrCmp(“abA”,”aba”)的值为（  D   ）。

 A. 1

 B. 0

 C. “abAaba”

 D. -1

1 4. 在C语言中，存储字符串“ABCD”需要占用（   C  ）字节。

 A. 4

 B. 2

 C. 5

 D. 3

1 5. 设主串为“ABcCDABcdEFaBc”，以下模式串能与主串成功匹配的是（    A    ）。

 A. Bcd

 B. BCd

 C. ABC

 D. Abc

1 6. 字符串 a1=“AEIJING”，a2=“AEI”，a3=“AEFANG”，a4=“AEFI”中最大的是（  A  ）。

 A. a1

 B. a2

 C. a3

 D. a4

1 7. 字符串〝abcd321ABCD〞的子串是（  B   ）。

 A. 〝abcABCD〞

 B. 〝21ABC〞

 C.  abcD

 D. 〝321a〞

1 8. 数组a经初始化char a[  ]=“English”；a[1]中存放的是（  C  ）。 

 A. 〝n〞

 B. 〝E〞

 C. 字符n

 D. 字符E

1 9. 空串的长度为（ A  ）。

 A. 0

 B. 1

 C. 2

 D. 3

---

数据结构课程中关于“字符串”的知识补充

一、字符串（串）的基本概念

术语	定义
串（String）	由零个或多个字符组成的有限序列
串长度	串中字符的个数（空串长度为0）
空串	长度为0的串，不包含任何字符，用 "" 表示
空格串	由一个或多个空格字符组成的串，长度 > 0，如 " "
主串	包含子串的串
子串	串中任意连续字符组成的子序列
子串位置	子串在主串中第一次出现时的第一个字符在主串中的序号

---

二、串的存储结构

1. 顺序存储（定长顺序串）

#define MaxSize 255
typedef struct {
    char data[MaxSize];
    int len;      // 串的实际长度
} SString;

• 优点：存取简单，随机访问

• 缺点：最大长度固定，可能浪费空间或溢出

2. 链式存储（链串）

typedef struct node {
    char data;
    struct node *next;
} LinkStrNode;

• 优点：长度动态，插入删除方便

• 缺点：存储密度低（每个字符需要一个指针）

• 改进：每个结点存多个字符（块链）

3. 堆分配存储

typedef struct {
    char *ch;     // 按需分配的空间
    int len;
} HString;

• 优点：动态分配，灵活高效

比较项	顺序串	链串	堆串
存储密度	高	低	高
动态扩展	需预分配	灵活	灵活
随机访问	O(1)	O(n)	O(1)

三、串的基本运算

运算	函数名（常见）	说明
串赋值	StrAssign(s,t)	将串t的值赋给s
串复制	StrCopy(s,t)	将t复制到s
串比较	StrCompare(s,t)	比较ASCII码，s>t返回正数，相等返回0
求串长	StrLength(s)	返回串中字符个数
串连接	Concat(s,t)	将t连接到s末尾
求子串	SubString(s,pos,len)	从pos位置取len个字符
模式匹配	Index(s,t)	求t在s中首次出现的位置
插入	StrInsert(s,pos,t)	在pos位置插入串t
删除	StrDelete(s,pos,len)	删除从pos开始的len个字符
替换	Replace(s,t,v)	将t替换为v

四、模式匹配算法

1. 简单匹配算法（BF算法）

int Index(SString S, SString T) {
    int i = 1, j = 1;
    while (i <= S.len && j <= T.len) {
        if (S.data[i] == T.data[j]) { i++; j++; }
        else { i = i - j + 2; j = 1; }
    }
    if (j > T.len) return i - T.len;
    return 0;
}

• 时间复杂度：O(n×m)，n为主串长，m为子串长

• 最坏情况：O((n-m+1)×m)

2. KMP算法

核心思想：利用已匹配部分的信息，避免回溯主串指针

next数组定义：

next[j] = 最大相等前后缀长度 + 1

j	1	2	3	4	5	6
模式	A	B	A	A	B	C
next	0	1	1	2	2	3

nextval数组（改进版）：

void get_nextval(char *T, int nextval[]) {
    int i = 1, j = 0;
    nextval[1] = 0;
    while (i < T[0]) {
        if (j == 0 || T[i] == T[j]) {
            i++; j++;
            if (T[i] != T[j]) nextval[i] = j;
            else nextval[i] = nextval[j];
        }
        else j = nextval[j];
    }
}

时间复杂度：O(n + m)

五、易错知识点总结

1. 空串 ≠ 空格串

   • 空串长度0

   • 空格串长度≥1，包含空格字符

2. "S" 与 'S' 的区别

   • "S"：字符串常量，占2字节（S + \0）

   • 'S'：字符常量，占1字节

3. 串的比较规则
   从左到右逐个字符比较ASCII码，直到出现不同字符或串结束

4. 子串必须是连续的
   "21ABC" 不是 "abcd321ABCD" 的子串（不连续）

5. C语言中字符串以 \0 结束
   存储长度 = 实际字符数 + 1

六、单元测试答案解析（部分易错题）

题号	答案	解析
1	A	串是字符的线性序列，故为特殊的线性表
2	C	求子串首次出现位置称为模式匹配
5	C	"ABCD" 占5字节（含\0）
6	B	空串≠空格串，空格串长度>0
7	C	串的特殊性在于数据元素是单个字符
8	B	空串与空格串不相同
13	D	"abA" < "aba"（'A' ASCII 65 < 'a' ASCII 97）
17	B	子串必须连续，"21ABC"在"abcd321ABCD"中不存在（注意大小写）