Рубрики

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

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

1) Рассмотрим псевдокод, приведенный ниже. Функция DoSomething () принимает в качестве аргумента указатель на корень произвольного дерева, представленного представлением leftMostChild-rightSibling. Каждый узел дерева имеет тип treeNode.

typedef struct treeNode* treeptr;

struct treeNode {

    treeptr leftMostChild, rightSibling;

};

int DoSomething (treeptr tree) {

    int value = 0;

    if (tree != NULL) {

        if (tree->leftMostChild == NULL)

            value = 1;

        else

            value = DoSomething(tree->leftMostChild);

        value = value + DoSomething(tree->rightSibling);

    }

    return(value);

}

Когда указатель на корень дерева передается в качестве аргумента DoSomething, значение, возвращаемое функцией, соответствует
(A) количество внутренних узлов в дереве.
(Б) высота дерева.
(C) количество узлов без правильного брата в дереве.
(D) количество листовых узлов в дереве.

Ответ: (Д)
В этом вопросе важно отметить представление дерева. Дерево представлено как крайняя левая дочерняя и правая форма родного брата. Таким образом, если самый левый дочерний элемент для узла равен NULL, то дочерний элемент этого узла отсутствует. Если мы посмотрим на функцию, мы можем заметить, что функция увеличивает «значение» на 1 только для конечного узла.

2) Предположим, что обнаружен алгоритм полиномиального времени, который правильно вычисляет наибольшую клику в данном графе. В этом сценарии, что из следующего представляет правильную диаграмму Венна классов сложности P, NP и NP Complete (NPC)?


(А) А
(Б) Б
(С) С
(D) D

Ответ: (Д)
Самая большая клика — это полная проблема NP. Если одна проблема полного NP может быть решена за полиномиальное время, то все они могут быть. Таким образом, набор NPC становится равным P.

Следующее заполнить пустые вопросы
3) Минимальное количество сравнений, необходимое для нахождения минимума и максимума в 100 чисел, составляет _________________.

Ответ: 147
Минимальное количество необходимых сравнений составляет 3n / 2 — 3 для n чисел. Пожалуйста, обратитесь к методу 3 Максимума и минимума массива, используя минимальное количество сравнений для более подробной информации.

4) Рассмотрим две строки A = «qpqrr» и B = «pqprqrp». Пусть x — длина самой длинной общей подпоследовательности (не обязательно смежной) между A и B, и пусть y — количество таких самых длинных общих подпоследовательностей между A и B. Тогда x + 10y = ___.

Ответ: 34
Самая длинная длина — 4. Существует 3 LCS длиной 4 «qprr», «pqrr» и «qpqr».

5) Предположим, что P, Q, R, S, T являются отсортированными последовательностями, имеющими длины 20, 24, 30, 35, 50 соответственно. Они должны быть объединены в одну последовательность, объединяя две последовательности одновременно. Число сравнений, которые потребуются в худшем случае оптимальным алгоритмом для этого, составляет ____.

Ответ: 358
Чтобы объединить два списка размером m и n, нам нужно выполнить сравнение m + n-1 в худшем случае. Поскольку нам нужно объединять 2 за раз, оптимальной стратегией было бы сначала брать списки наименьшего размера. Причина выбора двух самых маленьких предметов заключается в том, чтобы при объединении иметь минимальные предметы для повторения.
Сначала мы объединяем 20 и 24 и получаем список из 44, используя 43 сравнения в худшем случае. Затем мы объединяем 30 и 35 в список из 65, используя 64 сравнения наихудших случаев. Затем мы объединяем 50 и 44 в список из 94, используя 93 сравнения. Наконец, мы объединяем 94 и 65, используя 158 сравнений. Таким образом, общее количество сравнений составляет 43 + 64 + 93 + 158, что составляет 358.

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

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

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

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

0.00 (0%) 0 votes