Рубрики

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

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

1. Обычная Θ (n ^ 2) реализация сортировки вставкой для сортировки массива использует линейный поиск для определения позиции, в которой элемент должен быть вставлен в уже отсортированную часть массива. Если вместо этого мы используем бинарный поиск для определения позиции, наихудшее время выполнения будет (GATE CS 2003)
(а) остаются Θ (п ^ 2)
(б) стать Θ (n (log n) ^ 2)
(c) стать Θ (n log n)
(г) стать Θ (н)

Ответ (а)
Если мы используем бинарный поиск, то в худшем случае будет ⌈ Log 2 (n!) ⌉ сравнений, то есть Θ (n log n) (Если вы хотите знать, как ⌈ Log 2 (n!) ⌉ может быть равно Θ (n log n)), то посмотрите это для доказательства). Но алгоритм в целом все равно будет иметь время выполнения в среднем Θ (n ^ 2) из-за серии перестановок, необходимых для каждой вставки.

Ссылка:
http://en.wikipedia.org/wiki/Insertion_sort


2. Самая тесная нижняя граница для числа сравнений, в худшем случае для сортировки на основе сравнения, имеет порядок

а) н
б) п ^ 2
в) нлогн
d) n (log ^ 2) n

Ответ (с)
Количество сравнений, которое требует алгоритм сортировки сравнений, увеличивается пропорционально nlog (n), где n — количество элементов для сортировки. Эта граница асимптотически тесна:

Учитывая список различных чисел (мы можем предположить это, потому что это анализ наихудшего случая), есть n факторных перестановок, точно одна из которых является списком в отсортированном порядке. Алгоритм сортировки должен получить достаточно информации из сравнений, чтобы определить правильные перестановки. Если алгоритм всегда завершается после не более чем f (n) шагов, он не может различить более 2 ^ f (n) случаев, потому что ключи различны и каждое сравнение имеет только два возможных результата. Следовательно,


    2^f(n) >= n!, or equivalently f(n) > Log2(n!). 

Ссылки:
http://en.wikipedia.org/wiki/Comparison_sort
http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15451-s07/www/lecture_notes/lect0130.pdf


3. Проблемы 3-SAT и 2-SAT являются

а) как в П
б) оба НП завершены
в) NP-полная и в P соответственно
г) неразрешимые и NP-полные соответственно

Ответ (с)
Проблема булевой выполнимости (SAT) — это проблема решения, экземпляр которой представляет собой булево выражение, написанное с использованием только AND, OR, NOT, переменных и скобок. Проблема в том, что, учитывая выражение, существует ли какое-либо присвоение значений TRUE и FALSE переменным, которые сделают все выражение истинным? Формула логики высказываний называется выполнимой, если ее переменным можно присвоить логические значения таким образом, чтобы эта формула была истинной.

3-SAT и 2-SAT являются частными случаями k-выполнимости (k-SAT) или просто выполнимости (SAT), когда каждое предложение содержит ровно k = 3 и k = 2 литералов соответственно.

2-SAT — это P, а 3-SAT — NP Complete. (См. Это для объяснения)

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


4. Рассмотрим следующий график


Среди следующих последовательностей
Я) abeghf
II) abfehg
III) Abfhge
IV) Афгхб
Каковы глубинные обходы вышеупомянутого графика? (GATE CS 2003)

а) только I, II и IV
б) только я и IV
в) только II, III и IV
г) только I, III и IV

Ответ (г)

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

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

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

0.00 (0%) 0 votes