第8章 线性数据结构

本文是 CSP-J（入门级）数据结构板块的详细知识手册，对标"蓝皮书"式的系统讲解：每个知识点均包含 定义 → 存储/表示 → 核心操作（含 C++ 代码）→ 复杂度 → 重要性质 → 经典应用 → 易错点。

约定：所有代码均为 C++，以"能跑、好懂"为第一目标；数组大小 N 按题目数据范围取够；INF 表示无穷大（如 0x3f3f3f3f）。

---

1、线性结构（链表 / 栈 / 队列）

线性结构的特点是：数据元素之间是一对一的前后关系，除首尾外每个元素有唯一前驱和唯一后继。

1.1 链表（Linked List）

定义：用一组不连续的存储单元存放数据，每个元素（结点）除保存数据外，还保存指向下一个结点的指针。

单链表结点结构：

struct Node {
    int data;        // 数据域
    Node* next;      // 指针域：指向下一个结点
    Node(int v) : data(v), next(nullptr) {}  // 构造函数，next 初始为空
};

核心操作

• 遍历：从 head 出发，沿 next 走到 nullptr。

void printList(Node* head) {
    for (Node* p = head; p != nullptr; p = p->next)
        cout << p->data << ' ';
}

• 头插法（在表头插入）：新结点指向原头，头指针改指向新结点。时间 O(1)。

Node* insertHead(Node* head, int v) {
    Node* p = new Node(v);
    p->next = head;
    return p;   // 返回新的头指针
}

• 尾插法（在表尾插入）：需先找到尾结点（或维护尾指针）。遍历找尾 O(n)，有尾指针则可 O(1)。
• 按值删除：找到前驱，跳过目标结点并释放内存。

Node* removeVal(Node* head, int v) {
    Node* dummy = new Node(0);   // 哨兵结点，简化头结点删除
    dummy->next = head;
    Node* pre = dummy;
    while (pre->next) {
        if (pre->next->data == v) {
            Node* t = pre->next;
            pre->next = t->next;
            delete t;            // 释放内存，避免泄漏
        } else {
            pre = pre->next;
        }
    }
    head = dummy->next;
    delete dummy;
    return head;
}

变体

• 双链表：结点增加 prev 指针，可双向遍历，插入删除更灵活。
• 循环链表：尾结点 next 指向头，形成环。

复杂度与对比

操作	数组	链表
随机访问第 k 个	O(1)	O(n)
在已知位置插入/删除	O(n)（搬移）	O(1)（已知指针）
查找	O(n)	O(n)

经典应用：多项式相加、邻接表存图、LRU 缓存（提高级）、实现栈/队列。 易错点：① 插入/删除后忘记更新 head/next 指针；② 删除结点要 delete 防内存泄漏；③ 遍历判终用 p != nullptr 而非 p->next（否则漏掉尾结点）。

---

1.2 栈（Stack）

定义：后进先出（LIFO） 的线性表，只允许在栈顶插入（push）和删除（pop）。

顺序栈（数组实现）

const int N = 100005;
int stk[N], top = 0;          // top 表示栈中元素个数（也是下一个空位下标）
void push(int x) { stk[top++] = x; }
void pop()      { if (top > 0) top--; }
int  topv()     { return stk[top - 1]; }   // 栈顶元素
bool empty()    { return top == 0; }

核心性质：只能访问栈顶；pop 前必须判空，否则越界。

经典应用

• 括号匹配：遇左括号入栈，遇右括号出栈比对是否匹配。
• 表达式求值：中缀转后缀（逆波兰），再用栈计算。
• DFS 的隐式栈：递归本质是系统栈；非递归 DFS 用显式栈。
• 单调栈（提高级入门）：维护单调递增/递减的栈，快速求"左右第一个更大/更小元素"。

易错点：① 栈空时 pop/topv 会越界；② 数组栈要预留足够大小；③ 区分"top 指向栈顶元素"与"top 指向下一个空位"两种实现，保持一致即可。

---

1.3 队列（Queue）

定义：先进先出（FIFO） 的线性表，只允许在队尾入队（push）、队首出队（pop）。

循环队列（数组实现，解决"假溢出"）

