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

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

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

Яка структура даних працює за принципом «останнім прийшов — першим вийшов» (LIFO)?

1. AСтек
2. BЗв'язний список
3. CЧерга
4. DГеш-таблиця

Де розташований найменший елемент бінарної мін-купи?

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

Чому бінарну купу можна зберігати в масиві без жодних вказівників?

1. AУсі ключі в купі однакові
2. BЦе повне бінарне дерево, тож позиції визначаються простими формулами індексів
3. CМасиви автоматично зберігають ключі відсортованими, тож вказівники не потрібні
4. DКупи ніколи не містять понад 100 елементів

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

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

Який максимально можливий коефіцієнт заповнення геш-таблиці з відкритою адресацією?

1. A1
2. BМаксимуму немає
3. C0,5
4. D2

У BST з коренем 50, лівим піддеревом 30 (діти 20, 40) і правим піддеревом 70 (діти 60, 80) корінь видаляють за допомогою наступника в симетричному порядку. Який ключ стає новим коренем?

1. A80
2. B70
3. C40
4. D60

Вставлення ключа в AVL-дерево робить ліве піддерево вузла надто високим, причому новий ключ потрапив у ліве піддерево його лівої дитини (випадок «ліво-ліво»). Яке виправлення застосовують?

1. AОдинарний лівий поворот у незбалансованому вузлі
2. BПерефарбування вузла та його дитини
3. CОдинарний правий поворот у незбалансованому вузлі
4. DЛівий поворот у дитині, потім правий поворот у вузлі