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

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

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

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

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

1.Легка

Що робить операція peek (або top) стека?

  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.Середня

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

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

Який максимально можливий коефіцієнт заповнення геш-таблиці з відкритою адресацією?

  1. A0,5
  2. BМаксимуму немає
  3. C1
  4. D2
6.Середня

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

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

Яку гарантію щодо висоти дерева з n ключами дають правила червоно-чорного дерева?

  1. AВисота щонайбільше log2 n + 1
  2. BВисота щонайбільше n / 2
  3. CВисота щонайбільше 2 log2(n + 1)
  4. DВисота рівно log2 n
8.Складна

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

  1. AГеш-значення мусять бути простими числами
  2. BРівні геш-значення означають рівні ключі
  3. CРівні ключі мусять мати рівні геш-значення
  4. DРізні ключі мусять мати різні геш-значення

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

  1. 1. D · Повертає верхній елемент, не видаляючи його
  2. 2. B · Граф, ребра якого мають напрямок від однієї вершини до іншої
  3. 3. D · Два різні ключі відображаються в один індекс
  4. 4. A · У двозв'язному списку
  5. 5. C · 1
  6. 6. A · O(V + E)
  7. 7. C · Висота щонайбільше 2 log2(n + 1)
  8. 8. C · Рівні ключі мусять мати рівні геш-значення

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