Рубрики

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

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

1) Рассмотрим дуги дерева обхода BFS из исходного узла W в невзвешенном связном неориентированном графе. Дерево T, образованное дугами дерева, является структурой данных для вычислений.
(A) кратчайший путь между каждой парой вершин.
(B) кратчайший путь от W до каждой вершины графа.
(C) кратчайшие пути от W до только тех узлов, которые являются листьями T.
(D) самый длинный путь в графе

Ответ: (Б)
BFS всегда создает кратчайшие пути от источника ко всем остальным вершинам невзвешенного графа. Причина проста: в BFS мы сначала исследуем все вершины, которые находятся на расстоянии 1 ребра от источника, затем исследуем все вершины, которые находятся на расстоянии 2 ребер от источника, и так далее. Это свойство BFS делает его полезным во многих алгоритмах, таких как алгоритм Эдмондса – Карпа.

2) Рассмотрим следующий псевдокод. Какое общее количество умножений должно быть выполнено?

D = 2
for i = 1 to n do
   for j = i to n do
      for k = j + 1 to n do
           D = D * 3 

(A) Половина произведения трех последовательных целых чисел.
(B) Одна треть произведения трех последовательных целых чисел.
(C) Одна шестая произведения трех последовательных целых чисел.
(D) Ничего из вышеперечисленного.
Ответ (С)
Оператор «D = D * 3» выполняется n * (n + 1) * (n-1) / 6 раз. Давайте посмотрим, как.

Для i = 1 оператор умножения выполняется (n-1) + (n-2) + .. 2 + 1 раз.
Для i = 2 оператор выполняется (n-2) + (n-3) + .. 2 + 1 раз
……………………… ..
……………………….
Для i = n-1 оператор выполняется один раз.
Для i = n оператор вообще не выполняется

В общем, заявление выполняется в следующий раз
[(n-1) + (n-2) + .. 2 + 1] + [(n-2) + (n-3) + .. 2 + 1] +… + 1 + 0

Вышеприведенная серия может быть записана как
S = [n * (n-1) / 2 + (n-1) * (n-2) / 2 +… .. + 1]

Сумма вышеуказанных рядов может быть получена путем вычитания рядов из стандартного ряда S1 = n 2 + (n-1) 2 + .. 1 2 . Сумма этой стандартной серии составляет n * (n + 1) * (2n + 1) / 6

S1 — 2S = n + (n-1) +… 1 = n * (n + 1) / 2
2S = n * (n + 1) * (2n + 1) / 6 — n * (n + 1) / 2
S = n * (n + 1) * (n-1) / 6

3) Рассмотрим хеш-таблицу с 9 слотами. Хеш-функция h (k) = k mod 9. Столкновения разрешаются цепочкой. Следующие 9 ключей вставляются в порядке: 5, 28, 19, 15, 20, 33, 12, 17, 10. Максимальная, минимальная и средняя длины цепей в хеш-таблице, соответственно,
(А) 3, 0 и 1
(B) 3, 3 и 3
(С) 4, 0 и 1
(D) 3, 0 и 2

Ответ: (А)
Ниже приведены значения хэш-функции для всех ключей.

 5 --> 5
28 --> 1
19 --> 1  [Chained with 28]
15 --> 6
20 --> 2
33 --> 6  [Chained with 15]
12 --> 3
17 --> 8
10 --> 1 [Chained with 28 and 19]

Максимальная длина цепи равна 3. Ключи 28, 19 и 10 идут в один и тот же слот 1 и образуют цепь длиной 3.
Минимальная длина цепи 0, есть пустые слоты (0, 4 и 7).
Средняя длина цепи составляет (0 + 3 + 1 + 1 + 0 + 1 + 2 + 0 + 1) / 9 = 1

4) Очередь приоритетов реализована как Max-Heap. Изначально он имеет 5 элементов. Порядок обхода уровня в куче: 10, 8, 5, 3, 2. Два новых элемента 1 и 7 вставляются в кучу в указанном порядке. Уровень порядка обхода кучи после вставки элементов:
(А) 10, 8, 7, 3, 2, 1, 5
(Б) 10, 8, 7, 2, 3, 1, 5
(С) 10, 8, 7, 1, 2, 3, 5
(D) 10, 8, 7, 5, 3, 2, 1

Ответ: (А)

Initially heap has 10, 8, 5, 3, 2
    10
   /  \ 
  8    5
 / \
3   2

After insertion of 1
     10
   /   \ 
  8     5
 / \   /
3   2 1 
No need to heapify as 5 is greater than 1.


After insertion of 7
     10
   /   \ 
  8     5
 / \   / \
3   2 1   7
Heapify 5 as 7 is greater than 5
     10
   /   \ 
  8     7
 / \   / \
3   2 1   5
No need to heapify any further as 10 is
greater than 7 

5) Какое из следующих утверждений правильно определяет решение рекуррентного соотношения с T (1) = 1?

T(n) = 2T(n/2) + Logn 

(A) Θ (n)
(B) Θ (nLogn)
(C) Θ (n * n)
(D) Θ (log n)

Ответ: (А)
Это может быть решено с использованием мастер-метода . Это падает в случае 1.

7) Предположим, что реализация поддерживает инструкцию REVERSE, которая меняет порядок элементов в стеке, в дополнение к инструкциям PUSH и POP. Какое из следующих утверждений является ИСТИННЫМ относительно этого измененного стека?
(A) Очередь не может быть реализована с использованием этого стека.
(B) Очередь может быть реализована, когда ENQUEUE принимает одну инструкцию, а DEQUEUE — последовательность из двух инструкций.
(C) Очередь может быть реализована, когда ENQUEUE принимает последовательность из трех инструкций, а DEQUEUE принимает одну инструкцию.
(D) Очередь может быть реализована, где и ENQUEUE, и DEQUEUE принимают по одной инструкции каждая.

Ответ: (с)
Чтобы оформить предмет, просто поп.
Чтобы ЗАПРАВИТЬ предмет, мы можем сделать следующие 3 операции
1) ОБРАТНЫЙ
2) Жми
3) ОБРАТНЫЙ

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

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

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

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

0.00 (0%) 0 votes