2026年信息学奥林匹克算法设计竞赛章程试题及答案

2026年信息学奥林匹克算法设计竞赛章程试题及答案考试时长：120分钟满分：100分一、单选题（总共10题，每题2分，总分20分）1.在算法设计中，以下哪种方法不属于动态规划的应用场景？A.最长公共子序列问题B.背包问题C.最小生成树问题D.0-1背包问题2.快速排序的平均时间复杂度为？A.O(n²)B.O(nlogn)C.O(logn)D.O(n)3.在图论中，以下哪种算法用于求解单源最短路径问题？A.Dijkstra算法B.Floyd-Warshall算法C.Prim算法D.Kruskal算法4.以下哪种数据结构适合实现栈？A.链表B.哈希表C.堆D.数组5.在二分查找中，前提条件是？A.数据必须有序B.数据必须无序C.数据必须递减D.数据必须递增6.以下哪种算法属于贪心算法？A.快速排序B.Dijkstra算法C.拓扑排序D.二分查找7.在树结构中，一个节点的度是指？A.子节点的数量B.父节点的数量C.边的数量D.根节点的数量8.以下哪种排序算法不稳定？A.插入排序B.冒泡排序C.快速排序D.堆排序9.在哈希表中，冲突解决方法不包括？A.开放寻址法B.链地址法C.二分查找法D.哈希函数改进法10.以下哪种算法用于求解拓扑排序？A.深度优先搜索B.广度优先搜索C.Dijkstra算法D.Floyd-Warshall算法二、填空题（总共10题，每题2分，总分20分）1.算法的______复杂度衡量算法执行时间随输入规模增长的变化趋势。2.在快速排序中，选择______作为枢轴可以提高算法的稳定性。3.图的______表示图中顶点之间的连接关系。4.栈的______操作允许元素先进后出。5.二分查找的时间复杂度为______。6.贪心算法的核心思想是每一步都选择______的解。7.树的______是指根节点到叶节点的最长路径长度。8.堆排序是一种基于______结构的排序算法。9.哈希表的______是指键值到存储位置的映射函数。10.拓扑排序适用于______的求解。三、判断题（总共10题，每题2分，总分20分）1.动态规划适用于解决具有重叠子问题的最优问题。（√）2.快速排序在最坏情况下时间复杂度为O(n²)。（√）3.Floyd-Warshall算法可以求解所有顶点对的最短路径。（√）4.栈和队列都是线性数据结构。（√）5.二分查找适用于无序数据。（×）6.贪心算法一定能得到最优解。（×）7.树的度是指树中节点的最大度数。（×）8.堆排序是一种稳定的排序算法。（×）9.哈希表的冲突解决方法只有链地址法。（×）10.拓扑排序适用于有向无环图。（√）四、简答题（总共3题，每题4分，总分12分）1.简述动态规划与贪心算法的区别。2.解释二分查找算法的原理及其适用条件。3.描述图论中Dijkstra算法的基本思想。五、应用题（总共2题，每题9分，总分18分）1.给定一个背包容量为50，物品重量分别为[10,20,30]，价值分别为[60,100,120]。请用动态规划求解最大价值。2.已知一个有向图如下，请用Dijkstra算法求解从顶点A到顶点D的最短路径。```A→B(5),A→C(3),B→D(6),C→D(2)```【标准答案及解析】一、单选题答案1.C2.B3.A4.D5.A6.B7.A8.C9.C10.A解析：1.最小生成树问题通常用Prim或Kruskal算法解决，不属于动态规划。2.快速排序平均时间复杂度为O(nlogn)，最坏情况为O(n²)。3.Dijkstra算法用于单源最短路径。4.数组是栈的常见实现方式。5.二分查找要求数据有序。6.Dijkstra算法是贪心算法的典型应用。7.节点的度指子节点数量。8.快速排序不稳定。9.二分查找法不是哈希表冲突解决方法。10.深度优先搜索可用于拓扑排序。二、填空题答案1.时间2.中值3.邻接矩阵4.入栈5.O(logn)6.局部最优7.高度8.二叉堆9.哈希函数10.有向无环图三、判断题答案1.√2.√3.√4.√5.×6.×7.×8.×9.×10.√解析：5.二分查找要求有序数据。6.贪心算法不保证最优解。7.树的度指节点的子节点数量。8.堆排序不稳定。9.哈希表冲突解决方法还包括开放寻址法等。四、简答题解析1.动态规划通过存储子问题解避免重复计算，适用于有重叠子问题；贪心算法每步选择局部最优解，不保证全局最优。2.二分查找通过不断缩小查找范围，适用于有序数据，时间复杂度为O(logn)。3.Dijkstra算法通过贪心策略，逐步更新最短路径估计值，适用于带权无负权边图。五、应用题解析1.动态规划求解背包问题：设dp[i][j]为前i件物品在容量j下的最大价值。状态转移方程：dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])。结果：dp[3][50]=220（选物品2和3）。2.Dijkstra算法求解最短路径：初始化：dist[A]=0,dist[B]=∞,dist[C]=∞,dist[D]=∞。更新过程：-首选A→C(3)，dist[C]=3；-再选C→D(2)，dist[D]=5；最短路径：A→C→D，长度5。