第二十题选ABC 上述的三类排序算法在教材中都是稳定算法，归并排序也是稳定算法，基数排序对稳定的要求十分之高，其稳定性甚至会影响其正确性

第十九题选B 反例:3!!这个RPN，存在两个单目运算符，比操作数多1个

第十八题选A 这是RPN的特性之一，可以直观地展示出原中缀表达式运算的优先级，并保留原表达式各操作数的相对次序

第十七题选A 由于列表存在头尾节点，对应的指针可以便于我们直接对首末节点进行操作，因此，无论选择哪端作栈顶/底，其时间复杂度都为O(1)

第十六题选A 采用双栈当队时，假设前n个元素都先“入队”进入栈A，第一次进行"出队"操作时，所有元素都从栈A出栈到栈B，时间复杂度O(n)，但之后的每一次出栈操作，都只需要进行B.pop()即可，时间复杂度O(1)，故均摊下来，其均摊时间复杂度为O(1)

第十五题选B 递归函数的空间复杂度主要取决于递归深度而非递归实例总数 同时要注意，递归函数的空间复杂度也并非完全取决于递归深度，如归并排序过程中，递归深度为O(logn)，但由于其执行过程中申请了O(n)级别的临时空间，因此空间复杂度为O(n)

第十四题答案选A 根据起泡排序的特性，只有在遇到逆序对的时候，两个相邻元素才会进行交换，又由于是相邻元素间的交换，因此每次交换也只会消除这一对逆序对，故交换操作的次数与序列中逆序对总数相等

第十三题答案为B 由于列表循位置访问的特性，无论是有序列表还是无序列表，查找元素时都需要从头指针或尾指针出发来到相应的位置，此时有序列表采用折半查找反而效率会变低，故二者都需采用顺序查找，效率不会有明显差别

第十二题答案为A 如{2,1,1}，交换2和第一个1后变为{1,2,1}，虽然总逆序对数有所减少，但相邻逆序对数不变

第十一题答案为A 比如{3,2,1}，原本逆序对(2,1)之间的距离为1，迭代2轮后，(2,1)之间的距离变为2,有所增大

第十题答案为B 列表进行折半插入排序时，由于列表循位置访问的特性，其来到中点就需要花费Ω(n)的时间，因此哪怕是最好情况下，时间复杂度也会达到Ω(n^2)的程度

第九题答案为2025 这里直接给出结论： 有序向量长度n=fib(k)-1时 最大失败查找长度为k-1 最小失败查找长度为k-2 最大成功查找长度为k-1 最小成功查找长度为2

第八题的答案为A 在递归分解的过程中，参与的向量可能原本就是有序的，递归合并的过程中，参与合并的向量已经排序完毕了，因此必定是有序的

第七题的答案为A 为习题解析[2-41]的原题，大家可以自行观看书上的证明

第六题的答案为B 任一问题在最坏情况下的最低计算成本，即为该问题的复杂度下界 只有CBA式排序算法，或者说基于比较树模型的排序算法的复杂度下界才为Ω(nlogn) 其他排序，如桶排序，计数排序的复杂度下界并非如此

第五题答案为A 本题的的式子看着有些繁琐，我们不妨将其简化，让M=lglgn来代替 由换底公式可得(lgn)^lglglgn=(lglgn)^lglgn 因此，这道题其实就是在问：M!=O(M^M)，不难发现这必然成立

第四题答案为A 在程序执行过程中，我们一般采用的是常数代价准则，这意味着其输出，基本运算等操作的时间复杂度都将默认为O(1) 但对数代价准则则不同，它会考虑在实际操作运算过程中，我们需要读取每一个数的数位，fib(n)通常为θ(n)位，读取的操作本身也是要付出时间代价的，因此，那么仅仅是输出fib(n)，也会需要Ω(n)的时间

第三题答案为C 在826的语境里，就地算法是指的是空间复杂度O(1)的算法 A选项空间复杂度为O(n) B选项的空间复杂度为O(logn) D选项的空间复杂度为O(min(n,m)) 故只有C选项符合题意

第二题答案为A 本题源自习题解析[1-3d] 在进行起泡排序过程中，对于序列中的任何一个元素，只要由更小的元素位于其右侧，或更大的元素位于其左侧，那它迟早会与其发生交换。若序列中每一个元素都发生过n-1次交换，则说明每一个元素都与除自身之外的所有元素发生过交换。 该情况只有序列完全逆序时才符合。 更具体的证明可以采用反证法，大家不妨自行尝试

第一题答案为B

主定理扩展形式中，对该情况下的 $k$ 是有限定的，只有在 $k≥0$ 时，该结论才成立 因此本题错在对“任意整数”这个表述上 反例: $T(n)=2T(n/2)+n/\log n=\Theta(n\log\log n)$