Робочий аркуш «Структури даних» з відповідями

Що робить операція peek (або top) стека?

1. AПовертає нижній елемент стека
2. BВидаляє всі елементи зі стека
3. CВидаляє верхній елемент і повертає його
4. DПовертає верхній елемент, не видаляючи його

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

1. AРядок із V булевих значень
2. BНайкоротший шлях до кожної іншої вершини
3. CЗагальна кількість ребер у графі
4. DСписок сусідніх вершин

Що таке коефіцієнт заповнення (load factor) геш-таблиці?

1. AКількість колізій на цей момент
2. BЧас, потрібний для завантаження таблиці з диска
3. CКількість збережених елементів, поділена на кількість кошиків
4. DКількість кошиків, поділена на середню довжину збережених ключів

Скільки триває пошук слова довжиною L у префіксному дереві (trie) з фіксованим алфавітом?

1. AO(n), де n — кількість слів
2. BO(log n), де n — кількість слів
3. CO(L), незалежно від кількості збережених слів
4. DO(L × n)

Бінарне дерево має корінь 1 з лівою дитиною 2 і правою дитиною 3; вузол 2 має дітей 4 (ліва) і 5 (права). Який прямий обхід (preorder)?

1. A1 2 4 5 3
2. B4 2 5 1 3
3. C1 2 3 4 5
4. D4 5 2 3 1

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

1. A2i + 1
2. Bi + 1
3. C(i + 1) mod n
4. D(i − 1) mod n

Який очікуваний час пошуку за простого рівномірного гешування в геш-таблиці з ланцюжками, n ключами та m кошиками?

1. AO(log n)
2. BO(n)
3. CO(m)
4. DO(1 + α), де α = n / m

Який час роботи пошуку в ширину (BFS) у графі з V вершинами, що зберігається як матриця суміжності?

1. AO(V + E)
2. BO(V²)
3. CO(E log V)
4. DO(V)