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

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

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

Що таке листок у дереві?

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

Яка головна відмінність між статичним і динамічним масивом?

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

Ви маєте посилання на вузол у середині списку. У якому списку його можна видалити за O(1)?

1. AУ двозв'язному списку
2. BВ однозв'язному списку
3. CУ динамічному масиві
4. DУ відсортованому масиві

Вузол бінарного дерева пошуку має праве піддерево. Де розташований його наступник у симетричному порядку (in-order successor)?

1. AЗавжди його права дитина
2. BКрайній лівий вузол його правого піддерева
3. CЗавжди його батько
4. DКрайній правий вузол його лівого піддерева

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

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

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

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

Яка вартість однієї операції find у найгіршому випадку в структурі union-find з n елементами без об'єднання за рангом і стиснення шляхів?

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