ТЕСТ
(Въпросите на теста с по един верен и един
грешен отговор)
Посочете вярно или невярно е всяко от следващита твърдения за
точната оценка на сложността на дадения алгоритъм за сортиране на n
елемента.
(не) бързо сортиране на Хоор - O(n)
(да) пряка селекция - O(n2)
Дадена задача има размер на входа n. Разполагаме с два различни
алгоритъма A и B за решаването й, изискващи време an и bn2 съответно, където a и b са неизвестни положителни константи. Направено е
измерване на времето на работа на всеки от алгоритмите при стойности
на n = 1024 и 2048, при
което са получени следните резултати: за алгоритъм A - 128 и 256; за
алгоритъм B - 16 и 64. Посочете верните твърдения:
(да) Алгоритъм А ще бъде по-бавен от B за стойности на n, по-малки от 5.
(не) Алгоритъм B ще бъде по-бавен от D за стойности на n, по-малки от 8192.
Отбележете верните твърдения за примери на
комбинаторни конфигурации.
(да) 12 21 е пермутация без повторения за n=2
(не) 12 13 14 23 24 34 е пермутация без повторения за n=4, k=2
Посочете верни и неверни твърдения за
бързодействието на алгоритми при достатъчно големи входни данни и
зададени сложности.
(да) Алгоритъм със сложност O(n2) е по-бавен от
друг със сложност O(1)
(не) Алгоритъм със сложност O(1)
е по-бавен от друг със сложност O(n2)
Дадена е следната рекурсивна функция:
unsigned
no_gcd(unsigned a, unsigned b)
{ return (0 == b) ? a :
no_gcd(b, a/b); }
Отбележете верните и неверни съответствия "параметри на функция
-> върната стойност".
(да) 100, 50 -> 25
(не) 8, 24 -> 8
Посочете верните твърдения за метода
"разделяй и владей''.
(да) Разбиване на изходната задача на няколко подзадачи, решаване на
подзадачите и конструиране на решение на изходната задача.
(не) Методът се реализира само с нерекурсивни функции.
Посочете верните твърдения за динамичното
оптимиране.
(да) Биномни коефициенти се пресмятат с приложение на този метод.
(не) Методът изисква реализация с рекурсивна функция.
k-тият по големина елемент в несортиран
масив може да се намери (в най-лошия случай) за време:
(да) O(n2)
(не) O(1)
Алгоритъм за умножение на две n-цифрени
числа може да има сложност:
(да) O(n2)
(не) O(1)
Дадена е задача за раницата с 4 вида
предмети с тегла 2, 4, 1 и 5 и цени съответно 8, 15, 3 и 21.
Предполагаме, че има неограничени количества от всички предмети.
Решения ли са следните комбинации на зададено максимално тегло -
получена максимална цена?
(да) 12, 50
(не) 1, 4
Посочете верни и грешни твърдения за Стандартната библиотека с
шаблони (STL) на езика C++.
(не) Параметрите на алгоритъма за сортиране sort
са задължително итератори в STL.
(да) Контейнерът map съхранява
двойки елементи (ключ, стойност) и поддържа операция индекс.
Верни ли са следните твърдения за
класификация на задачите?
(да) Всяка задача с полиномиален алгоритъм за решаването й е
полиномиално проверима.
(не) NP = P
Посочете верните и неверни твърдения
относно асимпотичната нотация за конкретни функции.
(да) 4n
+ 1 е O(n)
(не) 5n + n2
е O(n)
Нека d(n), e(n),
f(n) и g(n) са функции с положителни
цели аргументи и положителни стойности. Вярно ли е следното
твърдение?
(да) Ако d(n) е O(f(n)), то a
+ d(n) е O(f(n)) за всяка
константа a.
(не) Ако d(n) е O(n) и e(n)
е O(n2), то d(n) + e(n)$
е O(n).