const int N = 100005;
int q[N], front = 0, rear = 0;   // front 指向队首，rear 指向下一个空位
void push(int x) { q[rear] = x; rear = (rear + 1) % N; }
void pop()       { front = (front + 1) % N; }
int  frontv()    { return q[front]; }
bool empty()     { return front == rear; }      // 判空
int  size()      { return (rear - front + N) % N; }

说明：循环队列牺牲一个存储位区分"空"与"满"（当 front == rear 判为空；满时 rear 的下一个是 front）。若需精确存满 N 个，可额外用 size 计数。

链队列：用链表实现，头出尾入，无需关心溢出。

STL 用法：#include <queue> 后 queue<int> q; q.push(x); q.pop(); q.front(); q.empty();

经典应用

• BFS（广度优先搜索）：队列保存待扩展结点，逐层扩展。
• 缓冲区 / 排队模型：如打印队列、滑动窗口（单调队列为提高级）。

易错点：① 普通数组队列反复入队出队会出现"假溢出"（尾到数组末尾但前面空着），必须用循环队列或 vector/deque；② pop 前判空；③ 区分 front/rear 的语义约定。

---

2、字符串基础概念

2.1 什么是"串"

定义：串（String）是由零个或多个字符组成的有限序列，记作 s = "a₁a₂…aₙ"。其中每个 aᵢ 是一个字符，长度 n 称为串长；n = 0 时为空串 ""。

重要性质：

• 串是一种线性结构：字符之间是一对一的前后关系，第 i 个字符有唯一前驱 i-1 与唯一后继 i+1（首尾除外）。
• 字符的"位置"从 0 开始编号（C/C++ 惯例）。
• 串的子串（substring）：从串中连续取出的一段，如 "abcde" 的子串有 "abc"、"cde"、"bcd" 等；空串是任意串的子串；任意串是其自身的子串。
• 串的子序列（subsequence）：可以不连续，如 "ace" 是 "abcde" 的子序列（J 级 rarely 考，了解即可）。

2.2 两种表示方式

CSP-J 中字符串有两种常见表示，必须都掌握：

方式①：C 风格字符数组（char s[]）

char s[105];        // 最多存 104 个字符 + 结尾 '\0'
s[0] = 'A'; s[1] = 'B'; s[2] = '\0';   // 手动补字符串结束符

• 以 '\0'（ASCII 0） 作为结尾标志，库函数靠它判断串的结束。
• 长度需手动留 1 个位置给 '\0'（开数组时 char s[N+1]）。
• 配套 <cstring> 库：strlen / strcpy / strcat / strcmp / strstr。

方式②：C++ string 类（推荐，CSP-J 复赛允许使用）

#include <string>
string s = "hello";
string t = s + " world";      // 可直接拼接
int len = s.length();         // 或 s.size()

• 自动管理内存与结尾，不需要 '\0'。
• 配套 <string> 成员函数：length/size / substr / find / append / erase / replace / insert / compare。
• 支持 + 拼接、== / < / > 字典序比较（重载了运算符）。

复杂度对比：字符数组 + strlen 是 O(n)（要扫到 '\0'）；string::length() 是 O(1)（内部存了长度）。日常用 string 更省心。

2.3 字符的本质：ASCII

定义：计算机用整数存储字符，ASCII 码是最常用的编码（0~127）。常见值：

• '0''9' → 4857（连续，故 int('7') - '0' = 7）
• 'A''Z' → 6590
• 'a''z' → 97122（'a' - 'A' = 32）
• 空格 ' ' → 32；换行 '\n' → 10；'\0' → 0

重要运算（J 级极常用）：

char c = '5';
int d = c - '0';            // d = 5（字符转数字）
char up = 'b' - 32;         // up = 'B'（小写转大写，要加 <cctype> 更稳妥）
if ('a' <= c && c <= 'z') {/* 判断小写字母 */}

易错：字符 '7' 与整数 7 不是一回事；'7' + 1 = '8'（整数 56），不是 8。要数字请用 c - '0'。

---

2.4、字符串的输入输出

2.4.1 基础读写

string s;
cin >> s;                   // 读一个"单词"，遇空格/换行/制表符停止
cout << s;                  // 输出

