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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

Что такое цикл в графе?

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

Что такое взвешенный граф?

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

Какая структура данных используется, чтобы проверить, сбалансированы ли скобки в «{[()]}»?

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

Префиксное дерево (trie) особенно эффективно для:

  1. AПоиска по префиксу, например автодополнения
  2. BСортировки чисел
  3. CХранения матриц
  4. DПоиска кратчайших путей
6.Средняя

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

  1. A14
  2. B24
  3. C10
  4. D11
7.Сложная

Удаление узла с двумя потомками из двоичного дерева поиска обычно выполняют так:

  1. AПерестраивают поддерево под ним с нуля и заново вставляют каждый содержавшийся в нём ключ
  2. BУдаляют всё поддерево
  3. CМеняют его местами с корнем
  4. DЗаменяют его in-order преемником (или предшественником) и удаляют тот узел
8.Сложная

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

  1. AОдиночный правый поворот в узле
  2. BЛевый поворот в левом потомке, затем правый поворот в узле
  3. CОдиночный левый поворот в узле
  4. DПравый поворот в левом потомке, затем левый поворот в узле

Ответы

  1. 1. C · Доступ к элементу с индексом i
  2. 2. B · Путь, который начинается и заканчивается в одной и той же вершине
  3. 3. D · Граф, в котором у каждого ребра есть числовое значение, например стоимость или расстояние
  4. 4. B · Стек
  5. 5. A · Поиска по префиксу, например автодополнения
  6. 6. A · 14
  7. 7. D · Заменяют его in-order преемником (или предшественником) и удаляют тот узел
  8. 8. B · Левый поворот в левом потомке, затем правый поворот в узле

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