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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

Какая операция выполняется за O(1) для массива, но за O(n) для односвязного списка?

  1. AЧтение первого элемента
  2. BУдаление головного элемента
  3. CДоступ к элементу с индексом i
  4. DВставка в начало
3.Лёгкая

Какая операция медленная в массиве, но быстрая в начале связного списка?

  1. AВставка в начало
  2. BЧтение последнего элемента по индексу
  3. CОпределение длины массива фиксированного размера
  4. DДоступ к 5-му элементу
4.Средняя

Ключи 50, 30, 70, 20, 40 вставляются в таком порядке в пустое двоичное дерево поиска. Кто левый потомок 30?

  1. A70
  2. B20
  3. C50
  4. D40
5.Средняя

В двоичной min-куче, хранящейся в массиве (индексация с 0), потомки узла с индексом i находятся на позициях:

  1. Ai + 1 и i + 2
  2. Bi/2 и i/2 + 1
  3. C2i + 1 и 2i + 2
  4. D2i и 2i + 1
6.Средняя

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

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

Каковы затраты времени и дополнительной памяти на разворот односвязного списка на месте?

  1. AO(n) времени и O(1) дополнительной памяти
  2. BO(1) времени и O(1) дополнительной памяти
  3. CO(n log n) времени и O(1) дополнительной памяти
  4. DO(n) времени и O(n) дополнительной памяти
8.Сложная

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

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

Ответы

  1. 1. C · Меньше значения узла
  2. 2. C · Доступ к элементу с индексом i
  3. 3. A · Вставка в начало
  4. 4. B · 20
  5. 5. C · 2i + 1 и 2i + 2
  6. 6. A · O(V + E)
  7. 7. A · O(n) времени и O(1) дополнительной памяти
  8. 8. A · Поворотами поднимает узел, к которому обращались, в корень

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