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

Яка головна відмінність між статичним і динамічним масивом?

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

Яка визначальна риса множини як абстрактного типу даних?

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Бінарна купа ребер

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

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

Ключі 50, 30, 70, 20, 40 вставляють у такому порядку в порожнє бінарне дерево пошуку. Яка ліва дитина вузла 30?

1. A20
2. B50
3. C40
4. D70

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

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

Яка структура дає змогу обчислити максимум кожного вікна розміру k у масиві за загальний час O(n)?

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