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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Какая структура данных лучше всего подходит для функции «отменить» (undo) в текстовом редакторе?

  1. AОчередь
  2. BХеш-множество
  3. CСтек
  4. DГраф
2.Лёгкая

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

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

Глубина узла в дереве — это:

  1. AЧисло рёбер от корня до этого узла
  2. BЧисло узлов в его поддереве
  3. CЧисло потомков этого узла
  4. DЧисло рёбер от этого узла до самого глубокого листа
4.Средняя

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

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

Какую структуру данных использует выполняющаяся программа для отслеживания активных вызовов функций и их локальных переменных?

  1. AДвоичное дерево поиска кадров
  2. BСтек вызовов
  3. CХеш-таблицу функций
  4. DОчередь памяти кучи
6.Средняя

Префиксное дерево (trie) особенно эффективно для:

  1. AПоиска по префиксу, например автодополнения
  2. BПоиска кратчайших путей
  3. CСортировки чисел
  4. DХранения матриц
7.Сложная

Каково при простом равномерном хешировании ожидаемое время поиска в хеш-таблице с цепочками, n ключами и m корзинами?

  1. AO(n)
  2. BO(m)
  3. CO(log n)
  4. DO(1 + α), где α = n / m
8.Сложная

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

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

Ответы

  1. 1. C · Стек
  2. 2. D · Вставка в начало
  3. 3. A · Число рёбер от корня до этого узла
  4. 4. C · Она симметрична относительно главной диагонали
  5. 5. B · Стек вызовов
  6. 6. A · Поиска по префиксу, например автодополнения
  7. 7. D · O(1 + α), где α = n / m
  8. 8. A · O(n) времени и O(1) дополнительной памяти

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