char c[105];
scanf("%s", c);             // 读一个单词（c 前不用 &，数组名即地址）
printf("%s\n", c);          // 输出

易错①：cin >> s 遇空格就停——只能读到第一个单词，无法读入含空格的整行。 易错②：混用 cin 与 getline 时的"换行符残留"——

int n; cin >> n;
string s;
getline(cin, s);            // 这里会读到刚才的换行符，s 变成空！
// 正确做法：先吃掉换行
cin.ignore();               // 或 cin >> n; cin.get();
getline(cin, s);

2.4.2 读入整行（含空格）

string line;
getline(cin, line);         // 读到换行符为止（换行符不纳入串）

char buf[105];
fgets(buf, sizeof(buf), stdin);  // C 风格读整行，含 '\n'（需手动去掉）

2.4.3 单字符读写

char c;
c = getchar();              // 读一个字符（含空格/换行）
cin.get(c);                 // 同上
putchar(c);                 // 输出一个字符

2.4.4 数字与字符串互转

// 数字 → 字符串
string s1 = to_string(123);     // "123"
char buf[20];
sprintf(buf, "%d", 123);        // C 风格，buf = "123"

// 字符串 → 数字
int x = stoi("123");            // 123
long long y = stoll("1234567890123");
int z = atoi("45abc");          // 45（遇到非数字停止，C 风格）

---

2.5、字符串遍历与索引

2.5.1 下标访问

string s = "abcdef";
for (int i = 0; i < s.length(); i++) {
    cout << s[i] << ' ';        // 0-based：s[0]='a'
}

2.5.2 范围 for（C++11）

for (char c : s) {              // c 是 s 中每个字符的副本
    cout << c;
}
// 若要修改：用引用
for (char &c : s) { c = toupper(c); }

2.5.3 逆序遍历

for (int i = (int)s.length() - 1; i >= 0; i--) {
    cout << s[i];
}

易错：s.length() 返回 size_t（无符号），直接 i >= 0 会死循环。务必写成 int i = (int)s.length() - 1，或先存 int n = s.length()。

---

2.5.4、常用库函数（分类速查）

2.5.4.1 <cstring>（字符数组）

函数	作用	复杂度
strlen(s)	求长度（扫到 '\0'）	O(n)
strcpy(a,b)	把 b 复制到 a	O(n)
strcat(a,b)	把 b 接到 a 末尾	O(n)
strcmp(a,b)	字典序比较，返回 $<0/0/>0$	O(n)
strstr(a,b)	在 a 中找 b 首次出现位置	O(nm)
memset(a,0,sizeof(a))	按字节填充（常用于初始化）	O(1)

char a[20] = "abc", b[20] = "abd";
int r = strcmp(a, b);       // 'c'(99) < 'd'(100) → r < 0，a 更小

2.5.4.2 <string>（C++ string 成员）

string s = "Hello World";
s.length();                 // 11
s.substr(0, 5);             // "Hello"（从下标0取5个字符）
s.substr(6);                // "World"（从6到末尾）
s.find("World");            // 返回 6（下标）；找不到返回 string::npos
s.find('o');                // 返回 4（第一个 'o'）
s.append("!");              // "Hello World!"
s.erase(5, 6);             // 删从下标5开始6个字符 → "Hello"
s.replace(6, 5, "C++");     // 把"World"换成"C++"
s.insert(5, " CCF");        // "Hello CCF World"
s.compare("Hello");         // 字典序比较

易错：substr(pos, len) 第二个参数是长度不是"结束下标"；下标越界会 runtime error。

2.5.4.3 <cctype>（字符分类与转换）

#include <cctype>
isdigit(c);   // 是否数字 '0'~'9'
isalpha(c);   // 是否字母
islower(c);   // 是否小写
isupper(c);   // 是否大写
isspace(c);   // 是否空白（空格/制表/换行）
tolower(c);   // 转小写
toupper(c);   // 转大写

这些函数参数/返回值都是 int（基于 ASCII），直接用于 char 即可。

2.5.4.4 字典序比较规则

串 a 与 b 的字典序：从首字符逐位比，第一个不同处谁的字符小，谁的串就小；若一方是另一方的前缀，则短的小（"abc" < "abcd"）。

