C++笔试试题解析

1、在下列排序算法中，初始数据集的排列顺序对算法性能无影响的是（）
A、插入排序 B、堆排序 C、冒泡排序 D、快速排序

答案: A

（插入排序：最优时间复杂度O(n)最差时间复杂度O(n^{2)平均时间复杂度O(n}2)
冒泡排序：最优时间复杂度O(n)最差时间复杂度O(n^{2)平均时间复杂度O(n}2)
快速排序：最优时间复杂度O(nlogn)最差时间复杂度O(n^2)平均时间复杂度O(nlogn)
堆排序：最优时间复杂度O(nlogn)最差时间复杂度O(nlogn)平均时间复杂度O(nlogn))

2、以下关于Cache的叙述中，正确的是（）
A、CPU中的Cache容量应大于CPU之外的Cache容量
B、Cache的设计思想是在合理成本下提高命中率
C、Cache的设计目标是容量尽可能与主存容量相等
D、在容量确定的情况下，替换算法的时间复杂度是影响Cache命中率的关键因素

答案:B
Cache（高速缓冲器）容量小于主存，但速度快于主存，慢于CPU，相当于CPU和主存间的一个缓冲器，Cache中存放最近使用过的内存内容（基于最近使用过的内容很可能被再次使用的原理）。若CPU寻访的内容在Cache中存放，则优先从Cache中读取，称为命中，否则称为脱靶，脱靶只能从主存中读取内容了。当Cache存储满