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

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

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

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

1. AГеш-таблицю
2. BЧергу
3. CСтек
4. DЧергу з пріоритетом

Яка операція повільна в масиві, але швидка на початку зв'язного списку?

1. AВставлення на початок
2. BДоступ до 5-го елемента
3. CЧитання останнього елемента за індексом
4. DВизначення довжини масиву фіксованого розміру

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

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

Як працює extract-min у бінарній мін-купі?

1. AВидаляють корінь і зсувають усі елементи на одну позицію ліворуч
2. BОстанній елемент переміщують у корінь і просіюють униз
3. CВидаляють останній елемент масиву
4. DШукають новий мінімум серед усіх листків

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

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

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

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

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

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