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

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

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

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

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

У якому порядку зворотний обхід (postorder) бінарного дерева відвідує вузли?

1. AЛіве піддерево, потім праве піддерево, потім вузол
2. BЛіве піддерево, потім вузол, потім праве піддерево
3. CВузол, потім ліве піддерево, потім праве піддерево
4. DПраве піддерево, потім вузол, потім ліве піддерево

У бінарній мін-купі, що зберігається в масиві (індексація з 0), діти вузла з індексом i розташовані на позиціях:

1. Ai/2 і i/2 + 1
2. Bi + 1 і i + 2
3. C2i + 1 і 2i + 2
4. D2i і 2i + 1

Яку структуру даних використовує пошук у глибину (DFS, ітеративна версія)?

1. AЛише геш-таблиця
2. BСтек
3. CКупа
4. DЧерга

Яку структуру даних використовують, щоб перевірити, чи збалансовані дужки в «{[()]}»?

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

Фільтр Блума може відповісти на запитання «чи належить цей елемент множині?»:

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

Дерево відрізків (segment tree) зазвичай використовують для:

1. AВідповідей на запити на діапазонах (наприклад, суми діапазонів) та оновлень за O(log n)
2. BСортування рядків за абеткою шляхом зберігання кожного префікса в окремому вузлі дерева
3. CРеалізації стека
4. DЗберігання ребер графа