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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

Что такое коллизия в хеш-таблице?

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

В односвязном списке каждый узел содержит:

  1. AДанные и ссылки на все остальные узлы
  2. BДанные и ссылку на следующий узел
  3. CДанные и индекс
  4. DТолько данные
4.Средняя

Хеш-таблица размера 7 использует h(k) = k mod 7 и линейное пробирование. Где окажется 17 после вставки 10?

  1. AВ индексе 6
  2. BВ индексе 4
  3. CВ индексе 0
  4. DВ индексе 3
5.Средняя

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

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

В двоичной min-куче, хранящейся в массиве (индексация с 0), потомки узла с индексом i находятся на позициях:

  1. A2i и 2i + 1
  2. Bi + 1 и i + 2
  3. C2i + 1 и 2i + 2
  4. Di/2 и i/2 + 1
7.Сложная

Какую проблему линейного пробирования в основном уменьшает двойное хеширование?

  1. AНеобходимость в хеш-функции
  2. BПервичную кластеризацию, при которой образуются длинные серии занятых ячеек
  3. CНеобходимость хранить ключи в таблице
  4. DСтоимость O(n) чтения значения по ключу
8.Сложная

Фильтр Блума может ответить на вопрос «принадлежит ли этот элемент множеству?»:

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

Ответы

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

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