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

Що зберігає відображення (map, словник)?

1. AПари однакових ключів
2. BПари ключ–значення з унікальними ключами
3. CЗначення, відсортовані за розміром
4. DЛише значення в порядку вставлення

Що зберігається для кожної вершини в поданні графа списками суміжності?

1. AСписок сусідніх вершин
2. BЗагальна кількість ребер у графі
3. CРядок із V булевих значень
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Чергу FIFO

Яке значення постфіксного виразу 3 4 + 2 * ?

1. A14
2. B11
3. C10
4. D24

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

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

Яка структура даних забезпечує кеш LRU (least recently used) з операціями get і put за O(1)?

1. AЛише стек
2. BОдин відсортований масив
3. CГеш-мапа в поєднанні з двозв'язним списком
4. DЛише бінарне дерево пошуку