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

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

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

Яка структура даних найкраще підходить для функції «скасувати» (undo) у текстовому редакторі?

1. AСтек
2. BГеш-множина
3. CЧерга
4. DГраф

Що зберігається для кожної вершини в поданні графа списками суміжності?

1. AРядок із V булевих значень
2. BЗагальна кількість ребер у графі
3. CНайкоротший шлях до кожної іншої вершини
4. DСписок сусідніх вершин

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

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

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

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

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

1. A√n
2. Blog₂ n
3. C1
4. Dn (дерево перетворюється на зв'язний список)

Потрібно зберігати k найменших значень із потоку n чисел, використовуючи O(k) пам'яті. Який підхід працює за час O(n log k)?

1. AЧерга FIFO з останніх k значень
2. BВідсортований масив усіх n значень
3. CМін-купа, що містить усі n значень, з якої наприкінці вилучають k найменших
4. DМакс-купа розміру k, корінь якої замінюють, коли надходить менше значення

Що робить розширюване дерево (splay tree) після кожного звертання?

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