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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

Что такое свойство max-кучи?

  1. AКлюч каждого левого потомка больше или равен ключу его правого соседа
  2. BКлючи отсортированы слева направо
  3. CВсе листья содержат максимальный ключ
  4. DКлюч каждого родителя больше или равен ключам его потомков
3.Лёгкая

Хеш-таблица (hash table) хранит данные в виде:

  1. AПар ключ–значение, расположение которых определяет хеш-функция
  2. BТолько отсортированного списка
  3. CДерева с упорядоченными ключами
  4. DСтроки фиксированной длины
4.Средняя

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

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

Сколько времени занимает проверка существования ребра (u, v) с помощью матрицы смежности?

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

Почему двоичную кучу можно хранить в массиве без каких-либо указателей?

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

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

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

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

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

Ответы

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

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