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

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

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

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

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

1.Легка

Геш-таблиця (hash table) зберігає дані у вигляді:

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

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

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

Що правильно щодо матриці суміжності неорієнтованого графа?

  1. AЇї головна діагональ завжди містить одиниці
  2. BВона завжди верхньотрикутна
  3. CВона симетрична відносно головної діагоналі
  4. DКожен рядок містить рівно одну 1
6.Середня

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

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

Структура union-find (система неперетинних множин) з об'єднанням за рангом і стисненням шляху має амортизовану вартість операції:

  1. AO(n)
  2. BРівно O(log n)
  3. CO(α(n)), обернена функція Аккермана, практично стала
  4. DO(n²)
8.Складна

Які витрати часу й додаткової пам'яті на обернення однозв'язного списку на місці?

  1. AO(n log n) часу та O(1) додаткової пам'яті
  2. BO(n) часу та O(1) додаткової пам'яті
  3. CO(1) часу та O(1) додаткової пам'яті
  4. DO(n) часу та O(n) додаткової пам'яті

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

  1. 1. C · Пар ключ–значення, розташування яких визначає геш-функція
  2. 2. C · У корені
  3. 3. D · Купу
  4. 4. C · В індексі ⌊(i − 1) / 2⌋
  5. 5. C · Вона симетрична відносно головної діагоналі
  6. 6. D · O(V²)
  7. 7. C · O(α(n)), обернена функція Аккермана, практично стала
  8. 8. B · O(n) часу та O(1) додаткової пам'яті

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