Рубрики

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

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

1) Ненаправленный граф G (V, E) содержит n (n> 2) узлов с именами v1, v2,… .vn. Два узла vi, vj связаны тогда и только тогда, когда 0 <| i — j | <= 2. Каждому ребру (vi, vj) присвоен вес i + j. Пример графика с n = 4 показан ниже.

Какова будет стоимость минимального связующего дерева (MST) такого графа с n узлами?
(A) 1/12 (11n ^ 2 — 5n)
(B) n ^ 2 — n + 1
(С) 6n — 11
(D) 2n + 1

Ответ: (Б)
Минимальное связующее дерево для 2 узлов будет

 (v1) _ (v2) 

Общий вес 3

Минимальное связующее дерево для 3 узлов будет

 (v1) _ (v2) 
    |
 (v3)

Общий вес = 3 + 4 = 7

Минимальное связующее дерево для 4 узлов будет

 (v1) _ (v2) _ (v4) 
    |
 (v3)

Общий вес = 3 + 4 + 6 = 13

Минимальное связующее дерево для 5 узлов будет

 (v1) _ (v2) _ (v4) 
    |
 (v3)
    |
 (v5)

Общий вес = 3 + 4 + 6 + 8 = 21

Минимальное связующее дерево для 6 узлов будет

 (v1) _ (v2) _ (v4) _ (v6)
    |
 (v3)
    |
 (v5)

Общий вес = 3 + 4 + 6 + 8 + 10 = 31

Из вышеприведенных примеров мы можем наблюдать, что когда мы добавляем k-й узел, вес связующего дерева увеличивается на 2k-2. Пусть T (n) — вес минимального остовного дерева. T (n) можно записать как

T (n) = T (n-1) + (2n-2) для n> 2
T (1) = 0, T (2) = 0 и T (2) = 3

Повторение может быть записано как сумма рядов (2n — 2) + (2n-4) + (2n-6) + (2n-8) +…. 3, и решение этой повторности есть n ^ 2 — n + 1.


2) Длина пути от v5 до v6 в MST предыдущего вопроса с n = 10 равна

(А) 11
(Б) 25
(С) 31
(D) 41

Ответ: (с)
Любой MST, имеющий более 5 узлов, будет иметь такое же расстояние между v5 и v6, как и базовая структура всех MST (с более чем 5 узлами).

 (v1) _ (v2) _ (v4) _  (v6) _ .  . (more even numbered nodes)
    |
 (v3)
    |
 (v5)
    |
    .
    .
(more odd numbered nodes)

Расстояние между v5 и v6 = 3 + 4 + 6 + 8 + 10 = 31

3) Рассмотрим два бинарных оператора «and» и «↓», причем приоритет оператора ↓ ниже, чем у оператора ↑. Оператор ↑ ассоциативно справа, а оператор ↓ ассоциативно слева. Что из следующего представляет дерево разбора для выражения (7 ↓ 3 ↑ 4 ↑ 3 ↓ 2)?

Ответ: (Б)
Рассмотрим данное выражение (7 ↓ 3 ↑ 4 ↑ 3 ↓ 2).

Поскольку приоритет ↑ выше, подвыражение ([3 ↑ 4 ↑ 3) будет оцениваться первым. В этом подвыражении сначала будет оцениваться 4 first 3, поскольку ↑ ассоциативно справа налево. Таким образом, выражение оценивается как ((7 ↓ (3 ↑ (4 ↑ 3))) ↓ 2). Также обратите внимание, что среди двух операторов ↓ первый оценивается перед вторым, потому что ассоциативность ↓ слева направо.

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

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

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

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

0.00 (0%) 0 votes