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

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

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

Яку структуру зазвичай використовують для реалізації черги з пріоритетом?

1. AКупу
2. BСтек
3. CРядок
4. DНевпорядкований однозв'язний список

Що таке листок у дереві?

1. AВузол без батька
2. BВузол із найбільшим значенням
3. CВузол рівно з однією дитиною
4. DВузол без дітей

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

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

Який абстрактний тип даних використовує алгоритм Дейкстри, щоб обрати наступну вершину для обробки?

1. AМін-чергу з пріоритетом
2. BЧергу FIFO
3. CМножину без упорядкування
4. DСтек

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

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

Видалення вузла з двома дітьми з бінарного дерева пошуку зазвичай виконують так:

1. AЗамінюють його in-order наступником (або попередником) і видаляють той вузол
2. BМіняють його місцями з коренем
3. CВидаляють усе піддерево
4. DПеребудовують піддерево під ним з нуля й повторно вставляють усі ключі, які воно містило

Яка основна перевага списку з пропусками (skip list) над відсортованим зв'язним списком?

1. AВін не використовує додаткової пам'яті
2. BОчікуваний пошук за O(log n) завдяки кільком рівням вказівників уперед
3. CГарантований пошук за O(1), бо кожен вузол зберігає вказівник на кожен інший вузол
4. DВін зберігає ключі без упорядкування