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

Безкоштовний робочий аркуш для друку «Структури даних»: 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.Середня

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

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

Чергу реалізовано двома стеками: push у стек «in» і pop зі стека «out», який поповнюють із «in», коли він порожній. Яка амортизована вартість однієї операції?

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

Симетричний обхід (in-order) бінарного дерева пошуку відвідує ключі:

  1. AУ порядку зростання (відсортовано)
  2. BПо рівнях
  3. CУ порядку вставлення
  4. DЗавжди в порядку спадання
7.Складна

Видалення вузла з двома дітьми з бінарного дерева пошуку зазвичай виконують так:

  1. AМіняють його місцями з коренем
  2. BЗамінюють його in-order наступником (або попередником) і видаляють той вузол
  3. CПеребудовують піддерево під ним з нуля й повторно вставляють усі ключі, які воно містило
  4. DВидаляють усе піддерево
8.Складна

Алгоритм Кана для топологічного сортування раз у раз видаляє вершини з напівстепенем входу 0. Яка структура зберігає ці вершини?

  1. AМакс-купа, упорядкована за напівстепенем виходу
  2. BМатриця суміжності, що фіксує, які вершини вже видалено
  3. CЧерга (або будь-яка колекція) вершин із напівстепенем входу 0
  4. DСтек усіх відвіданих ребер

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

  1. 1. A · Кількість ребер, з'єднаних із нею
  2. 2. C · Черга
  3. 3. D · Одним суцільним блоком, один за одним
  4. 4. D · O(L), незалежно від кількості збережених слів
  5. 5. A · O(1)
  6. 6. A · У порядку зростання (відсортовано)
  7. 7. B · Замінюють його in-order наступником (або попередником) і видаляють той вузол
  8. 8. C · Черга (або будь-яка колекція) вершин із напівстепенем входу 0

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