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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Какая структура данных лучше всего подходит для функции «отменить» (undo) в текстовом редакторе?

  1. AХеш-множество
  2. BОчередь
  3. CГраф
  4. DСтек
2.Лёгкая

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

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

Что такое узлы-братья (siblings) в дереве?

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

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

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

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

  1. AВ индексе ⌊(i − 1) / 2⌋
  2. BВ индексе i − 1
  3. CВ индексе 2i + 1
  4. DВ индексе ⌊i / 2⌋ + 1
6.Средняя

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

  1. AO(V²)
  2. BO(V + E)
  3. CO(E)
  4. DO(log V)
7.Сложная

Какая структура данных обеспечивает кэш LRU (least recently used) с операциями get и put за O(1)?

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

Каково время работы поиска в ширину на графе с V вершинами, хранящемся в виде матрицы смежности?

  1. AO(V)
  2. BO(V²)
  3. CO(E log V)
  4. DO(V + E)

Ответы

  1. 1. D · Стек
  2. 2. D · Стек
  3. 3. A · Узлы с общим родителем
  4. 4. A · Его помещают в конец массива и поднимают вверх (sift up), пока он нарушает свойство кучи
  5. 5. A · В индексе ⌊(i − 1) / 2⌋
  6. 6. A · O(V²)
  7. 7. B · Хеш-таблица в сочетании с двусвязным списком
  8. 8. B · O(V²)

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