Рубрики

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

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

1. В двоичной максимальной куче, содержащей n чисел, самый маленький элемент может быть найден во времени (GATE CS 2006)
(A) 0 (n)
(B) O (logn)
(С) 0 (логлогия)
(D) 0 (1)

Ответ (А)
В максимальной куче наименьший элемент всегда присутствует в листовом узле. Поэтому нам нужно проверить все листовые узлы на минимальное значение. В худшем случае сложность будет O (n)

         12
        /  \
      /      \
    8         7
   / \        / \
 /     \    /     \
2      3   4       5

2. Схема хранения двоичных деревьев в массиве X заключается в следующем. Индексирование X начинается с 1 вместо 0. Корень хранится в X [1]. Для узла, хранящегося в X [i], левый дочерний элемент, если он есть, сохраняется в X [2i], а правый дочерний элемент, если он есть, в X [2i + 1]. Чтобы иметь возможность хранить любое двоичное дерево в n вершинах, минимальный размер X должен быть. (GATE CS 2006)
(A) log2n
(B) n
(С) 2n + 1
(D) 2 ^ n — 1

Ответ (D)
Для двоичного дерева с перекосом вправо число узлов будет 2 ^ n — 1. Например, в нижнем двоичном дереве узел «A» будет храниться с индексом 1, «B» с индексом 3, «C» с индексом 7 и «D» в индексе 15.

A
 \
   \
    B
      \
        \
         C
           \
             \
              D

3. Какой из следующих алгоритмов сортировки требует минимального количества перестановок? (GATE CS 2006)
(A) Быстрая сортировка
(B) Вид вставки
(C) Выбор сортировки
(D) куча сортировки

Ответ (С)
Для сортировки выбора требуется минимальное количество свопов (Θ (n)).

4. Элемент в массиве X называется лидером, если он больше всех элементов справа от него в X. Лучший алгоритм для поиска всех лидеров в массиве (GATE CS 2006)
(A) Решает это в линейном времени, используя проход массива слева направо
(B) Решает это в линейном времени, используя проход массива справа налево
(C) Решает, используя разделяй и властвуй во времени 8 (nlogn)
(D) Решает это вовремя 8 (n2)

Ответ (Б)
Пожалуйста, смотрите этот пост для объяснения.

5. Рассмотрим взвешенный полный граф G на множестве вершин {v1, v2, ..vn} такой, что вес ребра (vi, vj) равен 2 | ij |. Вес минимального остовного дерева G составляет: (GATE CS 2006)
(A) n — 1
(B) 2n — 2
(C) nC2
(D) 2

Ответ (Б)
Минимальное остовное дерево такого графа

v1
  \
    v2
      \
       v3
         \
          v4
            .
              .
                .
                 vn
 

Вес минимального остовного дерева
= 2 | 2 — 1 | + 2 | 3 — 2 | + 2 | 4 — 3 | + 2 | 5 — 4 | …. + 2 | n — (n-1) |
= 2n — 2

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

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

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

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

0.00 (0%) 0 votes