数组、序列、集合、子串¶
方法速览¶
| 概念 | 关键词 | 一句话 |
|---|---|---|
| 数组 | 定长、连续、下标 | 固定座次表 |
| 序列 | 有序、可重复 | 排队（先后有意义） |
| 集合 | 无序、不重复 | 去重的口袋 |
| 子串 | 连续的一段 | 相邻才成串 |
| 子序列 | 保序不连续 | 抽队不换位 |
| 子集 | 任意选取 | 与顺序无关 |
概念对比表¶
| 对比项 | 数组 | 序列 | 集合 |
|---|---|---|---|
| 顺序 | 有（下标） | 有（位置） | 无 |
| 重复元素 | 可有 | 可有 | 不可 |
| 长度 | 定义时固定 | 可增长 | 看互异元素个数 |
| 例 | int a[10] |
1, 1, 2, 3 |
\(\{1, 2, 3\}\) |
序列 \(\{1,1,2,3\}\) 与 \(\{1,2,3\}\) 是不同的两个序列；作为集合则都是 \(\{1,2,3\}\)——“判重”是集合的灵魂。
子串与子序列¶
子串：原串中连续的一段字符。
- 长度 n 的字符串，子串（含空串之外的）共 \(\dfrac{n(n+1)}{2}\) 个按位置数；
- 本质不同（内容互不相同）要去重——重复子串只算一次。
例（2022 真题）：abcab 的本质不同子串：
| 长度 | 子串 | 个数 |
|---|---|---|
| 1 | a, b, c | 3 |
| 2 | ab, bc, ca | 3 |
| 3 | abc, bca, cab | 3 |
| 4 | abca, bcab | 2 |
| 5 | abcab | 1 |
共 \(3+3+3+2+1 = 12\) 个（按位置共 \(\frac{5\times6}{2} = 15\) 个，其中 ab、bc、abc 各重复一次）。
子序列：从中抽出若干字符、保持相对顺序、不要求连续。
abcde的ace、bd是子序列，ba（顺序反了）、ac（中间跳过）里ac是子序列而ba不是；- 长度 n 的串，子序列共 \(2^n\) 个（每个字符选或不选，含空序列）；
- 子串一定是子序列，反之不然。
对照：abc 中——子串 6 个（a、b、c、ab、bc、abc）；子序列 7 个非空（a、b、c、ab、ac、bc、abc）：ac 是子序列不是子串。
练习题目¶
练习 1 · 集合的判重¶
题目
\(\{1, 2, 2, 3\}\) 作为集合，元素个数是（ ）
- A. \(4\)
- B. \(2\)
- C. \(3\)
- D. \(8\)
答案与解析
答案：C
集合元素互异：两个 2 只算一个 → \(\{1,2,3\}\)。
练习 2 · 序列与集合的区别¶
题目
序列 \(1,2,3\) 与 \(3,2,1\)（ ）
- A. 相同——元素一样
- B. 作为序列不同，作为集合也不同
- C. 作为序列不同，作为集合相同
- D. 都不对
答案与解析
答案：C
作为序列不同（顺序是序列的一部分）；作为集合都是 \(\{1,2,3\}\) 相同。
练习 3 · 数组的特点¶
题目
数组区别于链表的核心特点是（ ）
- A. 只能存整数
- B. 元素不能重复
- C. 大小可任意变
- D. 连续存储、按下标随机访问
答案与解析
答案：D
内存连续 + 下标直达 = \(O(1)\) 随机访问；C 是链表的本领，B 是集合的规矩。
练习 4 · 子串的定义¶
题目
字符串的“子串”要求（ ）
- A. 长度至少为 2
- B. 任意挑字符但保序
- C. 必须包含首字符
- D. 连续的一段字符
答案与解析
答案：D
连续是子串的定义核心；B 描述的是子序列。
练习 5 · 子序列的定义¶
题目
字符串的“子序列”允许（ ）
- A. 重复使用同一位置的字符
- B. 颠倒顺序
- C. 跳着选字符但不能颠倒相对顺序
- D. 必须连续
答案与解析
答案：C
保序 + 不连续；abc 里 ba 不是子序列（顺序反了）。
练习 6 · 判子串¶
题目
对字符串 abcdef，下列是它的子串的是（ ）
- A.
ace - B.
bcd - C.
aec - D.
fa
答案与解析
答案：B
b、c、d 在原串中连续相邻；A/C 跳选（是子序列）；D 顺序颠倒。
练习 7 · 判子序列¶
题目
对字符串 abcdef，下列是它的子序列的是（ ）
- A.
bdf - B.
fed - C.
fa - D.
db
答案与解析
答案：A
b、d、f 在原串中先后顺序保持（跳着选合法）；其余选项相对顺序与原串相反。
练习 8 · 子串计数（按位置）¶
题目
长度为 6 的字符串，按位置数（允许内容重复）的子串共（ ）个。
- A. \(21\)
- B. \(36\)
- C. \(12\)
- D. \(64\)
答案与解析
答案：A
\(\dfrac{6\times7}{2} = 21\)：起点 6 种、终点不超起点，累计求和。
练习 9 · 本质不同子串（小例）¶
题目
aaa 的本质不同子串有（ ）个。
- A. \(6\)
- B. \(2\)
- C. \(1\)
- D. \(3\)
答案与解析
答案：D
按位置有 6 个子串，但内容只有 a、aa、aaa 三种——重复串只算一次。
练习 10 · 本质不同子串（真题变式）¶
题目
aba 的本质不同子串有（ ）个。
- A. \(3\)
- B. \(6\)
- C. \(4\)
- D. \(5\)
答案与解析
答案：D
按长度：1 个字符 {a, b}（2 个）；2 个 {ab, ba}（2 个）；3 个 {aba}（1 个）→ 共 5。
练习 11 · 子序列计数¶
题目
长度为 4 的字符串，子序列（含空序列）共（ ）个。
- A. \(16\)
- B. \(15\)
- C. \(10\)
- D. \(8\)
答案与解析
答案：A
每个字符选或不选：\(2^4 = 16\)；去掉空序列是 15（B）——“含不含空”要审题。
练习 12 · 非空子序列¶
题目
长度为 5 的字符串，非空子序列至多（ ）个（假设各不相同）。
- A. \(31\)
- B. \(32\)
- C. \(16\)
- D. \(15\)
答案与解析
答案：A
\(2^5 - 1 = 31\)；若字符有重复，本质不同会更少（题干的“至多”就是这个意思）。
练习 13 · 子串与子序列的关系¶
题目
“子串”与“子序列”的关系（ ）
- A. 互不相关
- B. 子串一定是子序列，反之不然
- C. 子序列一定是子串
- D. 完全等价
答案与解析
答案：B
连续是保序的特例：abc 的 bc 两者都是，ac 只是子序列。
练习 14 · 空串¶
题目
关于空串（长度为 0 的串）（ ）
- A. 不是任何串的子串
- B. 是任何串的子串（含空串本身）
- C. 只是不是子序列
- D. 不存在
答案与解析
答案：B
“连续取 0 个字符”得到的空串是所有串的子串；计数题先看清含不含空。
练习 15 · 数组下标¶
题目
C++ 中 int a[10] 的合法下标范围是（ ）
- A. \(1 \sim 10\)
- B. \(0 \sim 9\)
- C. \(0 \sim 10\)
- D. \(1 \sim 9\)
答案与解析
答案：B
C/C++ 数组从 0 编号：a[0] 是第一个，a[10] 越界。
练习 16 · 二维数组寻址¶
题目
int a[100][100]（按行存放），a[i][j] 相对 a 起始处的偏移是（ ）个 int。
- A. \(i \times 100 + j\)
- B. \(i + j \times 100\)
- C. \(i \times j\)
- D. \(i + j\)
答案与解析
答案：A
跳过前面 i 整行（每行 100 个）再走 j 个——按行存放就是“先行后列”。
练习 17 · 集合的运算¶
题目
\(\{1,2,3\} \cup \{3,4\}\) 与 \(\{1,2,3\} \cap \{3,4\}\) 分别是（ ）
- A. \(\{1,2,3,4\}\) 和 \(\{3\}\)
- B. \(\{1,2,3,3,4\}\) 和 \(\{3\}\)
- C. \(\{1,2,4\}\) 和 \(\{\}\)
- D. \(\{3\}\) 和 \(\{1,2,3,4\}\)
答案与解析
答案：A
并集合并去重、交集取公共——B 里出现重复元素违反集合定义。
练习 18 · 多重集¶
题目
允许元素重复出现的“集合”叫多重集。\(\{1,1,2\}\) 与 \(\{1,2\}\)（ ）
- A. 无法比较
- B. 都相同
- C. 都不同
- D. 作为多重集不同、作为集合相同
答案与解析
答案：D
多重集把“几个 1”也当信息；普通集合只看有没有。
练习 19 · 前缀与后缀¶
题目
abcd 的真前缀（不含自身的前缀）共有（ ）个。
- A. \(4\)
- B. \(3\)
- C. \(2\)
- D. \(1\)
答案与解析
答案：B
a、ab、abc（abcd 本身不算“真”）——真后缀同理 d、cd、bcd。
练习 20 · 前缀与子串¶
题目
前缀、后缀与子串的关系（ ）
- A. 前缀是子串、后缀不是
- B. 前缀和后缀都是子串
- C. 都不是子串
- D. 后缀是子序列而非子串
答案与解析
答案：B
从开头连续 / 到结尾连续——都是“连续的一段”。
练习 21 · 回文子串¶
题目
aba 的回文子串有（ ）个。
- A. \(5\)
- B. \(4\)
- C. \(3\)
- D. \(2\)
答案与解析
答案：C
子串共 5 个：a、b、ab、ba、aba；其中回文的是 a、b、aba 共 3 个（ab、ba 正反不同）。
练习 22 · 子序列不重复计位置¶
题目
aab 中子序列 ab 的“取法”有几种？内容互不相同的子序列共几个？（ ）
- A. \(2\) 种取法；\(6\) 个
- B. \(1\) 种取法；\(3\) 个
- C. \(2\) 种取法；不同子序列 \(5\) 个
- D. \(1\) 种取法；\(5\) 个
答案与解析
答案：C
两个 a 任选其一与 b 组成 ab（2 种取法）；不同子序列：a、b、aa、ab、aab 共 5 个。
练习 23 · 数组存字符串¶
题目
char s[] = "abc"; 数组 s 的长度（含结束符）是（ ）
- A. \(3\)
- B. \(4\)
- C. \(2\)
- D. \(5\)
答案与解析
答案：B
'a','b','c','\0'——结束符占一格；strlen(s) = 3 与 sizeof(s) = 4 差一。
练习 24 · 序列的子序列辨析¶
题目
序列 \(1, 2, 3, 4, 5\) 中，\(2, 4\) 与 \(4, 2\)（ ）
- A. 都是子序列
- B. 都不是
- C. 后者是子序列、前者不是
- D. 前者是子序列、后者不是
答案与解析
答案：D
2 在 4 前面（保序 ✓）；4 在 2 后面取出来顺序颠倒 ✗。
练习 25 · 概念综合¶
题目
下列说法错误的是（ ）
- A. 集合中的元素互不相同
- B. 子串必须连续
- C. 子序列必须连续
- D. 数组支持下标随机访问
答案与解析
答案：C
子序列恰恰不要求连续，只要求保序。
练习 26 · 计数综合¶
题目
ab 的：子串（按位置）、子序列（含空）、集合（字符集）分别是（ ）
- A. \(3\)、\(4\)、\(\{a,b\}\)
- B. \(4\)、\(4\)、\(\{a,b\}\)
- C. \(3\)、\(3\)、\(\{a,b\}\)
- D. \(2\)、\(4\)、\(\{a,b\}\)
答案与解析
答案：A
子串 a、ab、b 共 3；子序列 \(\emptyset\)、a、b、ab 共 \(2^2 = 4\)；字符集 \(\{a,b\}\) 2 个——同一串三种数法全不同。
历年真题¶
2022 年 · 第 14 题¶
题目
一个字符串中任意个连续的字符组成的子序列称为该字符串的子串，则字符串 abcab 有（ ）个内容互不相同的子串。
- A. \(12\)
- B. \(13\)
- C. \(14\)
- D. \(15\)
答案与解析
答案：A
按长度枚举再去重（完整表格见“子串与子序列”一节）：
| 长度 | 列出 | 互异个数 |
|---|---|---|
| 1 | a, b, c | 3 |
| 2 | ab, bc, ca | 3 |
| 3 | abc, bca, cab | 3 |
| 4 | abca, bcab | 2 |
| 5 | abcab | 1 |
共 12。按位置数是 \(\frac{5\times6}{2} = 15\) 个（D 的来源），其中 ab、bc、abc 因串内重复各被多数一次——“本质不同”= 位置数 − 重复。
易错小结¶
- 子串连续、子序列保序不连续；子串 ⊂ 子序列；
- n 长串按位置的子串 \(\dfrac{n(n+1)}{2}\) 个、子序列 \(2^n\) 个（含空）；本质不同要再去重（2022 真题 15 → 12）；
- 集合无序不重复；多重集才计重复个数；
- C++ 数组下标 \(0 \sim n-1\)；二维按行存放偏移 \(i\times\text{列数} + j\)；
sizeof("abc") = 4（含'\0'）、strlen = 3；- 审题三连：含不含空？按位置还是按内容？重复算不算？