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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

Как элементы массива хранятся в памяти?

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

Какая операция выполняется за O(1) для массива, но за O(n) для односвязного списка?

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

Сколько памяти занимает матрица смежности графа с V вершинами?

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

Сколько узлов в идеальном (perfect) двоичном дереве высоты h, если высота считается в рёбрах?

  1. A2h+1 − 1
  2. B2h + 1
  3. C2h
  4. Dh2
6.Средняя

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

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

Какое свойство поддерживает любое B-дерево идеально сбалансированным?

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

Сколько времени занимает поиск произвольного ключа в двоичной min-куче из n элементов?

  1. AO(log log n)
  2. BO(1)
  3. CO(log n)
  4. DO(n)

Ответы

  1. 1. A · Отображает ключ в индекс таблицы
  2. 2. C · В одном непрерывном блоке, один за другим
  3. 3. B · Доступ к элементу с индексом i
  4. 4. A · O(V²)
  5. 5. A · 2h+1 − 1
  6. 6. C · Стек вызовов
  7. 7. D · Все листья находятся на одной глубине
  8. 8. D · O(n)

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