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

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

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

Яку структуру даних використовують для обходу дерева по рівнях?

1. AЧергу з пріоритетом
2. BГеш-таблицю
3. CЧергу
4. DСтек

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

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

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

1. AЛінійне зондування
2. BМетод ланцюжків (separate chaining)
3. CПодвійне гешування
4. DКвадратичне зондування

Чергу реалізовано двома стеками: push у стек «in» і pop зі стека «out», який поповнюють із «in», коли він порожній. Яка амортизована вартість однієї операції?

1. AO(1)
2. BO(n²)
3. CO(log n)
4. DO(n)

Ключі 50, 30, 70, 20, 40 вставляють у такому порядку в порожнє бінарне дерево пошуку. Яка ліва дитина вузла 30?

1. A70
2. B20
3. C40
4. D50

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

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

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

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