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

У якому порядку зворотний обхід (postorder) бінарного дерева відвідує вузли?

1. AВузол, потім ліве піддерево, потім праве піддерево
2. BПраве піддерево, потім вузол, потім ліве піддерево
3. CЛіве піддерево, потім вузол, потім праве піддерево
4. DЛіве піддерево, потім праве піддерево, потім вузол

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

1. APush
2. BDequeue
3. CEnqueue
4. DInsert

Що таке корінь дерева?

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

Яке призначення сторожового (фіктивного, sentinel) вузла у зв'язному списку?

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

Що відбувається, коли геш-таблиця виконує повторне гешування (rehash) після того, як коефіцієнт заповнення перевищив поріг?

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

Скільки пам'яті займає матриця суміжності графа з V вершинами?

1. AO(E)
2. BO(V²)
3. CO(log V)
4. DO(V + E)

Які операції підтримує дерево Фенвіка (binary indexed tree) над масивом із n чисел за O(log n)?

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

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

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