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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что такое цикл в графе?

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

Какая операция медленная в массиве, но быстрая в начале связного списка?

  1. AОпределение длины массива фиксированного размера
  2. BЧтение последнего элемента по индексу
  3. CДоступ к 5-му элементу
  4. DВставка в начало
3.Лёгкая

В чём главное отличие статического массива от динамического?

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

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

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

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

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

Каков максимально возможный коэффициент заполнения хеш-таблицы с открытой адресацией?

  1. A2
  2. BМаксимума нет
  3. C1
  4. D0,5
7.Сложная

Временная сложность операции decrease-key в двоичной куче (при известной позиции элемента) составляет:

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

В кольцевом буфере front == rear может означать и «пуст», и «полон». Какой распространённый способ их различить?

  1. AХранить front и rear в одной переменной
  2. BДелать размер буфера степенью двойки
  3. CХранить отдельный счётчик элементов или всегда оставлять одну ячейку свободной
  4. DВсегда очищать буфер, когда front равен rear, так что состояние — пустой

Ответы

  1. 1. A · Путь, который начинается и заканчивается в одной и той же вершине
  2. 2. D · Вставка в начало
  3. 3. C · Динамический массив может расти, переходя в больший блок памяти
  4. 4. C · O(V²)
  5. 5. A · O(n), потому что последующие элементы нужно сдвинуть
  6. 6. C · 1
  7. 7. D · O(log n)
  8. 8. C · Хранить отдельный счётчик элементов или всегда оставлять одну ячейку свободной

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