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

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

1. AОдним суцільним блоком, один за одним
2. BУ випадкових місцях, обраних гешем
3. CРозкидано, зв'язані вказівниками
4. DУ дереві сторінок пам'яті

Що визначає бінарне дерево?

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), а обхід зв'язного списку — O(n)

Скільки часу потрібно, щоб перевірити наявність ребра (u, v) за допомогою матриці суміжності?

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

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

1. A4 2 5 1 3
2. B5 4 3 2 1
3. C4 5 2 3 1
4. D1 2 4 5 3

Якій властивості має відповідати червоно-чорне дерево?

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

Часова складність операції decrease-key у бінарній купі (за відомої позиції елемента) становить:

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