1.Легка
Що таке властивість макс-купи?
- AУсі листки містять максимальний ключ
- BКлюч кожного батька більший або дорівнює ключам його дітей
- CКлюч кожної лівої дитини більший або дорівнює ключу її правого брата чи сестри
- DКлючі відсортовано зліва направо
2.Легка
Як називається операція стека, що додає елемент на вершину?
- AEnqueue
- BPeek
- CPop
- DPush
3.Легка
Що таке орієнтований граф?
- AГраф, що не має циклів
- BГраф, у якому кожна пара різних вершин з'єднана ребром
- CГраф, ребра якого мають напрямок від однієї вершини до іншої
- DГраф, усі ребра якого мають ваги
4.Середня
Який максимально можливий коефіцієнт заповнення геш-таблиці з відкритою адресацією?
- A2
- B0,5
- C1
- DМаксимуму немає
5.Середня
Яка часова складність пошуку ключа в збалансованому бінарному дереві пошуку?
- AO(log n)
- BO(1)
- CO(n log n)
- DO(n)
6.Середня
Скільки триває пошук слова довжиною L у префіксному дереві (trie) з фіксованим алфавітом?
- AO(L × n)
- BO(n), де n — кількість слів
- CO(log n), де n — кількість слів
- DO(L), незалежно від кількості збережених слів
7.Складна
Скільки триває пошук довільного ключа в бінарній мін-купі з n елементів?
- AO(log n)
- BO(1)
- CO(n)
- DO(log log n)
8.Складна
У циклічному буфері front == rear може означати як порожній, так і заповнений буфер. Який поширений спосіб їх розрізнити?
- AЗавжди очищати буфер щоразу, коли front дорівнює rear, тож стан — порожній
- BЗберігати окремий лічильник елементів або завжди залишати одну комірку невикористаною
- CЗберігати front і rear в одній змінній
- DРобити розмір буфера степенем двійки
Ключ відповідей
- 1. B · Ключ кожного батька більший або дорівнює ключам його дітей
- 2. D · Push
- 3. C · Граф, ребра якого мають напрямок від однієї вершини до іншої
- 4. C · 1
- 5. A · O(log n)
- 6. D · O(L), незалежно від кількості збережених слів
- 7. C · O(n)
- 8. B · Зберігати окремий лічильник елементів або завжди залишати одну комірку невикористаною
Повні покрокові розв’язки: тренуйте цю тему на examproblems.com.