针对408计算机学科专业基础综合考试，算法题是数据结构科目的核心考查点，其特点是注重基础算法的原理、手写代码实现能力以及时间复杂度分析，而非追求偏难怪的算法。根据历年真题（2010-2024）的统计分析，以下是对“最核心高频考点”的总结，每个考点均附有核心代码模板和典型例题分析。

一、 核心高频考点与代码实现

1. 单链表反转（迭代与递归）

考点：对链表指针操作的深刻理解，是链表题目的基础。

  • 迭代法：使用三个指针 pre, cur, next 逐个反转。
  • 递归法：从链表尾部开始反转，需要理解递归栈。

代码实现 (C++):

// 迭代法
ListNode* reverseList_iterative(ListNode* head) {
    ListNode *pre = nullptr, *cur = head, *next = nullptr;
    while (cur) {
        next = cur->next; // 保存后继
        cur->next = pre;  // 反转指针
        pre = cur;        // 前驱后移
        cur = next;       // 当前后移
    }
    return pre; // 新的头节点
}

// 递归法
ListNode* reverseList_recursive(ListNode* head) {
    if (head == nullptr || head->next == nullptr) return head;
    ListNode* newHead = reverseList_recursive(head->next); // 递归到尾部
    head->next->next = head; // 反转指针
    head->next = nullptr;
    return newHead;
}

例题：给定单链表头节点，返回反转后的链表。(2010, 2019, 2022真题涉及链表操作)

2. 二叉树非递归遍历（前序、中序、后序）

考点：利用栈模拟递归过程，考查对遍历顺序和栈数据结构的掌握。

  • 前序：访问根 -> 右子树入栈 -> 左子树入栈。
  • 中序：一直将左子树入栈 -> 弹出访问 -> 转向右子树。
  • 后序：类似前序，但采用“根-右-左”的顺序遍历，然后反转结果。

代码实现 (C++) - 中序遍历:

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> stk;
    TreeNode* cur = root;
    while (cur != nullptr || !stk.empty()) {
        while (cur != nullptr) { // 深入左子树
            stk.push(cur);
            cur = cur->left;
        }
        cur = stk.top(); stk.pop(); // 回溯到父节点
        res.push_back(cur->val);    // 访问
        cur = cur->right;           // 转向右子树
    }
    return res;
}

3. 快速排序

考点：分治思想，核心是 partition 操作。必须掌握其不稳定性、平均O(nlogn)和最坏O(n²)的时间复杂度，以及递归与非递归实现。

代码实现 (C++) - 递归版:

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high]; // 选最后一个元素为基准
    int i = low - 1; // 小于pivot的区域的边界
    for (int j = low; j < high; ++j) {
        if (arr[j] < pivot) {
            swap(arr[++i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1; // 返回基准的最终位置
}

void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

例题：手写快速排序算法，并对序列 [5, 3, 8, 1, 2] 进行排序演示。(2017, 2020真题)

4. 归并排序

考点：稳定的O(nlogn)排序，分治与合并两个有序数组的过程。常用于链表排序和外部排序。

代码实现 (C++):

void merge(vector<int>& arr, int left, int mid, int right) {
    vector<int> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++]; // 稳定性的关键
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    for (int p = 0; p < k; ++p) arr[left + p] = temp[p];
}

void mergeSort(vector<int>& arr, int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

5. KMP算法 (next数组构建与匹配)

考点：字符串匹配的核心算法。重点在于理解 最长相等前后缀 的概念，并能手算或代码构建 next 数组。

代码实现 (C++):

// 构建next数组 (前缀表，不减一版本)
vector<int> getNext(string pattern) {
    int n = pattern.size();
    vector<int> next(n, 0);
    for (int i = 1, j = 0; i < n; ++i) { // j指向前缀末尾，i指向后缀末尾
        while (j > 0 && pattern[i] != pattern[j]) j = next[j - 1]; // 回退
        if (pattern[i] == pattern[j]) ++j;
        next[i] = j;
    }
    return next;
}

// KMP匹配
int kmpSearch(string text, string pattern) {
    vector<int> next = getNext(pattern);
    int j = 0; // 模式串指针
    for (int i = 0; i < text.size(); ++i) { // i是文本串指针
        while (j > 0 && text[i] != pattern[j]) j = next[j - 1];
        if (text[i] == pattern[j]) ++j;
        if (j == pattern.size()) return i - j + 1; // 匹配成功
    }
    return -1;
}

例题：给定模式串 "ababc"，求其 next 数组，并说明在文本串 "abababcab" 中的匹配过程。(2019, 2024真题高频)

6. 二分查找

考点：有序数组查找的经典算法。必须掌握循环不变量的思想，以及寻找左边界和右边界的变种。

代码实现 (C++) - 标准版:

int binarySearch(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1; // 闭区间
    while (left <= right) {
        int mid = left + (right - left) / 2; // 防止溢出
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

// 变种：寻找第一个等于target的位置（左边界）
int leftBound(vector<int>& nums, int target) {
    int left = 0, right = nums.size(); // 左闭右开
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] >= target) right = mid;
        else left = mid + 1;
    }
    return (left < nums.size() && nums[left] == target) ? left : -1;
}

7. DFS (深度优先搜索) 与 BFS (广度优先搜索)

考点：图/树遍历的基础。DFS常用递归或栈，BFS必须用队列。常与路径查找、连通分量等问题结合。

代码实现 (C++) - 图的邻接表DFS/BFS:

// DFS 递归
vector<bool> visited;
void dfs(vector<vector<int>>& graph, int node) {
    visited[node] = true;
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) dfs(graph, neighbor);
    }
}

