数据结构和算法|集30-yiteyi-C++库

GATE CS 2013考试中提出了以下问题。

null

1）对于无向图，以下哪项陈述是正确的？ P：奇数阶顶点的数量是偶数 Q：所有顶点的度数之和是偶数

A）仅P B）只问 C） P和Q D） P和Q都不是

答复（C） Q是真的：因为图形是无向的，所以每一条边都会使度数之和增加2。 P是真的：如果我们考虑度和减所有偶数度，我们得到偶数（因为Q是真的）。所以奇数阶顶点的总数必须是偶数。

2）考虑八个顶点的无向随机图。一对顶点之间存在边的概率为1/2。长度为3的无序循环的预期数量是多少？ （A） 1/8 （B）一, （C）七, （D）八,

答复（C）长度为3的循环可以由3个顶点组成。总共有8C3种方法可以从8个顶点中选择3个顶点。两个顶点之间存在边的概率为1/2。因此，长度为3=（8C3）*（1/2）^3=7的无序循环的预期数量

3） Bellman-Ford单源最短路径算法在n个顶点的完整图上的时间复杂度是多少？ （A） Θ（n） ^2. ) （B） Θ（n） ^2. Logn）（C） Θ（n） ^3. ) （D） Θ（n） ^3. Logn）

答案（C）。 Bellman-Ford算法的时间复杂度为Θ（VE），其中V是顶点数，E是边数（参见这 ).如果图是完整的，E的值变成Θ（V） ² ).因此，总体时间复杂度变为Θ（V ^3. )

4）以下哪项陈述是正确的？ （1）确定无向图中是否存在圈的问题在P中。（2）确定无向图中是否存在圈的问题是NP问题。（3）如果问题a是NP完全问题，则存在一个非确定性多项式时间算法来解决问题a。

（A） 1、2和3 （B）仅限1和2 （C）只有2和3 （D）仅限1和3

答复（A） 1. 这是正确的，因为使用DFS可以在多项式时间内完成周期检测（参见这 ). 2. 是真的，因为P是NP的子集。 3. 是真的，因为NP完全也是NP和NP均值的子集 N 论确定性 P 多项式时间解存在。（见这 )

5）以下哪一项是表示将对象插入n个节点的二元搜索树的时间复杂度的最严格上界？ （A） O（1）（B） O（对数n）（C） O（n）（D） O（n日志n）

答复（C）最坏的情况发生在歪斜的树上。在倾斜树中，当一个新节点作为最底层节点的子节点插入时，插入时间需要遍历所有节点。例如，考虑下面的树和插入小于70的情况。

6）以下哪一项是表示使用选择排序对n个数字进行排序所需的掉期数量的最紧上界？ （A） O（对数n）（B） O（n）（C） O（n日志n）（D） O（n^2）

答复（B）选择排序只需要O（n）交换。看见这详细信息。

7）考虑下面的操作以及Enqueue和DeCube操作队列，其中k是全局参数

MultiDequeue(Q){
   m = k
   while (Q is not empty and m  > 0) {
      Dequeue(Q)
      m = m - 1
   }
}

在一个初始为空的队列上，n个MultiDequeue（）操作序列的最坏时间复杂度是多少？ （A） Θ（n）（B） Θ（n+k）（C） Θ（nk）（D） Θ（n） ^2. )

答复（A）由于队列最初是空的，while循环的条件永远不会变为真。所以时间复杂度是Θ（n）

请看门角所有上一年的论文/解决方案/解释、教学大纲、重要日期、笔记等。

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

文章版权归作者所有，未经允许请勿转载。

THE END