数据结构和算法|集14

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

1.我们在n个元素上有一个二进制堆，希望在这个堆中再插入n个元素（不一定是一个接一个）。此操作所需的总时间为 （A） Θ（logn） （B） Θ（n） （C） Θ（nlogn） （D） Θ（n） ^2. )

在二进制堆中插入的最差时间复杂度是O（Logn）（参见 维基 ).因此，在大小为n的堆中插入n个元素应该需要Θ（nlogn）时间。 但是选择 （B） 似乎是更合适的答案。O（n）复杂性的解决方案之一是将堆的’n’元素和其他’n’元素放在一起，以O（2n）=O（n）的形式构造堆。感谢pankaj提出这个解决方案。

2.使用队列数据结构实现了广度优先搜索算法。访问下图中节点的一个可能顺序是

（A） MNOPQR （B） NQMPOR （C） QMNPRO （D） QMNPOR

答复（C）

3、考虑以下功能：

  f(n)   = 2^n
  g(n)   = n!
  h(n)   = n^logn 

（A） f（n）=O（g（n））；g（n）=O（h（n）） （B） f（n）=&欧姆；（g（n））；g（n）=O（h（n）） （C） g（n）=O（f（n））；h（n）=O（f（n）） （D） h（n）=O（f（n））；g（n）=&欧姆；（f（n））

答复（D）

根据增长顺序：h（n）

   lognlogn < n < log(n!)  (logs of the given f(n), g(n) and h(n)).

请注意，log（n！）=Θ（nlogn）

4.确定一个整数在n个整数的排序数组中出现的次数是否超过n/2所需的最小比较次数为： （A） Θ（n） （B） Θ（logn） （C） Θ（对数*n） （D） Θ（n）

答复（B）

请看帖子 检查排序数组中的多数元素 详细信息。

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