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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

  1. APop
  2. BPeek
  3. CEnqueue
  4. DPush
2.Лёгкая

Что определяет двоичное дерево?

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

Что такое коллизия в хеш-таблице?

  1. AДва одинаковых ключа хранятся дважды
  2. BВ таблице заканчивается память
  3. CДва разных ключа отображаются в один и тот же индекс
  4. DКлюч вообще невозможно хешировать
4.Средняя

Сколько времени занимает поиск слова длины L в префиксном дереве (trie) с фиксированным алфавитом?

  1. AO(L), независимо от числа хранимых слов
  2. BO(log n), где n — число слов
  3. CO(n), где n — число слов
  4. DO(L × n)
5.Средняя

У вас есть ссылка на узел в середине списка. В каком списке его можно удалить за O(1)?

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

Как в кольцевой очереди, хранящейся в массиве ёмкостью n, вычисляется следующая позиция после индекса i?

  1. Ai + 1
  2. B2i + 1
  3. C(i + 1) mod n
  4. D(i − 1) mod n
7.Сложная

Фильтр Блума может ответить на вопрос «принадлежит ли этот элемент множеству?»:

  1. AС возможными ложноположительными, но без ложноотрицательных результатов
  2. BВсегда точно
  3. CС возможными ложноотрицательными, но без ложноположительных результатов
  4. DТолько для чисел
8.Сложная

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

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

Ответы

  1. 1. D · Push
  2. 2. A · У каждого узла не более двух потомков
  3. 3. C · Два разных ключа отображаются в один и тот же индекс
  4. 4. A · O(L), независимо от числа хранимых слов
  5. 5. C · В двусвязном списке
  6. 6. C · (i + 1) mod n
  7. 7. A · С возможными ложноположительными, но без ложноотрицательных результатов
  8. 8. D · Одиночный правый поворот в несбалансированном узле

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