Тест_1

1. Посочете верните твърдения (т.е. тези, за които съществува строго доказателство).

2. Каква е сложността в най-лошия случай на алгоритъма за търсене на елемент в подреден (сортиран) масив "двоично търсене''?

3. Участник в "`Къци Вапцаров шоу'' трябва да познае число между 1 и n включително, като има право да задава въпроси, на които се отговаря само с "да/не''. Какъв брой въпроси са необходими в най-лошия случай, ако участникът използва оптимална стратегия?

4. Стек е структура от данни, за която важи правилото: ...

5. Сложността на алгоритъма за бързо сортиране (quicksor) на масив от n елемента в най-лошия случай е от порядъка на: ...

6. Дадена задача има размер на входа n. Разполагаме с два различни алгоритъма за решаването й, изискващи време cn и dn2 съответно, където c и d са неизвестни константи. Направено е измерване на времето на работа на всеки от алгоритмите при стойности на n 1024 и 2048, при което са получени следните резултати: cn - 128 и 256; dn2 -  16 и 64. Посочете верните твърдения: ...

7. Отбележете верните твърдения за примери на комбинаторни конфигурации:

8. k-ият по големина елемент в сортиран масив може да се намери (в най-лошия случай) за време: ...

9. Последователното търсене в масив има сложност: ...

10. Функцията за определяне на броя на операците на даден алгоритъм се задава с рекурентната зависимост:

T(0) = 1, T(n) = 2T(n–1) + n, n > 1.

Тогава сложността на алгоритъма е:

11. С кое от следните имена свързвате произхода на думата "алгоритъм'': ... :)

<>12. Какво мислите за теста?  :).