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

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

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

В однозв'язному списку кожен вузол містить:

1. AДані та індекс
2. BДані та посилання на наступний вузол
3. CДані та посилання на всі інші вузли
4. DЛише дані

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

1. AВизначення довжини масиву фіксованого розміру
2. BДоступ до 5-го елемента
3. CВставлення на початок
4. DЧитання останнього елемента за індексом

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

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

Симетричний обхід (in-order) бінарного дерева пошуку відвідує ключі:

1. AЗавжди в порядку спадання
2. BУ порядку зростання (відсортовано)
3. CПо рівнях
4. DУ порядку вставлення

У бінарній мін-купі, що зберігається в масиві (індексація з 0), діти вузла з індексом i розташовані на позиціях:

1. A2i + 1 і 2i + 2
2. B2i і 2i + 1
3. Ci/2 і i/2 + 1
4. Di + 1 і i + 2

Дерево відрізків (segment tree) зазвичай використовують для:

1. AСортування рядків за абеткою шляхом зберігання кожного префікса в окремому вузлі дерева
2. BРеалізації стека
3. CЗберігання ребер графа
4. DВідповідей на запити на діапазонах (наприклад, суми діапазонів) та оновлень за O(log n)

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

1. AВоно потребує бінарного дерева пошуку як додаткового сховища, тож використовує O(n) додаткової пам'яті
2. BВоно стабільне й потребує O(n) додаткової пам'яті
3. CВоно працює за час O(n) на будь-яких вхідних даних
4. DВоно сортує на місці за час O(n log n) у найгіршому випадку, але не є стабільним