1 操作系统是算法吗？请说说算法和程序的区别。

答：不是。

算法是满足下述性质的指令序列：
（1）输入：有零个或多个外部量作为算法的输入。

（2）输出：算法产生至少一个量作为输出。

（3）确定性：组成算法的每条指令清晰、无歧义。

（4）有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限
程序是算法用某种程序设计语言的具体实现。

程序可以不满足算法的性质(4)即有限性。

2 关于描述时间复杂度的符号O Ωθ,请简要描述它们的含义。

答：O的定义：如果存在正的常数C和自然数N0，使得当N≥N0时有f(N)≤Cg(N)，则称函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N))。

即f(N)的阶不高于g(N)的阶。

Ω的定义：如果存在正的常数C和自然数N0，使得当N≥N0时有f(N)≥Cg(N)，则称函数f(N)当N充分大时下有界，且g(N)是它的一个下界，记为f(N)=Ω(g(N))。

即f(N)的阶不低于g(N)的阶。

θ的定义：定义f(N)= θ(g(N))当且仅当f(N)=O(g(N))且f(N)= Ω(g(N))。

此时称f(N)与g(N)同阶。

3 算法A的运行时间至少是O（n2），这种说法正确吗？为什么？
答：不正确。

因为时间复杂度的符号O描述的是函数具有上界，即最多的运行时间是O（n2）。

6、插入排序、合并排序和快速排序这三种算法，哪几种使用了分治策略？请简述之。

答：合并排序和快速排序使用了分治的策略。

合并排序：对要排序的数组A[low…high]，令mid=[(low+high)/2]，用A[mid]把原数组A[low…high]分成两个子数组，然后对两个子数组进行排序，在合并两个已牌子徐的子数组，产生排序数组。

快速排序：对要排序的数组A[low…high]，先使用算法SPLIT重新排列元素，使得原先在A[low]中的祝愿占据其正确的位置A[w]，并且所有小于或等于A[w]的元素所处的位置为A[low…w-1]，而所有大于A[w]的元素所处的位置是A[w+1…high]。

在对子数组A[low…w-1]和A[w+1…high]递归地排序，产生整个排序数组。

归并排序要好于插入排序，插入排序要好于冒泡排序。

7、分治法适合求解的问题一般具有那些特征？分治法可分为哪三个主要步骤？
答：适合分治法求解的问题一般具有以下特征：
（1）问题的规模缩小到一定程度就可以容易地解决
（2）问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质
（3）基于子问题的解可以合并为原问题的解
（4）问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

分治法可分为以下三个步骤：
分解（Divide）：将原问题分解为子问题
解决（Conquer）：求解子问题
合并（Combine）：组合子问题的解得到原问题的解。

分治法的基本思想：
分治法的基本思想是将规模较大的问题分解为规模较小的子问题，子问题之间相互独立且与原问题同类。

求解子问题，然后将子问题的解合并为原问题的解。

分治法的求解实例：
合并排序，快速排序
最大元最小元
最近点对问题
求第i小元素问题
8、试说明分治法求最大最小元算法的主要思想。

给出求最大最小元算法的时间复杂度。

答：将要排序的数组分割成两半，A[1…n/2]和A[(n/2)+1…n]，在每一半中找到最大值和最小值，并返回这两个最小值中的最小值及这两个最大值中的最大值。

时间复杂度是O（n）
9、试说明分治法寻找最近点对算法的主要步骤。

该算法中有哪几个点最为关键？
答：1）分解：对所有的点按照x坐标从小到大排序，根据下标进行分割，使点集分成两个集合。

2）解决：递归寻找PL和PR中的最近点对，设其找到的最近点对的距离分别是δL和δR， 置δ=min(δL, δR)。

3）合并：可能并不是δ，存在这样的情况，一个点在PL中，另一个点在PR中，而这两点之间的距离小于δ。

只考虑分割线两侧距离各为δ的点，继续压缩点的范围。

难点：如何在现行时间内获得YL,YR,XL,XR,X’
10、可用动态规划法求解的问题通常具有那些特征？
答：若一个问题可以分解为若干个高度重复的子问题，且问题也具有最优子结构性质，就可以用动态规划法求解。

动态规划法求解的问题通常具有那些特征：
1）子问题的高度重复性
2）最优子结构性质
具体方式：可以递推的方式逐层计算最优值并记录必要的信息，最后根据记录的信息构造最优解。

动态规划方法总体思想：
保存已解决的子问题的答案，在需要时使用，从而避免大量重复计算。

动态规划方法解题步骤：
1）找出最优解的性质，并刻画其结构特征
2）递归地定义最优值（写出动态规划方程）
3）以自底向上的递推方式计算出最优值
4）根据计算最优值时得到的信息，以递归方法构造一个最优解
动态规划的应用实例：
矩阵连乘
最长公共子序列问题
最优二叉搜索树问题
流水作业的调度
11、对于以下流水作业的调度问题，请给出最优调度，并写出计算过程，机器数为2，作业数为4，作业i在机器1上的加工所需的时间为ai，作业i在机器2上的加工时间为bi，（a1，a2，a3，a4）=（5,12,4,8），（b1，b2，b3，b4）=（6,2,14,7）
答：当输入作业数为4时：
每个作业在M1上的执行时间为t[I,1],在M2上的执行时间为t[I,2]，数据为：
算法按照先执行t[I,1]<t[I,2]的作业，保证在M2机器上没有等待，作业1,3满足条件，被选择先执行。

当选择第一个作业时，算法选择让M2第一次等待时间做少的那个，所以在t[I,1]<t[I,2]的集合中，t[I,1]越小越好。

当执行t[I,1]》=t[I,2]的作业时，要保证最后一个作业在M2上的执行时间最短，所以作业2,4按照t[I,2]非增序排列。

综上所述，作业的执行顺序为：3,1,4,2
12、什么事备忘录方法？在什么情况下使用最为有效？矩阵连乘问题适合用备忘录方法吗？
答：当某个问题可以用动态规划法求解,但二维数组中有相当一部分元素在整个计算中都
不会被用到。

因此，不需要以递推方式逐个计算二维数组中元素，而采用备忘录方法：数组中的元素只是在需要计算时才去计算，计算采用递归方式，值计算出来之后将其保存起
来以备它用。

这种方法称之为备忘录方法。

下列情况时使用备忘录方法：
若有大量的子问题无需求解时，用备忘录方法较省时。

【但当无需计算的子问题只有少部分或全部都要计算时，用递推方法比备忘录方法要好（如矩阵连乘，最优二分搜索树）】所以矩阵连乘问题不适合用备忘录方法。

13、贪心算法的基本思想是什么？贪心算法适合求解的问题具有哪些特征？贪心算法求解的问题一定可以获得最优解码？
答：
贪心算法的基本思想：
适用于求解最优化问题的算法往往包含一系列步骤，每一步都有一组选择。

贪心算法总是作出在当前看来是最好的选。

择贪心算法并不从整体最优上加以考虑，它所作出的选择只是在某种意义上的局部最优选择。

贪心算法适合求解的问题具有的特征：
1）贪心选择性质
2）最优子结构性质
贪心算法一定能得到最优解吗？
贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。

在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。