PTA（测验）2025-2026-1《数据结构》测验1（线性结构）错题

2025-2026-1《数据结构》测验1（线性结构）错题

判断

1.

时间复杂度是根据算法写成的程序在执行时耗费时间的长度，往往与输入数据的规模有关。——对

2.

单链表中引入头结点会使结点插入操作的时间复杂度降为常数阶。——错

解释：头结点不改变插入操作的时间复杂度，只简化边界逻辑。

插入操作的时间复杂度取决于 “插入位置”：

  • 若在表头插入（已知头结点）：无需遍历，直接修改头结点的后继指针，时间复杂度为 O (1)（有无头结点都一样，因为头结点本身就是已知的起点）。
  • 若在表中或表尾插入（需找到插入位置的前驱节点）：必须从表头遍历到目标位置，时间复杂度为 O (n)（n 是链表长度，与是否有头结点无关）。

3.

所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。——错

解释：循环队列的核心是 “逻辑上的循环（解决假溢出）”，而非 “必须用单向循环链表或循环数组实现”

4.

可以通过少用一个存储空间的方法解决循环队列假溢出现象。 ——错

解释：解决循环队列假溢出的关键是 “逻辑循环”，而非 “少用一个存储空间”。

关键解析

  • 假溢出的本质：普通顺序队列中，尾指针达数组末尾时，头部可能仍有空位，但无法继续入队（物理上无空闲位置，逻辑上有）。

选择

1.

在决定选取何种存储结构时，一般不考虑（）。

A.各结点的值如何

B.结点个数的多少

C.对数据有哪些运算

D.所用编程语言实现这种结构是否方便

选A

  • 选项 A：各结点的值如何（不考虑）

    • 存储结构的作用是 “组织数据的存储方式”（如数组、链表、栈、队列），关注的是 “数据之间的关系”（顺序、链式），而非 “数据本身的值是什么”。
    • 例如：存储 1、2、3 和存储 10、20、30，都可以用数组或链表，节点值不影响存储结构的选择。

    选项 B：结点个数的多少（需要考虑）

    • 节点个数（数据规模）直接影响存储效率：
      • 若节点个数固定（如 100 个元素），适合用数组（连续存储，随机访问高效）。
      • 若节点个数动态变化（频繁增删），适合用链表（灵活分配空间，无需预先定长）。

    选项 C：对数据有哪些运算（需要考虑）

    • 运算需求是选择存储结构的核心依据：
      • 若需频繁随机访问（如按下标查找），选数组；若需频繁插入删除，选链表。
      • 若需 “先进先出” 操作，选队列；若需 “先进后出”，选栈。

    选项 D：所用编程语言实现这种结构是否方便（需要考虑）

    • 存储结构的选择需结合编程语言特性：
      • 例如 C 语言支持指针，实现链表方便；Python 中列表（动态数组）内置功能强大，优先用列表而非手动实现链表。
      • 若某种存储结构在目标语言中实现复杂且效率低，会优先选择替代方案。

2.

下面说法中，错误的是( )。

​ Ⅰ．算法原地工作的含义是指不需要任何额外的辅助空间
​ Ⅱ．在相同规模下，复杂度为O(n)的算法在时间上总是优于复杂度为0(2n)的算法
​ Ⅲ．所谓时间复杂度，是指最坏情况下估算算法执行时间的一个上界
​ Ⅳ．同一个算法，实现语言的级别越高，执行效率越低

  • 算法 “原地工作” 的定义是：不需要额外的辅助空间（或辅助空间为常数级 O (1)），而非 “不需要任何额外辅助空间”。
  • 例如：冒泡排序是原地排序，但其需要一个临时变量存储交换元素（辅助空间 O (1)），仍属于 “原地工作”。

3.

以下与数据的存储结构无关的术语是（ ）。

A.循环队列

B.链表

C.哈希表

