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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

В двоичном дереве поиска значения в левом поддереве узла:

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

Что содержит указатель next последнего узла односвязного списка?

  1. AАдрес первого узла
  2. BNull (узла нет)
  3. CАдрес предыдущего узла
  4. DЧисло узлов в списке
4.Средняя

Какова высота двоичного дерева поиска с n узлами в худшем случае, если ключи вставляются в отсортированном порядке?

  1. Alog₂ n
  2. Bn (дерево превращается в связный список)
  3. C√n
  4. D1
5.Средняя

Почему обход массива на практике часто гораздо быстрее обхода связного списка той же длины?

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

Сколько памяти занимают списки смежности для графа с V вершинами и E рёбрами?

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

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

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

Временная сложность операции decrease-key в двоичной куче (при известной позиции элемента) составляет:

  1. AO(log n)
  2. BO(1)
  3. CO(n log n)
  4. DO(n)

Ответы

  1. 1. B · Очередь
  2. 2. D · Меньше значения узла
  3. 3. B · Null (узла нет)
  4. 4. B · n (дерево превращается в связный список)
  5. 5. C · Элементы массива расположены непрерывно, поэтому хорошо используют кэш процессора
  6. 6. C · O(V + E)
  7. 7. A · Одиночный правый поворот в несбалансированном узле
  8. 8. A · O(log n)

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