1. 算法的特性与程序辨析#

考研核心考点：算法需满足有穷性、确定性、可行性、输入、输出五大特性，其中有穷性是算法与程序的核心区别——程序（如操作系统）可以无限运行，不满足有穷性。常考选择题辨析算法与程序的差异，以及简答题简述算法的五大特性。

2. 渐近时间复杂度与大O表示法#

考研核心考点：

• 渐近时间复杂度的定义：忽略低阶项、常数系数，保留最高阶项，记作$O(f(n))$，用于描述算法随输入规模增长的时间增长趋势。
• 常见复杂度阶数排序：$O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(n^3) < O(2^n)$
• 常考题型：推导循环结构的时间复杂度，区分最好、最坏、平均时间复杂度（如顺序查找的最好$O(1)$、最坏$O(n)$、平均$O(n/2)$）。

3. 线性表的顺序存储及其操作复杂度#

顺序表采用数组实现，存储地址连续：

• 按位查找：$O(1)$，可直接通过下标访问
• 按值查找：$O(n)$，需遍历数组匹配元素
• 插入/删除操作：平均需要移动$n/2$个元素，时间复杂度$O(n)$，仅在表尾操作时可达到$O(1)$。 考研常考选择题对比顺序表与链表的操作复杂度，以及简答题分析顺序表的优缺点。

4. 单链表的插入删除与时间复杂度#

单链表采用链式存储，无需连续存储空间：

• 按位置插入/删除：需先遍历找到目标节点的前驱，时间复杂度$O(n)$
• 已知目标节点的插入/删除：可直接修改指针，时间复杂度$O(1)$（考研常考该场景的编程实现）
• 头插法、尾插法建表：头插法复杂度$O(n)$，尾插法若带有尾指针可优化为一次遍历完成，总复杂度$O(n)$。 常考单链表的编程题实现，以及复杂度分析。

5. 循环链表的结构与应用#

循环链表分为单向循环链表与双向循环链表：

• 单向循环链表：尾节点的next指针指向头节点，无需遍历即可找到任意节点的后继，常用于解决单向链表无法快速访问尾节点的问题
• 双向循环链表：每个节点带有前驱与后继指针，尾节点的next指向头节点，头节点的prior指向尾节点，支持双向遍历，常用于实现双向队列。 考研常考循环链表的判空、判尾条件，以及应用场景分析。

6. 栈的两种栈顶指针设置方式#

栈是后进先出的线性结构，栈顶指针的两种常见实现：

1. 栈顶指针指向栈顶元素的下一个位置：初始状态top = 0，入栈时先存储元素再top++，出栈时先top--再取出元素，栈空条件为top == 0，栈满条件为top == maxSize
2. 栈顶指针指向栈顶元素本身：初始状态top = -1，入栈时先top++再存储元素，出栈时先取出元素再top--，栈空条件为top == -1，栈满条件为top == maxSize -1 考研常考选择题区分两种实现的栈空栈满条件，以及代码实现细节。

7. 循环队列的判空判满实现#

循环队列用于解决顺序队列的假溢出问题，常见三种实现方式：

1. 牺牲一个单元法（考研最常考）：栈满条件为(rear + 1) % maxSize == front，栈空条件为front == rear，牺牲的单元用于区分空与满的状态
2. 计数器法：设置一个计数器count，count == 0时为空，count == maxSize时为满
3. 标记法：设置tag标记，0表示上次操作是出队，1表示上次操作是入队，当front == rear && tag == 0为空，front == rear && tag ==1为满。 常考选择题给出循环队列的front与rear值，判断队列中元素个数。

8. 前缀、后缀表达式转换与求值#

这是考研408的高频考点，难点在于转换规则与求值顺序：

• 中缀转后缀（逆波兰式）：借助栈实现，规则为：
  1. 遇到操作数直接输出
  2. 遇到运算符：弹出栈中优先级大于等于当前运算符的运算符，再将当前运算符压栈；遇到左括号直接压栈，遇到右括号则弹出栈中元素直到左括号（左括号不输出）
  3. 遍历结束后弹出栈中剩余的所有运算符
• 后缀表达式求值：借助栈实现，遇到操作数压栈，遇到运算符弹出两个栈顶元素（注意：后弹出的是左操作数），计算结果后压栈，最终栈顶元素即为结果
• 前缀表达式（波兰式）：与后缀类似，仅遍历方向相反，从右向左扫描求值。 常考手工转换与求值的选择题、简答题。

9. 数组与矩阵的下标存储地址计算#

• 一维数组：LOC(i) = LOC(0) + i * sizeof(ElemType)
• 二维数组：
  1. 行优先：LOC(i,j) = LOC(0,0) + (i * n + j) * sizeof(ElemType)（n为列数）
  2. 列优先：LOC(i,j) = LOC(0,0) + (j * m + i) * sizeof(ElemType)（m为行数）
• 特殊矩阵压缩存储：对称矩阵、三角矩阵仅存储下三角/上三角元素，稀疏矩阵采用三元组表或十字链表存储，考研常考特殊矩阵的地址计算公式。