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

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

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

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

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

1.Легка

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

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

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

  1. APop
  2. BPeek
  3. CEnqueue
  4. DPush
3.Легка

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

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

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

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

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

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

Яке значення постфіксного виразу 3 4 + 2 * ?

  1. A11
  2. B14
  3. C10
  4. D24
7.Складна

Чому бази даних для індексів часто використовують B+ дерева, а не звичайні B-дерева?

  1. AB+ дерева використовують бінарні внутрішні вузли, що зменшує кількість зчитувань із диска
  2. BУсі записи розташовані у зв'язаних листках, що робить сканування діапазонів ефективним
  3. CB+ дерева зберігають дані лише в корені
  4. DB+ дерева не потребують збалансування
8.Складна

Часова складність операції decrease-key у бінарній купі (за відомої позиції елемента) становить:

  1. AO(1)
  2. BO(n)
  3. CO(log n)
  4. DO(n log n)

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

  1. 1. D · Два різні ключі відображаються в один індекс
  2. 2. D · Push
  3. 3. C · Список сусідніх вершин
  4. 4. B · O(n), бо наступні елементи доводиться зсувати
  5. 5. D · O(V²)
  6. 6. B · 14
  7. 7. B · Усі записи розташовані у зв'язаних листках, що робить сканування діапазонів ефективним
  8. 8. C · O(log n)

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