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

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

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

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

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

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

Ключи 50, 30, 70, 20, 40 вставляются в таком порядке в пустое двоичное дерево поиска. Кто левый потомок 30?

  1. A70
  2. B20
  3. C50
  4. D40
7.Сложная

Каково время работы поиска в ширину на графе с V вершинами, хранящемся в виде матрицы смежности?

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

Какие операции поддерживает за O(log n) дерево Фенвика (binary indexed tree) над массивом из n чисел?

  1. AПоиск медианы за O(1)
  2. BВставку элементов в любую позицию
  3. CЗапросы префиксных сумм и обновления отдельного элемента
  4. DСортировку массива и двоичный поиск

Ответы

  1. 1. D · Возвращает верхний элемент, не удаляя его
  2. 2. C · Кучу
  3. 3. C · Вершин (узлов), соединённых рёбрами
  4. 4. C · В порядке возрастания (отсортированно)
  5. 5. A · Стек
  6. 6. B · 20
  7. 7. D · O(V²)
  8. 8. C · Запросы префиксных сумм и обновления отдельного элемента

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