算法 -凯发k8导航

现在有一个几乎顺序排列的，非常大的列表。问以下哪些算法有可能得到时间复杂度o(n)? a.冒泡排序b.插入排序c.选择排序d.归并排序e.快速排序正确答案：冒泡排序；插入排序；归并排序

所谓排序算法的稳定性是指：排序前，2个相等的数，其在序列的前后位置顺序，和排序后它们两个的前后位置顺序相同。以下哪些排序算法是稳定的？ a.冒泡排序b.插入排序c.归并排序d.快速排序e.选择排序f.希尔排序正确答案：冒泡排序；插入排序；归并排序

以下哪些说法是错误的？ a.函数值缓存可以减少算法的时间复杂度b.函数值缓存不能减少算法的空间复杂度c.动态规划可以减少算法的时间复杂度d.动态规划不能减少算法的空间复杂度e.函数值缓存不能减少算法的时间复杂度f.函数值缓存可以减少算法的空间复杂度g.动态规划可以减少算法的空间复杂度h、动态规划不能减少算法的时间复杂度正确答案：函数值缓存不能减少算法的时间复杂度；函数值缓存可以减少算法的空间复杂度；动态规划可以减少算法的空间复杂度；动态规划不能减少算法的时间复杂度

已知数列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)

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

以下哪些算法适合用栈来实现？ a.实现undo和redo功能的算法b.html标签匹配算法c.求列表平均数的算法d.1到n的累计求和算法正确答案：实现undo和redo功能的算法；html标签匹配算法

关于“图灵机”，下列说法不正确的个数为：1）图灵机给出的是计算机的理论模型；2）图灵机的状态转移函数q,x,y,r(或l或n),p，其实就是一条指令，即在q状态下，当输入为x时，输出为y，读写头向右(r)、向左(l)移动一格或不动(n)，状态变为p；3）图灵机是一种离散的、有穷的、构造性的问题求解思路；4）凡是能用算法方法解决的问题也一定能用图灵机解决，凡是图灵机解决不了的问题算法也解决不了。 a.0b.1c.2d.3正确答案：0