Рубрики

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

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

1) Пусть G — граф с n вершинами и m ребрами. Какова самая тесная верхняя граница времени бега при первом поиске глубины G? Предположим, что граф представлен с использованием матрицы смежности.
(A) O (n)
(B) O (m + n)
(С) O (n 2 )
(D) O (мн)

Ответ: (с)
Объяснение: Поиск в глубине Поиск графика занимает O (m + n) время, когда график представлен с использованием списка смежности.

В представлении матрицы смежности граф представлен в виде матрицы «nxn». Чтобы выполнить DFS, для каждой вершины мы проходим строку, соответствующую этой вершине, чтобы найти все смежные вершины (в представлении списка смежности мы проходим только смежные вершины вершины). Следовательно, временная сложность становится O (n 2 )

2) Рассмотрим корневое двоичное дерево, представленное с помощью указателей. Наилучшая верхняя граница времени, необходимая для определения количества поддеревьев, имеющих ровно 4 узла O (n a Logn b ). Тогда значение + 10b равно ________

Ответ: 1
Объяснение: Мы можем найти поддерево с 4 узлами за O (n) времени. Следующее может быть простым подходом.
1) Обходите дерево снизу вверх и найдите размер поддерева, укорененного в текущем узле.
2) Если размер становится 4, то выведите текущий узел.

int print4Subtree(struct Node *root)

{

    if (root == NULL)

      return 0;

    int l =  print4Subtree(root->left);

    int r =   print4Subtree(root->right);

    if ((l + r + 1) == 4)

       printf("%d ", root->data);

    return (l + r + 1);

}

3) Рассмотрим ориентированный граф, приведенный ниже. Что из следующего является ИСТИННЫМ?


(A) Граф не имеет топологического порядка
(B) Как PQRS, так и SRPQ являются топологическими
(C) PSRQ и SPRQ имеют топологическое упорядочение
(D) PSRQ — единственный топологический порядок

Ответ: (с)
Объяснение:
Граф не содержит циклов, поэтому существует топологическое упорядочение.
P и S должны появляться перед R и Q, потому что есть ребра от P до R и Q, а также от S до R и Q.
См. Топологический порядок для более подробной информации.

4) Пусть P — программа быстрой сортировки для сортировки чисел в порядке возрастания с использованием первого элемента в качестве точки разворота. Пусть t1 и t2 будут количеством сравнений, сделанных P для входов {1, 2, 3, 4, 5} и {4, 1, 5, 3, 2} соответственно. Что из следующего имеет место?
(А) t1 = 5
(B) t1 <t2
(С) t1> t2
(D) t1 = t2

Ответ: (с)
Объяснение: Когда первый или последний элемент выбран в качестве сводного, наихудший случай быстрой сортировки возникает для отсортированных массивов.
На каждом этапе быстрой сортировки числа делятся в соответствии со следующим повторением.
T (n) = T (n-1) + O (n)

5) Рассмотрим следующую функцию C, в которой size — это количество элементов в массиве E:
Значение, возвращаемое функцией MyX, является

int MyX(int *E, unsigned int size)

{

    int Y = 0;

    int Z;

    int i, j, k;

  

    for (i = 0; i < size; i++)

        Y = Y + E[i];

  

    for (i = 0; i < size; i++)

        for (j = i; j < size; j++)

        {

            Z = 0;

            for (k = i; k <= j; k++)

                Z = Z + E[k];

            if (Z > Y)

                Y = Z;

        }

    return Y;

}

(A) максимально возможная сумма элементов в любом подмассиве массива E.
(B) максимальный элемент в любом подмассиве массива E.
(C) сумма максимальных элементов во всех возможных подмассивах массива E
(D) сумма всех элементов в массиве E.

Ответ: (А)
Пояснение: функция выполняет следующее
Y используется для хранения максимальной суммы, видимой на данный момент, а Z используется для хранения текущей суммы
1) Инициализируйте Y как сумму всех элементов
2) Для каждого элемента вычислите сумму всех подмассивов, начиная с arr [i]. Сохраните текущую сумму в Z. Если Z больше, чем Y, то обновите Y.


Смотрите ниже для полного решения всех работ GATE CS 2014

GATE-CS-2014- (Set-1)
GATE-CS-2014- (Set-2)
GATE-CS-2014- (Set-3)

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

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

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

0.00 (0%) 0 votes