Робочий аркуш «Алгоритми та складність» з відповідями

Що таке рекурсія?

1. AТип структури даних
2. BЦикл, який ніколи не закінчується
3. CФункція, яка викликає саму себе для менших вхідних даних
4. DМетод сортування

Доступ до елемента масиву за індексом займає:

1. AO(1)
2. BO(log n)
3. CO(n²)
4. DO(n)

Яку складність зазвичай має алгоритм із двома вкладеними циклами, кожен із яких виконується n разів?

1. AO(2n)
2. BO(n)
3. CO(log n)
4. DO(n²)

Який розв'язок рекурентного співвідношення T(n) = T(n − 1) + O(1)?

1. AO(log n)
2. BO(2ⁿ)
3. CO(n)
4. DO(n²)

Чому основу логарифма в «великому O» зазвичай не вказують, як-от в O(log n)?

1. AОснова має значення лише для малих n
2. BУсі логарифми в інформатиці мають основу 10, тож вона мається на увазі
3. CЛогарифми завжди округлюють до цілих
4. DЛогарифми з різними основами відрізняються лише сталим множником

Який розв'язок рекурентного співвідношення T(n) = 2T(n/2) + O(1)?

1. AO(log n)
2. BO(n log n)
3. CO(n²)
4. DO(n)

Найкоротші прості шляхи можна знайти за поліноміальний час. Що відомо про пошук найдовшого простого шляху між двома вершинами в загальному графі?

1. AВона нерозв'язна
2. BЇї можна розв'язати алгоритмом Дейкстри з від'ємними вагами
3. CЇї завжди можна розв'язати за O(V + E)
4. DЦе NP-складна задача

Який алгоритм знаходить мінімальне кістякове дерево, багаторазово додаючи найдешевше ребро, яке не утворює циклу?

1. AАлгоритм Дейкстри
2. BАлгоритм Краскала
3. CАлгоритм Прима, що починає з однієї вершини
4. DАлгоритм Флойда–Воршелла