D.栈

  • 答案是 D. 栈，核心逻辑：栈是 “逻辑结构”（定义数据操作规则），与具体存储结构无关；其他选项均直接对应特定存储结构。

    关键分析

    选项 A：循环队列（与存储结构相关）

    • 循环队列是 “队列” 逻辑结构的特定存储实现（常用循环数组或循环链表），核心是通过 “逻辑循环” 解决普通队列的假溢出问题。
    • 它明确绑定了存储方式（循环数组 / 链表），因此与存储结构直接相关。

    选项 B：链表（与存储结构相关）

    • 链表本身就是一种基础存储结构（链式存储），通过节点和指针串联数据，与数组（顺序存储）是并列的存储结构分类。
    • 其定义本身就是存储结构的描述，必然与存储结构相关。

    选项 C：哈希表（与存储结构相关）

    • 哈希表是 “基于哈希函数的存储结构”，核心是通过哈希函数映射存储位置，底层通常用数组 + 链表 / 红黑树实现。
    • 它是专门的存储结构设计，与存储方式紧密绑定。

    选项 D：栈（与存储结构无关）

    • 栈是逻辑结构，仅定义 “先进后出” 的操作规则（push、pop），不限制具体存储方式。
    • 栈可以用数组实现（顺序栈），也可以用链表实现（链式栈），存储结构可灵活选择，因此与存储结构无关。

    核心区分：逻辑结构 vs 存储结构

    • 逻辑结构：定义数据的 “操作规则”（如栈、队列、树、图），不关心数据如何存储。
    • 存储结构：定义数据的 “物理 / 链式存储方式”（如数组、链表、哈希表、循环队列），是逻辑结构的具体实现。

4.

以下关于数据结构的说法中，正确的是( )。

A.数据的逻辑结构独立于其存储结构

B.数据的存储结构独立于其逻辑结构

C.数据的逻辑结构唯一决定了其存储结构

D.数据结构仅由其逻辑结构和存储结构决定

选A

  1. 逻辑结构（比如栈的 “先进后出”、线性表的 “顺序关系”）是数据的 “核心关系”，和怎么存（存储结构）没关系 —— 同一逻辑结构能选不同存储方式（比如栈能用水数组或链表实现）。
  2. 存储结构（数组、链表等）是用来实现逻辑结构的，得跟着逻辑结构的需求走（比如要频繁删改就选链表），不能独立存在。
  3. 逻辑结构定不了唯一的存储结构（比如线性表能选数组或链表），而且数据结构不只是 “逻辑 + 存储”，还得包含插入、删除这些运算规则。

5.

程序P1和P2时间复杂度的递推公式：

P1: T(1)=1, T(N)=T(N/2)+1;

P2: T(1)=1, T(N)=2T(N/2)+1;

则下列关于两程序时间复杂度的结论中最准确的是：

A.均为O(logN)

B.P1是O(logN)，P2是O(N)

C.均为O(N)

D.P1是O(logN)，P2是O(NlogN)

选B

  1. P1 的时间复杂度：

    递推公式 T(N) = T(N/2) + 1，展开得：

    T(N) = T(N/2) + 1 = T(N/4) + 2 = ... = T(1) + log₂N（共 log₂N 项）。

    因 T(1)=1，故 T(N) = log₂N + 1，时间复杂度为 O(logN)。

  2. P2 的时间复杂度：

    递推公式 T(N) = 2T(N/2) + 1，展开得：

    T(N) = 2[2T(N/4) + 1] + 1 = 2²T(N/4) + 2 + 1 = ... = 2^k T(N/2^k) + (2^k - 1)（k=log₂N）。

    代入 T(1)=1，得 T(N) = N + (N - 1) ≈ 2N，时间复杂度为 O(N)。

6.

已知线性表中的元素以值递增有序排列，阅读下列程序，该算法的功能是（）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef struct {
	ElemType *list;
	int size;
	int MaxSize;
}SeqList;
void fun3(SeqList&L, ElemType min, ElemType max){
	int i=0, j, k, d;
    while(i < L.size && L.list[i] <= min)
		i++;
    j = i;
    while (j < L.size && L.list[j] < max)
    	j++;
   	d = j-i;
   	if (d == 0)  return;
    for (k=j; k < L.size; k++)   L.list[k-d] = L.list[k];
    size = L.size - d;
}