string a = "apple", b = "apply";
// 第4位 'e'(101) < 'y'(121) → a < b
vector<string> v = {"banana","apple","cat"};
sort(v.begin(), v.end());    // 升序字典序：apple, banana, cat

---

2.6、字符串基本处理技巧（蓝皮书核心）

2.6.1 字符统计 / 桶计数

定义：用一个数组 cnt[256]（或 cnt[26] 仅字母）统计每个字符出现次数。

string s = "aabcc";
int cnt[256] = {0};          // 全 0 初始化
for (char c : s) cnt[(unsigned char)c]++;
// cnt['a']=2, cnt['b']=1, cnt['c']=2

应用：统计字母频率、判断能否组成回文、判字母异位词。 复杂度：O(n)。

2.6.2 回文判断

定义：正读反读都一样的串（如 "aba"、"abba"）。

bool isPalindrome(const string &s) {
    int i = 0, j = (int)s.length() - 1;
    while (i < j) {
        if (s[i] != s[j]) return false;
        i++; j--;
    }
    return true;
}

应用：回文串、最长回文子串（J 级通常暴力或中心扩展；Manacher 属 CSP-S，不要求）。

2.6.3 反转字符串

string s = "hello";
reverse(s.begin(), s.end());            // "olleh"（需 #include <algorithm>）
// 或手动双指针（见 5.2 思路）

应用：判断回文、单词翻转、数字翻转。

2.6.4 子串查找（暴力 / 库函数）

// 方法①：直接用 string::find（最常用，底层 O(nm)）
size_t pos = s.find("abc");
if (pos != string::npos) { /* 找到了 */ }

// 方法②：手写暴力匹配（理解原理）
bool bruteForce(const string &t, const string &p) {
    int n = t.length(), m = p.length();
    for (int i = 0; i + m <= n; i++) {     // O(nm)
        bool ok = true;
        for (int j = 0; j < m; j++)
            if (t[i+j] != p[j]) { ok = false; break; }
        if (ok) return true;
    }
    return false;
}

重要性质：暴力匹配最坏 O(n·m)；KMP / Sunday 等高效算法属 CSP-S（提高级），本文仅预告，J 级用 find 或暴力已足够。

2.6.5 字符串分割（按分隔符）

// 按空格切分单词（用 stringstream）
#include <sstream>
string line = "I love C++";
stringstream ss(line);
string w;
while (ss >> w) cout << w << '\n';    // I / love / C++

// 按自定义分隔符（如逗号）
vector<string> split(const string &s, char d) {
    vector<string> res; string cur;
    for (char c : s) {
        if (c == d) { res.push_back(cur); cur.clear(); }
        else cur += c;
    }
    res.push_back(cur);                // 最后一个
    return res;
}

2.6.6 去重 / 字母异位词（Anagram）

// 判断两串是否为异位词（字母相同、顺序不同）
bool isAnagram(string a, string b) {
    if (a.length() != b.length()) return false;
    int cnt[26] = {0};
    for (char c : a) cnt[c-'a']++;
    for (char c : b) cnt[c-'a']--;
    for (int i = 0; i < 26; i++) if (cnt[i] != 0) return false;
    return true;
}

---

2.7、串上的算法（CSP-J 范围）

2.7.1 前缀和 / 差分在串上

把字符映射到整数，即可把"区间计数"转成前缀和问题。

// 例：给定只含 'a'/'b' 的串，多次询问 [l,r] 内 'a' 的个数
string s = "ababa";
int pre[105] = {0};          // pre[i] = 前 i 个字符中 'a' 的个数
for (int i = 0; i < s.length(); i++)
    pre[i+1] = pre[i] + (s[i] == 'a');
// 询问 [l,r]（0-based）：ans = pre[r+1] - pre[l]

复杂度：预处理 O(n)，每次询问 O(1)。 应用：子串字母计数、判断子串是否互为异位词（固定长度窗口）。

2.7.2 字符串哈希（滚动哈希 / Rabin-Karp）

定义：把串映射成一个大整数（哈希值），用于快速比较两子串是否相等。

滚动哈希（自然溢出 / 双哈希）：

