2026年35界noi试题答案

2026年35界noi试题答案

一、单项选择题（10题，每题2分）1.以下哪种数据结构不支持快速随机访问？A.数组B.单链表C.哈希表D.二叉搜索树2.在C++标准库中，vector容器的底层实现主要基于哪种数据结构？A.数组B.双向链表C.栈D.队列3.以下算法中，不属于贪心算法典型应用的是？A.哈夫曼编码B.最短路径（Dijkstra）C.活动选择问题D.最小生成树（Kruskal）4.对于一个具有n个顶点的无向图，使用邻接矩阵存储时，空间复杂度为？A.O(n)B.O(n²)C.O(nlogn)D.O(n+e)，其中e为边数5.以下哪种排序算法在排序过程中不需要额外空间（除了常数空间）？A.归并排序B.快速排序C.堆排序D.冒泡排序6.在动态规划中，“状态定义”的核心原则是？A.状态必须包含所有可能的决策B.状态应尽可能小，以减少冗余C.状态必须能通过转移方程递推得到D.状态必须是数值型的7.以下关于图的遍历说法错误的是？A.BFS适合寻找最短路径（无权图）B.DFS可以用于检测图中是否有环C.无向图的DFS会将所有连通分量遍历D.拓扑排序仅适用于有向无环图（DAG）8.以下哪个问题最适合使用分治算法解决？A.最短路径问题B.排序问题C.大整数乘法D.并查集操作9.在算法复杂度分析中，“大O符号”的作用是？A.精确计算算法执行时间B.描述算法时间复杂度的上界C.比较不同算法的绝对效率D.仅用于递归算法的复杂度分析10.以下关于哈希表的描述错误的是？A.哈希表的平均查找时间复杂度通常为O(1)B.链地址法是解决哈希冲突的常用方法C.哈希表的空间复杂度总是高于数组D.哈希函数的设计直接影响哈希表的性能二、填空题（10题，每题2分）1.冒泡排序在最坏情况下的时间复杂度是______，此时需要进行______次元素比较。2.堆排序的基本思想是利用______的性质，每次从堆顶取出最大（或最小）元素后，调整堆结构以保持堆的性质。3.在动态规划中，“最长递增子序列（LIS）”问题的状态转移方程通常定义为dp[i]=max(dp[j]+1)，其中j的范围是______。4.图的“拓扑排序”是对有向无环图（DAG）的顶点进行排序，使得对于每一条有向边(u,v)，顶点u在排序中都出现在顶点v的______。5.哈夫曼编码中，每个字符的编码长度与其出现频率成______（正/负）相关，这种编码方式的平均长度通常是______（最小/最大）的。6.并查集（Union-Find）数据结构中，主要操作是______和______，其优化方法包括路径压缩和______。7.KMP算法的核心是通过预处理字符串得到______数组，用于在模式匹配时避免不必要的字符比较，其时间复杂度为______。8.对于n个元素的完全二叉树，其高度h满足的关系是______（用对数表示），叶子节点的数量最多为______。9.在“最大公约数（GCD）”的计算中，欧几里得算法（辗转相除法）的时间复杂度主要取决于______，其递归形式的终止条件是______。10.在Python中，列表（list）的append操作的时间复杂度通常为______，而插入操作（insert(pos,x)）的时间复杂度为______。三、判断题（10题，每题2分）1.时间复杂度为O(n)的算法一定比时间复杂度为O(logn)的算法快。（）2.归并排序是一种稳定的排序算法，且其空间复杂度为O(n)。（）3.深度优先搜索（DFS）在遍历图时，一定会访问所有连通分量的顶点。（）4.动态规划问题中，只要状态定义正确，状态转移方程一定能直接通过递推得到最优解。（）5.哈希表在处理大量数据时，其查找效率总是高于其他数据结构。（）6.邻接表存储图时，对于边数较少的图，其空间利用率高于邻接矩阵。（）7.快速排序算法的平均时间复杂度是O(nlogn)，而最坏情况下是O(n²)，因此实际应用中通常会先随机化选择基准元素。（）8.当一个问题的最优子结构和重叠子问题同时满足时，动态规划是解决该问题的唯一方法。（）9.二叉树的中序遍历结果为左子树、根、右子树，因此可以通过中序和后序遍历序列唯一确定一棵二叉树。（）10.贪心算法在任何情况下都能得到问题的最优解，尤其是在组合优化问题中。（）四、简答题（4题，每题5分）1.请简述“最小生成树（MST）”问题的Kruskal算法的核心步骤，并说明其时间复杂度主要由哪部分决定。2.解释“动态规划（DP）”与“记忆化搜索”在解决递归问题时的区别与联系，并举例说明在什么场景下记忆化搜索更高效。3.分析“单源最短路径”问题中，当图中存在负权边但无负环时，Dijkstra算法和Bellman-Ford算法的适用性及各自的优缺点。4.讨论“数据结构选择”的基本原则，并举例说明在以下场景中应选择的合适数据结构：（1）频繁插入和删除操作的线性序列；（2）需要快速查找和插入的无序集合；（3）实现优先队列功能。五、讨论题（4题，每题5分）1.请讨论“二分查找”算法的适用条件和局限性，并设计一个能够处理“重复元素”的二分查找变种算法，使其能返回第一个等于目标值的元素位置，并分析其时间复杂度。2.在解决“区间覆盖”问题时，假设有n个区间，每个区间有开始时间和结束时间，目标是选择最少数量的区间以覆盖整个时间范围（例如从0到T）。请分析贪心算法（按结束时间排序选择）的正确性，并讨论是否存在其他算法（如动态规划）的适用性，比较两者的时间复杂度和空间复杂度。3.考虑一个“任务调度”问题：有n个任务，每个任务有执行时间和截止时间，目标是判断是否能在截止时间前完成所有任务。请讨论使用贪心算法（按截止时间排序或按执行时间排序）的优劣，并说明该问题是否存在多项式时间算法。4.对于“0-1背包问题”，当物品的重量和价值满足什么条件时，贪心算法（按单位价值排序）能得到最优解？请详细证明贪心选择性质，并举例说明当单位价值排序无法得到最优解时，动态规划算法的必要性。答案和解析一、单项选择题1.B解析：单链表通过指针顺序访问，无法随机访问；数组、哈希表、二叉搜索树均支持随机访问。2.A解析：vector是动态数组，基于数组实现，支持随机访问和高效尾插。3.B解析：Dijkstra算法基于贪心，不属于典型贪心算法，哈夫曼编码、活动选择、Kruskal算法均为贪心。4.B解析：邻接矩阵需n×n空间，n为顶点数，边数e不影响空间复杂度。5.C解析：堆排序仅需O(1)额外空间（原地排序），归并排序需O(n)，快速排序平均O(logn)，冒泡排序O(1)但时间差。6.B解析：状态定义应最小化冗余，需包含子问题信息，转移方程需结合子问题结果。7.D解析：拓扑排序仅适用于DAG，而DFS/BFS可检测环，但DFS/BFS遍历所有连通分量顶点。8.C解析：分治算法将问题分解为独立子问题（如大整数乘法），排序、最短路径、并查集非分治典型场景。9.B解析：大O符号描述时间复杂度上界，非精确值，比较算法效率需统一规模，递归算法复杂度需用递归树或主定理。10.C解析：哈希表空间复杂度取决于负载因子，非总是高于数组，如小数据量数组更优。二、填空题1.O(n²)，n(n-1)/2解析：最坏情况为逆序数组，比较次数为n(n-1)/2。2.堆解析：堆排序利用完全二叉树的堆性质，每次调整堆顶元素。3.0≤j<i且nums[j]<nums[i]解析：LIS中dp[i]表示前i个元素的最长子序列，j需遍历所有小于当前元素的位置。4.前面解析：拓扑排序要求所有有向边的起点在终点之前。5.负，最小解析：频率越高编码越短，平均长度最小。6.查找（find），合并（union），按秩合并解析：并查集核心操作，按秩合并优化合并效率。7.next，O(n+m)解析：KMP预处理next数组需O(m)，匹配需O(n)，总O(n+m)。8.h=floor(log₂n)+1，2^(h-1)解析：完全二叉树高度h=⌊log₂n⌋+1，叶子最多为2^(h-1)。9.两个数的大小，其中一个数为0解析：欧几里得算法复杂度取决于输入数的大小，终止条件为余数为0。10.O(1)，O(n)解析：Pythonlistappend为尾插，时间O(1)；insert需移动元素，时间O(n)。三、判断题1.×解析：n=100时O(n)=100，O(logn)≈7，前者更快；但n=1000时O(n)=1000，O(logn)≈10，后者更快。2.√解析：归并排序稳定，空间复杂度O(n)（需临时数组）。3.√解析：DFS通过递归或栈实现，可遍历所有连通分量。4.×解析：动态规划需结合最优子结构和重叠子问题，状态转移需验证正确性。5.×解析：哈希表在负载因子过高时冲突增加，效率下降，小规模数据数组更优。6.√解析：边数少的图邻接表仅存储有效边，空间利用率高于邻接矩阵的n²。7.√解析：随机化基准元素可避免已排序数组的最坏情况，提升平均效率。8.×解析：动态规划非唯一方法，如记忆化搜索也可解决重叠子问题。9.√解析：中序+后序遍历可通过后序确定根，中序划分左右子树，唯一确定二叉树。10.×解析：贪心算法仅在满足贪心选择性质时有效，组合优化问题中可能无法得最优解。四、简答题1.Kruskal算法核心步骤：①初始化每个顶点为独立集合；②按边权从小到大排序；③依次选边，若两端点不同集则合并，直到连通。时间复杂度主要由边排序决定，为O(eloge)，e为边数。2.动态规划自底向上，记忆化搜索自顶向下。动态规划需先定义状态和转移方程，适合子问题独立的场景；记忆化搜索通过递归+缓存避免重复计算，适合树状结构或状态转移复杂的问题（如树的最长路径）。3.Dijkstra不适用负权边（无法松弛到最优），时间O(mlogn)；Bellman-Ford可处理负权边，需n-1次迭代，时间O(nm)；SPFA（队列优化）是Bellman-Ford变种，效率更高但可能退化。4.基本原则：操作频率、数据访问模式、规模。①频繁插入删除用双向链表（如Pythondeque）；②快速查找用哈希表（如Pythondict）；③优先队列用堆（如Pythonheapq）。五、讨论题1.二分查找要求数组有序，重复元素变种需返回第一个位置：初始化low=0,high=n-1，若mid=target，令high=mid缩小范围，否则移动low/high。时间复杂度O(logn)，需确保数组存在目标元素或返回-1。2.贪心按结束时间排序：正确性证明，每次