Рубрики

Структуры данных и алгоритмы | Набор 30

На экзамене GATE CS 2013 были заданы следующие вопросы.

1) Какое из следующих утверждений является / является ИСТИНОЙ для неориентированного графа?
P: число вершин нечетной степени четное
Q: сумма степеней всех вершин четна

А) Р Только
B) Q Только
C) и P и Q
D) Ни P, ни Q

Ответ (С)
Q верно: поскольку граф не является ненаправленным, каждое ребро увеличивает сумму градусов на 2.
P истинно: если мы рассмотрим сумму степеней и вычтем все четные степени, мы получим четное число (потому что Q истинно). Таким образом, общее количество вершин нечетной степени должно быть четным.

2) Рассмотрим неориентированный случайный граф из восьми вершин. Вероятность наличия ребра между парой вершин равна 1/2. Каково ожидаемое количество неупорядоченных циклов длины три?
(А) 1/8
(Б) 1
(С) 7
(D) 8

Ответ (С)
Цикл длины 3 может быть сформирован с 3 вершинами. Всего может быть 8C3 способов выбрать 3 вершины из 8. Вероятность наличия ребра между двумя вершинами равна 1/2. Итак, ожидаемое количество неупорядоченных циклов длиной 3 = (8C3) * (1/2) ^ 3 = 7

3) Какова временная сложность алгоритма Белтмана-Форда с одним источником кратчайшего пути на полном графе из n вершин?
(A) Θ (n 2 )
(B) Θ (n 2 Logn)
(C) Θ (n 3 )
(D) Θ (n 3 Logn)

Ответ (С).
Временная сложность алгоритма Беллмана-Форда Θ (VE), где V — число вершин, а E — число ребер (см. Это ). Если график полон, значение E становится Θ (V 2 ). Таким образом, общая сложность времени становится Θ (V 3 )

4) Какие из следующих утверждений являются ИСТИННЫМИ?
(1) Проблема определения того, существует ли цикл в неориентированном графе, находится в P.
(2) Задача определения, существует ли цикл в неориентированном графе, находится в NP.
(3) Если задача A является NP-полной, существует недетерминированный алгоритм полиномиального времени для решения A.

(А) 1,2 и 3
(B) 1 и 2 только
(C) только 2 и 3
(D) 1 и 3 только

Ответ (А)
1 верно, потому что обнаружение цикла может быть сделано за полиномиальное время с использованием DFS (см. Это ).
2 верно, потому что P является подмножеством NP.
3 справедливо потому , что NP также полное подмножество NP и NP означает N на детерминированной Р olynomial времени решение существует. (См. Это )

5) Какой из следующих пунктов является самой жесткой верхней границей, которая представляет временную сложность вставки объекта в двоичное дерево поиска из n узлов?
(A) O (1)
(B) O (log n)
(Против)
(D) O (n log n)

Ответ (С)
Наихудший случай происходит с перекошенным деревом. В перекошенном дереве, когда новый узел вставляется как дочерний элемент самого нижнего узла, время для вставки требует обхода всех узлов. Например, рассмотрим следующее дерево и случай, когда вставлено что-то меньше 70.

             100
            /
           90
          /
        80
       /
     70   

6) Какой из следующих пунктов является самой узкой верхней границей, представляющей количество перестановок, необходимых для сортировки n чисел с использованием сортировки выбора?
(A) O (log n)
(B) O (n)
(С) O (n log n)
(D) O (n ^ 2)

Ответ (Б)
Сортировка выбора требует только O (n) перестановок. Смотрите это для деталей.

7) Рассмотрим следующую операцию вместе с операциями постановки и удаления в
очереди, где 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) Θ (нк)
(D) Θ (n 2 )

Ответ (А)
Поскольку очередь изначально пуста, условие цикла while никогда не становится истинным. Таким образом, сложность времени Θ (n)

Пожалуйста, смотрите GATE Corner для всех документов / решений / объяснений предыдущего года, учебных планов, важных дат, заметок и т. Д.

Пожалуйста, пишите комментарии, если вы найдете какие-либо неправильные ответы / объяснения, или вы хотите поделиться дополнительной информацией по темам, обсужденным выше.

Рекомендуемые посты:

Структуры данных и алгоритмы | Набор 30

0.00 (0%) 0 votes