const long long B = 131;            // 进制基数（常用 131/13331）
const long long MOD = 1e9 + 7;      // 取模防溢出（或 unsigned long long 自然溢出）
string s = "abcde";
long long h[105], p[105];
p[0] = 1; h[0] = 0;
for (int i = 0; i < s.length(); i++) {
    p[i+1] = p[i] * B % MOD;
    h[i+1] = (h[i] * B + s[i]) % MOD;
}
// 子串 s[l..r] 的哈希： (h[r+1] - h[l]*p[r-l+1] % MOD + MOD) % MOD
auto subHash = [&](int l, int r) {
    long long v = (h[r+1] - h[l] * p[r-l+1] % MOD + MOD) % MOD;
    return v;
};

性质：两子串相等 ⟺ 哈希值相等（理论上可能冲突，用双哈希或自然溢出降概率）。 应用：快速判子串相等、最长公共子串、字符串匹配（Rabin-Karp）。

已在前文《数据结构知识详解·哈希表》详细展开，此处为串上应用的衔接。

2.7.3 模式匹配（暴力为主）

J 级模式匹配用 §5.4 的 find 或暴力即可。若题目数据小（n,m ≤ 10³~10⁴），暴力 O(nm) 完全够用。KMP / 扩展 KMP / AC 自动机属 CSP-S，本文不展开，但需知道它们"解决更长串/多模式匹配"的定位。

2.7.4 字典序排序

vector<string> v = {"c", "ab", "abc", "a"};
sort(v.begin(), v.end());        // "a" < "ab" < "abc" < "c"
// 按长度 + 字典序：自定义比较
sort(v.begin(), v.end(), [](const string &x, const string &y){
    if (x.length() != y.length()) return x.length() < y.length();
    return x < y;
});

---

2.7.4 经典应用与模板题方向

题型	思路	关键技巧
统计字母出现次数	桶计数 cnt[26]	仅字母时下标 c-'a'
判断回文	双指针	注意奇偶长度
单词翻转	stringstream 分割后逐个 reverse	或直接整体 reverse
整数翻转（含负数）	转字符串 to_string → reverse → stoi	注意前导 0、溢出
凯撒密码 / 移位	c = (c - 'a' + k) % 26 + 'a'	循环取模
删除/替换字符	erase / replace / 重建新串	重建新串更不易错
最长连续相同字符	线性扫描计数	维护 cur/max
子串频次（小字母表）	枚举所有子串 + 哈希/计数	数据小可暴力
判断两串异位词	两个桶相减	§5.6
公共前缀	逐位比对到首个不同	长度取 min

---

2.7.5 易错点与复习清单

必记易错点：

1. 下标从 0 开始；取末尾字符是 s[s.length()-1]，不是 s[s.length()]。
2. cin >> s 遇空格截断；读整行用 getline；cin 后接 getline 要 cin.ignore() 吃掉换行。
3. s.length() 是无符号类型；做减法比较一定要先强转 (int) 或存成 int n，否则 n-1 在空串时变成极大值导致死循环。
4. 字符 '7' ≠ 整数 7；字符转数字用 c - '0'，数字转字符用 d + '0'。
5. 字符数组必须留 '\0'：开 char s[N+1]，库函数靠 '\0' 判断结束。
6. substr(pos, len) 第二参是长度；越界会 runtime error。
7. string::find 找不到返回 string::npos（不是 -1），比较务必用 != string::npos。
8. 字符串拼接 + 两侧至少有一个是 string（不能两个都是 "..." 字面量直接 +）。

范围边界（与提高级 CSP-S 的衔接）：

• J 级：字符数组/string、I/O、cctype/<string> 库、桶计数、回文、反转、暴力匹配、find、前缀和计数、滚动哈希（了解）、字典序排序。
• S 级才要求：KMP / Sunday、Manacher、Trie（字典树）、AC 自动机、后缀数组/自动机、后缀自动机、扩展 KMP。这些在 J 级不需要深入，但建议学有余力时预习。

一句话复习：字符串就是"披着线性结构外衣的字符数组"——下标从 0、字符即 ASCII 整数、库函数分 <cstring>/<string>/<cctype> 三套，处理套路是遍历 + 桶 + 双指针 + 哈希。

---

3、哈希表（Hash Table，含冲突处理）

3.1 基本概念

