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

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

已知数列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)根据递推式写出求数列值的递归算法，问原始算法与采用函数值缓存的算法时间复杂度分别为多少？

已知数列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.动态规划不能减少算法的空间复杂度E.函数值缓存不能减少算法的时间复杂度F.函数值缓存可以减少算法的空间复杂度G.动态规划可以减少算法的空间复杂度H、动态规划不能减少算法的时间复杂度正确答案：函数值缓存不能减少算法的时间复杂度；函数值缓存可以减少算法的空间复杂度；动态规划可以减少算法的空间复杂度；动态规划不能减少算法的时间复杂度

所谓排序算法的稳定性是指：排序前，2个相等的数，其在序列的前后位置顺序，和排序后它们两个的前后位置顺序相同。以下哪些排序算法是稳定的？

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