TEST

ТЕСТ
(въпросите на теста с по един верен и един грешен отговор)

Посочете верните твърдения за динамичното оптимиране.
(не) Всички алгоритми, основани на този метод, имат сложност O(n log n).
(да) Метод, при който обикновено се запълва таблица с решения на подзадачи с цел избягване на повторни пресмятания.

Намерете разстоянието на Левенщайн между дадените два низа. Отговорете с ДА, ако намереното разстояние е даденото число.
(да) movie, love, 2
(не) some, same, 2

Посочете верните твърдения за графи.
(да) Граф G наричаме наредената двойка (V, A), където V е крайно множеството от върховете на графа, а А е крайно множество от дъги (двойки върхове).
(не) Хамилтонов цикъл в граф се нарича цикъл, съдържащ всички връхове от графа.

Посочете верните твърдения за алгоритми за графи.
(да) Свързан неориентиран граф съдържа ойлеров цикъл тогава и само тогава когато всички върхове на графа са от четна степен.
(не) Алгоритъмът за транзитивното затваряне може да премахне дъга.

Да се намери дължината на критичния път в зададения ацикличен насочен граф и се отговори с ДА, ако тя е равна точно на числото, дадено след задаването на графа.
(да) (1 2 12), (2 3 40), (2 5 17), (4 5 30), (5 6 20), (6 3 20), 70
(не) (1 2 1), (1 4 2), (2 5 2), (4 5 1), (5 3 5), (5 6 3), (6 3 4), 12

Да се намери лицето на непресичащ се многоъгълник със зададени координати на върховете с теоремата на Пик. Да се отговори с ДА, ако намереното лице е равно на даденото число.
(да) (0,0), (0,1), (1,1), (2,2), (2,1), (1,0); 2
(не) (0,0), (0,1), (1,1), (2,2), (3,1), (1,0); 4

Да се намери лицето на фигурата, определена от графиката на функцията f(x), абцисната ос и двете вертикални прави през точките (0,0) и (1,0). Да се отговири с ДА, ако намереното лице е по-голямо от 1.
(не) f(x) = x²
(да) f(x) = 3x

Дадена е дробна задача за раницата с 4 вида предмети с тегла 20, 40, 12 и 35 и цени съответно 5, 8, 2 и 5. Решения ли са следните комбинации на зададено "максимално тегло'', "получена максимална цена''?
(не) 10, 2
(да) 20, 5

Дадена е задачата за задания и крайни срокове. Да се пресметнат спечелените точки при зададени ("продължителност'' "краен срок''). Да се отговири с ДА, ако пресметнатата стойност е равна последното зададено число.
(да) (4 2), (3 5), (2 7), (4 5), -10
(не) (4 2), (3 5), (2 7), (4 13), 2

Верни ли са следните твърдения за алчни алгоритми?
(да) Съставят лесно, обикновено реализацията на алгоритъма не е сложна.
(не) Винаги намират оптималното решение на задачата.

Даден е код на редица с поредни еднакви малки латински букви, кодирана с ESC символ z. Да се преброи колко пъти се среща дадената буква в редицата и да се отговори с ДА, ако този брой е последното число.
(да) ababzcab, a, 5
(не) ababzcab, b, 4

Да се направи код на Хъфман за дадения низ от малки латински букви, да се кодира низа и да се види, дали даденото число е дължината (в бита) на кодирания низ.
(да) afbabcdefacbabcdecde, 52
(не) ааafbabcdefacbabcdecde, 54

Колко дъги ще има графа след транзитивно затваряне?
(отг. 3) (1 2), (2 3)
(отг. 2) (1 2), (1 3)

Даден е ориентиран ацикличен граф и линейна наредба на върховете му. Отговорете с ДА, ако наредбата е топологично сортиране.
(да) (a c), (b d); abcd
(не) (a c), (b d); bcad

Верни ли са следните твърдения за оценка на алгоритми в графи? Върховете на графа са n, а дъгите - m.
(да) Свързаност на граф може да се определи с алгоритъм със сложност O(n+m).
(не) Задачата за търговския пътник се решава за време O(n²).