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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что делает хеш-функция в хеш-таблице?

  1. AОтображает ключ в индекс таблицы
  2. BПодсчитывает, сколько ключей хранится
  3. CШифрует значения в таблице
  4. DСортирует ключи в таблице
2.Лёгкая

Что делает операция peek (или top) стека?

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

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

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

В дорожной сети 100 000 перекрёстков, каждый соединён примерно с 4 другими. Какое представление подходит лучше всего?

  1. AСписки смежности
  2. BМатрица смежности
  3. CОдин отсортированный массив вершин
  4. DДвоичная куча рёбер
5.Средняя

Как вставляется новый элемент в двоичную кучу?

  1. AЕго помещают в конец массива и поднимают вверх (sift up), пока он нарушает свойство кучи
  2. BЕго помещают в корень и опускают вниз
  3. CЕго вставляют в отсортированную позицию, сдвигая все бо́льшие элементы на одно место вправо
  4. DВсю кучу перестраивают с нуля
6.Средняя

Где в двоичной куче, хранящейся в массиве с индексацией от 0, находится родитель узла с индексом i?

  1. AВ индексе 2i + 1
  2. BВ индексе ⌊i / 2⌋ + 1
  3. CВ индексе ⌊(i − 1) / 2⌋
  4. DВ индексе i − 1
7.Сложная

Объект хранится как ключ в хеш-отображении, а затем меняется поле, используемое его хеш-функцией. Каков вероятный результат?

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

Вставка ключа в АВЛ-дерево делает левое поддерево узла слишком высоким, причём новый ключ попал в левое поддерево его левого потомка (случай левый–левый). Какое исправление применяется?

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

Ответы

  1. 1. A · Отображает ключ в индекс таблицы
  2. 2. A · Возвращает верхний элемент, не удаляя его
  3. 3. C · Вставка в начало
  4. 4. A · Списки смежности
  5. 5. A · Его помещают в конец массива и поднимают вверх (sift up), пока он нарушает свойство кучи
  6. 6. C · В индексе ⌊(i − 1) / 2⌋
  7. 7. B · Поиск объекта может не удаться, потому что он лежит в корзине своего старого хеша
  8. 8. B · Одиночный правый поворот в несбалансированном узле

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