目标：把"关键字"通过一个哈希函数 h(key) 直接映射到存储位置，理想情况下增删查都是 O(1)。

哈希函数：把任意 key（整数、字符串…）算成一个整数地址。

• 除留余数法（最常用）：h(key) = key % M，M 取大质数可减少冲突。
• 字符串常用滚动哈希（见 5.4）。

冲突（Collision）：不同 key 经 h 映射到同一位置，必然发生（因为 key 空间 >> 地址空间）。哈希表设计的核心就是冲突处理。

装填因子（Load Factor）：α = 已存元素数 / 桶数。α 越大冲突越多，一般保持 α 较小（如 < 0.7）。

3.2 冲突处理一：拉链法（链地址法）

每个桶挂一个链表（或 vector），冲突的元素都挂在同一桶下。

const int M = 10007;            // 大质数作模数
vector<int> bucket[M];
int h(int x) { return (x % M + M) % M; }   // 防负数
void insert(int x) { bucket[h(x)].push_back(x); }
bool find(int x) {
    int id = h(x);
    for (int v : bucket[id]) if (v == x) return true;
    return false;
}

特点：冲突只让链表变长，不会"堆积"；删除方便；空间按需增长。平均查找 O(1+α)。

3.3 冲突处理二：开放寻址法

所有元素都放在数组本身，冲突时按某种规则探测下一个空位。

• 线性探测：h(key), h(key)+1, h(key)+2, …（模 M），直到空位。
• 平方探测：h(key), h(key)+1², h(key)+2², …
• 双重散列：用第二个哈希函数决定步长。

const int M = 20011;            // 质数且 > 元素数
int slot[M]; bool used[M] = {false};
void insert(int x) {
    int id = h(x);
    while (used[id]) id = (id + 1) % M;   // 线性探测
    slot[id] = x; used[id] = true;
}

特点：无需额外指针，缓存友好；但易产生聚集（clustering），删除需做"懒惰删除"标记（不能直接清掉，否则断链）。

3.4 字符串哈希（滚动哈希，竞赛常用）

把字符串看成一个 B 进制大数（如 B=131），用模 MOD 取指纹，支持快速求子串哈希（如 Rabin-Karp 字符串匹配、判子串相等）。

const int B = 131, MOD = 1e9 + 7, N = 100005;
long long h[N], p[N];   // h[i]: 前缀 s[1..i] 的哈希；p[i]: B^i % MOD
p[0] = 1;
for (int i = 1; i <= n; i++) {
    p[i] = p[i-1] * B % MOD;
    h[i] = (h[i-1] * B + s[i]) % MOD;
}
// 子串 s[l..r] 的哈希（1-based）
long long sub(int l, int r) {
    return (h[r] - h[l-1] * p[r-l+1] % MOD + MOD) % MOD;
}

应用：快速判断两段子串是否相等、最长回文子串（配合二分）、字符串去重。

---

教材结构说明

本章在原教材中以 练习题/选择题 为主，没有单独的知识讲解部分。以下内容按教材原有顺序整理，并将答案做成 Docusaurus/MDX 可折叠形式。

1. 哈希表：线性探查

设有一个含有 13 个元素的 Hash 表（地址 0~12），Hash 函数是：

H(key) = key % 13

其中 % 是求余数运算。

用线性探查法解决冲突，则对于序列：

(2、8、31、20、19、18、53、27)

18 应放在第几号格中（ ）。

• A. 5
• B. 9
• C. 4
• D. 0

查看答案

答案：B

2. 哈希表：冲突处理

给定地址区间为 0~9 的哈希表，哈希函数为：

h(x) = x % 10

采用线性探查的冲突解决策略：出现冲突时，向后探查第一个空地址存储；若地址 9 冲突，则从地址 0 重新开始探查。

哈希表初始为空表，依次存储：

(71, 23, 73, 99, 44, 79, 89)

请问 89 存储在哈希表哪个地址中（ ）。

• A. 9
• B. 0
• C. 1
• D. 2

查看答案

答案：D

3. 哈希表：mod 函数

现有一个地址区间为 0~10 的哈希表。出现冲突时，向后找第一个空地址存储；到地址 10 冲突后，从 0 开始向后探查。

现在依次存储：

