数据结构第4章字符串：单元测试19题全解析（含串匹配、子串、空串与空格串区别）
第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.两串的长度相等，并且对应位置上的字符相同
10.在实际应用中，要输入多个字符串，且长度无法预定。则应该采用（）存储比较合适（A）。
A.链式
B.顺序
C.堆结构
D.无法确定
11.下列关于串的叙述中，不正确的是（B）。
A.串是字符的有限序列
B.空串是由空格构成的串
C.模式匹配是串的一种重要运算
D.串既可以采用顺序存储，也可以采用链式存储
12.串是一种特殊的线性表，其特殊性体现在（B）。
A.可以顺序存储
B.数据元素是一个字符
C.可以链接存储
D.数据元素可以是多个字符
13.串函数StrCmp(“abA”,”aba”)的值为（D）。
A.1
B.0
C.“abAaba”
D.-1
14.在C语言中，存储字符串“ABCD”需要占用（C）字节。
A.4
B.2
C.5
D.3
15.设主串为“ABcCDABcdEFaBc”，以下模式串能与主串成功匹配的是（A）。
A.Bcd
B.BCd
C.ABC
D.Abc
16.字符串a1=“AEIJING”，a2=“AEI”，a3=“AEFANG”，a4=“AEFI”中最大的是（A）。
A.a1
B.a2
C.a3
D.a4
17.字符串〝abcd321ABCD〞的子串是（B）。
A.〝abcABCD〞
B.〝21ABC〞
C.abcD
D.〝321a〞
18.数组a经初始化char a[ ]=“English”；a[1]中存放的是（C）。
A.〝n〞
B.〝E〞
C.字符n
D.字符E
19.空串的长度为（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)
五、易错知识点总结
空串 ≠ 空格串
空串长度0
空格串长度≥1，包含空格字符
"S" 与 'S' 的区别
"S"：字符串常量，占2字节（S + \0）'S'：字符常量，占1字节
串的比较规则
从左到右逐个字符比较ASCII码，直到出现不同字符或串结束子串必须是连续的
"21ABC"不是"abcd321ABCD"的子串（不连续）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"中不存在（注意大小写） |