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

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

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

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

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

Глибина вузла в дереві — це:

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

Кільцевий буфер (ring buffer) зазвичай використовують для реалізації:

1. AГеш-функції
2. BЧерги фіксованого розміру
3. CБінарного дерева пошуку
4. DОбходу графа

Яка висота бінарного дерева пошуку з n вузлами в найгіршому випадку, якщо ключі вставляються у відсортованому порядку?

1. Alog₂ n
2. Bn (дерево перетворюється на зв'язний список)
3. C1
4. D√n

Яку структуру даних використовує пошук у глибину (DFS, ітеративна версія)?

1. AЧерга
2. BКупа
3. CСтек
4. DЛише геш-таблиця

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

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

Яка основна перевага списку з пропусками (skip list) над відсортованим зв'язним списком?

1. AВін не використовує додаткової пам'яті
2. BОчікуваний пошук за O(log n) завдяки кільком рівням вказівників уперед
3. CГарантований пошук за O(1), бо кожен вузол зберігає вказівник на кожен інший вузол
4. DВін зберігає ключі без упорядкування