GESP-C++五级 题库
快速排序算法的时间复杂度与输入是否有序无关,始终稳定为 O(n log n)。( )
快速排序的 平均时间复杂度为 O(nlog?n),但最坏情况下退化为 O(n^2)。
其性能与输入数据是否有序及 pivot 选择策略密切相关。
归并排序算法的时间复杂度与输入是否有序无关,始终稳定为 O(n log n)。( )
归并排序无论输入数据是否有序,归并排序的时间复杂度 始终为 O(nlog?n)。这是因为:
分解阶段:将数组递归地分成两半,直到子数组长度为 1,共需 log?n 层递归。
合并阶段:每一层需要 O(n) 的时间合并两个有序子数组。
总时间复杂度:递归深度 log?n × 每层 O(n)) = O(nlog?n)。
二分查找适用于对无序数组和有序数组的查找。( )
二分查找(Binary Search)是一种高效的查找算法,其前提条件:输入数组 必须是有序的。
小杨有100元去超市买东西,每个商品有各自的价格,每种商品只能买1个,小杨的目标是买到最多数量的商品。小杨采用的策略是每次挑价格最低的商品买,这体现了分治思想。( )
分治法的核心是:
分解:将问题划分为若干 相互独立且结构相同 的子问题。
解决:递归解决子问题。
合并:将子问题的解合并为原问题的解。
小杨的策略是 每次选当前最便宜的商品,这种策略的本质是贪心算法。
不是分治,因为无问题分解,无子问题合并。
归并排序算法体现了分治算法,每次将大的待排序数组分成大小大致相等的两个小数组,然后分别对两个小数组进行排序,最后对排好序的两个小数组合并成有序数组。( )
分治法的核心是:
分解:将问题划分为若干 相互独立且结构相同 的子问题。
解决:递归解决子问题。
合并:将子问题的解合并为原问题的解。
归并排序体现了分治算法。
对有序数组 {5,13,19,21,37,56,64,75,88,92,100} 进行二分查找,成功查找元素 19 的比较次数是2。
递归函数每次调用自身时,系统都会为新开启的函数分配内存,以存储局部变量、调用地址和其他信息等,导致递归通常比迭代更加耗费内存空间。
在操作系统中,需要对一组进程进行循环。每个进程被赋予一个时间片,当时间片用完时,CPU将切换到下一个进程。这种循环操作可以通过环形链表来实现。
进行是循环的,一个进程的时间片用完之后,进行下一个进程,所以进程可以用循环链表实现。
找出自然数 n 以内的所有质数,常用算法有埃拉托斯特尼(埃氏)筛法和线性筛法,其中线性筛法效率更高。
常见的质数筛有埃氏筛和欧拉筛(线性筛法),其中埃氏筛的时间复杂度为O(nlogn),经过一定的优化,可以到O(nloglogn),欧拉筛的时间复杂度为O(n),大部分情况下,欧拉筛的效率更高。
唯一分解定理表明任何一个大于 1 的整数都可以唯一地分解为素数之和。
任何一个大于等于2的整数,都可以唯一的分解为若干个质数的幂次方的乘积的形式
贪心算法通过每一步选择局部最优解,从而一定能获得最优解。
贪心算法的使用条件是:局部最优能够得到全局最优,不是所有的问题都可以通过贪心实现,因为局部最优不一定能得到全局最优
快速排序和归并排序的平均时间复杂度均为 O(nlogn),且都是稳定排序。
快速排序的均摊时间复杂度为O(nlogn),归并排序的时间复杂度是稳定的O(nlogn),所以对于时间复杂度的描述是正确的,但是快速排序不是稳定排序。