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

Що таке дек (deque, двостороння черга)?

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

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

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

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

1. AДані, вказівник на наступний вузол і вказівник на попередній вузол
2. BДані та два вказівники: один на наступний вузол і один на вузол після нього
3. CДані та лише вказівник на наступний вузол
4. DДві копії даних і один вказівник

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

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

Префіксне дерево (trie) особливо ефективне для:

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

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

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

Чим radix-дерево (стиснене префіксне дерево) краще за звичайне trie?

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

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

1. AЗамінюють його in-order наступником (або попередником) і видаляють той вузол
2. BПеребудовують піддерево під ним з нуля й повторно вставляють усі ключі, які воно містило
3. CВидаляють усе піддерево
4. DМіняють його місцями з коренем