Тест - Основи структури даних i алгоритми: поняття алгоритму; визначення його часової та просторової (за обсягом пам’яті) складності

Прогрес тесту

правильно

неправильно

не відповіли

Питання 1 з 22

Яка просторова складність алгоритму, який для обробки масиву розміру $n$ створює додатковий масив того ж розміру $n$?

$O(1)$ $O(\log n)$ $O(n)$ $O(n^2)$

Питання 2 з 22

Для яких задач часто застосовуються алгоритми з часовою складністю $O(n!)$?

Швидкі сортування великих масивів Пошук елементів у великих базах даних Задачі, що потребують генерації всіх можливих перестановок Задачі з великими наборами даних, де потрібна логарифмічна швидкість

Питання 3 з 22

Який клас складності є гіршим за $O(2^n)$?

$O(n \log n)$ $O(n^3)$ $O(n!)$ $O(\log n)$

Питання 4 з 22

Алгоритм, який виконує $N$ операцій зчитування і $N$ операцій запису для вхідних даних розміром $N$, має часову складність:

$O(1)$ $O(\log N)$ $O(N)$ $O(N^2)$

Питання 5 з 22

Вкажіть правильний порядок зростання часової складності (від найменшої до найбільшої) для великих $n$:

$O(n)$, $O(\log n)$, $O(n^2)$ $O(\log n)$, $O(n)$, $O(n^2)$ $O(n^2)$, $O(n)$, $O(\log n)$ $O(1)$, $O(n)$, $O(n \log n)$

Питання 6 з 22

Просторова складність $O(1)$ означає:

Алгоритм дуже швидкий Алгоритм використовує константний обсяг пам'яті, незалежно від розміру вхідних даних Алгоритм не використовує пам'ять Алгоритм має лінійну залежність від пам'яті

Питання 7 з 22

Яка асимптотична нотація описує верхню межу (найгірший випадок) часової складності алгоритму?

$O$ (Big O) $\Omega$ (Omega) $\Theta$ (Theta) $o$ (Small o)

Питання 8 з 22

Який клас складності вважається найефективнішим для великих вхідних даних ($n$)?

$O(n^2)$ $O(\log n)$ $O(n)$ $O(n \log n)$

Питання 9 з 22

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

Фіксована просторова складність Базова просторова складність Допоміжна просторова складність Незалежна просторова складність

Питання 10 з 22

Яка з наведених ситуацій є прикладом найкращого випадку часової складності для алгоритму пошуку елемента у невідсортованому масиві?

Елемент знаходиться в середині масиву Елемент знаходиться в кінці масиву Елемент не знайдено в масиві Елемент є першим у масиві

Питання 11 з 22

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

Скінченність Визначеність Вхідні дані Ефективність у використанні пам'яті

Питання 12 з 22

Яка з наступних операцій має константну часову складність $O(1)$?

Пошук елемента у невідсортованому зв'язному списку Вставка елемента у відсортований масив Звернення до $i$-го елемента масиву за індексом Сортування масиву

Питання 13 з 22

Що означає "скінченність" як властивість алгоритму?

Алгоритм завжди має нульові вхідні дані Алгоритм повинен завершувати свою роботу за скінченну кількість кроків Алгоритм повинен мати точно один вихідний результат Кожен крок алгоритму повинен бути простим для виконання

Питання 14 з 22

Розгляньте наступний фрагмент коду:

for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // деякі операції O(1) } }

Яка часова складність цього фрагмента?

$O(n)$ $O(\log n)$ $O(n^2)$ $O(n \log n)$

Питання 15 з 22

Нотація $\Theta(g(n))$ (Theta Notation) використовується для опису:

Найгіршого випадку складності Найкращого випадку складності Щільної межі складності (як верхньої, так і нижньої) Лише верхньої межі складності

Питання 16 з 22

Яка з наступних властивостей алгоритму гарантує, що його кроки не мають двозначностей?

Скінченність Вхідні дані Визначеність Ефективність

Питання 17 з 22

Алгоритм має часову складність $O(n \log n)$. Що станеться з часом його виконання, якщо розмір вхідних даних $n$ збільшиться в чотири рази?

Збільшиться приблизно в 4 рази Збільшиться приблизно в $4 \log 4$ рази Збільшиться приблизно в $16$ разів Залишиться незмінним

Питання 18 з 22

Метод сортування злиттям (Merge Sort) має часову складність:

$O(n^2)$ $O(n \log n)$ $O(n)$ $O(\log n)$

Питання 19 з 22

Який з наступних алгоритмів має лінійну часову складність у найгіршому випадку?

Бінарний пошук у відсортованому масиві Сортування бульбашкою Послідовний пошук у невідсортованому масиві Доступ до елемента масиву за індексом

Питання 20 з 22

Яке твердження про просторову складність рекурсивного алгоритму є правильним?

Вона завжди $O(1)$ Вона залежить від глибини стеку рекурсії Вона завжди $O(n)$ Вона не впливає на загальну продуктивність

Питання 21 з 22

Що характеризує алгоритм з експоненціальною часовою складністю $O(2^n)$?

Він завжди швидший за $O(n^2)$ Його час виконання подвоюється з кожним збільшенням $n$ Він застосовується для задач, які не вимагають великих обчислювальних ресурсів Його час виконання дуже швидко зростає при збільшенні $n$

Питання 22 з 22

Якщо алгоритм виконує $5n^2 + 3n - 10$ операцій, яка його асимптотична часова складність у нотації "Велике О"?

$O(n)$ $O(n^2)$ $O(n^3)$ $O(1)$

Меню

Пояснення

Повідомити про помилку

Тест Завершено!