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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

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

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

Как называется операция стека, добавляющая элемент на вершину?

  1. APush
  2. BEnqueue
  3. CPeek
  4. DPop
4.Средняя

Хеш-таблица размера 7 использует h(k) = k mod 7 и линейное пробирование. Где окажется 17 после вставки 10?

  1. AВ индексе 0
  2. BВ индексе 3
  3. CВ индексе 6
  4. DВ индексе 4
5.Средняя

АВЛ-деревья (AVL) и красно-чёрные деревья гарантируют:

  1. AХранение ключей в порядке вставки
  2. BВысоту O(log n) благодаря перебалансировке
  3. CЧто ни у одного узла нет двух потомков
  4. DПоиск за константное время в любом случае
6.Средняя

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

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

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

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

Какую проблему линейного пробирования в основном уменьшает двойное хеширование?

  1. AПервичную кластеризацию, при которой образуются длинные серии занятых ячеек
  2. BНеобходимость хранить ключи в таблице
  3. CНеобходимость в хеш-функции
  4. DСтоимость O(n) чтения значения по ключу

Ответы

  1. 1. D · Стек
  2. 2. B · Число инцидентных ей рёбер
  3. 3. A · Push
  4. 4. D · В индексе 4
  5. 5. B · Высоту O(log n) благодаря перебалансировке
  6. 6. A · Его помещают в конец массива и поднимают вверх (sift up), пока он нарушает свойство кучи
  7. 7. B · Левый поворот в левом потомке, затем правый поворот в узле
  8. 8. A · Первичную кластеризацию, при которой образуются длинные серии занятых ячеек

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