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

Яка операція має складність O(1) для масиву, але O(n) для однозв'язного списку?

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

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

1. APush
2. BPeek
3. CPop
4. DEnqueue

Що робить геш-функція в геш-таблиці?

1. AВідображає ключ в індекс у таблиці
2. BШифрує значення в таблиці
3. CСортує ключі в таблиці
4. DРахує, скільки ключів збережено

Яку структуру даних використовують, щоб перевірити, чи збалансовані дужки в «{[()]}»?

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

Геш-таблиця розміру 7 використовує h(k) = k mod 7 і лінійне зондування. Після вставлення 10 де буде збережено 17?

1. AВ індексі 0
2. BВ індексі 3
3. CВ індексі 4
4. DВ індексі 6

Як працює extract-min у бінарній мін-купі?

1. AВидаляють корінь і зсувають усі елементи на одну позицію ліворуч
2. BВидаляють останній елемент масиву
3. CШукають новий мінімум серед усіх листків
4. DОстанній елемент переміщують у корінь і просіюють униз

Чому в геш-таблиці з відкритою адресацією видалення часто виконують за допомогою позначки «надгробок» (tombstone)?

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

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

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