// BFS 队列
void bfs(vector<vector<int>>& graph, int start) {
    vector<bool> visited(graph.size(), false);
    queue<int> q;
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        for (int neighbor : graph[cur]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

8. 拓扑排序 (Kahn算法)

考点：对有向无环图(DAG)进行排序，判断图中是否有环。核心是入度表和队列。

代码实现 (C++):

vector<int> topologicalSort(int numCourses, vector<vector<int>>& prerequisites) {
    vector<vector<int>> graph(numCourses);
    vector<int> inDegree(numCourses, 0);
    // 建图，计算入度
    for (auto& edge : prerequisites) {
        graph[edge[1]].push_back(edge[0]); // edge[1] -> edge[0]
        inDegree[edge[0]]++;
    }
    queue<int> q;
    for (int i = 0; i < numCourses; ++i) if (inDegree[i] == 0) q.push(i);
    
    vector<int> result;
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        result.push_back(cur);
        for (int next : graph[cur]) {
            if (--inDegree[next] == 0) q.push(next);
        }
    }
    // 如果结果数量不等于节点数，说明有环
    return result.size() == numCourses ? result : vector<int>();
}

例题：给定课程依赖关系，判断能否完成所有课程学习。(2019真题)

9. 最长递增子序列 (LIS) - 动态规划

考点：经典一维动态规划。dp[i] 表示以 nums[i] 结尾的LIS长度。优化方法（贪心+二分）也需了解。

代码实现 (C++) - 基础DP (O(n²)):

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1); // 初始长度为1
    int maxLen = 1;
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        maxLen = max(maxLen, dp[i]);
    }
    return maxLen;
}

10. 快慢指针（找环、倒数第k个节点）

考点：双指针技巧的经典应用，空间复杂度O(1)。

  • 找环：快指针每次走两步，慢指针每次走一步。相遇则有环，相遇后从头和相遇点同速出发，再次相遇点为环入口。
  • 倒数第k个节点：快指针先走k步，然后快慢指针同速前进，快指针到末尾时，慢指针即指向倒数第k个。

代码实现 (C++):

// 链表找环入口
ListNode *detectCycle(ListNode *head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) { // 有环
            ListNode *ptr1 = head, *ptr2 = slow;
            while (ptr1 != ptr2) {
                ptr1 = ptr1->next;
                ptr2 = ptr2->next;
            }
            return ptr1; // 环入口
        }
    }
    return nullptr; // 无环
}

// 链表倒数第k个节点
ListNode* getKthFromEnd(ListNode* head, int k) {
    ListNode *fast = head, *slow = head;
    for (int i = 0; i < k; ++i) fast = fast->next; // 快指针先走k步
    while (fast) {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

二、 备考策略与例题总结

  1. 理解优于死记：务必理解每个算法的核心思想、步骤和时间复杂度/空间复杂度。408常要求分析算法复杂度。
  2. 手写代码：在纸上或白板上能流畅写出无语法错误的伪代码或C/C++代码片段。特别注意边界条件（如空链表、空树、数组越界）。
  3. 真题驱动：将上述算法与历年真题（尤其是近十年）结合练习。例如，快速排序和归并排序常考排序过程演示和复杂度比较；KMP常考next数组手算。
  4. 对比学习：
    • 排序算法：对比快速排序（不稳定、原地）和归并排序（稳定、需额外空间）的优劣。
    • 遍历：对比DFS（深度优先，栈/递归）和BFS（广度优先，队列）的应用场景。
    • 查找：对比二分查找（O(logn)）与顺序查找（O(n)）。

典型综合例题：设计一个算法，判断一棵二叉树是否为平衡二叉树（任何节点的左右子树高度差不超过1）。要求写出算法思想，并给出时间复杂度分析。

  • 思路：后序遍历，在计算高度的同时判断平衡性。
  • 代码框架： 
    int checkHeight(TreeNode* root) {
    if (!root) return 0;
    int leftH = checkHeight(root->left);
    if (leftH == -1) return -1;
    int rightH = checkHeight(root->right);
    if (rightH == -1) return -1;
    if (abs(leftH - rightH) > 1) return -1;
    return max(leftH, rightH) + 1;
}
bool isBalanced(TreeNode* root) {
    return checkHeight(root) != -1;
}
  • 分析：时间复杂度O(n)，每个节点访问一次；空间复杂度O(h)，递归栈深度为树高。

参考来源

 

# 排序算法 # 服务器 # 算法 # 数据结构
Logo
EazyDevelop社区

一站式 AI 云服务平台

更多推荐

cover

5分钟玩转基于ModelEngine Nexent的智能体全流程工程最佳实践 - 智能AI客服

avatar EazyDevelop社区
cover

通俗理解 ERP，ERP 到底是什么？

avatar EazyDevelop社区
cover

【LeetCode刷题日记】一篇彻底搞懂KMP算法（附LeetCode28.详解）及原理剖析

avatar EazyDevelop社区