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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

Какая структура данных работает по принципу «первым пришёл — первым ушёл» (FIFO)?

  1. AКуча
  2. BБинарное дерево
  3. CСтек
  4. DОчередь
3.Лёгкая

Какая структура данных работает по принципу «последним пришёл — первым ушёл» (LIFO)?

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

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

  1. AОчередь FIFO
  2. BМножество без упорядочения
  3. CСтек
  4. DОчередь с приоритетом по минимуму
5.Средняя

У вас есть ссылка на узел в середине списка. В каком списке его можно удалить за O(1)?

  1. AВ двусвязном списке
  2. BВ динамическом массиве
  3. CВ односвязном списке
  4. DВ отсортированном массиве
6.Средняя

Чему равно значение постфиксного выражения 3 4 + 2 * ?

  1. A11
  2. B24
  3. C14
  4. D10
7.Сложная

Какие операции поддерживает за O(log n) дерево Фенвика (binary indexed tree) над массивом из n чисел?

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

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

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

Ответы

  1. 1. A · Вставка в начало
  2. 2. D · Очередь
  3. 3. D · Стек
  4. 4. D · Очередь с приоритетом по минимуму
  5. 5. A · В двусвязном списке
  6. 6. C · 14
  7. 7. D · Запросы префиксных сумм и обновления отдельного элемента
  8. 8. C · Первичную кластеризацию, при которой образуются длинные серии занятых ячеек

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