余弦の博客

文章介绍了PAT（程序设计能力测试）中关于二叉搜索树和AVL树的几道经典题目，涵盖判断两序列是否生成同一棵二叉搜索树、求AVL树根节点、生成完全二叉搜索树的层次遍历等核心内容，重点讲解了通过中序遍历和完全二叉树性质推导层次遍历的解题思路。

文章整理了PAT（程序设计能力测试）线性结构模块中的四道经典题目，涵盖链表操作与栈的应用。题目包括两个有序链表的合并、一元多项式的乘法与加法、链表分段反转以及栈的弹出序列判断，重点训练链表基本操作、合并同类项、分段反转和栈的模拟推导能力。

本文档是关于“复杂度”主题的题目集，包含三个问题：最大子列和问题（基础题）、最大子序列和问题（考研真题，难度较高）以及二分查找（函数填空题）。每个题目均涉及算法设计与实现，重点考察学生对动态规划、分治思想及边界处理的理解，其中部分测试点易错，需特别注意。

文章系统总结了经典博弈论模型：斐波那契博弈、巴什博弈、威佐夫博弈、尼姆博弈及SG函数理论，并介绍了Green Hackenbush树上删边游戏。核心结论表明，不同博弈的必败态可通过数学规律或SG函数判定，其中斐波那契博弈中总石子数为斐波那契数时先手必败，巴什博弈中当n%(m+1)==0时先手必败，尼姆博弈中异或和为0则先手必败，而SG函数可将任意公平组合游戏转化为等价的Nim博弈进行求解。

本文是作者在学习浙大《数据结构》MOOC课程过程中，系统整理和记录的PTA题目集，涵盖了线性结构、二叉树、二叉搜索树、图、排序、散列查找等核心内容，每部分均包含题目解析与代码实现，结合C++和C语言编写，部分使用STL简化操作。文章以周为单位详细梳理了学习进度与解题思路，体现了数据结构知识的系统学习与实践过程。

文章介绍了最小生成树问题的两种经典算法：Kruskal算法和Prim算法。Kruskal算法通过按边权排序并使用并查集判断连通性来构造最小生成树，而Prim算法从一个节点出发，逐步扩展生成树，适用于稠密图。文章结合多道经典题目（如HDU1863、1879、1875和洛谷P3366）说明了这两种算法的应用场景与实现方法。

文章总结了2020年蓝桥杯模拟省赛的题目及解题思路，涵盖填空题和9道编程题，涉及组合数学、字符串处理、摆动序列、螺旋矩阵、圆面积最大化、最小生成树等知识点，其中部分题目使用了递归、记忆化搜索或图论算法，最后一题因是现场学习Prim算法而未完全确认正确性。

文章系统介绍了动态规划（动规）的基本思想与解题方法，包括从递归到动规的转化、动规的五步解题思路（问题分解、状态定义、值的确定、边界状态、状态转移方程），以及动规适用问题的特征（最优子结构性质和无后效性）。通过四个经典例题（数字三角形、神奇的口袋、最长公共子序列、最长上升子序列）详细说明了如何建立状态、设计转移方程并求解最优解。

文章系统介绍了图的基本概念、表示方法（邻接矩阵与邻接表）、图的遍历（DFS与BFS）、图的连通性与路径问题，重点讲解了无权图和有权图的单源最短路径算法（基于BFS和Dijkstra），以及最小生成树的构造方法（Kruskal与Prim算法）。内容从理论到实践，涵盖了图的建模、遍历、最短路径和最小生成树的核心算法与实现思路。

文章介绍了堆和哈夫曼树的基本概念与操作，以及并查集的简要说明。堆是一种基于完全二叉树的数组结构，支持插入、删除和建堆操作，最大堆可通过逐层调整在O(N)时间内构建；哈夫曼树是带权路径长度最小的二叉树，通过最小堆实现节点合并，用于高效编码，如哈夫曼编码，满足前缀码特性以实现压缩存储。