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

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

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

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

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

Що містить кожен вузол двозв'язного списку?

1. AДві копії даних і один вказівник
2. BДані, вказівник на наступний вузол і вказівник на попередній вузол
3. CДані та два вказівники: один на наступний вузол і один на вузол після нього
4. DДані та лише вказівник на наступний вузол

У бінарній мін-купі, що зберігається в масиві (індексація з 0), діти вузла з індексом i розташовані на позиціях:

1. Ai + 1 і i + 2
2. Bi/2 і i/2 + 1
3. C2i і 2i + 1
4. D2i + 1 і 2i + 2

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

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

Префіксне дерево (trie) особливо ефективне для:

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

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

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

Як визначити, чи містить однозв'язний список цикл, використовуючи O(1) додаткової пам'яті?

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