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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что содержит каждый узел двусвязного списка?

  1. AДанные и два указателя: один на следующий узел и один на узел после него
  2. BДанные, указатель на следующий узел и указатель на предыдущий узел
  3. CДве копии данных и один указатель
  4. DДанные и только указатель на следующий узел
2.Лёгкая

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

  1. AСтруктура, допускающая вставку и удаление с обоих концов
  2. BДве отдельные очереди в одном массиве
  3. CОчередь, отсортированная по приоритету
  4. DОчередь, допускающая удаление только с конца
3.Лёгкая

Глубина узла в дереве — это:

  1. AЧисло рёбер от корня до этого узла
  2. BЧисло узлов в его поддереве
  3. CЧисло потомков этого узла
  4. DЧисло рёбер от этого узла до самого глубокого листа
4.Средняя

Сколько времени занимает проверка существования ребра (u, v) с помощью матрицы смежности?

  1. AO(1)
  2. BO(E)
  3. CO(log V)
  4. DO(V)
5.Средняя

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

  1. A24
  2. B14
  3. C11
  4. D10
6.Средняя

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

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

Какова стоимость одной операции find в худшем случае в структуре union-find с n элементами без объединения по рангу и сжатия путей?

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

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

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

Ответы

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

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