Рубрики

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

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

1) Количество различных минимальных связующих деревьев s для взвешенного графика ниже ____

Ответ: 6
Выделены ( зеленым ) края, выбранные для создания MST. В правой части MST мы можем выбрать край «a» или «b». В левой части мы можем выбрать «c», «d» или «e» в MST.
Есть 2 варианта выбора одного ребра и 3 варианта выбора другого. Таким образом, всего 2 * 3 возможных MST.

2) Рассмотрим следующее корневое дерево с вершиной P, помеченной как корень

Порядок, в котором узлы посещаются во время обхода в порядке
(A) SQPTRWUV
(B) SQPTURWV
(C) SQPTWUVR
(D) SQPTRUWV

Ответ: (А)
Единственная путаница в этом вопросе состоит в том, что есть 3 ребенка R. Так, когда должен появиться R — после U или после R? Есть две возможности: SQPTRWUV и SQPTWURV. В качестве опции A присутствует только 1-я возможность, II-й возможности там нет. Поэтому вариант А является правильным ответом.

3) Пусть A — квадратная матрица размера nx n. Рассмотрим следующую программу. Каков ожидаемый результат?

C = 100

for i = 1 to n do

    for j = 1 to n do

    {

        Temp = A[i][j] + C

        A[i][j] = A[j][i]

        A[j][i] = Temp - C

    }

for i = 1 to n do

    for j = 1 to n do

        Output(A[i][j]);

(A) Сама матрица A
(B) Транспонировать матрицы A
(C) Добавление 100 к верхним диагональным элементам и вычитание 100 из диагональных элементов A
(D) Ничего из вышеперечисленного

Ответ: А
Если мы посмотрим на внутренние операторы первых циклов, мы можем заметить, что операторы меняют местами A [i] [j] и A [j] [i] для всех i и j.
Поскольку цикл выполняется для всех элементов, каждый элемент A [l] [m] будет заменен дважды: один раз для i = l и j = m, а затем для i = m и j = l. Обмен дважды означает, что матрица не меняется.

4) Минимальное количество арифметических операций, необходимое для оценки полинома P (X) = X 5 + 4X 3 + 6X + 5 для заданного значения X с использованием только одной временной переменной.
(А) 6
(Б) 7
(С) 8
(D) 9

Ответ: Б
Мы можем заключить полином в скобки, чтобы минимизировать количество операций (см . Метод Хорнера ). Мы получаем X (X 2 (X 2 + 4) + 6) + 5 после скобок.

Following is sequence of operations to be used.
Note that we are allowed to use only one variable.
res = X*X
res = res + 4
res = X*res
res = X*res
res = res + 6
res = X*res
res = res + 5

5) У вас есть массив из n элементов. Предположим, вы реализуете быструю сортировку , всегда выбирая центральный элемент массива в качестве оси. Тогда самая жесткая верхняя граница для худшего случая
(A) O (n 2 )
(B) O (nLogn)
(C) Θ (nLogn)
(D) O (n 3 )

Ответ: (А)
Средний элемент всегда может быть крайним элементом (минимальным или максимальным) в отсортированном порядке, поэтому временная сложность в худшем случае становится равной O (n 2 )

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

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

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

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

0.00 (0%) 0 votes