Алгоритми та структури даних: тренувальні задачі й екзаменаційні питання

Нотація «O велике», час виконання поширених алгоритмів і компроміси між масивами, зв’язними списками, деревами, геш-таблицями й графами.

Тренуйте цей курс безкоштовноТренувати цей курсСкласти пробний іспитБезкоштовних задач щодня: 5. Без картки.

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

Теми цього курсу

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

Поради до іспиту: Алгоритми та структури даних

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

Розв’язані приклади

Алгоритми та складністьЛегка

Яка нотація описує верхню межу зростання?

  1. AВелике Омега
  2. BМале омега
  3. CВелике O
  4. DВелике Тета
Показати підказки
  1. «Не більше ніж».
  2. Дві неправильні відповіді тепер закреслено. Одна з двох решти правильна.
Показати відповідь і пояснення

Чому це відповідь

O задає верхню межу, Ω — нижню межу, а Θ — точну (асимптотично щільну) межу.

Відповідь

C · Велике O
Структури данихСередня

Як працює extract-min у бінарній мін-купі?

  1. AВидаляють останній елемент масиву
  2. BОстанній елемент переміщують у корінь і просіюють униз
  3. CВидаляють корінь і зсувають усі елементи на одну позицію ліворуч
  4. DШукають новий мінімум серед усіх листків
Показати підказки
  1. Збережіть повноту дерева, а потім виправте порядок.
  2. Дві неправильні відповіді тепер закреслено. Одна з двох решти правильна.
Показати відповідь і пояснення

Чому це відповідь

Останній елемент заповнює порожнє місце в корені й обмінюється з меншою дитиною, доки не виконується властивість купи, що займає O(log n).

Відповідь

B · Останній елемент переміщують у корінь і просіюють униз

Як проходить тренування

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

Пов’язані курси

Основи інформатикиДискретна математикаКомп’ютерні мережі
Тренуйте цей курс безкоштовноТренувати цей курсСкласти пробний іспитБезкоштовних задач щодня: 5. Без картки.