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

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

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

Що таке колізія в геш-таблиці?

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

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

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

Який максимально можливий коефіцієнт заповнення геш-таблиці з відкритою адресацією?

1. A2
2. B1
3. CМаксимуму немає
4. D0,5

Чергу реалізовано двома стеками: push у стек «in» і pop зі стека «out», який поповнюють із «in», коли він порожній. Яка амортизована вартість однієї операції?

1. AO(1)
2. BO(n²)
3. CO(n)
4. DO(log n)

Яка часова складність пошуку ключа в збалансованому бінарному дереві пошуку?

1. AO(n)
2. BO(n log n)
3. CO(1)
4. DO(log n)

Яка основна перевага списку з пропусками (skip list) над відсортованим зв'язним списком?

1. AВін не використовує додаткової пам'яті
2. BГарантований пошук за O(1), бо кожен вузол зберігає вказівник на кожен інший вузол
3. CВін зберігає ключі без упорядкування
4. DОчікуваний пошук за O(log n) завдяки кільком рівням вказівників уперед

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

1. AБо зменшення вдвічі за половинного заповнення призвело б до втрати елементів
2. BЩоб уникнути повторних змін розміру, коли push і pop чергуються біля межі
3. CЩоб масив залишався відсортованим
4. DБо розподілювач пам'яті може звільняти пам'ять лише чвертями блока