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

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

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

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

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

1.Легка

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

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

Яка структура даних працює за принципом «першим прийшов — першим вийшов» (FIFO)?

  1. AБінарне дерево
  2. BКупа
  3. CЧерга
  4. DСтек
3.Легка

Яка визначальна риса множини як абстрактного типу даних?

  1. AВона зберігає елементи у відсортованому порядку
  2. BВона дозволяє доступ лише з одного кінця
  3. CВона зберігає елементи без дублікатів
  4. DВона зберігає пари ключ–значення
4.Середня

Скільки пам'яті використовує список суміжності для графа з V вершинами та E ребрами?

  1. AO(E²)
  2. BO(V + E)
  3. CO(V × E)
  4. DO(V²)
5.Середня

Дорожня мережа має 100,000 перехресть, кожне з'єднане приблизно з 4 іншими. Яке подання найдоречніше?

  1. AОдин відсортований масив вершин
  2. BСписок суміжності
  3. CБінарна купа ребер
  4. DМатриця суміжності
6.Середня

Кільцевий буфер (ring buffer) зазвичай використовують для реалізації:

  1. AЧерги фіксованого розміру
  2. BГеш-функції
  3. CБінарного дерева пошуку
  4. DОбходу графа
7.Складна

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

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

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

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

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

  1. 1. D · Два різні ключі відображаються в один індекс
  2. 2. C · Черга
  3. 3. C · Вона зберігає елементи без дублікатів
  4. 4. B · O(V + E)
  5. 5. B · Список суміжності
  6. 6. A · Черги фіксованого розміру
  7. 7. C · Лівий поворот у лівій дитині, потім правий поворот у вузлі
  8. 8. C · O(V²)

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