Въпроси на Тест1 Посочете верните твърдения за прости числа, т.е. тези, за които съществува строго доказателство. Каква е сложността (в най-лошия случай) на дадената функция за двоично търсене в сортиран масив от n елемента? Каква е сложността (в най-лошия случай) на дадената функция за последователно търсене в масив от n елемента? Участник в състезание трябва да познае намислено число между 1 и n включително, като има право да задава въпроси, на които се отговаря само с "да/не". Колко най-много въпроси са необходими за намиране на намисленото число? Посочете вярно или невярно е всяко от следващита твърдения за сложността (най-лошия случай) на дадения алгоритъм за сортиране на n елементен масив. Дадена задача има размер на входа n. Разполагаме с два различни алгоритъма A и B за решаването и, изискващи време an и bn^2 съответно, където a и b са неизвестни константи. Направено е измерване на времето на работа на всеки от алгоритмите при стойности на n 1024 и 2048, при което са получени следните резултати: за алгоритъм A -- 128 и 256; за алгоритъм B -- 16 и 64. Посочете верните твърдения: Отбележете верните твърдения за примери на комбинаторни конфигурации. Посочете верни и неверни твърдения за бързодействието на алгоритми при достатъчно големи входни данни и зададени сложности. Проста стратегия за разрешаване на колизии в хеш таблиците е линейно пробване. Нека е дадена хеш таблица A = {35,14,E,21,E,12,E} с дължина N=7, където E означава "empty" елемент. Хеш функцията е h(k) = k mod 7. Отбележете верните и неверни съответствия при добавяне на елементи в таблицата, където -> означава "е еквивалентно на". Дадена е следната рекурсивна функция unsigned no_gcd(unsigned a, unsigned b) { return (0 == b) ? a : no_gcd(b, a/b); } Отбележете верните и неверни съответствия параметри на функция -> върната стойност.