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

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

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

Що таке вузли-брати (siblings) у дереві?

1. AВузли зі спільним батьком
2. BВузли на однаковій глибині в різних піддеревах
3. CВузол і його батько
4. DВузли без дітей

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

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

Яка вартість вставлення елемента в середину масиву з n елементів?

1. AO(1), бо індекс відомий
2. BO(log n) через бінарний пошук
3. CO(n), бо наступні елементи доводиться зсувати
4. DO(n²), бо кожен елемент переміщується n разів

Геш-таблиця розміру 7 використовує h(k) = k mod 7 і лінійне зондування. Після вставлення 10 де буде збережено 17?

1. AВ індексі 6
2. BВ індексі 0
3. CВ індексі 4
4. DВ індексі 3

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

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

Алгоритм Кана для топологічного сортування раз у раз видаляє вершини з напівстепенем входу 0. Яка структура зберігає ці вершини?

1. AЧерга (або будь-яка колекція) вершин із напівстепенем входу 0
2. BМакс-купа, упорядкована за напівстепенем виходу
3. CМатриця суміжності, що фіксує, які вершини вже видалено
4. DСтек усіх відвіданих ребер

Ключі 5, 3, 8, 1 вставляють у такому порядку в порожню бінарну мін-купу на основі масиву. Який остаточний масив?

1. A[1, 3, 8, 5]
2. B[3, 1, 8, 5]
3. C[1, 3, 5, 8]
4. D[1, 5, 8, 3]