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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

Что такое коэффициент заполнения (load factor) хеш-таблицы?

  1. AЧисло коллизий на данный момент
  2. BЧисло корзин, делённое на среднюю длину хранимых ключей
  3. CВремя загрузки таблицы с диска
  4. DЧисло хранимых элементов, делённое на число корзин
3.Лёгкая

Что определяет двоичное дерево?

  1. AУ каждого узла не более двух потомков
  2. BКаждый узел хранит двоичное число
  3. CВ дереве ровно два уровня
  4. DУ каждого узла ровно два потомка
4.Средняя

Что происходит, когда хеш-таблица выполняет рехеширование после превышения порога коэффициента заполнения?

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

Какова стоимость вставки элемента в середину массива из n элементов?

  1. AO(n), потому что последующие элементы нужно сдвинуть
  2. BO(1), потому что индекс известен
  3. CO(n²), потому что каждый элемент сдвигается n раз
  4. DO(log n) из-за двоичного поиска
6.Средняя

Симметричный обход (in-order) двоичного дерева поиска посещает ключи:

  1. AВ порядке возрастания (отсортированно)
  2. BПо уровням
  3. CВ порядке вставки
  4. DВсегда в порядке убывания
7.Сложная

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

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

Для чего используется структура union-find в алгоритме Краскала построения минимального остовного дерева?

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

Ответы

  1. 1. C · Число рёбер от корня до этого узла
  2. 2. D · Число хранимых элементов, делённое на число корзин
  3. 3. A · У каждого узла не более двух потомков
  4. 4. B · Выделяется таблица большего размера, и каждый ключ вставляется заново
  5. 5. A · O(n), потому что последующие элементы нужно сдвинуть
  6. 6. A · В порядке возрастания (отсортированно)
  7. 7. A · Хранить отдельный счётчик элементов или всегда оставлять одну ячейку свободной
  8. 8. C · Для проверки, соединены ли уже два конца ребра

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