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

Безкоштовний робочий аркуш для друку «Структури даних»: 8 задач від легких до рівня іспиту, з ключем відповідей. Роздрукуйте його або збережіть як PDF.

Новий робочий аркушТренуватися онлайн з підказками

Для викладачів: можна безкоштовно друкувати, копіювати й використовувати на заняттях. Кожен новий аркуш має нові значення і власні відповіді. Будемо вдячні за посилання на ExamProblems на сторінці вашого курсу.

Ім’я: ____________________   Дата: ____________

1.Легка

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

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

Що таке орієнтований граф?

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

Яка головна відмінність між статичним і динамічним масивом?

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

Чому обхід масиву на практиці часто значно швидший, ніж обхід зв'язного списку такої самої довжини?

  1. AОбхід масиву загалом має складність O(1), а обхід зв'язного списку — O(n)
  2. BМасиви використовують менше інструкцій для порівняння значень
  3. CЗв'язні списки завжди зберігають елементи на диску
  4. DЕлементи масиву розташовані суцільно, тож добре використовують кеш процесора
5.Середня

Який метод розв'язання колізій зберігає ключі, що конфліктують, у списку в тому самому кошику?

  1. AПодвійне гешування
  2. BКвадратичне зондування
  3. CМетод ланцюжків (separate chaining)
  4. DЛінійне зондування
6.Середня

Скільки триває пошук слова довжиною L у префіксному дереві (trie) з фіксованим алфавітом?

  1. AO(L), незалежно від кількості збережених слів
  2. BO(L × n)
  3. CO(log n), де n — кількість слів
  4. DO(n), де n — кількість слів
7.Складна

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

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

Якого правила мають дотримуватися геш і рівність, щоб геш-таблиця працювала правильно?

  1. AГеш-значення мусять бути простими числами
  2. BРізні ключі мусять мати різні геш-значення
  3. CРівні ключі мусять мати рівні геш-значення
  4. DРівні геш-значення означають рівні ключі

Ключ відповідей

  1. 1. C · Купу
  2. 2. D · Граф, ребра якого мають напрямок від однієї вершини до іншої
  3. 3. C · Динамічний масив може зростати, переміщуючись до більшого блоку пам'яті
  4. 4. D · Елементи масиву розташовані суцільно, тож добре використовують кеш процесора
  5. 5. C · Метод ланцюжків (separate chaining)
  6. 6. A · O(L), незалежно від кількості збережених слів
  7. 7. D · O(α(n)), обернена функція Аккермана, практично стала
  8. 8. C · Рівні ключі мусять мати рівні геш-значення

Повні покрокові розв’язки: тренуйте цю тему на examproblems.com.