余弦の博客

文章介绍了三道排序相关的编程题，涵盖算法思维与细节处理： 1. 10-Sort 4“工作经历排序”考察最高效的排序方法； 2. 10-Sort 5“PAT判题排名”要求根据提交得分生成排名，处理相同分数时按解题数和ID排序，注意编译失败的特殊情况； 3. 10-Sort 6“通过交换(0,i)实现排序”需分析排列中的循环结构，根据0的位置计算最小交换次数，分为两种情况分别求解。

本文介绍了三个关于排序算法的练习题，主要考察插入排序和归并排序的识别，以及插入排序与堆排序的区分。通过对比初始序列经过若干次排序后的结果，判断使用的是插入排序还是归并排序，或插入排序与堆排序。文章强调使用迭代版本的归并排序和堆排序来简化问题处理。

本文介绍了归并排序的非递归版本，指出其额外空间复杂度最低为O(N)，相较于递归版本的高时空开销，非递归版本在空间使用上更为高效。文章通过教授陈越的MOOC课程进行了清晰讲解，并直接提供了带注释的代码。

文章介绍了图的拓扑排序（Topological Sort）及其应用，包括AOV网络和AOE网络中的关键路径问题，以及常见排序算法如冒泡排序、插入排序和希尔排序的原理、优缺点及效率分析。

文章介绍了图论中三个经典的题目：村庄高速公路连接问题（最小生成树）、项目工期计算（拓扑排序）和关键活动识别。前两题分别使用Kruskal算法和拓扑排序求解，第三题在此基础上增加最晚完成时间与松弛时间计算，判断关键路径。文章强调代码复杂度较高，建议根据时间安排尝试，且指出在提交时曾因代码交换导致错误。

文章介绍了三道图论相关的算法题：第一题通过Floyd算法求最短路径，找出使最大变换长度最小的动物；第二题同样使用Floyd算法求最短跳跃路径，并记录路径中最小首跳的方案；第三题是Dijkstra算法的变种，用于在多条最短路径中选择总成本最小的路径。三题均涉及图的最短路径计算，难度由基础到进阶。

本文介绍了三个图论问题：第一个是输出图中所有连通集的DFS和BFS结果，第二个是通过图搜索帮助拯救詹姆斯·邦德，第三个是计算社交网络中每个节点满足“六度分隔”理论的比例。这些问题从基础到进阶，涵盖了图的遍历与连通性分析。

本文介绍了三道数据结构与算法题目：第05-Tree 7题要求根据最小堆的插入序列和索引，输出从指定节点到根节点的路径；第05-Tree 8题基于并查集实现计算机网络连接判断，支持路径压缩优化；第05-Tree 9题考察Huffman编码的最优性，通过构建Huffman树计算最优平均码长，并验证学生提供的编码是否为前缀码且长度最优。

本文介绍了四道关于二叉搜索树和AVL树的典型题目：判断不同插入序列是否生成相同的二叉搜索树、求AVL树的根节点、构造完全二叉搜索树的层序遍历序列，以及实现二叉搜索树的基本操作。文章提供了问题分析、解题思路和代码实现，并强调了理解二叉搜索树性质和递归构造方法的重要性。

本文介绍了四道关于线性结构的C语言编程题，涵盖链表合并、多项式乘法与加法、链表逆序以及栈的弹出序列判断。题目从基础操作入手，训练链表和栈的核心算法，强调在实际操作中对边界条件和逻辑判断的处理，是数据结构学习中的典型练习。