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

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

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

Висоту дерева зазвичай визначають як:

1. AКількість ребер на найдовшому шляху від кореня до листка
2. BЗагальну кількість вузлів у дереві, враховуючи корінь і кожен листок
3. CКількість дітей кореня
4. DКількість листків у дереві

Скільки ребер має дерево з n вузлами?

1. A2n
2. Bn − 1
3. Cn
4. Dn + 1

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

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

Де розташований батько вузла з індексом i в бінарній купі, що зберігається в масиві з індексацією від 0?

1. AВ індексі 2i + 1
2. BВ індексі i − 1
3. CВ індексі ⌊i / 2⌋ + 1
4. DВ індексі ⌊(i − 1) / 2⌋

Скільки вузлів має ідеальне бінарне дерево висоти h, якщо висоту рахують у ребрах?

1. A2^h
2. B2^h+1 − 1
3. Ch²
4. D2h + 1

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

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

Структура union-find (система неперетинних множин) з об'єднанням за рангом і стисненням шляху має амортизовану вартість операції:

1. AO(n)
2. BO(α(n)), обернена функція Аккермана, практично стала
3. CO(n²)
4. DРівно O(log n)