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

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

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

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

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

1.Легка

Як елементи масиву зберігаються в пам'яті?

  1. AУ випадкових місцях, обраних гешем
  2. BУ дереві сторінок пам'яті
  3. CРозкидано, зв'язані вказівниками
  4. DОдним суцільним блоком, один за одним
2.Легка

Що таке вузли-брати (siblings) у дереві?

  1. AВузли на однаковій глибині в різних піддеревах
  2. BВузли зі спільним батьком
  3. CВузли без дітей
  4. DВузол і його батько
3.Легка

Яку структуру даних використовують для обходу дерева по рівнях?

  1. AЧергу з пріоритетом
  2. BСтек
  3. CЧергу
  4. DГеш-таблицю
4.Середня

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

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

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

  1. A11
  2. B10
  3. C14
  4. D24
6.Середня

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

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

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

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

Для кожного елемента масиву потрібно знайти наступний більший елемент праворуч від нього за загальний час O(n). Яка структура допоможе?

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

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

  1. 1. D · Одним суцільним блоком, один за одним
  2. 2. B · Вузли зі спільним батьком
  3. 3. C · Чергу
  4. 4. C · O(V + E)
  5. 5. C · 14
  6. 6. D · Список суміжності
  7. 7. B · Замінюють його in-order наступником (або попередником) і видаляють той вузол
  8. 8. D · Стек, що зберігає елементи, які чекають на свою відповідь

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