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

Що таке властивість макс-купи?

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

Що зберігає відображення (map, словник)?

1. AПари ключ–значення з унікальними ключами
2. BЛише значення в порядку вставлення
3. CЗначення, відсортовані за розміром
4. DПари однакових ключів

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

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

Що правильно щодо матриці суміжності неорієнтованого графа?

1. AКожен рядок містить рівно одну 1
2. BЇї головна діагональ завжди містить одиниці
3. CВона симетрична відносно головної діагоналі
4. DВона завжди верхньотрикутна

Що відбувається, коли геш-таблиця виконує повторне гешування (rehash) після того, як коефіцієнт заповнення перевищив поріг?

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

Яке значення постфіксного виразу 3 4 + 2 * ?

1. A24
2. B14
3. C10
4. D11

Який час роботи пошуку в ширину (BFS) у графі з V вершинами, що зберігається як матриця суміжності?

1. AO(V²)
2. BO(V)
3. CO(V + E)
4. DO(E log V)

Алгоритм Кана для топологічного сортування раз у раз видаляє вершини з напівстепенем входу 0. Яка структура зберігає ці вершини?

1. AСтек усіх відвіданих ребер
2. BМакс-купа, упорядкована за напівстепенем виходу
3. CМатриця суміжності, що фіксує, які вершини вже видалено
4. DЧерга (або будь-яка колекція) вершин із напівстепенем входу 0