Рубрики

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

GATE CS, MCQ

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

1) Пусть w (n) и A (n) обозначают соответственно время выполнения в наихудшем и среднем случаях алгоритма, выполняемого на входе размера n. что из перечисленного ВСЕГДА ИСТИНА?
(A) A (n) = Ω (W (n))
(B) A (n) = Θ (W (n))
(C) A (n) = O (W (n))
(D) A (n) = o (W (n))

Ответ (С)
Временная сложность в наихудшем случае всегда больше или равна средней сложности времени.

2) Наихудшее время выполнения для поиска элемента в сбалансированном дереве двоичного поиска с n2 ^ n элементами
(A) Θ (n log n)
(B) Θ (n2 n )
(С) Θ (н)
(D) Θ (log n)

Ответ (С)
Время поиска элемента составляет Θ (h), где h — высота дерева двоичного поиска (BST). Рост высоты сбалансированного BST является логертимичным с точки зрения количества узлов. Таким образом, наихудшее время для поиска элемента будет Θ (Log (n * 2 ^ n)), который равен Θ (Log (n) + Log (2 ^ n)), который равен Θ (Log (n) + n), который можно записать как Θ (n).

3) Предполагая, что P! = NP, что из следующего верно?
(A) NP-полный = NP
(B) NP-полная ∩ P = Φ
(C) NP-Hard = NP
(D) P = NP-полный

Ответ (Б)
Ответ B (ни одна NP-полная задача не может быть решена за полиномиальное время). Потому что, если одна проблема NP-Complete может быть решена за полиномиальное время, то все проблемы NP могут быть решены за полиномиальное время. Если это так, то NP и P множество становятся одинаковыми, что противоречит данному условию.

4) Высота дерева определяется как количество ребер на самом длинном пути в дереве. Функция, показанная в псевдокоде ниже, вызывается как высота (корень) для вычисления высоты двоичного дерева с корнем в корне указателя дерева.

Соответствующее выражение для двух полей B1 и B2:
(A) B1: (1 + высота (n-> справа)), B2: (1 + макс (h1, h2))
(B) B1: (высота (n-> справа)), B2: (1 + макс (h1, h2))
(C) B1: высота (n-> справа), B2: максимум (h1, h2)
(D) B1: (1 + высота (n-> справа)), B2: максимум (h1, h2)

Ответ (А)
Поле B1 освобождается, когда левое поддерево n равно NULL, а правое sbtree не равно NULL. В этом случае высота n будет высотой правого поддерева плюс один.
Блок B2 выполняется, когда левые и правые ветви дерева n не равны NULL. В этом случае высота n будет максимальной из высоты левого и правого стволов дерева n плюс 1.

5) Список из n строк, каждая из которых имеет длину n, сортируется в лексикографическом порядке с использованием алгоритма сортировки слиянием. Наихудшее время выполнения этого вычисления
(A) O (n log n)
(B) O (n 2 log n)
(C) O (n ^ 2 + log n)
(D) O (n ^ 2)

Ответ (Б)
Дерево повторений для сортировки слиянием будет иметь высоту Logn. И работа O (n 2 ) будет выполняться на каждом уровне дерева рекуррентности (каждый уровень включает в себя n сравнений, а в худшем случае для сравнения требуется время O (n)). Таким образом, временная сложность этой сортировки слиянием будет O (n 2 log n).

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

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

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

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

0.00 (0%) 0 votes