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

Бесплатный лист заданий для печати по теме «Структуры данных»: 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.Средняя

Зачем нужен сторожевой (фиктивный, sentinel) узел в связном списке?

  1. AЧтобы список был отсортирован
  2. BЧтобы упростить код, убрав особые случаи в голове или хвосте
  3. CЧтобы список не мог вырасти сверх фиксированного максимального числа узлов
  4. DЧтобы хранить число элементов
5.Средняя

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

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

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

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

Почему B-деревья используются в базах данных и файловых системах?

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

Алгоритм Кана для топологической сортировки многократно удаляет вершины с полустепенью захода 0. Какая структура хранит эти вершины?

  1. AСтек всех посещённых рёбер
  2. BМатрица смежности, фиксирующая, какие вершины уже удалены
  3. CMax-куча, упорядоченная по полустепени исхода
  4. DОчередь (или любая коллекция) вершин с полустепенью захода 0

Ответы

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

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