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

Що таке колізія в геш-таблиці?

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

Що містить кожен вузол двозв'язного списку?

1. AДві копії даних і один вказівник
2. BДані та два вказівники: один на наступний вузол і один на вузол після нього
3. CДані, вказівник на наступний вузол і вказівник на попередній вузол
4. DДані та лише вказівник на наступний вузол

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

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

Симетричний обхід (in-order) бінарного дерева пошуку відвідує ключі:

1. AУ порядку вставлення
2. BУ порядку зростання (відсортовано)
3. CПо рівнях
4. DЗавжди в порядку спадання

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

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

Бінарне дерево має корінь 1 з лівою дитиною 2 і правою дитиною 3; вузол 2 має дітей 4 (ліва) і 5 (права). Який прямий обхід (preorder)?

1. A1 2 4 5 3
2. B4 5 2 3 1
3. C4 2 5 1 3
4. D1 2 3 4 5

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

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

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

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