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

Що таке зважений граф?

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

Що таке коефіцієнт заповнення (load factor) геш-таблиці?

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

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

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

Дорожня мережа має 100,000 перехресть, кожне з'єднане приблизно з 4 іншими. Яке подання найдоречніше?

1. AБінарна купа ребер
2. BОдин відсортований масив вершин
3. CСписок суміжності
4. DМатриця суміжності

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

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

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

1. AO(V + E)
2. BO(V × E)
3. CO(V²)
4. DO(E²)

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

1. AВисота рівно log₂ n
2. BВисота щонайбільше n / 2
3. CВисота щонайбільше log₂ n + 1
4. DВисота щонайбільше 2 log₂(n + 1)

Об'єкт зберігається як ключ у геш-відображенні (hash map), а потім змінюється поле, яке використовує його геш-функція. Який імовірний результат?

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