2026年noi线上测试题及答案

2026年noi线上测试题及答案

一、单项选择题(10题，每题2分)1.在无向图G中，若顶点u与顶点v之间存在路径，则称u和v是连通的。若图G中任意两个顶点都是连通的，则称G为？A)完全图B)连通图C)强连通图D)二分图2.解决哈希冲突的开放定址法中，探测序列为H(key),H(key)+1,H(key)+2,...,H(key)+k(k<m)的方法是？A)线性探测法B)平方探测法C)双散列法D)链地址法3.已知一棵二叉树的先序遍历序列为ABDECF，中序遍历序列为DBEAFC，则后序遍历序列是？A)DEBFCAB)DEBFCC)DBEFCAD)DEFBCA4.下列排序算法中，最坏时间复杂度为O(nlogn)且是稳定排序的是？A)快速排序B)堆排序C)归并排序D)希尔排序5.使用动态规划算法求解的问题通常需要具备的性质是？A)最优子结构B)贪心选择性质C)无后效性D)A和C6.在图的广度优先搜索(BFS)中，通常使用的辅助数据结构是？A)栈(Stack)B)队列(Queue)C)优先队列(PriorityQueue)D)集合(Set)7.一棵高度为5的满二叉树(根结点高度为1)，其结点总数为？A)15B)16C)31D)328.在算法分析中，记号Θ表示？A)渐进上界B)非渐进紧确上界C)渐进紧确界D)渐进下界9.下列数据结构中，插入和删除操作在表的两端都可以高效进行的是？A)栈(Stack)B)队列(Queue)C)双端队列(Deque)D)优先队列(PriorityQueue)10.对于长度为n的无序数组，查找最大元素的最小时间复杂度是？A)O(1)B)O(logn)C)O(n)D)O(nlogn)二、填空题(10题，每题2分)1.在Dijkstra算法求解单源最短路径时，若使用二叉堆实现优先队列，其时间复杂度为________。2.快速排序在平均情况下的时间复杂度是________，在最坏情况下的时间复杂度是________。3.一个包含n个元素的二叉堆(最小堆)，其插入(Insert)操作的时间复杂度是________。4.在深度优先搜索(DFS)递归实现中，通常需要________数据结构来标记已访问过的结点。5.表达式`(a+b)(c-d/e)`的后缀表达式(逆波兰式)是________。6.一个具有n个顶点的无向完全图，其边的数目是________。7.分治法的三个基本步骤是分解、________和合并。8.假设使用KMP算法在文本串T(长度为n)中查找模式串P(长度为m)，该算法的时间复杂度是________。9.将一个递归算法转换为非递归算法时，通常需要显式地使用________数据结构来模拟递归调用栈。10.AVL树是一种________二叉树，通过旋转操作保持其平衡因子在________范围内。三、判断题(10题，每题2分)1.()背包问题总是可以用贪心算法得到最优解。2.()归并排序算法在任何情况下都需要额外的O(n)辅助空间。3.()图的邻接矩阵表示法对于稀疏图的空间利用率通常高于邻接表表示法。4.()深度优先搜索(DFS)可以用于检测有向图中的环。5.()最小生成树(MST)是唯一的。6.()二分查找算法可以应用于任何有序数组。7.()若一个问题是NP完全问题，则它一定可以在多项式时间内验证一个解的正确性。8.()拓扑排序只适用于有向无环图(DAG)。9.()所有递归算法都可以很容易地改写为非递归的迭代算法。10.()在哈希表中，装载因子(LoadFactor)等于表中已存储的键值对数目除以数组的长度。四、简答题(4题，每题5分)1.简述分治法和动态规划的主要区别。2.解释什么是栈溢出(StackOverflow)及其在递归程序中常见的原因。3.简述二叉搜索树(BST)的基本性质以及其中序遍历结果的特点。4.描述Dijkstra算法求解单源最短路径的基本思想及其限制条件（不能处理哪些图）。五、讨论题(4题，每题5分)1.讨论在算法设计中，时间复杂度和空间复杂度之间通常存在的权衡(Trade-off)，并举例说明。2.讨论贪心算法和动态规划算法在解决最优化问题上的异同点。3.阐述哈希表(HashTable)的工作原理，并分析其查找、插入和删除操作的平均时间复杂度及最坏时间复杂度。4.比较图的邻接矩阵和邻接表两种存储结构的优缺点及其适用场景。==========答案与解析==========一、单项选择题答案1.B)连通图2.A)线性探测法3.A)DEBFCA4.C)归并排序5.D)A和C(最优子结构和无后效性)6.B)队列(Queue)7.C)31(2^5-1=31)8.C)渐进紧确界9.C)双端队列(Deque)10.C)O(n)(必须扫描所有元素才能确定最大值)二、填空题答案1.O((V+E)logV)2.O(nlogn),O(n²)3.O(logn)4.访问标记数组(VisitedArray/MarkArray)5.ab+cde/-6.n(n-1)/27.解决(Conquer)8.O(n+m)9.栈(Stack)10.自平衡二叉搜索/平衡的,[-1,0,1]或-1,0,1(平衡因子绝对值不超过1)三、判断题答案1.×(只有部分背包问题可以用贪心)2.√(标准的归并排序需要O(n)辅助空间合并)3.×(邻接矩阵空间O(V²),邻接表空间O(V+E),稀疏图E远小于V²,邻接表更优)4.√(DFS过程中遇到后向边(BackEdge)则说明存在环)5.×(当存在权重相等的边时，MST可能不唯一)6.×(必须是在支持随机访问的有序数组上)7.√(NP完全问题是NP问题，NP问题定义即是解能在多项式时间内被验证的问题)8.√(拓扑排序要求图无环)9.×(虽然理论上可行，但一些复杂的递归逻辑改写迭代非常困难)10.√(装载因子定义α=n/m,n为元素数，m为哈希表长度)四、简答题答案1.分治与动态规划区别：分治法将问题分解为相互独立的子问题，递归求解后合并结果，子问题可能被重复计算。动态规划将问题分解为相互重叠的子问题，通过表格存储子问题解避免重复计算，适用于具有最优子结构和重叠子问题性质的问题。分治通常自顶向下递归，动态规划常自底向上或记忆化递归。2.栈溢出及原因：栈溢出指程序执行时使用的栈内存空间超过了系统分配的限制导致程序崩溃。在递归程序中常见原因：递归深度过大（如未优化的树遍历、斐波那契递归）、递归缺少有效终止条件（无限递归）、递归函数参数或局部变量占用栈空间过多。每次递归调用都会在栈上压入新的栈帧，累积超过限制即溢出。3.BST性质及中序特点：二叉搜索树(BST)性质：左子树所有节点值小于根节点值；右子树所有节点值大于根节点值；左右子树也分别是BST。中序遍历BST的结果是一个按节点值升序排列的有序序列。4.Dijkstra算法思想与限制：Dijkstra算法基于贪心策略，从源点开始，逐步确定到达所有其他顶点的最短路径。它维护一个距离数组，每次从未确定最短路径的顶点中选择距离最小的顶点，松弛其邻接边。限制：不能处理图中存在负权边的情况，因为贪心选择在此情况下无法保证得到全局最优解（可能导致错误结果）。要求所有边的权重非负。五、讨论题答案1.时空复杂度权衡：提高算法效率常常需要在时间和空间之间权衡。优化时间（提升速度）可能消耗更多内存（空间），反之亦然。例如，查表（预处理、缓存结果）能显著降低时间复杂度（如从O(n)到O(1)），但需存储额外数据（空间开销）。动态规划用空间（表格）存储子问题解避免重复计算，牺牲空间换取时间。预处理数组（如前缀和）使后续查询更快。有时选择空间效率高的数据结构（如链表）操作耗时更多（O(n)查找）。2.贪心与动态规划异同：相同点：都用于求解最优化问题，都通过构造子问题的最优解来寻求原问题的最优解（或近似解）。不同点：贪心算法每一步基于当前状态做出看似最优的选择（贪心选择），一旦选择不再回退，通常高效但未必能得到全局最优解（需问题具有贪心选择性质）。动态规划通过解决子问题并组合最优解，考虑所有可能的选择，通常能得到全局最优解，但常涉及填表操作，时间和空间开销更大。贪心“一往无前”，动态规划“瞻前顾后”。3.哈希表原理与复杂度：原理：通过哈希函数将键映射到数组的特定位置（桶）存储值。处理冲突方法：开放寻址（线性/平方探测）或链地址（链表/树）。查找：平均O(1)（假设良好哈希函数、合适装载因子），最坏O(n)（所有键冲突到一个桶，链地址法）；插入/删除：平均O(1)，最坏O(n)（同上）。链地址法最坏情况取决于桶内数据结构（链表O(n)，树O(logn)）。控制装载因子（通常<0.7）是保证平均性能的关键。扩容(rehashing)操作耗费O(n)。4.邻接矩阵与邻接表比较：邻接矩阵：二维数组`adjMatrix[u][v]`表示边(u,v)。优点：检查任意两点间是否有边极快O(1)；易于实现部分算法（如Floyd-Warshall）。缺点：空间复杂度高O(V²)；稀疏图空