Рубрики

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

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

1) Рекуррентное соотношение, фиксирующее оптимальное время задачи Ханойской башни с n дисками, имеет вид
(A) T (n) = 2T (n — 2) + 2
(B) T (n) = 2T (n — 1) + n
(C) T (n) = 2T (n / 2) + 1
(D) T (n) = 2T (n — 1) + 1

Ответ (D)

Ниже приведены шаги для рекурсивного решения проблемы Ханойской башни .

Let the three pegs be A, B and C. The goal is to move n pegs from A to C.
To move n discs from peg A to peg C:
    move n-1 discs from A to B. This leaves disc n alone on peg A
    move disc n from A to C
    move n?1 discs from B to C so they sit on disc n

Рекуррентная функция T (n) для временной сложности вышеупомянутого рекурсивного решения может быть записана следующим образом.

T (n) = 2T (n-1) + 1

2) Рассмотрим ориентированный граф, показанный на рисунке ниже. Существует несколько кратчайших путей между вершинами S и T. Какой из них будет сообщен алгоритмом кратчайшего пути Диджстры? Предположим, что на любой итерации кратчайший путь к вершине v обновляется только при обнаружении строго более короткого пути к v.

(A) SDT
(B) SBDT
(С) SACDT
(D) SACET

Ответ (D)

3) Предположим, что круговая очередь емкостью (n — 1) элементов реализована с помощью массива из n элементов. Предположим, что операция вставки и удаления выполняется с использованием REAR и FRONT в качестве переменных индекса массива соответственно. Первоначально REAR = FRONT = 0. Условия для определения полной очереди и пустой очереди:
(A) Полный: (REAR + 1) mod n == FRONT, пустой: REAR == FRONT
(B) Полный: (REAR + 1) mod n == FRONT, пустой: (FRONT + 1) mod n == REAR
(C) Полный: REAR == FRONT, пустой: (REAR + 1) mod n == FRONT
(D) Полный: (FRONT + 1) mod n == REAR, пустой: REAR == FRONT

Ответ (А)
Смотрите это для деталей.

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

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

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

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

0.00 (0%) 0 votes