2026年NOIP普及组初赛算法复杂度分析基础练习

2026年NOIP普及组初赛算法复杂度分析基础练习一、单选题（共5题，每题3分）1.题目：以下算法中，时间复杂度最接近O(nlogn)的是？A.冒泡排序B.快速排序C.插入排序D.选择排序2.题目：对于一个长度为n的数组，以下哪个操作的时间复杂度是O(1)？A.查找第k小的元素B.插入一个新元素C.删除最后一个元素D.计算所有元素的和3.题目：若一个算法的时间复杂度为T(n)=3n²+2n+1，当n趋向无穷时，其渐进时间复杂度为？A.O(n²)B.O(n)C.O(logn)D.O(1)4.题目：以下数据结构中，删除第一个元素的时间复杂度一定是O(1)的是？A.链表B.堆C.队列D.二叉搜索树5.题目：哈希表在理想情况下，插入和查找操作的时间复杂度为？A.O(n)B.O(logn)C.O(1)D.O(n²)二、填空题（共5题，每题4分）1.题目：计算1+2+3+...+n的和，以下时间复杂度为O(1)的算法是________。2.题目：对一个长度为n的有序数组进行二分查找，其时间复杂度为________。3.题目：堆排序的时间复杂度为________。4.题目：若一个算法的时间复杂度为T(n)=5n³+100n²+10n，其最坏情况下的时间复杂度为________。5.题目：在链表中删除一个已知位置的节点，其时间复杂度为________。三、简答题（共3题，每题7分）1.题目：解释什么是“渐进时间复杂度”，并举例说明为什么有时候需要忽略常数项和低阶项。2.题目：比较快速排序和归并排序的时间复杂度，并说明它们在实际应用中的优缺点。3.题目：解释哈希表的冲突解决方法，并说明开放地址法和链地址法的区别。四、计算题（共2题，每题10分）1.题目：给定一个递归函数：deffib(n):ifn<=2:return1else:returnfib(n-1)+fib(n-2)请分析该函数的时间复杂度，并给出改进后的时间复杂度。2.题目：对于以下代码，请分别计算其时间复杂度：foriinrange(n):forjinrange(i):print(i,j)五、编程题（共2题，每题10分）1.题目：编写一个函数，计算一个链表中所有节点的值之和。链表节点的定义如下：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=next要求：时间复杂度为O(n)，空间复杂度为O(1)。2.题目：编写一个函数，实现二分查找。输入为一个有序数组和一个目标值，输出为目标值的索引（若不存在则返回-1）。要求：时间复杂度为O(logn)。答案与解析一、单选题1.答案：B解析：快速排序的平均时间复杂度为O(nlogn)，而其他排序算法的时间复杂度较高（如冒泡排序和插入排序为O(n²)，选择排序为O(n²)）。2.答案：C解析：在数组末尾删除元素可以直接修改末尾指针，时间复杂度为O(1)。其他操作（如查找、插入）通常需要O(n)或O(logn)的时间。3.答案：A解析：当n趋向无穷时，高阶项起主导作用，因此T(n)=O(n²)。4.答案：A解析：链表可以通过修改前驱节点的next指针来删除第一个元素，时间复杂度为O(1)。其他数据结构（如堆、树）通常需要O(logn)或O(n)的时间。5.答案：C解析：在理想情况下（无冲突），哈希表的插入和查找操作时间复杂度为O(1)。二、填空题1.答案：直接计算公式解析：1+2+3+...+n=n(n+1)/2，直接计算的时间复杂度为O(1)。2.答案：O(logn)解析：二分查找每次将搜索范围减半，时间复杂度为O(logn)。3.答案：O(nlogn)解析：堆排序包括建堆和多次堆调整，总时间复杂度为O(nlogn)。4.答案：O(n³)解析：最高阶项为n³，因此最坏情况下的时间复杂度为O(n³)。5.答案：O(n)解析：删除节点需要遍历链表找到前驱节点，时间复杂度为O(n)。三、简答题1.答案：渐进时间复杂度用于描述算法运行时间随输入规模增长的变化趋势，忽略常数项和低阶项的原因是：-常数项对大输入规模影响较小（如O(100n)≈O(n)）。-低阶项在大规模输入时被高阶项主导（如O(n²+n)≈O(n²)）。举例：T(n)=5n³+100n²+10n，其渐进复杂度为O(n³)，因为n³是最高阶项。2.答案：-时间复杂度：-快速排序：平均O(nlogn)，最坏O(n²)。-归并排序：稳定O(nlogn)。-优点：-快速排序：常数项较小，通常比归并排序快。-归并排序：稳定性好，适合链表排序。-缺点：-快速排序：最坏情况性能差，需要优化。-归并排序：需要额外空间（O(n)）。3.答案：-冲突解决方法：-开放地址法：当哈希冲突时，线性探测（顺序查找下一个空槽）。-链地址法：每个槽位指向一个链表，冲突元素加入链表。-区别：-开放地址法：所有元素存储在哈希表数组中，空间利用率高。-链地址法：使用链表处理冲突，适合大量冲突场景。四、计算题1.答案：-原始函数时间复杂度：递归树深度为n，每层节点数近似为2^k，总复杂度O(2^n)，实际非常低效。-改进方法：使用动态规划存储子问题结果，时间复杂度降为O(n)。2.答案：-外层循环：n次。-内层循环：i次（从0到i-1）。-总次数：1+2+3+...+n=n(n+1)/2。-时间复杂度：O(n²)。五、编程题1.答案：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefsum_list(head):total=0whilehead:total+=head.valhead=head.nextreturntotal2.答案：pythondefbinary_search(arr,target):left,right=0,len(arr)-1whileleft<=right:mid=(left