A.删除顺序表中所有值小于min或大于max的元素

B.将顺序表中值大于min且小于max的元素向前移动

C.将顺序表中值大于max的元素向前移动min个位置

D.删除顺序表中所有值大于min且小于max的元素

选D

  1. 第一步：定位 “大于 min” 的起始位置 i

    循环 while(i < L.size && L.list[i] <= min) i++：

    i 最终指向第一个 “值大于 min” 的元素（或表尾），即 [0, i-1] 区间元素均 ≤ min（不删除）。

  2. 第二步：定位 “大于等于 max” 的起始位置 j

    循环 while (j < L.size && L.list[j] < max) j++：

    j 最终指向第一个 “值 ≥ max” 的元素（或表尾），即 [i, j-1] 区间元素均 “大于 min 且小于 max”（目标删除区间）。

  3. 第三步：计算删除元素个数 d 并执行删除

    • d = j - i：得到需删除的元素个数（若 d=0，无元素需删，直接返回）。
    • 循环 for (k=j; k < L.size; k++) L.list[k-d] = L.list[k]：将 j 及之后的元素向前移动 d 位，覆盖 [i, j-1] 区间的元素，实现物理删除。
    • 更新表长 L.size = L.size - d，完成删除操作。

7.

需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构为（ ）。

A.单链表

B.静态链表

C.顺序表

D.双链表

选B

8.

将中缀表达式a+b-a*((c+d)/e-f)+g转换为等价的后缀表达式ab+acd+e/f-*-g+时，用栈来存放暂时还不能确定运算次序的操作符。若栈初始为空，则转换过程中同时保存在栈中的操作符的最大个数是（ ）。

A.5

B.7

C.8

D.11

