数据结构和算法|集19

在2009门CS考试中提出了以下问题。

1.设X为NP类问题。那么以下哪一项是正确的？ （A） 对于X，没有多项式时间算法。 （B） 如果X可以在多项式时间内确定地求解，那么P=NP。 （C） 如果X是NP难的，那么它是NP完全的。 （D） X可能是不可判定的。

答复（C） （A） 不正确，因为集合NP同时包含P（多项式时间可解）和NP完全。 （B） 不正确，因为X可能属于P（与（A）的原因相同） （C） 是正确的，因为NP完备集是NP和NP难集的交集。 （D） 是不正确的，因为所有的NP问题都可以在有限的运算集中判定。

2.在最坏的情况下，使用选择排序对n个元素进行排序所需的交换数是多少？ （A） Θ（n） （B） Θ（n logn） （C） Θ（n） ^2. ) （D） Θ（nn） ^2. 日志（n）

答复（A） 下面是按升序排序的选择排序算法。

   1. Find the minimum value in the list
   2. Swap it with the value in the first position
   3. Repeat the steps above for the remainder of the list (starting at
      the second position and advancing each time)

从算法中可以看出，选择排序仅在找到当前拾取元素的适当位置后才执行交换。所以有O（n）交换是在选择排序中执行的。 因为交换需要写入数组，如果写入内存的成本明显高于读取，则选择排序更可取。如果物品很大，但钥匙很小，通常会出现这种情况。写入时间至关重要的另一个例子是存储在EEPROM或闪存中的阵列。没有其他算法可以减少数据移动。

参考资料： http://en.wikipedia.org/wiki/Selection_sort

3.算法的运行时间由以下递推关系表示：

    if  n <= 3  then   T(n) = n
    else T(n) = T(n/3) + cn

以下哪一项代表算法的时间复杂度？ （A） Θ（n） （B） Θ（n logn） （C） Θ（n） ^2. ) （D） Θ（n） ^2. 日志（n）

答复（A）

T(n) = cn + T(n/3)
     = cn + cn/3 + T(n/9)
     = cn + cn/3 + cn/9 + T(n/27)
Taking the sum of infinite GP series. The value of T(n) will
be less than this sum.
T(n) <= cn(1/(1-1/3))
     <= 3cn/2

or we can say 
cn <= T(n) <= 3cn/2
Therefore T(n) = Θ(n)

这也可以通过使用 主定理 用于解决复发问题。给出的表达式是 案例3 关于这个定理。

4.使用哈希函数h（k）=k mod 10的开放寻址和线性探测，将键12、18、13、2、3、23、5和15插入长度为10的初始空哈希表中。生成的哈希表是什么？

答复（C） 要想了解开放寻址的概念，你可以从 维基百科 . 开放寻址或封闭哈希是哈希表中冲突解决的一种方法。使用这种方法，可以通过探测或搜索数组中的其他位置（探测序列）来解决哈希冲突，直到找到目标记录或未使用的数组槽，这表明表中没有这样的键。众所周知的探针序列包括：

线性探测 探针之间的间隔是固定的——通常为1。 二次探测 探针之间的间隔线性增加（因此，指数由二次函数描述）。 双重散列 每个记录的探测间隔是固定的，但由另一个哈希函数计算。

如果您发现任何答案/解释不正确，或者您想分享有关上述主题的更多信息，请发表评论。