现在有一个几乎顺序排列的，非常大的列表。问以下哪些算法有可能得到时间复杂度O(N)?
A.冒泡排序B.插入排序C.选择排序D.归并排序E.快速排序正确答案：冒泡排序；插入排序；归并排序

下列哪个算法使用到了分治策略？
A.二分查找B.单词最短编辑距离C.迷宫寻路D.博物馆大盗问题正确答案：二分查找

函数值缓存最适合使用哪种Python中的数据类型？
A.列表B.字典C.集合D.栈正确答案：字典

已知数列G(x)满足：G(1)=G(2)=G(3)=G(4)=1G(x)=G(x-1)+G(x-2)+G(x-3)+G(x-4)(x≥5)根据递推式写出求数列值的递归算法，问原始算法与采用函数值缓存的算法时间复杂度分别为多少？
A.O(4^n);O(n)B.O(5^n);O(n^2)C.O(n^4);O(n^2)D.O(5^n);O(1)正确答案：O(4^n);O(n)

博物馆大盗问题中，若共有8件宝物，背包总重为25单位，使用动态规划算法求解时需要建立多大的数组？
A.9x26B.9x25C.10x25D.10x26E.8x25F.8x26G.10x27H、9x27I、8×27正确答案：9×26

以下哪些问题可用动态规划算法解决？
A.斐波那契数列求值B.单词最短编辑距离C.列表排序D.后缀表达式求值正确答案：斐波那契数列求值；单词最短编辑距离

以下哪些说法是错误的？
A.函数值缓存可以减少算法的时间复杂度B.函数值缓存不能减少算法的空间复杂度C.动态规划可以减少算法的时间复杂度D.动态规划不能减少算法的空间复杂度E.函数值缓存不能减少算法的时间复杂度F.函数值缓存可以减少算法的空间复杂度G.动态规划可以减少算法的空间复杂度H、动态规划不能减少算法的时间复杂度正确答案：函数值缓存不能减少算法的时间复杂度；函数值缓存可以减少算法的空间复杂度；动态规划可以减少算法的空间复杂度；动态规划不能减少算法的时间复杂度

以下关于冒泡和选择排序算法的叙述何者正确？
A.平均时间复杂度上，冒泡排序的复杂度较低B.平均时间复杂度上，选择排序的复杂度较低C.空间复杂度上，冒泡排序的复杂度较低D.空间复杂度上，选择排序的复杂度较低E.其它选项皆不正确。正确答案：其它选项皆不正确。

以下关于归并和快速排序算法的叙述何者正确？
A.平均时间复杂度上，归并排序的复杂度较低B.平均时间复杂度上，快速排序的复杂度较低C.空间复杂度上，归并排序的复杂度较低D.空间复杂度上，快速排序的复杂度较低E.其它选项皆不正确。正确答案：空间复杂度上，快速排序的复杂度较低

设一组初始记录关键字序列(5，2，6，3，8)，利用冒泡排序进行升序排序，则第一趟冒泡排序的结果为以下何者？
A.2，5，3，6，8B.2，5，6，3，8C.2，3，5，6，8?D.2，3，6，5，8正确答案：2，5，3，6，8

设一组初始记录关键字序列(5，2，6，3，8)，利用插入排序进行升序排序，则第二次插入排序的结果为以下何者？
A.2，3，5，6，8B.2，5，3，6，8C.2，5，6，3，8D.5，2，3，6，8正确答案：2，5，6，3，8

给定两个已分别排序好的列表mylst1,mylst2，两者的长度分别为mn为已知，现要查找两表合并后的中位数，问最好的查找方式的时间复杂度？（可以理解为，查找alist=sorted(mylst1+mylst2)的中位数的时间复杂度）
A.O(m^2)B.O(mn)C.O(mlogn)D.O(logm)E.O(nlogm)正确答案：O(logm)