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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что такое дек (deque, двусторонняя очередь)?

  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.Средняя

У двоичного дерева корень 1 с левым потомком 2 и правым потомком 3; у узла 2 потомки 4 (левый) и 5 (правый). Каков обратный обход (postorder)?

  1. A5 4 3 2 1
  2. B4 2 5 1 3
  3. C4 5 2 3 1
  4. D1 2 4 5 3
5.Средняя

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

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

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

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

Временная сложность операции decrease-key в двоичной куче (при известной позиции элемента) составляет:

  1. AO(n log n)
  2. BO(n)
  3. CO(1)
  4. DO(log n)
8.Сложная

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

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

Ответы

  1. 1. A · Структура, допускающая вставку и удаление с обоих концов
  2. 2. A · У каждого узла не более двух потомков
  3. 3. C · В одном непрерывном блоке, один за другим
  4. 4. C · 4 5 2 3 1
  5. 5. C · В двусвязном списке
  6. 6. B · O(V + E)
  7. 7. D · O(log n)
  8. 8. D · O(V²)

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