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

Безкоштовний робочий аркуш для друку «Структури даних»: 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. AO(1)
  2. BO(log n)
  3. CO(n)
  4. DO(n log n)
5.Середня

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

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

Ви маєте посилання на вузол у середині списку. У якому списку його можна видалити за O(1)?

  1. AУ двозв'язному списку
  2. BУ відсортованому масиві
  3. CВ однозв'язному списку
  4. DУ динамічному масиві
7.Складна

Вузол AVL-дерева незбалансований, бо праве піддерево його лівої дитини стало надто високим (випадок «ліво-право»). Яке виправлення застосовують?

  1. AОдинарний лівий поворот у вузлі
  2. BЛівий поворот у лівій дитині, потім правий поворот у вузлі
  3. CОдинарний правий поворот у вузлі
  4. DПравий поворот у лівій дитині, потім лівий поворот у вузлі
8.Складна

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

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

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

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

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