Рубрики

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

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

1. Пусть X — задача, принадлежащая классу NP. Тогда что из следующего является ИСТИННЫМ?
(A) Нет алгоритма полиномиального времени для X.
(B) Если X можно решить детерминистически за полиномиальное время, то P = NP.
(C) Если X NP-сложен, то он NP-завершен.
(D) X может быть неразрешимым.

Ответ (С)
(A) неверно, потому что набор NP включает в себя как P (разрешимое за полиномиальное время), так и NP-Complete.
(B) неверно, потому что X может принадлежать P (та же причина, что и (A))
(C) правильно, потому что NP-полный набор является пересечением NP и Hard-наборов.
(D) неверно, потому что все проблемы NP разрешимы в конечном наборе операций.

2. Какое количество свопов требуется для сортировки n элементов с использованием сортировки выбора, в худшем случае?
(A) Θ (n)
(B) Θ (n log n)
(C) Θ (n 2 )
(D) Θ (nn 2 log n)

Ответ (А)
Вот алгоритм выбора сортировки для сортировки по возрастанию.

   1. Find the minimum value in the list
   2. Swap it with the value in the first position
   3. Repeat the steps above for the remainder of the list (starting at
      the second position and advancing each time)

Как видно из алгоритма, сортировка выбора выполняет своп только после нахождения соответствующей позиции текущего выбранного элемента. Таким образом, в сортировке выбора выполняется O (n) перестановок.
Поскольку подкачки требуют записи в массив, сортировка выбора предпочтительнее, если запись в память значительно дороже, чем чтение. Это обычно тот случай, если предметы огромные, а ключи маленькие. Другим примером, где время записи имеет решающее значение, является массив, хранящийся в EEPROM или Flash. Нет другого алгоритма с меньшим перемещением данных.

Ссылки:
http://en.wikipedia.org/wiki/Selection_sort

3. Время выполнения алгоритма представлено следующим рекуррентным соотношением:

    if  n <= 3  then   T(n) = n
    else T(n) = T(n/3) + cn

Что из следующего представляет временную сложность алгоритма?
(A) Θ (n)
(B) Θ (n log n)
(C) Θ (n 2 )
(D) Θ (n 2 log n)

Ответ (A)

 T (n) = cn + T (n / 3)
= cn + cn / 3 + T (n / 9)
= cn + cn / 3 + cn / 9 + T (n / 27)
Взяв сумму бесконечных рядов GP. Значение T (n) будет
быть меньше этой суммы.
Т (п)

Это также может быть решено с помощью основной теоремы для решения повторений. Данное выражение лежит в случае 3 теоремы.

4. Ключи 12, 18, 13, 2, 3, 23, 5 и 15 вставляются в первоначально пустую хеш-таблицу длиной 10 с использованием открытой адресации с хеш-функцией h (k) = k mod 10 и линейным зондированием. Что такое результирующая хеш-таблица?

Ответ (С)
Чтобы получить представление об открытой концепции адресации, вы можете перейти по ссылкам ниже из Википедии.
,
Открытая адресация или закрытое хеширование - это метод разрешения коллизий в хеш-таблицах. С помощью этого метода конфликт хэшей разрешается путем зондирования или поиска в альтернативных местах в массиве (последовательности проб) до тех пор, пока не будет найдена целевая запись или не найден неиспользуемый слот массива, что указывает на отсутствие такого ключа в стол. Хорошо известные последовательности зондов включают в себя:

линейное зондирование, в котором интервал между зондами фиксирован - часто в 1.
квадратичное зондирование, в котором интервал между зондами увеличивается линейно (следовательно, индексы описываются квадратичной функцией).
двойное хеширование, в котором интервал между зондами фиксирован для каждой записи, но вычисляется другой хеш-функцией.

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

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

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

0.00 (0%) 0 votes