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

В однозв'язному списку кожен вузол містить:

1. AДані та посилання на наступний вузол
2. BДані та посилання на всі інші вузли
3. CЛише дані
4. DДані та індекс

Що таке степінь вершини в неорієнтованому графі?

1. AЇї позиція в списку суміжності
2. BКількість вершин у графі
3. CКількість ребер, з'єднаних із нею
4. DДовжина найдовшого шляху з неї

Що робить геш-функція в геш-таблиці?

1. AВідображає ключ в індекс у таблиці
2. BРахує, скільки ключів збережено
3. CШифрує значення в таблиці
4. DСортує ключі в таблиці

Дорожня мережа має 100,000 перехресть, кожне з'єднане приблизно з 4 іншими. Яке подання найдоречніше?

1. AБінарна купа ребер
2. BОдин відсортований масив вершин
3. CМатриця суміжності
4. DСписок суміжності

Бінарне дерево має корінь 1 з лівою дитиною 2 і правою дитиною 3; вузол 2 має дітей 4 (ліва) і 5 (права). Який зворотний обхід (postorder)?

1. A4 2 5 1 3
2. B5 4 3 2 1
3. C4 5 2 3 1
4. D1 2 4 5 3

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

1. A2^h
2. Bh²
3. C2h + 1
4. D2^h+1 − 1

Ключі 5, 3, 8, 1 вставляють у такому порядку в порожню бінарну мін-купу на основі масиву. Який остаточний масив?

1. A[1, 3, 5, 8]
2. B[1, 5, 8, 3]
3. C[1, 3, 8, 5]
4. D[3, 1, 8, 5]

Які операції підтримує дерево Фенвіка (binary indexed tree) над масивом із n чисел за O(log n)?

1. AЗапити префіксних сум і оновлення окремих елементів
2. BСортування масиву та бінарний пошук
3. CВставлення елементів у будь-яку позицію
4. DЗнаходження медіани за O(1)