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

Глибина вузла в дереві — це:

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

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

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

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

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

Вузол бінарного дерева пошуку має праве піддерево. Де розташований його наступник у симетричному порядку (in-order successor)?

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

Яку структуру даних використовують, щоб перевірити, чи збалансовані дужки в «{[()]}»?

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

Яке призначення сторожового (фіктивного, sentinel) вузла у зв'язному списку?

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

Яка структура даних забезпечує кеш LRU (least recently used) з операціями get і put за O(1)?

1. AГеш-мапа в поєднанні з двозв'язним списком
2. BОдин відсортований масив
3. CЛише стек
4. DЛише бінарне дерево пошуку

У циклічному буфері front == rear може означати як порожній, так і заповнений буфер. Який поширений спосіб їх розрізнити?

1. AЗавжди очищати буфер щоразу, коли front дорівнює rear, тож стан — порожній
2. BРобити розмір буфера степенем двійки
3. CЗберігати front і rear в одній змінній
4. DЗберігати окремий лічильник елементів або завжди залишати одну комірку невикористаною