(0, 1, 2, 3, 4, 5, 6, 7)

哈希函数为 mod。

请问 7 存储在哈希表哪个地址中（ ）。

• A. 5
• B. 6
• C. 7
• D. 8

查看答案

答案：C

4. 字符串的非空子串

设字符串：

S = "Olympic"

S 的非空子串的数目是（ ）。

• A. 29
• B. 28
• C. 16
• D. 17

查看答案

答案：B

5. 字符串

以下关于字符串的判定语句中正确的是（ ）。

• A. 字符串是一种特殊的线性表
• B. 串的长度必须大于零
• C. 字符串不可以用数组来表示
• D. 空格字符组成的串就是空串

查看答案

答案：A

6. 字符串相邻交换

定义一种字符串操作为：交换相邻两个字符。

将：

DACFEB

变为：

ABCDEF

最少需要（ ）次上述操作。

• A. 7
• B. 8
• C. 9
• D. 6

查看答案

答案：A

7. 链表特点

链表不具有的特点是（ ）。

• A. 插入删除不需要移动元素
• B. 不必事先估计存储空间
• C. 所需空间与线性表长度成正比
• D. 可随机访问任一元素

查看答案

答案：D

8. 双向链表查询复杂度

在含有 n 个元素的双向链表中，查询是否存在关键字为 k 的元素，最坏情况下运行的时间复杂度是（ ）。

• A. O(1)
• B. O(log n)
• C. O(n)
• D. O(nlogn)

查看答案

答案：C

9. 链表的存储地址

线性表若采用链表存储结构，要求内存中可用存储单元地址（ ）。

• A. 必须连续
• B. 部分地址必须连续
• C. 一定不连续
• D. 连续不连续均可

查看答案

答案：D

10. 栈：入栈顺序

已知元素：

(8，25，14，87，51，90，6，19，20)

问这些元素以怎样的顺序进入栈，才能使出栈的顺序满足：

• 8 在 51 前面
• 90 在 87 后面
• 20 在 14 后面
• 25 在 6 前面
• 19 在 90 后面

（ ）。

• A. 20，6，8，51，90，25，14，19，87
• B. 51，6，19，20，14，8，87，90，25
• C. 19，20，90，8，6，25，51，14，87
• D. 6，25，51，8，20，19，90，87，14

查看答案

答案：D

11. 栈：合法出栈序列

对于入栈顺序为：

a, b, c, d, e, f, g

的序列，下列（ ）不可能是合法的出栈序列。

• A. a, b, c, d, e, f, g
• B. a, d, c, b, e, g, f
• C. a, d, b, c, g, f, e
• D. g, f, e, d, c, b, a

查看答案

答案：C

12. 栈和队列

设栈 S 和队列 Q 的初始状态为空。

元素：

e1, e2, e3, e4, e5, e6

依次通过栈 S，一个元素出栈后即进入队列 Q。

若出队的顺序为：

e2, e4, e3, e6, e5, e1

则栈 S 的容量至少应该为（ ）。

• A. 2
• B. 3
• C. 4
• D. 5

查看答案

答案：B

13. 数制运算

(2070)<sub>16</sub> + (34)<sub>8</sub> 的结果不正确的是（ ）。

• A. (8332)<sub>10</sub>
• B. (208C)<sub>16</sub>
• C. (100000000110)<sub>2</sub>
• D. (20214)<sub>8</sub>

查看答案

答案：C

14. 【多选】哈希函数

将：

(2, 6, 10, 17)

分别存储到某个地址区间为 0~10 的哈希表中。

如果哈希函数 h(x) 为（ ），将不会产生冲突。

其中 a mod b 表示 a 除以 b 的余数。

• A. x mod 11
• B. x^2 mod 11
• C. 2^x mod 11
• D. ⌊√x⌋ mod 11

查看答案

答案：C、D

15. 【多选】栈的出栈序列

设栈 S 的初始状态为空，元素：

a, b, c, d, e, f, g

依次入栈。

以下出栈序列不可能出现的有（ ）。

• A. a, b, c, e, d, f, g
• B. b, c, a, f, e, g, d
• C. a, e, c, b, d, f, g
• D. g, e, f, d, c, b, a

查看答案

答案：C、D