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

Що таке колізія в геш-таблиці?

1. AКлюч узагалі не можна гешувати
2. BУ таблиці закінчується пам'ять
3. CДва різні ключі відображаються в один індекс
4. DДва однакові ключі зберігаються двічі

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

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

Що зберігає відображення (map, словник)?

1. AЛише значення в порядку вставлення
2. BПари ключ–значення з унікальними ключами
3. CЗначення, відсортовані за розміром
4. DПари однакових ключів

Яку структуру даних використовує пошук у глибину (DFS, ітеративна версія)?

1. AЛише геш-таблиця
2. BКупа
3. CЧерга
4. DСтек

Ви маєте посилання на вузол у середині списку. У якому списку його можна видалити за O(1)?

1. AВ однозв'язному списку
2. BУ відсортованому масиві
3. CУ динамічному масиві
4. DУ двозв'язному списку

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

1. A4 5 2 3 1
2. B4 2 5 1 3
3. C1 2 4 5 3
4. D5 4 3 2 1

Як визначити, чи містить однозв'язний список цикл, використовуючи O(1) додаткової пам'яті?

1. AЗберігати кожен відвіданий вузол у геш-множині
2. BРухати один вказівник на один крок, а інший — на два кроки й перевіряти, чи вони зустрінуться
3. CВідсортувати список і шукати дублікати
4. DРахувати вузли, доки кількість не перевищить поле довжини списку

Алгоритм Кана для топологічного сортування раз у раз видаляє вершини з напівстепенем входу 0. Яка структура зберігає ці вершини?

1. AМатриця суміжності, що фіксує, які вершини вже видалено
2. BСтек усіх відвіданих ребер
3. CМакс-купа, упорядкована за напівстепенем виходу
4. DЧерга (або будь-яка колекція) вершин із напівстепенем входу 0