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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

Что такое степень вершины в неориентированном графе?

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

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

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

Какова высота двоичного дерева поиска с n узлами в худшем случае, если ключи вставляются в отсортированном порядке?

  1. An (дерево превращается в связный список)
  2. Blog₂ n
  3. C1
  4. D√n
5.Средняя

Что верно для матрицы смежности неориентированного графа?

  1. AОна всегда верхнетреугольная
  2. BВ каждой строке ровно одна 1
  3. CНа её главной диагонали всегда стоят единицы
  4. DОна симметрична относительно главной диагонали
6.Средняя

Кольцевой буфер (ring buffer) обычно используют для реализации:

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

Вставка ключа в АВЛ-дерево делает левое поддерево узла слишком высоким, причём новый ключ попал в левое поддерево его левого потомка (случай левый–левый). Какое исправление применяется?

  1. AПерекрашивание узла и его потомка
  2. BОдиночный левый поворот в несбалансированном узле
  3. CЛевый поворот в потомке, затем правый поворот в узле
  4. DОдиночный правый поворот в несбалансированном узле
8.Сложная

Какому правилу должны подчиняться хеш и равенство, чтобы хеш-таблица работала правильно?

  1. AИз равенства хешей следует равенство ключей
  2. BЗначения хеша должны быть простыми числами
  3. CРазные ключи должны иметь разные значения хеша
  4. DРавные ключи должны иметь равные значения хеша

Ответы

  1. 1. C · Возвращает верхний элемент, не удаляя его
  2. 2. C · Число инцидентных ей рёбер
  3. 3. A · Доступ к элементу с индексом i
  4. 4. A · n (дерево превращается в связный список)
  5. 5. D · Она симметрична относительно главной диагонали
  6. 6. A · Очереди фиксированного размера
  7. 7. D · Одиночный правый поворот в несбалансированном узле
  8. 8. D · Равные ключи должны иметь равные значения хеша

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