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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

  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. AСтек
  2. BСбалансированное двоичное дерево поиска
  3. CНеотсортированный связный список
  4. DХеш-таблица
5.Средняя

Симметричный обход (in-order) двоичного дерева поиска посещает ключи:

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

Какова стоимость вставки элемента в середину массива из n элементов?

  1. AO(1), потому что индекс известен
  2. BO(n), потому что последующие элементы нужно сдвинуть
  3. CO(n²), потому что каждый элемент сдвигается n раз
  4. DO(log n) из-за двоичного поиска
7.Сложная

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

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

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

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

Ответы

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

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