Рубрики

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

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

1) Программа P читает 500 целых чисел в диапазоне [0..100], представляющих 500 студентов. Затем он печатает частоту каждой оценки выше 50. Каков наилучший способ для P хранить частоты?
(а) Массив из 50 чисел
(б) массив из 100 чисел
(в) массив из 500 чисел
(d) Динамически распределенный массив из 550 номеров

Ответ (а)
Массив размером 50 выглядит наилучшим вариантом для хранения количества студентов для каждой оценки. Нам нужно хранить частоты оценок выше 50. Мы можем игнорировать оценки ниже 50, а чтобы индексировать оценки выше 50, мы можем вычесть 50 из значения оценки /


2) Ненаправленный граф G имеет n узлов. Его матрица смежности задается квадратной матрицей n × n, у которой (i) диагональные элементы равны 0, а (ii) недиагональные элементы равны 1. что из следующего является ИСТИННЫМ?

(а) Граф G не имеет минимального связующего дерева (MST)
(б) График G имеет уникальный MST стоимости n-1
(c) График G имеет несколько различных MST, каждый из которых имеет стоимость n-1.
(d) График G имеет несколько связующих деревьев с разными затратами.

Ответ (с)
Если все недиагональные элементы равны 1, то каждая вершина связана с любой другой вершиной графа с ребром веса 1. Такой граф имеет несколько различных MST со стоимостью n-1. Смотрите пример ниже.

Связный граф:

Ниже приведены три минимальных остовных дерева, каждое стоимостью 2,0.
Минимальное остовное дерево 1

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

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

3) Известно, что временная сложность вычисления транзитивного замыкания бинарного отношения на множестве из n элементов:
а) O (n)
б) O (nLogn)
c) O (n ^ (3/2))
г) О (п ^ 3)

Ответ (г)
В математике транзитивное замыкание бинарного отношения R на множестве X является наименьшим транзитивным отношением на X, содержащим R. Если исходное отношение транзитивно, транзитивное замыкание будет тем же отношением; в противном случае переходное замыкание будет другим отношением.

В информатике понятие транзитивного замыкания можно рассматривать как построение структуры данных, которая позволяет ответить на вопросы достижимости. То есть можно ли перейти от узла a к узлу другого узла b за один или несколько переходов? Бинарное отношение говорит вам только о том, что узел a связан с узлом b, а этот узел b связан с узлом c и т. Д. После построения транзитивного замыкания в операции O (1) можно определить, что узел c доступен с узла а.

Алгоритм Варшалла можно использовать для построения транзитивного замыкания ориентированных графов (). В оригинальной формулировке алгоритма Варшалла граф является невзвешенным и представлен булевой матрицей смежности. Затем операция сложения заменяется логическим соединением (И), а минимальная операция — логическим дизъюнкцией (ИЛИ).

Ссылки:
http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
http://en.wikipedia.org/wiki/Transitive_closure

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

(а) 10, 8, 7, 5, 3, 2, 1
(б) 10, 8, 7, 2, 3, 1, 5
(в) 10, 8, 7, 1, 2, 3, 5
(d) 10, 8, 7, 3, 2, 1, 5

Ответ (D)

Оригинал Max-Heap это:

        10
       /  \
      8    5
     / \
    3   2

После вставки 1.

         10
       /    \
      8      5
     / \    /
    3   2 1 

После вставки 7.

         10
       /   \
      8     7
    / \    / \ 
   3   2  1   5

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

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

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

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

0.00 (0%) 0 votes