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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

В чём главное отличие статического массива от динамического?

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

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

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

Как называется операция очереди, удаляющая элемент из начала?

  1. ADequeue
  2. BEnqueue
  3. CInsert
  4. DPush
4.Средняя

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

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

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

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

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

  1. A2i и 2i + 1
  2. Bi + 1 и i + 2
  3. C2i + 1 и 2i + 2
  4. Di/2 и i/2 + 1
7.Сложная

В BST с корнем 50, левым поддеревом 30 (потомки 20, 40) и правым поддеревом 70 (потомки 60, 80) корень удаляют с помощью in-order преемника. Какой ключ станет новым корнем?

  1. A40
  2. B60
  3. C70
  4. D80
8.Сложная

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

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

Ответы

  1. 1. B · Динамический массив может расти, переходя в больший блок памяти
  2. 2. C · Null (узла нет)
  3. 3. A · Dequeue
  4. 4. A · Очереди фиксированного размера
  5. 5. B · O(1)
  6. 6. C · 2i + 1 и 2i + 2
  7. 7. B · 60
  8. 8. D · O(n) времени и O(1) дополнительной памяти

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