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

В однозв'язному списку кожен вузол містить:

1. AЛише дані
2. BДані та посилання на всі інші вузли
3. CДані та посилання на наступний вузол
4. DДані та індекс

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

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

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

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

Бінарне дерево має корінь 1 з лівою дитиною 2 і правою дитиною 3; вузол 2 має дітей 4 (ліва) і 5 (права). Який прямий обхід (preorder)?

1. A1 2 4 5 3
2. B4 5 2 3 1
3. C4 2 5 1 3
4. D1 2 3 4 5

Що правильно щодо матриці суміжності неорієнтованого графа?

1. AВона завжди верхньотрикутна
2. BКожен рядок містить рівно одну 1
3. CВона симетрична відносно головної діагоналі
4. DЇї головна діагональ завжди містить одиниці

Який метод розв'язання колізій зберігає ключі, що конфліктують, у списку в тому самому кошику?

1. AЛінійне зондування
2. BМетод ланцюжків (separate chaining)
3. CПодвійне гешування
4. DКвадратичне зондування

Чому бази даних для індексів часто використовують B+ дерева, а не звичайні B-дерева?

1. AB+ дерева використовують бінарні внутрішні вузли, що зменшує кількість зчитувань із диска
2. BB+ дерева не потребують збалансування
3. CУсі записи розташовані у зв'язаних листках, що робить сканування діапазонів ефективним
4. DB+ дерева зберігають дані лише в корені

Часова складність операції decrease-key у бінарній купі (за відомої позиції елемента) становить:

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