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

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

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

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

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

1.Легка

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

  1. ADequeue
  2. BEnqueue
  3. CInsert
  4. DPush
2.Легка

Яка операція має складність O(1) для масиву, але O(n) для однозв'язного списку?

  1. AЧитання першого елемента
  2. BВставлення на початок
  3. CДоступ до елемента з індексом i
  4. DВидалення головного елемента
3.Легка

Яка операція повільна в масиві, але швидка на початку зв'язного списку?

  1. AДоступ до 5-го елемента
  2. BВизначення довжини масиву фіксованого розміру
  3. CВставлення на початок
  4. DЧитання останнього елемента за індексом
4.Середня

Яка вартість вставлення елемента в середину масиву з n елементів?

  1. AO(n), бо наступні елементи доводиться зсувати
  2. BO(n²), бо кожен елемент переміщується n разів
  3. CO(log n) через бінарний пошук
  4. DO(1), бо індекс відомий
5.Середня

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

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

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

  1. AВ індексі i − 1
  2. BВ індексі ⌊i / 2⌋ + 1
  3. CВ індексі 2i + 1
  4. DВ індексі ⌊(i − 1) / 2⌋
7.Складна

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

  1. AO(V)
  2. BO(V²)
  3. CO(V + E)
  4. DO(E log V)
8.Складна

Для чого використовують структуру union-find в алгоритмі Краскала для мінімального кістякового дерева?

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

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

  1. 1. A · Dequeue
  2. 2. C · Доступ до елемента з індексом i
  3. 3. C · Вставлення на початок
  4. 4. A · O(n), бо наступні елементи доводиться зсувати
  5. 5. D · Пошуку за префіксом, наприклад автодоповнення
  6. 6. D · В індексі ⌊(i − 1) / 2⌋
  7. 7. B · O(V²)
  8. 8. A · Щоб перевірити, чи вже з'єднані два кінці ребра

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