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

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

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

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

1. APush
2. BDequeue
3. CEnqueue
4. DInsert

Що робить операція peek (або top) стека?

1. AПовертає верхній елемент, не видаляючи його
2. BПовертає нижній елемент стека
3. CВидаляє верхній елемент і повертає його
4. DВидаляє всі елементи зі стека

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

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

Який максимально можливий коефіцієнт заповнення геш-таблиці з відкритою адресацією?

1. A2
2. B0,5
3. C1
4. DМаксимуму немає

Яку структуру даних використовує виконувана програма, щоб відстежувати активні виклики функцій та їхні локальні змінні?

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

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

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

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

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