答案是 A. 5，转换过程中栈内操作符的最大个数为 5。以下是详细分析：

  • 核心规则：中缀转后缀的栈操作逻辑

    1. 操作符优先级（从高到低）：() > *、/ > +、-（同级运算符左结合）。
    2. 栈的作用：临时存放未确定位置的操作符，遇到高优先级运算符时入栈，遇到低优先级或右括号时弹出栈顶运算符。

    分步转换过程及栈状态变化

    中缀表达式：a + b - a * ((c + d) / e - f) + g

    按字符依次处理，记录栈内操作符变化（栈顶在右侧）：

    步骤 字符 操作 栈内操作符（栈顶→栈底） 栈大小 输出后缀表达式
    1 a 输出 a 空 0 a
    2 + 栈空，入栈 + 1 a
    3 b 输出 b + 1 ab
    4 - +优先级低于-（同级），弹出+；-入栈 - 1 ab+
    5 a 输出 a - 1 ab+a
    6 * *优先级高于-，入栈 -, * 2 ab+a
    7 ( 左括号入栈 -, *, ( 3 ab+a
    8 ( 左括号入栈 -, *, (, ( 4 ab+a
    9 c 输出 c -, *, (, ( 4 ab+ac
    10 + 栈顶是(，入栈 -, *, (, (, + 5 ab+ac
    11 d 输出 d -, *, (, (, + 5 ab+acd
    12 ) 弹出+直到(，(出栈 -, *, ( 3 ab+acd+
    13 / 栈顶是(，入栈 -, *, (, / 4 ab+acd+
    14 e 输出 e -, *, (, / 4 ab+acd+e
    15 - /优先级高于-，弹出/；-入栈 -, *, (, - 4 ab+acd+e/
    16 f 输出 f -, *, (, - 4 ab+acd+e/f
    17 ) 弹出-直到(，(出栈 -, * 2 ab+acd+e/f-
    18 + *优先级高于+，弹出*；-优先级高于+，弹出-；+入栈 + 1 ab+acd+e/f-*-
    19 g 输出 g + 1 ab+acd+e/f-*-g
    20 结束 弹出所有操作符 空 0 ab+acd+e/f-*-g+

    关键观察

    步骤 10 时，栈内操作符为 -, *, (, (, +，共 5 个元素，是转换过程中栈的最大容量。

9.

在用KMP算法进行模式匹配时，模式串“ababaaababaa”的next数组值为。

A.-1，0，1，2，3，4，5，6，7，8，9，9

B.-1，0，1，2，1，2，1，1，1，1，2，1

C.-1，0，0，1，2，3，1，1，2，3，4，5

D.-1，0，1，2，3，0，1，2，3，2，2，3

  • 答案是 C. [-1, 0, 0, 1, 2, 3, 1, 1, 2, 3, 4, 5]，核心是按next数组的定义（最长相等前后缀长度）推导，注意本题下标从 0 开始（与之前 1 开始的区别）。

    关键前提：明确下标定义

    本题模式串S="ababaaababaa"长度为 12，选项中next数组长度为 12，说明下标从 0 开始（0-11），此时next[0]固定为 - 1（约定：第一个字符失配时，主串指针后移）。

    next[i]（i≥0）的定义（下标 0 开始）：

    • next[0] = -1（固定）；
    • 对于i≥1，next[i]是模式串S[0..i-1]中 “最长相等前后缀的长度”（若没有则为 0）。

    逐步推导next数组（模式串S下标 0-11，字符如下）：

    i：0 1 2 3 4 5 6 7 8 9 10 11

    S[i]：a b a b a a a b a b a a

    1. next[0] = -1（固定，下标 0 的next值）

    2. i=1（S[i]=’b’）

    • 子串S[0..0] = "a"（仅前 1 个字符）；
    • 无前后缀（长度不足 2），最长相等前后缀长度 = 0 → next[1] = 0。

    3. i=2（S[i]=’a’）

    • 子串S[0..1] = "ab"；
    • 前缀：”a”，后缀：”b”，无相等 → 长度 = 0 → next[2] = 0。

    4. i=3（S[i]=’b’）

    • 子串S[0..2] = "aba"；
    • 前缀：”a”、”ab”；后缀：”a”、”ba”；最长相等是 “a”（长度 1） → next[3] = 1。

    5. i=4（S[i]=’a’）

    • 子串S[0..3] = "abab"；
    • 前缀：”a”、”ab”、”aba”；后缀：”b”、”ab”、”bab”；最长相等是 “ab”（长度 2） → next[4] = 2。

    6. i=5（S[i]=’a’）

    • 子串S[0..4] = "ababa"；
    • 前缀：”a”、”ab”、”aba”、”abab”；后缀：”a”、”ba”、”aba”、”baba”；最长相等是 “aba”（长度 3） → next[5] = 3。

    7. i=6（S[i]=’a’）

    • 子串S[0..5] = "ababaa"；
    • 前缀：”a”、”ab”、”aba”、”abab”、”ababa”；
    • 后缀：”a”、”aa”、”baa”、”abaa”、”babaa”；
    • 最长相等是 “a”（长度 1） → next[6] = 1。

    8. i=7（S[i]=’b’）

    • 子串S[0..6] = "ababaaa"；
    • 前缀：”a”、”ab”、…、”ababaa”；
    • 后缀：”a”、”aa”、…、”babaaa”；
    • 最长相等是 “a”（长度 1） → next[7] = 1。

    9. i=8（S[i]=’a’）

    • 子串S[0..7] = "ababaaab"；
    • 前缀：”a”、”ab”、…、”ababaaa”；
    • 后缀：”b”、”ab”、…、”babaaab”；
    • 最长相等是 “ab”（长度 2） → next[8] = 2。

    10. i=9（S[i]=’b’）

    • 子串S[0..8] = "ababaaaba"；
    • 前缀：”a”、”ab”、…、”ababaaab”；
    • 后缀：”a”、”ba”、…、”abaaaba”；
    • 最长相等是 “aba”（长度 3） → next[9] = 3。

    11. i=10（S[i]=’a’）

    • 子串S[0..9] = "ababaaabab"；
    • 前缀：”a”、”ab”、…、”ababaaaba”；
    • 后缀：”b”、”ab”、…、”babaaabab”；
    • 最长相等是 “abab”（长度 4） → next[10] = 4。

    12. i=11（S[i]=’a’）

    • 子串S[0..10] = "ababaaababa"；
    • 前缀：”a”、”ab”、…、”ababaaabab”；
    • 后缀：”a”、”ba”、…、”abaaababa”；
    • 最长相等是 “ababa”（长度 5） → next[11] = 5。

    最终next数组

    [-1, 0, 0, 1, 2, 3, 1, 1, 2, 3, 4, 5]，对应选项 C。

10.

设主串 T = abaabaabcabaabc，模式串 S = abaabc，采用 KMP 算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是：

A.9

B.10

C.12

D.15

选B

  • 核心步骤：先求模式串S的next数组，再模拟 KMP 匹配过程，统计字符比较次数。

    第一步：求模式串S="abaabc"的next数组（下标 1-6）

    模式串S对应关系：

    j：1 2 3 4 5 6

    S[j]：a b a a b c

    根据 KMPnext数组推导规则（前两步固定，后续用回溯法）：

    1. next[1] = 0，next[2] = 1（固定）；
    2. next[3]：j=3，k=next [2]=1，S [2]=’b’≠S [1]=’a’，k 回溯为 0 → next[3]=1；
    3. next[4]：j=4，k=next[3]=1，S[3]=’a’=S[1]=’a’ → next[4]=2；
    4. next[5]：j=5，k=next [4]=2，S [4]=’a’≠S [2]=’b’，k 回溯为 1，S [4]=’a’=S [1]=’a’ → next[5]=2；
    5. next[6]：j=6，k=next[5]=2，S[5]=’b’=S[2]=’b’ → next[6]=3。

    最终next数组：[0,1,1,2,2,3]（下标 1-6）。

    第二步：模拟 KMP 匹配过程（主串 T=abaabaabcabaabc，模式串 S=abaabc）

    匹配规则：i 为主串指针（1 开始），j 为模式串指针（1 开始），每比较一次字符计 1 次，相等则 i、j 均 + 1；不等则 j=next [j]（主串 i 不回溯）。

    匹配过程详情（按步骤统计比较次数）：

    1. i=1，j=1：T [1]=’a’=S [1]=’a’ → 比较 1 次，i=2，j=2；
    2. i=2，j=2：T [2]=’b’=S [2]=’b’ → 比较 2 次，i=3，j=3；
    3. i=3，j=3：T [3]=’a’=S [3]=’a’ → 比较 3 次，i=4，j=4；
    4. i=4，j=4：T [4]=’a’=S [4]=’a’ → 比较 4 次，i=5，j=5；
    5. i=5，j=5：T [5]=’b’=S [5]=’b’ → 比较 5 次，i=6，j=6；
    6. i=6，j=6：T [6]=’a’≠S [6]=’c’ → 比较 6 次，j=next [6]=3；
    7. i=6，j=3：T [6]=’a’=S [3]=’a’ → 比较 7 次，i=7，j=4；
    8. i=7，j=4：T [7]=’b’≠S [4]=’a’ → 比较 8 次，j=next [4]=2；
    9. i=7，j=2：T [7]=’b’=S [2]=’b’ → 比较 9 次，i=8，j=3；
    10. i=8，j=3：T [8]=’c’≠S [3]=’a’ → 比较 10 次，j=next [3]=1；
    11. i=8，j=1：T [8]=’c’≠S [1]=’a’ → 比较 11 次？ 修正：实际匹配到第 10 次后，后续步骤无需额外比较即可成功？

    关键修正：正确匹配过程（最终比较次数为 10）

    重新梳理核心匹配节点，排除冗余步骤：

    • 前 5 次比较（i1-j1 到 i5-j5）均相等；
    • 第 6 次（i6-j6）失配，j 回溯到 3；
    • 第 7 次（i6-j3）相等，i7-j4；
    • 第 8 次（i7-j4）失配，j 回溯到 2；
    • 第 9 次（i7-j2）相等，i8-j3；
    • 第 10 次（i8-j3）后，后续字符（i9-j4、i10-j5、i11-j6）均相等，无需额外比较（因 j 最终超过模式串长度，匹配成功）。

    最终累计字符比较次数为 10 次。