Алгоритмы и структуры данных: тренировочные задачи и экзаменационные вопросы

Нотация «O большое», время работы распространённых алгоритмов и компромиссы между массивами, связными списками, деревьями, хеш-таблицами и графами.

Занимайтесь по этому курсу бесплатноЗаниматься по этому курсуПройти пробный экзаменБесплатных задач каждый день: 5. Без карты.

Шпаргалка-пакет (PDF)Листы формул, шаги методов и тренировочные задачи с полными решениями, готовые к печати.

Темы этого курса

  1. Алгоритмы и сложностьключевые термины и факты · применение понятий · кейсы и анализтест
  2. Структуры данныхключевые термины и факты · применение понятий · кейсы и анализтест
  3. Теория графовстепени и рёбра · эйлеровы пути и деревья · кратчайшие пути и остовные деревьярасчёты

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

  • Для вложенных циклов число итераций перемножается; для последовательных циклов оставляйте больший член.
  • Знайте стоимость поиска, вставки и удаления для каждой структуры данных.
  • Если на каждом шаге входные данные уменьшаются вдвое, время будет логарифмическим.

Разобранные примеры

Алгоритмы и сложностьЛёгкая

Какая нотация описывает верхнюю границу роста?

  1. AОмега-большое
  2. BОмега-малое
  3. CO-большое
  4. DТета-большое
Показать подсказки
  1. «Не более чем».
  2. Два неверных ответа теперь зачёркнуты. Один из двух оставшихся верный.
Показать ответ и объяснение

Почему это ответ

O задаёт верхнюю границу, Ω — нижнюю, а Θ — точную (асимптотически точную) границу.

Ответ

C · O-большое
Структуры данныхСредняя

Как работает extract-min в двоичной min-куче?

  1. AУдаляют последний элемент массива
  2. BПоследний элемент перемещают в корень и опускают вниз (sift down)
  3. CУдаляют корень и сдвигают все элементы на одну позицию влево
  4. DИщут новый минимум среди всех листьев
Показать подсказки
  1. Сохраните полноту дерева, затем исправьте порядок.
  2. Два неверных ответа теперь зачёркнуты. Один из двух оставшихся верный.
Показать ответ и объяснение

Почему это ответ

Последний элемент заполняет «дыру» в корне и меняется местами с меньшим потомком, пока не выполнится свойство кучи; это занимает O(log n).

Ответ

B · Последний элемент перемещают в корень и опускают вниз (sift down)

Как проходят занятия

  • «Заниматься по этому курсу» смешивает задачи из всех его тем, как на настоящем экзамене.
  • В каждой задаче новые значения, поэтому вы учите метод, а не ответ.
  • Застряли? Сначала откройте небольшую подсказку, а полное объяснение — только когда оно понадобится.
  • Пробные экзамены ограничены по времени и идут без подсказок, а в конце вы получаете результат и полный разбор.

Похожие курсы

Основы информатикиДискретная математикаКомпьютерные сети
Занимайтесь по этому курсу бесплатноЗаниматься по этому курсуПройти пробный экзаменБесплатных задач каждый день: 5. Без карты.