1. 项目概述一份来自“战场”的编程题攻坚笔记如果你正在备战江苏大学计算机相关专业的885程序设计科目尤其是被那些分值高、灵活性强的编程大题所困扰那么这份笔记可能就是为你准备的。它不是一本面面俱到的教科书而更像是一位“过来人”在题海战术中用时间和错误换来的实战心得汇编。我当年备考时市面上能找到的资料大多是知识点罗列或者真题的简单答案但对于“如何从零开始思考一道题”、“如何避开阅卷老师扣分的坑”、“如何在有限时间内写出既对又好的代码”这些关键问题却鲜有提及。这份笔记的核心就是试图填补这个空白。“885程序设计”的编程题通常不会去考那些偏门、冷僻的语法角落它的重点在于考察考生利用C/C通常是主要语言解决实际问题的综合能力。这包括了基础的数据结构数组、链表、栈、队列、树应用、经典算法思想递归、分治、动态规划、搜索的理解以及最重要的——将抽象问题转化为可执行代码的工程化思维。笔记的内容正是围绕这些核心展开通过对历年真题和典型模拟题的逐题精解拆解出通用的解题框架、常见的“陷阱”设置点以及代码实现的优化技巧。无论你是编程基础稍弱需要一步步跟练的新手还是已经刷过不少题但总在细节上丢分的进阶考生都能从中找到针对性的参考。2. 笔记内容架构与核心价值解析2.1 为什么是“笔记”而非“题解大全”市面上不乏各种考研真题的参考答案但很多答案只给出了最终的正确代码缺少了最关键的思考过程。这份笔记的独特价值在于它的“过程性”。它记录的不是一个静态的结果而是一个动态的、可能包含试错的解题路径。2.1.1 还原真实解题场景笔记中对于每道题的记录通常会包含以下几个层次初读题意与信息提取第一时间圈出题目中的输入输出格式、数据范围、特殊约束例如“时间复杂度要求O(n log n)”。这是避免方向性错误的第一步。例如一道关于“链表去重”的题如果数据范围是10^5那么用O(n^2)的双重循环暴力解法就肯定不可行必须立刻考虑哈希表等O(n)的方法。思路萌芽与方案对比记录下最初想到的几种可能解法。比如遇到一个查找问题可能会同时想到顺序查找、二分查找和用std::map。笔记会分析每种方法在此题上下文下的优劣二分要求有序额外排序是否划算map查询快但空间开销和常数时间是否可接受伪代码与边界推演在动手写代码前先用自然语言或简化的伪代码勾勒出主干逻辑。同时专门花时间思考边界情况输入为空链表怎么办数字全是负数怎么办整数运算溢出怎么办笔记会把这些易漏的边界点明确标出。代码实现与现场调试这是核心部分。笔记里的代码往往带有注释解释某行代码为何这样写比如“这里使用pre-next判空是为了统一处理头节点删除的情况”。还会记录编写时犯过的典型错误比如指针操作失误、循环条件写反等并附上修正后的正确版本和原因。复盘与优化点解出题目后会回头审视代码是否足够清晰是否有冗余计算能否用更简洁的数据结构这部分内容对于追求高分尤其重要展现了你的代码素养。2.1.2 聚焦高频考点与命题趋势通过对多年题目的梳理笔记会总结出885编程题的几个稳定出题方向线性结构应用这是基础中的基础。数组的查找、旋转、合并链表的增删改查、反转、环检测栈与队列在表达式求值、括号匹配、层次遍历中的应用。这些题目往往看似简单但要求代码健壮、处理所有边界。树与图的基础操作二叉树的各种遍历递归与非递归、重建二叉树、求深度、找最近公共祖先图的表示邻接矩阵/表、DFS/BFS遍历。这部分不仅考代码更考对递归思想的理解。经典算法思想动态规划DP和深度优先搜索DFS是两大重点。DP常考背包问题、路径问题、字符串编辑距离等DFS则多用于排列组合、棋盘类问题。笔记会重点讲解如何识别题目具有“最优子结构”适合DP或“全排列”特征适合DFS/回溯。模拟与字符串处理这类题目描述可能较长需要仔细阅读理解规则然后耐心地用代码模拟整个过程。字符串处理则常涉及翻转、分割、子串查找等需要熟练掌握string的相关操作和算法。2.2 笔记的使用方法论如何让它价值最大化拥有一份好笔记不等于就能考好。关键在于如何使用。我建议采取“三轮学习法”第一轮通读与建立索引。不要一开始就逐题死磕代码。先快速浏览笔记的目录和每个题目的“问题描述”与“核心思路”部分对整体的考点范围和解题套路有一个宏观印象。可以在笔记本或电子文档旁用自己的话标记出哪些是“必须掌握”的哪些是“难点需要反复看”的。第二轮精研与动手复现。这是最花时间也最重要的一步。找一张白纸或打开一个空的代码编辑器遮住笔记中的“代码实现”部分只看题目和思路提示尝试自己独立完成。这个过程一定会卡壳这时再去看笔记中对应的“思路萌芽”和“边界推演”部分看看自己的思考在哪里出现了偏差。最后再对照笔记的代码学习其编码风格、错误处理方式和优化技巧。务必自己把代码敲一遍运行并通过测试用例。第三轮总结与专题突破。在完成一定数量的题目后进行横向总结。例如把所有关于“链表”的题目放在一起总结出处理链表问题的通用技巧如使用哑节点简化边界、快慢指针法。把所有“动态规划”的题目放在一起归纳出状态定义、转移方程的寻找规律。这时笔记就从一个题解集合变成了你自己的知识体系和解题工具箱。注意切忌将笔记当作“答案背记库”。考研编程题千变万化直接碰到原题的概率很低。笔记的价值在于其蕴含的思维过程和代码范式。通过笔记学习如何思考比记住某道题的答案重要一百倍。3. 核心题型深度剖析与实战编码3.1 线性结构链表操作中的“哑节点”艺术链表题是面试和考试中的常客也是容易因边界条件处理不当而失分的地方。其中“哑节点”Dummy Node技巧是简化逻辑、减少出错的利器。3.1.1 场景引入删除链表中指定值的所有节点题目给定一个单链表头节点head和一个整数val删除链表中所有值为val的节点并返回新的头节点。初学者常写的“坑人”代码ListNode* removeElements(ListNode* head, int val) { ListNode* cur head; ListNode* prev nullptr; while (cur ! nullptr) { if (cur-val val) { if (prev nullptr) { // 要删除的是头节点 head cur-next; delete cur; cur head; } else { prev-next cur-next; delete cur; cur prev-next; } } else { prev cur; cur cur-next; } } return head; }这段代码逻辑正确但问题在于对头节点的删除需要特殊处理if (prev nullptr)这使得循环内的逻辑判断变得复杂容易出错。使用哑节点优化后的代码ListNode* removeElements(ListNode* head, int val) { // 创建一个哑节点其next指向原始头节点 ListNode* dummy new ListNode(0); dummy-next head; ListNode* prev dummy; // prev始终指向当前处理节点的前一个节点 ListNode* cur head; while (cur ! nullptr) { if (cur-val val) { // 删除cur节点 prev-next cur-next; delete cur; cur prev-next; // cur更新为prev的下一个继续判断 } else { // 非目标节点prev和cur正常后移 prev cur; cur cur-next; } } // 新的头节点是哑节点的下一个节点 ListNode* newHead dummy-next; delete dummy; // 释放哑节点内存 return newHead; }优化点解析统一化操作引入dummy节点后原链表的头节点head变成了dummy-next。无论要删除的是否是原头节点删除操作都统一为prev-next cur-next。prev永远指向一个实际存在的节点初始是dummy避免了prev为nullptr的特殊判断。逻辑更清晰循环体内的逻辑只剩下“如果当前节点值等于val就删除否则就向后遍历”。思维负担大大减轻。返回值处理最终只需返回dummy-next即使原链表所有节点都被删除返回的也是nullptr完全正确。3.1.2 哑节点的其他妙用合并两个有序链表创建一个哑节点作为结果链表的起始点可以避免判断结果链表头是来自list1还是list2的繁琐逻辑。链表反转在迭代法中哑节点可以作为新链表的头方便进行节点插入。实操心得在涉及链表头部可能发生变化的操作删除、插入、合并时养成优先考虑使用哑节点的习惯。这多写的一行代码能为你节省大量的调试时间并让代码更健壮。这是区分“能做题”和“能做好题”的一个小细节但往往就是阅卷时的加分点。3.2 树形结构非递归遍历的栈模拟二叉树的递归遍历代码简洁但理解其调用栈的过程对于掌握树的结构至关重要。而非递归遍历则是考试的重点因为它显式地使用了栈更能体现对遍历过程的理解。3.2.1 二叉树的中序遍历非递归递归思路是“左-根-右”。非递归实现需要用栈来模拟系统调用栈。vectorint inorderTraversal(TreeNode* root) { vectorint result; stackTreeNode* stk; TreeNode* cur root; while (cur ! nullptr || !stk.empty()) { // 1. 一路向左将途径节点全部入栈 while (cur ! nullptr) { stk.push(cur); cur cur-left; } // 2. 弹出栈顶节点此时它是当前最左的未访问节点 cur stk.top(); stk.pop(); result.push_back(cur-val); // 访问“根” // 3. 转向右子树 cur cur-right; } return result; }关键点解析外层循环条件cur ! nullptr || !stk.empty()。只要当前节点不为空或栈不为空就说明还有节点待处理。这是容易写错的地方。内层循环模拟递归中不断深入左子树的过程直到左子为空。访问时机当从栈中弹出节点时意味着它的左子树已经全部访问完毕按照“左-根-右”的顺序此时应该访问该节点本身。指针转移访问完当前节点后将cur指向其右子树开始下一轮对右子树的“左链入栈”过程。3.2.2 二叉树的前序遍历非递归前序遍历是“根-左-右”。由于访问顺序和入栈顺序有差异实现略有不同。vectorint preorderTraversal(TreeNode* root) { vectorint result; if (root nullptr) return result; stackTreeNode* stk; stk.push(root); while (!stk.empty()) { TreeNode* node stk.top(); stk.pop(); result.push_back(node-val); // 先访问根 // 注意栈是后进先出为了先处理左子树需要先压入右孩子 if (node-right) stk.push(node-right); if (node-left) stk.push(node-left); } return result; }与前序递归的对比递归是“访问根然后递归左再递归右”。这里用栈模拟时我们主动控制了入栈顺序先右后左。这样出栈时就能保证先访问根然后下一个出栈的是左子节点符合前序左子树处理完再处理右子树。注意事项非递归后序遍历是最复杂的通常需要记录节点是否被访问过或者采用“根-右-左”再反转的技巧。在885考试中掌握前序和中序的非递归写法通常就足够了。重点理解栈如何模拟函数调用以及访问节点的时机如何对应不同的遍历顺序。3.3 动态规划从“爬楼梯”到状态转移方程动态规划是区分度很高的考点。很多同学害怕DP觉得状态和方程难以定义。其实可以从最简单的模型入手建立套路。3.3.1 经典入门爬楼梯问题题目每次可以爬1或2个台阶到第n阶有多少种方法状态定义dp[i]表示到达第i阶台阶的方法总数。这是最直观的定义。状态转移方程要想到达第i阶只能从第i-1阶爬1步上来或者从第i-2阶爬2步上来。所以dp[i] dp[i-1] dp[i-2]。初始条件dp[0] 1站在起点算一种方法dp[1] 1。或者从dp[1]1, dp[2]2开始。代码实现int climbStairs(int n) { if (n 2) return n; int dp_i_2 1; // dp[i-2] int dp_i_1 2; // dp[i-1] int dp_i; for (int i 3; i n; i) { dp_i dp_i_1 dp_i_2; dp_i_2 dp_i_1; // 滚动更新 dp_i_1 dp_i; } return dp_i_1; }这里使用了空间优化滚动数组因为dp[i]只依赖于前两个状态。在考试中如果n不大直接用一个vectorint dp(n1)也是完全可以的代码更清晰。3.3.2 进阶思考最小路径和题目给定一个m x n的网格每个格子有非负整数找一条从左上角到右下角的路径使得路径上的数字总和最小。状态定义dp[i][j]表示从(0,0)走到(i,j)位置的最小路径和。状态转移方程要走到(i,j)只能从上方(i-1,j)或左方(i,j-1)过来。所以dp[i][j] grid[i][j] min(dp[i-1][j], dp[i][j-1])。初始条件dp[0][0] grid[0][0]。第一行dp[0][j]只能从左方来所以是累加第一列dp[i][0]只能从上方来也是累加。代码实现原地修改grid作为dp数组int minPathSum(vectorvectorint grid) { int m grid.size(), n grid[0].size(); // 初始化第一行和第一列 for (int j 1; j n; j) grid[0][j] grid[0][j-1]; for (int i 1; i m; i) grid[i][0] grid[i-1][0]; for (int i 1; i m; i) { for (int j 1; j n; j) { grid[i][j] min(grid[i-1][j], grid[i][j-1]); } } return grid[m-1][n-1]; }3.3.3 DP解题的通用步骤定义状态问什么就定义什么。通常是dp[i]或dp[i][j]代表某个子问题的最优解。找出状态转移方程思考如何从已知的小问题答案推导出大问题的答案。这是DP的核心也是最难的一步。多问自己要得到dp[i]需要哪些dp[?]它们之间是什么关系加、减、取最值确定初始条件Base Case最小的、不可再分的问题的解是什么比如dp[0],dp[1]。确定计算顺序确保在计算dp[i]时它所依赖的子状态都已经被计算出来了。通常是顺序遍历。考虑空间优化如果状态转移只依赖于有限的几个前序状态可以用滚动数组压缩空间。实操心得刷DP题不要贪多。找几道经典题目如斐波那契、爬楼梯、背包问题、最长公共子序列、编辑距离反复琢磨直到能闭着眼睛写出状态定义和转移方程。形成肌肉记忆后遇到新题才能举一反三。在考场上如果一时想不出方程可以先尝试用dp[i][j]定义与问题规模相关的状态然后暴力枚举可能的状态转移来源往往能发现规律。4. 编码规范、调试技巧与考场策略4.1 写出让阅卷老师舒服的代码考研编程题通常是人工阅卷或机器阅卷辅以人工复核。清晰的代码结构和良好的习惯能直接提升印象分。4.1.1 命名与格式变量/函数名使用有意义的英文或拼音缩写。i, j, k用于循环下标可以接受但head,cur,prev,dp,result这类名字比a, b, c, p1, p2要好得多。缩进与空格严格遵守缩进通常4个空格。运算符两边加空格如int sum a b;。逗号后加空格。这些细节能让代码块层次清晰。注释在关键算法步骤、复杂的条件判断、或者自己容易混淆的地方写上简短注释。例如// 使用快慢指针检测环、// 处理头节点被删除的情况。但不要每行都注释。4.1.2 函数设计与模块化即使题目只要求写一个函数也要有模块化思维。如果一个函数过长比如超过50行考虑是否可以将其中清晰的逻辑段落抽取成独立的辅助函数。例如在二叉树题中单独写一个getHeight(TreeNode* node)函数来计算高度会使主函数更清晰。4.1.3 输入输出与异常处理明确接口严格按照题目要求的函数签名来写不要擅自修改参数类型或返回值。处理边界在函数开头对输入参数进行合法性判断。如果题目说链表可能为空那么if (head nullptr) return nullptr;这样的代码就是必要的。资源管理在C中如果使用了new动态分配内存如创建哑节点记得在函数返回前delete除非题目要求返回的链表需要保留。这是一个很好的编程习惯展示。4.2 高效调试与自测方法考场没有IDE但掌握一些简单的调试技巧能帮你快速定位问题。4.2.1 静态查错法写完代码后不要急着运行先静下心来“读”一遍自己的代码检查循环边界for (int i 0; i n; i)和for (int i 0; i n; i)差一次迭代后果可能是数组越界。特别注意while循环的终止条件。检查指针操作对于链表题检查指针在nullptr时是否还被解引用-。检查new和delete是否配对。检查递归出口递归函数必须有明确的、能到达的终止条件否则就是无限递归。代入简单用例在脑子里或用笔在纸上代入一个最简单的例子比如链表只有1个或2个节点数组为空或只有一个元素一步步模拟代码执行。4.2.2 设计测试用例在平时练习和考场上如果允许在草稿纸上演算设计几组有针对性的测试用例常规用例验证基本功能。边界用例输入为空、为1、为最大值/最小值。特殊用例链表有环、二叉树是单支、数组有重复元素、数字可能溢出等。破坏性用例故意输入不符合题目假设的数据看你的代码是否健壮虽然考试通常保证输入合法但自己测试时可以考虑。4.3 考场时间分配与策略885考试时间紧张编程题部分需要合理规划。通览全卷拿到试卷先快速浏览所有编程题评估难度和复杂度。先做思路最清晰的建立信心。先思路后代码对于每道题花5-10分钟在草稿纸上理清思路写出伪代码或关键步骤确认边界条件。不要一上来就埋头写代码思路错了写得再工整也是白费。分步实现按照思路先搭建函数框架和主要逻辑确保主干正确。然后再补充细节如输入处理、边界判断。如果时间真的不够写出清晰的核心算法和注释也能争取部分分数。留出检查时间最后至少留出10-15分钟检查。重点检查变量名是否写错、括号是否匹配、循环初值和终值、返回值是否正确。5. 常见“坑点”与易错点实录这里汇总了在练习和考试中极易出错的一些细节堪称“血泪教训”合集。5.1 指针与内存操作空指针解引用这是段错误Segmentation Fault的主要原因。在访问p-val或*p之前必须确保p ! nullptr。尤其是在链表操作中while (p-next)和while (p)的循环条件有本质区别。指针丢失与内存泄漏在链表节点删除或插入时调整指针顺序至关重要。错误的顺序可能导致链表断裂或内存无法释放。例如删除节点时应先prev-next cur-next再delete cur。如果先delete cur就丢失了修改前驱节点指针的机会。野指针指针被delete后其值并非立即变成nullptr除非你主动赋值。继续使用这个指针是未定义行为。良好的习惯是delete p; p nullptr;。5.2 数组与下标下标越界C/C不检查数组越界但这会导致不可预知的结果。牢记数组有效下标范围是[0, size-1]。在循环中特别是使用i-1,i1时要格外小心边界。迭代器失效在使用vector的erase或insert操作后指向被修改位置及其后位置的迭代器、指针、引用都可能失效。如果需要边遍历边删除通常建议使用while循环配合erase的返回值或者从后往前遍历。5.3 递归与栈溢出缺少递归出口递归函数必须有明确的、能在有限步骤内触发的终止条件Base Case。否则会无限递归直到栈空间耗尽Stack Overflow。重复计算在递归解决如斐波那契数列问题时会产生大量的重复计算fib(5)会计算多次fib(2)。这是引入“记忆化搜索”Memoization或直接改用动态规划的重要原因。深度过大对于树形结构如果树退化成链表递归深度可能达到O(n)有可能导致栈溢出。考试中一般数据规模不会这么大但要知道这个风险。5.4 整数运算与溢出中间结果溢出这是最隐蔽的错误之一。例如计算(a b) / 2来求平均值如果a和b都是很大的正数ab可能已经超过int范围而溢出即使结果本身在范围内。安全的写法是a (b - a) / 2。负数取模在C/C中-3 % 2的结果是-1而不是1。如果期望得到非负余数需要手动调整((a % b) b) % b。移位运算优先级1 n 1的意思是1 (n1)而不是(1 n) 1。位运算的优先级低于加减法使用时最好加括号。5.5 标准库使用误区vector的size()方法返回的是size_t类型这是一个无符号整数。如果写for (int i 0; i vec.size() - 1; i)当vec为空时vec.size()-1会变成一个非常大的正数无符号下溢导致循环次数异常。安全的做法是先把size()赋给int变量或者使用i 1 vec.size()作为条件。string的substr(pos, len)第二个参数是长度不是结束位置。s.substr(0, s.find(‘ ‘))是常见的用法但如果find返回string::npos-1直接作为长度参数会导致异常。这份笔记的价值不在于它记录了多少道题而在于它试图呈现解每一道题时的“思维流”和“操作流”。备考的过程就是将这些外部的、他人的经验内化为自己的条件反射和肌肉记忆的过程。我个人的体会是编程能力的提升没有捷径就是“理解-模仿-实践-总结”的循环。当你拿到一道新题能下意识地开始分析数据范围、联想相似题型、在纸上勾勒出状态转移方程或树形遍历路径时你就已经站在了一个更高的起点上。最后再分享一个小心得平时练习时可以有意地限制时间模拟考场压力。一道中等难度的题争取在25-30分钟内完成从读题到AC的全过程。这种时间紧迫感下的决策和编码能力正是考试中最需要的。