Рубрики

Структуры данных и алгоритмы | Комплект 26

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

1) Макс-куча — это куча, в которой значение каждого родителя больше или равно значению его потомков. Что из следующего является max-heap?

Ответ: (Б)
Бинарное дерево является max-heap, если оно является полным бинарным деревом (Полное бинарное дерево — это бинарное дерево, в котором каждый уровень, за исключением, возможно, последнего, полностью заполнен, а все узлы расположены как можно левее) и следует свойство max-heap (значение каждого родителя больше или равно значению его потомков).

А) не является максимальной кучей, потому что это не полное двоичное дерево
B) является max-heap, потому что это полное двоичное дерево и соответствует свойству max-heap.
C) не является max-heap, потому что 8 является чили 5 в этом дереве, поэтому нарушает свойство max-heap.
D) не является max-heap, потому что 8 — это Чили из 5 в этом дереве, поэтому нарушает свойство max-heap. В этом дереве есть много других узлов, которые нарушают свойство max-heap в этом дереве.

2) Четыре матрицы M1, M2, M3 и M4 с размерами pxq, qxr, rxs и sxt соответственно можно умножить несколькими способами с разным количеством полных скалярных умножений. Например, при умножении на ((M1 X M2) X (M3 X M4)) общее количество умножений равно pqr + rst + prt. При умножении на (((M1 X M2) X M3) X M4) общее количество скалярных умножений равно pqr + prs + pst.

Если p = 10, q = 100, r = 20, s = 5 и t = 80, то необходимое число скалярных умножений равно
А) 248000
Б) 44000
В) 19000
D) 25000

Ответ (С)
Мы получаем минимальное количество умножений, используя ((M1 X (M2 X M3)) X M4).

Общее количество умножений = 100x20x5 (для M2 x M3) + 10x100x5 + 10x5x80 = 19000.


3) Какой из приведенных вариантов обеспечивает возрастающий порядок асимптотической сложности функций f1, f2, f3 и f4?

f1 (n) = 2 ^ n
f2 (n) = n ^ (3/2)
f3 (n) = nLogn
f4 (n) = n ^ (Logn)

А) f3, f2, f4, f1
Б) f3, f2, f1, f4
В) f2, f3, f1, f4
D) f2, f3, f4, f1

Ответ (А)
См. Http://geeksquiz.com/algorithms-analysis-of-algorithms-question-9/ для объяснения.


4) Нам дан набор из n различных элементов и немеченое двоичное дерево с n узлами. Сколько способов мы можем заполнить дерево заданным набором, чтобы оно стало бинарным деревом поиска?

А) 0
Б) 1
В) п!
D) (1 / (n + 1)). 2nCn

Ответ (Б)

Смотрите это объяснение от PeddaBoku.

5) Алгоритм определения длины самой длинной монотонно возрастающей последовательности чисел в массиве A [0: n-1] приведен ниже.
Обозначим через Li длину самой длинной монотонно возрастающей последовательности, начиная с индекса i в массиве


Какие из следующих утверждений верно?

(A) Алгоритм использует парадигму динамического программирования
(B) Алгоритм имеет линейную сложность и использует парадигму ветвления и границ
(C) Алгоритм имеет нелинейную полиномиальную сложность и использует парадигму ветвления и границ
(D) Алгоритм использует парадигму разделяй и властвуй.

Ответ: (А)

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

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

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

Структуры данных и алгоритмы | Комплект 26

0.00 (0%) 0 votes