Рубрики

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

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

1. У нас есть двоичная куча для n элементов, и мы хотим вставить еще n элементов (не обязательно один за другим) в эту кучу. Общее время, необходимое для этого
(A) Θ (logn)
(B) Θ (n)
(C) Θ (nlogn)
(D) Θ (n 2 )

В худшем случае сложность времени для вставки в двоичную кучу — это O (Logn) (см. Wiki ). Таким образом, вставка n элементов в кучу размером n должна занять Θ (nlogn) времени.
Но выбор (B) кажется более подходящим ответом. Одно из решений сложности O (n) может состоять в том, чтобы взять 'n' элементов кучи и других 'n' элементов вместе и построить кучу в O (2n) = O (n). Спасибо pankaj за предложение этого решения.

2. Алгоритм поиска в ширину был реализован с использованием структуры данных очереди. Один из возможных порядков посещения узлов следующего графа

(A) MNOPQR
(B) NQMPOR
(C) QMNPRO
(D) QMNPOR

Ответ (С)


3. Рассмотрим следующие функции:

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

Какое из следующих утверждений об асимптотическом поведении f (n), g (n) и h (n) верно?
(A) f (n) = O (g (n)); g (n) = O (h (n))
(B) f (n) = Ω (g (n)); g (n) = O (h (n))
(С) g (n) = O (f (n)); h (n) = O (f (n))
(D) h (n) = O (f (n)); g (n) = Ω (f (n))

Ответ (D)

По порядку роста: h (n) lognlogn

Обратите внимание, что log (n!) = Θ (nlogn)


4. Минимальное количество сравнений, необходимое для определения того, появляется ли целое число более n / 2 раз в отсортированном массиве из n целых чисел, равно

(A) Θ (n)
(B) Θ (logn)
(C) Θ (log * n)
(D) Θ (н)

Ответ (Б)

Пожалуйста, смотрите подробности в сообщении Проверка на элемент большинства в отсортированном массиве .

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

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

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

0.00 (0%) 0 votes