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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Какая структура данных работает по принципу «последним пришёл — первым ушёл» (LIFO)?

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

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

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

Хеш-таблица размера 7 использует h(k) = k mod 7 и линейное пробирование. Где окажется 17 после вставки 10?

  1. AВ индексе 0
  2. BВ индексе 6
  3. CВ индексе 3
  4. DВ индексе 4
6.Средняя

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

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

Что делает косое дерево (splay tree) после каждого обращения?

  1. AПерекрашивает узлы на пути поиска
  2. BПоворотами поднимает узел, к которому обращались, в корень
  3. CПерестраивает всё дерево в сбалансированном виде
  4. DПеремещает узел, к которому обращались, в лист
8.Сложная

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

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

Ответы

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

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