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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

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

  1. AОчередь
  2. BКуча
  3. CСтек
  4. DБинарное дерево
3.Лёгкая

Какую структуру обычно используют для реализации очереди с приоритетом?

  1. AСтек
  2. BКучу
  3. CНеупорядоченный односвязный список
  4. DСтроку
4.Средняя

Что происходит, когда хеш-таблица выполняет рехеширование после превышения порога коэффициента заполнения?

  1. AВ новый список переполнения в конце таблицы переносятся только конфликтующие ключи
  2. BСамые старые ключи удаляются, чтобы освободить место
  3. CСуществующие ключи сортируются на месте
  4. DВыделяется таблица большего размера, и каждый ключ вставляется заново
5.Средняя

Какой абстрактный тип данных использует алгоритм Дейкстры для выбора следующей обрабатываемой вершины?

  1. AСтек
  2. BОчередь с приоритетом по минимуму
  3. CОчередь FIFO
  4. DМножество без упорядочения
6.Средняя

Кольцевой буфер (ring buffer) обычно используют для реализации:

  1. AОбхода графа
  2. BХеш-функции
  3. CДвоичного дерева поиска
  4. DОчереди фиксированного размера
7.Сложная

Какое утверждение о пирамидальной сортировке (heapsort) верно?

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

Узел АВЛ-дерева разбалансирован, потому что правое поддерево его левого потомка стало слишком высоким (случай левый–правый). Какое исправление применяется?

  1. AПравый поворот в левом потомке, затем левый поворот в узле
  2. BОдиночный правый поворот в узле
  3. CОдиночный левый поворот в узле
  4. DЛевый поворот в левом потомке, затем правый поворот в узле

Ответы

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

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