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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

  1. AАдрес первого узла
  2. BNull (узла нет)
  3. CЧисло узлов в списке
  4. DАдрес предыдущего узла
2.Лёгкая

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

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

В двоичном дереве поиска значения в левом поддереве узла:

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

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

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

Сколько памяти занимает матрица смежности графа с V вершинами?

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

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

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

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

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

Динамический массив удваивается при заполнении. Почему многие реализации уменьшают его, только когда он заполнен на четверть, а не наполовину?

  1. AЧтобы массив оставался отсортированным
  2. BПотому что уменьшение вдвое при половинном заполнении привело бы к потере элементов
  3. CЧтобы избежать повторных изменений размера, когда push и pop чередуются вблизи границы
  4. DПотому что распределитель памяти может освобождать память только четвертями блока

Ответы

  1. 1. B · Null (узла нет)
  2. 2. B · У каждого узла не более двух потомков
  3. 3. A · Меньше значения узла
  4. 4. D · O(L), независимо от числа хранимых слов
  5. 5. A · O(V²)
  6. 6. A · O(n), потому что последующие элементы нужно сдвинуть
  7. 7. D · Одиночный правый поворот в несбалансированном узле
  8. 8. C · Чтобы избежать повторных изменений размера, когда push и pop чередуются вблизи границы

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