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

Матриця зручніша для зберігання назв вершин у вигляді рядків

Список суміжності зберігає для кожної вершини список її сусідів, матриця — двовимірну таблицю з відмітками про ребра

Вони ідентичні за пам'яттю та швидкістю для будь-якого графа

Яка різниця між списком суміжності (adjacency list) та матрицею суміжності (adjacency matrix) для представлення графу?

Перевірка знань базових понять алгоритмів, оцінки складності, масивів, списків, черг, стеків, сортировок та графів.

Тип даних у програмуванні

Послідовність інструкцій або дій для розв'язання задачі

Пристрій комп'ютерного обладнання

Точну кількість операцій, які виконає алгоритм

Час виконання в секундах

Точний обсяг пам'яті в байтах

Як масштабується витрата часу або пам'яті при збільшенні розміру вхідних даних

Що характеризує нотація «Big O» (O-нотація)?

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

Масив повинен містити лише унікальні елементи

Масив повинен бути відсортованим

Масив має бути реалізований через зв'язаний список

Масив має бути статичним за розміром

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

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

Статичний масив автоматично розширюється при додаванні елементів

Динамічний масив завжди має фіксований розмір

Статичному масиву неможливо звернутися по індексу

У статичному масиві розмір зафіксований, а динамічний може виділяти нові блоки і копіювати дані при розширенні

Чим відрізняються статичний і динамічний масиви з точки зору управління пам'яттю?

Масив із властивостями-ключами замість індексів

Масив, що містить пропуски (empty slots) і різнорідні типи

Масив, де всі елементи розташовані під суцільними індексами і мають однаковий тип

Об'єкт із парами ключ-значення

У JavaScript що з переліченого зазвичай вважається "щільним" (dense) масивом?

Копіюється посилання на область у купі

Копіюється саме значення (по значенню)

Одна змінна перетворюється у вказівник

Значення зберігається тільки у глобальній пам'яті

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

Цикл, який виконується за допомогою for/while

Метод оптимізації виконання коду компілятором

Функція, що викликає сама себе та має базовий випадок для виходу

Тип даних для зберігання чисел

Що таке рекурсія в програмуванні?

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

Яка складність за часом у середньому у QuickSort (швидка сортування) для n елементів?

Обчислення хеш-функції для кожного елемента

Поділ масиву на підмасиви, сортування їх і об'єднання результатів

Перебір усіх можливих перестановок

Заміна елементів тільки зі сусідніми

Який принцип лежить в основі сортування методом "розділяй і володарюй"?

Послідовність елементів, що зберігаються суцільно в пам'яті

Колекція ключ-значення на основі хеш-таблиці

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

Спеціальний вид масиву для тільки чисел

Що називають зв'язним (linked) списком?

O(n) — потрібно пройти від початку до потрібного місця

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

Елементи вибираються довільно

Елементи завжди видаляються з кінця

Який принцип роботи черги (queue)?

Random Access (доступ у довільному порядку)

Який принцип роботи стека (stack)?

Кожен вузол містить два значення

Кожен вузол містить посилання і на попередній, і на наступний вузол

Зберігає дані у двох різних масивах

Не підтримує видалення елементів

Що таке двонаправлений (doubly) зв'язаний список у порівнянні з однобічним?

Одновимірний масив чисел

Набір вузлів (вершин) та ребер (зв'язків) між ними

Таблиця з двома стовпцями

Тип сортування для списків

Що таке граф у структурі даних?

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

BFS використовує стек, а DFS — чергу

BFS використовує чергу, а DFS — стек або рекурсію

Обидва використовують лише масив

BFS і DFS не використовують ніяких додаткових структур даних

Чим відрізняється обхід в ширину (BFS) від обходу в глибину (DFS) у графі з точки зору структури даних, яка використовується?

Повільно зростає і підходить для великих n

Зростає дуже швидко, набагато швидше за поліноміальні функції

Що таке факторіальна складність (O(n!)) і як вона поводиться при зростанні n?

Питання 19 з 22