Тест з алгоритмів та структур даних: базові поняття та реалізації

Яка найгірша часовa складність quicksort (наприклад, при поганому виборі pivot)?

Що таке алгоритм?

За якими основними критеріями оцінюють ефективність алгоритму?

Що показує нотація «Big O» (О-біг O)?

Яка з наведених складностей є константною?

Яка складність характерна для алгоритмів, що ділять проблему навпіл на кожному кроці (наприклад, бінарний пошук)?

Коли часову складність називають лінійною O(n)?

Що зазвичай призводить до квадратичної складності O(n^2)?

Як описують факторіальну складність O(n!)?

Як поводяться константи при оцінці у Big O?

Яка часовa складність доступу до елемента масиву за індексом?

Яка амортизована складність додавання елемента в кінець динамічного масиву (push) у більшості реалізацій?

Яка складність вставки елемента у кінець масиву у найгіршому випадку (коли потрібно виділити нову пам'ять і скопіювати дані)?

Яка складність вставки елемента на початок масиву?

Чим відрізняється статичний масив від динамічного?

Що таке «плотний» (dense) масив у контексті реалізації мов, наприклад JS?

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

Як передаються об'єкти або масиви при присвоєнні між змінними?

Де зазвичай зберігаються примітивні значення і де — об'єкти у пам'яті (спрощено)?

Яка складність лінійного пошуку (послідовного перебору) у масиві?

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

Що обов'язково має бути у рекурсивної функції, щоб вона завершилась?

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

Для яких задач рекурсія зазвичай є природним вибором?

Яка ідея сортування вибором (selection sort)?

Як працює bubble sort (пузиркова сортування)?

Яка середня часовa складність для bubble sort і selection sort?

Який підхід використовує quicksort (сортування Хоара)?

Які два загальні варіанти реалізації quicksort згадуються найчастіше?

Яка середня часовa складність quicksort?

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

Що таке амортизована складність у контексті динамічних масивів?

Яка складність вставки нового елемента на початок пов'язного списку (маючи вказівник на голову)?

Яка складність доступу до k-го елемента у однозв'язному списку?

Що дає двусвязний список у порівнянні з однозв'язним?

Яким принципом керується черга (queue)?

Яким принципом керується стек (stack)?

Що таке deque (дек)?

З яких двох основних компонентів складається граф?

Яка пара представлень графа: список суміжності і матриця суміжності, для яких умов вони підходять краще?

Яка структура даних використовується при реалізації BFS (пошук в ширину)?

Яка структура або метод використовується для реалізації DFS (пошук в глибину)?

Яке твердження про BFS і найкоротший шлях є вірним?

Який алгоритм призначений для пошуку найкоротшого шляху у зваженому графі з невід'ємними вагами ребер?

Яка часовa складність обходу графа (BFS або DFS) при представленні списком суміжності?

Який обсяг пам'яті займає матриця суміжності для графа з V вершинами?

При обході двовимірної матриці (матриці) якою технікою зазвичай користуються?

Які кроки описують принцип 'divide and conquer' (розділяй і володарюй)?

Коли доцільніше використовувати зв'язаний список замість масиву?

Яка структура даних найприродніша для представлення стеку викликів функцій та рекурсії?