Рубрики

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

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

1 Рассмотрим полный неориентированный граф с множеством вершин {0, 1, 2, 3, 4}. Запись Wij в матрице W ниже — это вес ребра {i, j}.

Каков минимально возможный вес остовного дерева T в этом графе, чтобы вершина 0 была листовым узлом в дереве T?
(А) 7
(Б) 8
(С) 9
(D) 10

Ответ (D)

Чтобы получить минимальное остовное дерево с вершиной 0 в качестве листа, сначала удалите 0-ю строку и 0-й столбец, а затем получите минимальное остовное дерево (MST) оставшегося графа. Как только у нас есть MST оставшегося графа, подключите MST к вершине 0 с ребром с минимальным весом (у нас есть два варианта, поскольку в 0-й строке есть две 1).


2. В графе, приведенном в вопросе 1, каков минимально возможный вес пути P от вершины 1 до вершины 2 в этом графе, чтобы P содержало не более 3 ребер?

(А) 7
(Б) 8
(С) 9
(D) 10

Ответ (Б)
Путь: 1 -> 0 -> 4 -> 2
Вес: 1 + 4 + 3

3. Последовательность степеней простого графа — это последовательность степеней узлов в графе в убывающем порядке. Какая из следующих последовательностей не может быть последовательностью степеней любого графа?
I. 7, 6, 5, 4, 4, 3, 2, 1
II. 6, 6, 6, 6, 3, 3, 2, 2
III. 7, 6, 6, 4, 4, 3, 2, 2
Внутривенно 8, 7, 7, 6, 4, 2, 1, 1

(А) I и II
(B) III и IV
(C) только IV
(D) II и IV

Ответ (D)

В последовательности IV у нас есть вершина со степенью 8, которая невозможна в простом графе (без собственных петель и без кратных ребер) с общим числом вершин равным 8. Максимально возможная степень в таком графе равна 7.

В последовательности II четыре вершины соединены с 6 другими вершинами, но оставшиеся 4 вершины имеют степени 3, 3, 2 и 2, которые невозможны в простом графе (без собственных циклов и без кратных ребер).

4. Рассмотрим дерево B +, в котором максимальное количество ключей в узле равно 5. Каково минимальное количество ключей в любом некорневом узле?
(А) 1
(БИ 2
(С) 3
(D) 4

Ответ (Б)
Поскольку максимальное количество ключей равно 5, максимальное число дочерних элементов, которое может иметь узел, равно 6. По определению B-дерева минимальное количество дочерних элементов , которое может иметь узел, будет 6/2 = 3. Поэтому минимальное количество ключей, которое может иметь узел может иметь 2 (3-1).

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

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

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

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

0.00 (0%) 0 votes