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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что хранит отображение (map, словарь)?

  1. AПары ключ–значение с уникальными ключами
  2. BТолько значения в порядке вставки
  3. CЗначения, отсортированные по размеру
  4. DПары одинаковых ключей
2.Лёгкая

Где находится наименьший элемент двоичной min-кучи?

  1. AВ каком-то листе, который придётся искать
  2. BВ корне
  3. CВ последней позиции массива
  4. DВ самом левом листе
3.Лёгкая

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

  1. AОно хранит пары ключ–значение
  2. BОно допускает доступ только с одного конца
  3. CОно хранит элементы без повторений
  4. DОно хранит элементы в отсортированном порядке
4.Средняя

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

  1. AO(V + E)
  2. BO(V × E)
  3. CO(V²)
  4. DO(E²)
5.Средняя

Очередь реализована двумя стеками: push в стек «in», pop из стека «out», который при опустошении заполняется из «in». Какова амортизированная стоимость одной операции?

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

Как работает extract-min в двоичной min-куче?

  1. AУдаляют последний элемент массива
  2. BПоследний элемент перемещают в корень и опускают вниз (sift down)
  3. CУдаляют корень и сдвигают все элементы на одну позицию влево
  4. DИщут новый минимум среди всех листьев
7.Сложная

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

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

Чем radix-дерево (сжатое префиксное дерево) лучше обычного trie?

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

Ответы

  1. 1. A · Пары ключ–значение с уникальными ключами
  2. 2. B · В корне
  3. 3. C · Оно хранит элементы без повторений
  4. 4. A · O(V + E)
  5. 5. A · O(1)
  6. 6. B · Последний элемент перемещают в корень и опускают вниз (sift down)
  7. 7. A · Поворотами поднимает узел, к которому обращались, в корень
  8. 8. D · Оно сливает цепочки узлов с одним потомком в одно ребро, помеченное строкой

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