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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

Что хранит отображение (map, словарь)?

  1. AПары одинаковых ключей
  2. BЗначения, отсортированные по размеру
  3. CПары ключ–значение с уникальными ключами
  4. DТолько значения в порядке вставки
3.Лёгкая

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

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

Какова временная сложность поиска ключа в сбалансированном двоичном дереве поиска?

  1. AO(n)
  2. BO(1)
  3. CO(n log n)
  4. DO(log n)
5.Средняя

Что верно для матрицы смежности неориентированного графа?

  1. AОна всегда верхнетреугольная
  2. BВ каждой строке ровно одна 1
  3. CОна симметрична относительно главной диагонали
  4. DНа её главной диагонали всегда стоят единицы
6.Средняя

Сколько времени занимает поиск слова длины L в префиксном дереве (trie) с фиксированным алфавитом?

  1. AO(L), независимо от числа хранимых слов
  2. BO(log n), где n — число слов
  3. CO(L × n)
  4. DO(n), где n — число слов
7.Сложная

В кольцевом буфере front == rear может означать и «пуст», и «полон». Какой распространённый способ их различить?

  1. AВсегда очищать буфер, когда front равен rear, так что состояние — пустой
  2. BДелать размер буфера степенью двойки
  3. CХранить отдельный счётчик элементов или всегда оставлять одну ячейку свободной
  4. DХранить front и rear в одной переменной
8.Сложная

Ключи 5, 3, 8, 1 вставляются в таком порядке в пустую двоичную min-кучу на массиве. Каков итоговый массив?

  1. A[1, 3, 8, 5]
  2. B[1, 3, 5, 8]
  3. C[3, 1, 8, 5]
  4. D[1, 5, 8, 3]

Ответы

  1. 1. B · Кучу
  2. 2. C · Пары ключ–значение с уникальными ключами
  3. 3. B · Структура, допускающая вставку и удаление с обоих концов
  4. 4. D · O(log n)
  5. 5. C · Она симметрична относительно главной диагонали
  6. 6. A · O(L), независимо от числа хранимых слов
  7. 7. C · Хранить отдельный счётчик элементов или всегда оставлять одну ячейку свободной
  8. 8. A · [1, 3, 8, 5]

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