Структуры данных: лист заданий с ответами

Бесплатный лист заданий для печати по теме «Структуры данных»: 8 задач от простых до экзаменационного уровня, с ответами. Распечатайте его или сохраните как PDF.

Новый лист заданийЗаниматься онлайн с подсказками

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что хранится для каждой вершины в представлении графа списками смежности?

  1. AКратчайший путь до каждой другой вершины
  2. BСписок соседних вершин
  3. CОбщее число рёбер графа
  4. DСтрока из V булевых значений
2.Лёгкая

Как называется операция очереди, удаляющая элемент из начала?

  1. ADequeue
  2. BInsert
  3. CEnqueue
  4. DPush
3.Лёгкая

Что такое дек (deque, двусторонняя очередь)?

  1. AСтруктура, допускающая вставку и удаление с обоих концов
  2. BОчередь, допускающая удаление только с конца
  3. CДве отдельные очереди в одном массиве
  4. DОчередь, отсортированная по приоритету
4.Средняя

Какая структура данных используется, чтобы проверить, сбалансированы ли скобки в «{[()]}»?

  1. AСтек
  2. BХеш-таблица
  3. CДвоичное дерево поиска
  4. DОчередь
5.Средняя

Симметричный обход (in-order) двоичного дерева поиска посещает ключи:

  1. AВсегда в порядке убывания
  2. BВ порядке вставки
  3. CПо уровням
  4. DВ порядке возрастания (отсортированно)
6.Средняя

Чему равно значение постфиксного выражения 3 4 + 2 * ?

  1. A14
  2. B10
  3. C24
  4. D11
7.Сложная

Сколько времени занимает поиск произвольного ключа в двоичной min-куче из n элементов?

  1. AO(log log n)
  2. BO(1)
  3. CO(log n)
  4. DO(n)
8.Сложная

В чём главное преимущество списка с пропусками (skip list) перед отсортированным связным списком?

  1. AОн хранит ключи без упорядочения
  2. BОн не использует дополнительной памяти
  3. CОжидаемый поиск за O(log n) благодаря нескольким уровням указателей вперёд
  4. DГарантированный поиск за O(1), потому что каждый узел хранит указатель на каждый другой узел

Ответы

  1. 1. B · Список соседних вершин
  2. 2. A · Dequeue
  3. 3. A · Структура, допускающая вставку и удаление с обоих концов
  4. 4. A · Стек
  5. 5. D · В порядке возрастания (отсортированно)
  6. 6. A · 14
  7. 7. D · O(n)
  8. 8. C · Ожидаемый поиск за O(log n) благодаря нескольким уровням указателей вперёд

Полные пошаговые решения: занимайтесь этой темой на examproblems.com.