💯 Алгоритмы и структуры данных [Тема 1-4] — ответы на тесты Синергия / МОИ / МТИ / МосАП

Алгоритмы и структуры данных > Тест 1 / Тест 2 / Тест 3 / Тест 4 / Итоговый тест

• правильные ответы на вопросы из тестов по данной дисциплине
• вопросы отсортированы в лексикографическом порядке

Алгоритмы и структуры данных

• Тема 1. Основы алгоритмизации, основы оптимизации, алгоритмы на списковые структуры данных, алгоритмы на массивы.
• Тема 2. Алгоритмы поиска и сортировки, рекурсивные алгоритмы, численные алгоритмы, хэш
• Тема 3. Графы, алгоритмы на древовидные структуры данных.
• Тема 4. Полезные алгоритмы, алгоритмы на графы, строковые алгоритмы.
• Итоговая аттестация
• Анкета обратной связи

Абсолютное значение числа находится при помощи функции …

Тип ответа: Текcтовый ответ

АВЛ-дерево в программировании — это …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• бинарное дерево, несбалансированное по высоте
• дерево отрезков, сбалансированное по высоте
• бинарное дерево, сбалансированное по высоте
• дерево отрезков, несбалансированное по высоте

Алгоритм нахождения заданного значения, суть которого заключается в последовательном сравнении каждого элемента массива с искомым значением — это …

Тип ответа: Текcтовый ответ

Алгоритм нахождения частного двух чисел словесно можно описать в следующей последовательности:

Тип ответа: Сортировка

• 1 Объявить две переменные (делимое и делитель)
• 2 Присвоить значения переменным
• 3 Отсеять возможную ошибку, которая может быть связана с нулевым делителем
• 4 Найти частное (разделить делимое на делитель)
• 5 Записать результат в новую переменную

Алгоритм пузырьковой сортировки в наихудшем случае может иметь временную сложность, которая равна …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• O(n)
• O(n^2)
• O(1)
• O(n log n)

Алгоритм сортировки, который обычно использует функция std::sort(), имеет название …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• “Быстрая сортировка”
• “Сортировка вставкой”
• “Пузырьковая сортировка”
• “Сортировка слиянием”

Алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий, называется …

Тип ответа: Текcтовый ответ

Алгоритм, в котором действия выполняются однократно и строго последовательно, называется …

Тип ответа: Текcтовый ответ

Алгоритм, в котором команды повторяются некоторое количество раз подряд, называется …

Тип ответа: Текcтовый ответ

Алгоритм, выполняющий действия однократно и строго последовательно, называется ...

Тип ответа: Текcтовый ответ

Алгоритм, выполняющий либо одну, либо другую последовательность действий, в зависимости от условия, называется …

Тип ответа: Текcтовый ответ

Алгоритм, который находит кратчайшие пути от одного узла графа до всех остальных, имеющий название фамилии учёного, называется алгоритмом …

Тип ответа: Текcтовый ответ

Алгоритм, который последовательно делит пополам заранее отсортированный массив данных для поиска нужного элемента, называется …

Тип ответа: Текcтовый ответ

Алгоритм, повторяющий команды несколько раз подряд, называется …

Тип ответа: Текcтовый ответ

Алгоритмы в программировании часто используются с массивами. Массивы — это фундаментальные структуры данных, которые служат для хранения коллекций элементов. Понимание того, как эффективно манипулировать массивами и обрабатывать их, необходимо любому программисту. Для того, чтобы проверить ваши знания, вам потребуется правильно ответить на ряд вопросов. Какой индекс у первого элемента массива? Какая структура данных часто используется для реализации динамических массивов, которые автоматически изменяют размер по мере необходимости? Когда целесообразно использовать технику с двумя указателями при работе с массивами? Какая ключевая характеристика “разрежённого” массива?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• Индекс первого элемента массива равен нулю. Структура данных std::list часто используется для реализации динамических массивов. Технику с двумя указателями целесообразно использовать при бинарном поиске. Ключевая характеристика “разрежённого” массива заключается в наличии нулевых и NULL значений.
• Индекс первого элемента массива равен нулю. Структура данных std::vector часто используется для реализации динамических массивов. Технику с двумя указателями целесообразно использовать для решения задач с указателем, перемещающимся с каждого конца массива. Ключевая характеристика “разрежённого” массива — это содержание, в основном, нулевых или NULL значений.
• Индекс первого элемента массива равен нулю или единице, в зависимости от его типа. Структура данных std::queue часто используется для реализации динамических массивов. Технику с двумя указателями целесообразно использовать при реверсировании массива. Ключевая характеристика “разрежённого” массива заключается в том, что он содержит только простые числа.

Алгоритмы можно описать следующими способами:

Тип ответа: Множественный выбор • с выбором нескольких правильных ответов из предложенных вариантов

• обобщённым
• словесным
• программным
• графическим

Алгоритмы, которые на каждом шагу принимают локально оптимальное решение, не ориентируясь на глобальный результат, называются …

Тип ответа: Текcтовый ответ

Алгоритмы, принимающие на каждом шагу локально оптимальное решение, не ориентируясь на глобальный результат, называются …

Тип ответа: Текcтовый ответ

Бинарное полное дерево, все листья которого находятся на одном уровне, называется …

Тип ответа: Текcтовый ответ

В бинарном дереве с высотой 3 максимальное количество узлов равно …

Тип ответа: Текcтовый ответ

В бинарном дереве узел, находящийся на самом верху, называется …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• корневым
• листовым
• родительским
• дочерним

В графе представление связи или отношения между двумя узлами осуществляется при помощи …

Тип ответа: Текcтовый ответ

В графе циклом является …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• путь, который проходит через каждую вершину только один раз
• узел, не имеющий рёбер
• путь, который начинается и заканчивается в одном и том же узле
• набор узлов без рёбер

В дереве отрезков каждый листовой узел представляет собой …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• диапазон массива
• корень дерева
• один элемент массива
• двоичное значение

В информатике графом называют …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• математическое уравнение
• алгоритм сортировки
• коллекцию узлов и рёбер
• структуру данных, используемую для хранения текста

В направленном графе рёбра имеют …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• определённое направление
• несколько направлений
• только динамическую длину
• только статическую длину

В основном для поиска минимального остовного дерева в связном графе используется алгоритм …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• Дейкстры
• Прима
• поиска в глубину
• поиска в ширину

В основном рекурсивные алгоритмы чаще всего применяются в …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• инициализации переменных
• сортировке массивов
• нахождении факториалов чисел
• реверсировании строк

В программе объявлен и проинициализирован объект: std::string error{ “Invalid password!” }; Его значение выводится на экран.Каким будет вывод, если к объекту последовательно применить методы replace(8, 5, “username”, 4), append(“name”) и c_str()?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• Invalid username!
• Invalid user!name
• Invalid userord!name
• Invalid nameord!name

В программе объявлен и проинициализирован объект: std::string greeting{ “Hello World!!!” }; Его значение выводится на экран. Каким будет вывод, если к объекту последовательно применить методы insert(6, “Beautiful “), erase(12) и replace(7, 1, “Bro”)?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• Hello BBeauti
• Hello BroBeauti
• Hello BBroauti
• Hello BBro

В языке С++ для обеспечения корректности жадного алгоритма необходимо …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• случайно генерировать выборы решений
• экономить ресурсы оперативной памяти
• проанализировать проблему для обеспечения локально оптимального выбора на каждом шаге
• ориентироваться только на оптимальное глобальное решение

В языке С++ красно-чёрным деревом является …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• несбалансированное дерево АВЛ
• двоичное дерево поиска, в котором баланс осуществляется на основе “цвета” узла
• дерево отрезков с фиксированным количеством разноцветных узлов
• сбалансированное дерево с высотой равной не более нескольких единиц

В языке С++ сериализация — это …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• преобразование объектов в поток байтов для хранения или передачи
• экономия ресурсов при динамическом выделении памяти
• оптимизация использования памяти
• сортировка данных для быстрого доступа к ним

В языке C++ деревом отрезков называется …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• бинарное дерево с тремя дочерними узлами для каждого узла
• структура данных с информацией об интервалах массива в виде дерева
• дерево с одним узлом
• связный список с бинарными данными

В языке C++ добавление элементов в стек осуществляется с помощью метода …

Тип ответа: Текcтовый ответ

В языке C++ контейнером стандартной библиотеки, который обычно реализуется в виде двусвязного списка, является …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• std::vector
• std::list
• std::queue
• std::set

В языке C++ максимальная глубина рекурсии …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• зависит от компилятора
• не имеет какого-либо предела
• определяется объёмом RAM
• фиксирована и равна 1000

Временная сложность алгоритма линейного поиска равна …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• O(1)
• O(log n)
• O(n)
• O(n^2)

Временную сложность проталкивания элемента в стек на языке C++ можно описать как …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• O(1)
• O(log n)
• O(n)
• O(n log n)

Вызов функцией самой себя непосредственно в этой же функции использует рекурсию, которая является …

Тип ответа: Текcтовый ответ

Выполнение поставленной задачи при последовательно чётко определённых действиях называется …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• алгоритмом
• методом
• функцией
• структурой

Главная цель оптимизации алгоритмов заключается в …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• повышении производительности программы
• снижении сложности кода
• снижении веса файла программы
• повышении читаемости кода

Главное преимущество использования std::list в C++ — это …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• произвольный доступ к элементам
• эффективная вставка и удаление элементов в любой позиции
• автоматическая сортировка элементов
• наличие контейнера фиксированного размера

Главным недостатком использования жадного алгоритма является …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• наличие больших вычислительных затрат
• применимость только для решения задач сортировки
• сложность написания алгоритма
• возможное нахождение неоптимального решения задачи

Граф в информатике — это …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• структура данных, используемая для хранения текста
• коллекция узлов и рёбер
• математическое уравнение
• алгоритм сортировки

Декартово дерево — это структура данных, сочетающая в себе свойства бинарного дерева поиска и бинарной кучи. В нём каждый узел имеет два свойства: ключ и приоритет. Ключи соответствуют свойству двоичного дерева поиска, а приоритеты - свойству двоичной кучи. Вам нужно будет верно ответить на несколько вопросов, чтобы проверить ваше понимание данной темы в языке C++. Какие свойства должны иметь приоритеты? Для чего используются вращения? Какая временная сложность при операции поиска? Какая временная сложность при операциях добавления и удаления?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• Приоритеты должны назначаться в заданной последовательности. Вращения используются для сохранения баланса. Временная сложность при поиске равна O(log n). Временная сложность при операциях добавления и удаления равна O(log n).
• Приоритеты должны иметь значения в зависимости от позиции в дереве. Вращения используются для сохранения баланса. Временная сложность при поиске равна O(log n). Временная сложность при добавлении и удалении равна O(n).
• Приоритеты должны назначаться случайным образом. Вращения используются для сохранения свойства максимальной кучи. Временная сложность при поиске равна O(log n). Временная сложность при добавлении и удалении равна O(log n).

Дерево отрезков в языке С++ — это …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• дерево с одним узлом
• связный список с бинарными данными
• бинарное дерево с тремя дочерними узлами для каждого узла
• структура данных с информацией об интервалах массива в виде дерева

Дерево, в котором разница между высотой левого и правого поддеревьев одного узла значительно отличается, называется …

Тип ответа: Текcтовый ответ

Дерево, в котором у каждого узла высоты его левого и правого поддеревьев отличаются не более чем на единицу, называется …

Тип ответа: Текcтовый ответ

Деревом АВЛ является ...

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• бинарное дерево, сбалансированное по высоте
• дерево отрезков, сбалансированное по высоте
• бинарное дерево, несбалансированное по высоте
• дерево отрезков, несбалансированное по высоте

Для добавления элементов в стек используется метод …

Тип ответа: Текcтовый ответ

Для изменения порядка следования элементов в контейнере может быть использована функция …

Тип ответа: Текcтовый ответ

Для использования функции std::sort() требуется подключить заголовочный файл …

Тип ответа: Текcтовый ответ

Для нахождения заданного значения используется алгоритм, последовательно сравнивающий каждый элемент массива с искомым значением, который называется …

Тип ответа: Текcтовый ответ

Для обеспечения корректности жадного алгоритма необходимо …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• проанализировать проблему для обеспечения локально оптимального выбора на каждом шаге
• случайно генерировать выборы решений
• экономить ресурсы оперативной памяти
• ориентироваться только на оптимальное глобальное решение

Для округления числа с плавающей точкой к ближайшему целому числу используется функция …

Тип ответа: Текcтовый ответ

Для поиска в отсортированном массиве чаще других используется поисковой алгоритм C++ под названием …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• бинарный поиск
• линейный поиск
• поиск по принципу “первый-второй”
• поиск в глубину

Для поиска минимального остовного дерева в связном графе можно использовать алгоритм …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• Прима
• поиска в ширину
• поиска в глубину
• Дейкстры

Для получения верхнего элемента из стека без его удаления используется метод …

Тип ответа: Текcтовый ответ

Для создания персистентной переменной обычно используется ключевое слово ...

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• const
• static
• extern
• auto

Для сортировки элементов в массиве обычно используется функция стандартной библиотеки C++, которая называется …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• std::max()
• std::find()
• std::sort()
• std::reverse()

Для удаления элементов по значению из списка std::list используется метод …

Тип ответа: Текcтовый ответ

Для хранения персистентных данных во время выполнения программы наиболее подходящим типом из списка является …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• double
• char
• SQLCHAR
• ofstream

Заголовочный файл в C++, который требуется подключить для использования функции std::sort(), является <…>

Тип ответа: Текcтовый ответ

Запись определённого количества объектов с заданными размерами в поток вывода осуществляется при помощи стандартной функции …

Тип ответа: Текcтовый ответ

Имеется исходный вектор, элементами которого являются следующие целые числа: 1, 2, 3, 4, 5. Чему будет равна сумма размера и ёмкости вектора после того, как мы добавим в него три одинаковых элемента со значением 10?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• 16
• 17
• 18
• 19

Имеется исходный вектор, элементами которого являются следующие целые числа: 5, 10, 15, 20, 25, 35. Чему будет равно произведение размера и ёмкости вектора после того, как мы удалим четыре последних элемента?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• 4
• 12
• 16
• 6

Имеется следующая функция: int functionName(int n) { if (n <= 1) return 1 + 3; else return n + functionName(n - 1); } Какое значение вернёт данная функция при n = 9?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• 45
• 35
• 48
• 34

Имеется следующая функция: int functionName(int n) { if (n <= 1) return 1; else return n * functionName(n - 1); } Какое значение вернёт данная функция при n = 5?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• 120
• 24
• 125
• 110

Имеется следующая функция: int functionName(int n) { if (n <= 1) return 1 + 3; else return n + functionName(n - 1); } Какое значение вернёт данная функция при п = 9?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• 45
• 35
• 48
• 34

Имеется список целых чисел: 19, 3, 6, 15, 11, 7, 12. Постройте дерево, узлы которого равны каждому значению из списка. Такое дерево должно соответствовать свойствам минимальной кучи. В какой последовательности будут расположены узлы кучи? Какое значение будет иметь корневой узел?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• Последовательность узлов: 3, 6, 7, 11, 12, 15, 19. Значение корня: 19.
• Последовательность узлов: 19, 15, 12, 11, 7, 6, 3. Значение корня: 3.
• Последовательность узлов: 19, 15, 12, 11, 7, 6, 3. Значение корня: 19.
• Последовательность узлов: 3, 6, 7, 11, 12, 15, 19. Значение корня: 3.

Имеется список целых чисел: 9, 2, 5, 1, 3, 7, 8. Постройте дерево, узлы которого равны каждому значению из списка. Такое дерево должно соответствовать свойствам максимальной кучи. В какой последовательности будут расположены узлы кучи? Какое значение будет иметь корневой узел?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• Последовательность узлов: 9, 8, 7, 5, 3, 2, 1. Значение корня: 1.
• Последовательность узлов: 1, 2, 3, 5, 7, 8, 9. Значение корня: 1.
• Последовательность узлов: 9, 8, 7, 5, 3, 2, 1. Значение корня: 9.
• Последовательность узлов: 1, 2, 3, 5, 7, 8, 9. Значение корня: 9.

Использование и хранение ранее решённых проблем в динамическом программировании — это …

Тип ответа: Текcтовый ответ

Каждый листовой узел в дереве отрезков представляет собой …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• один элемент массива
• двоичное значение
• корень дерева
• диапазон массива

Каждый узел в дереве отрезков имеет максимум дочерних узлов в количестве равном …

Тип ответа: Текcтовый ответ

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

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• std::queue
• std::set
• std::list
• std::vector

Красно-чёрное дерево — это ...

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• двоичное дерево поиска, в котором баланс осуществляется на основе “цвета” узла
• сбалансированное дерево с высотой равной единице
• дерево отрезков с фиксированным количеством узлов
• несбалансированное дерево АВЛ

Линейный поиск имеет временную сложность …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• O(log n)
• O(1)
• O(n)
• O(n^2)

Листовой узел в бинарном дереве …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• имеет хотя бы один дочерний элемент
• не имеет дочерних элементов
• имеет ровно два дочерних элемента
• имеет ровно один дочерний элемент

Максимальная глубина рекурсии в языке C++ …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• фиксирована и равна 1000
• определяется объёмом RAM
• не имеет какого-либо предела
• зависит от компилятора

Максимальное количество узлов в бинарном дереве с высотой 3 равно …

Тип ответа: Текcтовый ответ

Метод программирования, позволяющий решать сложные задачи путём их разбиения на более простые, называется …

Тип ответа: Текcтовый ответ

Методом, который используется для удаления элементов из списка std::list по значению, является …

Тип ответа: Текcтовый ответ

Модификация кода и его настройка компиляции для производства более эффективного программного обеспечения называется …

Тип ответа: Текcтовый ответ

Название процесса преобразования данных в форму, которая может быть сохранена, передана или восстановлена в исходное состояние — это ...

Тип ответа: Текcтовый ответ

Названием параметра, который показывает зависимость времени работы программы от входных данных, является …

Тип ответа: Текcтовый ответ

Наихудшей временной сложностью алгоритма пузырьковой сортировки является …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• O(1)
• O(n)
• O(n^2)
• O(n log n)

Настройка компиляции кода и его модификация для производства более эффективного ПО называется …

Тип ответа: Текcтовый ответ

Нахождение частного двух чисел словесно можно описать следующей последовательностью:

Тип ответа: Сортировка

• 1 Объявить две переменные (делитель и делимое)
• 2 Присвоить значения переменным
• 3 Отсеять возможную ошибку, которая может быть связана с нулевым делителем
• 4 Найти частное (разделить делимое на делитель)
• 5 Записать результат в новую переменную

Неверно, что алгоритм можно описать следующим способом:

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• словесным
• обобщённым
• графическим
• программным

Неверно, что в бинарном дереве листовой узел …

Тип ответа: Множественный выбор • с выбором нескольких правильных ответов из предложенных вариантов

• имеет ровно один дочерний элемент
• имеет хотя бы один дочерний элемент
• имеет ровно два дочерних элемента
• не имеет дочерних элементов

Неверно, что одним из распространённых приёмов оптимизации является …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• обфускация кода
• мемоизация
• вызов встроенных функций
• развёртывание циклов

Неверно, что основным видом алгоритмов является:

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• циклический
• линейный
• разветвляющийся
• прерывистый

Общий подход к решению задач с использованием динамического программирования осуществляется при помощи …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• поиска в ширину
• бинарного поиска
• мемоизации и табуляции
• динамического выделения памяти

Объект или точка в графе, который является фундаментальным строительным блоком, называется …

Тип ответа: Текcтовый ответ

Одним из способов представления графа в виде матрицы является …

Тип ответа: Текcтовый ответ

Оператором остатка от деления является …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• /
• %
• &
• \

Основная структура данных, которая связана со стеком в языке C++ — это …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• массив
• очередь
• дерево
• список

Основная цель оптимизации алгоритмов в C++ заключается в …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• снижении сложности кода
• снижении веса файла программы
• повышении читаемости кода
• повышении производительности программы

Основное преимущество использования динамического программирования в языке C++ заключается в …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• наличии гарантий оптимального решения различных задач любых уровней сложности
• снижении временной сложности алгоритмов
• возможности избежать использования рекурсии
• повышении эффективности за счёт однократного решения подпроблем и хранения их решений

Основной задачей такого алгоритма является нахождение кратчайших путей от одного узла графа до всех остальных, имеющий название фамилии учёного, и он называется алгоритмом …

Тип ответа: Текcтовый ответ

Основным преимуществом использования std::list является …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• эффективная вставка и удаление элементов в любой позиции
• автоматическая сортировка элементов
• наличие контейнера фиксированного размера
• наличие возможности произвольного доступа к элементам

Остаток от деления можно найти при помощи оператора …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• %
• *
• &
• ˂˂

Параметр, показывающий зависимость времени работы программы от входных данных — это …

Тип ответа: Текcтовый ответ

Персистентная переменная обычно создаётся при помощи ключевого слова …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• extern
• const
• auto
• static

Поведение функции, при котором она вызывает сама себя называется …

Тип ответа: Текcтовый ответ

Поисковой алгоритм C++, который чаще других используется для поиска в отсортированном массиве — это …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• линейный поиск
• бинарный поиск
• поиск в глубину
• поиск по принципу “первый-второй”

Поисковой алгоритм, который последовательно делит пополам заранее отсортированный массив данных для обнаружения нужного элемента, называется …

Тип ответа: Текcтовый ответ

Получение доступа к элементу, находящемуся в определённой позиции в списке std::list осуществляется при помощи метода …

Тип ответа: Текcтовый ответ

Получить верхний элемент из стека, не удаляя его, можно при помощи функции-члена …

Тип ответа: Текcтовый ответ

Последовательностью чётко определённых действий, выполнение которых ведёт к решению поставленной задачи, называется …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• методом
• параметризацией
• алгоритмом
• функцией

Представление связи или отношения между двумя узлами в графе осуществляется при помощи …

Тип ответа: Текcтовый ответ

Представлением графа в виде матрицы является …

Тип ответа: Текcтовый ответ

При использовании динамического программирования главным преимуществом является …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• снижение временной сложности алгоритмов
• повышение эффективности за счёт однократного решения подпроблем и хранения их решений
• возможность избежать использование рекурсивных вызовов
• наличие гарантий оптимального решения различных задач любых уровней сложности

При использовании жадного алгоритма главным недостатком является …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• возможное нахождение неоптимального решения задачи
• сложность написания алгоритма
• применимость только для решения задач сортировки
• наличие больших вычислительных затрат

При классической нумерации вершин дерева отрезков корень будет иметь номер …

Тип ответа: Текcтовый ответ

Проталкивание элемента в стек осуществляется с временной сложностью равной …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• O(log n)
• O(n)
• O(1)
• O(n log n)

Процесс преобразования данных в форму, которая может быть сохранена, передана или восстановлена в исходное состояние, называется …

Тип ответа: Текcтовый ответ

Путь в графе, в котором совпадают начальный и конечный узлы, называется …

Тип ответа: Текcтовый ответ

Путь, в котором начальный и конечный узлы совпадают в графе, называется …

Тип ответа: Текcтовый ответ

Расположение данных в определённом порядке по какому-либо признаку называется …

Тип ответа: Текcтовый ответ

Расположите в правильном порядке действия необходимые для достижения персистентного хранения данных:

Тип ответа: Сортировка

• 1 Объявить и определить структуры данных
• 2 Открыть файл в режиме записи
• 3 Использовать сериализацию
• 4 Записать данные в файл
• 5 Закрыть файл

Расположите в правильном порядке действия, необходимые для обхода графа с помощью поиска в глубину:

Тип ответа: Сортировка

• 1 Поместить начальный узел в стек
• 2 Пока стек не пуст, извлечь из него узел
• 3 Пометить извлечённый узел как посещённый
• 4 Исследовать соседние непроверенные вершины от извлечённого узла
• 5 Если нужные вершины найдены, поместить их в стек

Расположите следующие алгоритмы сортировки в правильном порядке от наиболее эффективного к наименее эффективному по их средней временной сложности:

Тип ответа: Сортировка

• 1 Быстрая сортировка
• 2 Сортировка слиянием
• 3 Сортировка кучей
• 4 Сортировка вставкой
• 5 Пузырьковая сортировка

Расположите следующие алгоритмы сортировки в правильном порядке от наименее эффективного к наиболее эффективному по их средней временной сложности:

Тип ответа: Сортировка

• 1 Пузырьковая сортировка
• 2 Сортировка вставкой
• 3 Сортировка кучей
• 4 Сортировка слиянием
• 5 Быстрая сортировка

Рёбра в направленном графе имеют …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• только динамическую длину
• только статическую длину
• определённое направление
• несколько направлений

Результат “5 / 2” будет равен …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• 2.5
• 3
• 2.50
• 2

Результат “7 / 2” будет равен …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• 4
• 3.5
• 3.50
• 3

Рекурсивные алгоритмы чаще всего применяются в …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• нахождении факториалов чисел
• сортировке массивов
• реверсировании строк
• инициализации переменных

Рекурсия, которая создаётся за счёт вызова функцией самой себя непосредственно в этой же функции, называется …

Тип ответа: Текcтовый ответ

Решение задач с использованием динамического программирования обычно осуществляется при помощи …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• бинарного поиска
• мемоизации и табуляции
• поиска в ширину
• динамического выделения памяти

Решение сложных задач путём их разбиения на более простые осуществляется при помощи метода программирования, который называется …

Тип ответа: Текcтовый ответ

Самыми распространёнными приёмами оптимизации являются:

Тип ответа: Множественный выбор • с выбором нескольких правильных ответов из предложенных вариантов

• развёртывание циклов
• вызов встроенных функций
• мемоизация
• обфускация кода

Смысл сериализации заключается в …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• оптимизации использования памяти
• преобразовании объектов в поток байтов для хранения или передачи
• сортировке данных для быстрого доступа к ним
• экономии ресурсов при динамическом выделении памяти

Стандартная функция, которая записывает определённое количество объектов с заданными размерами в поток вывода, имеет название …

Тип ответа: Текcтовый ответ

Структуры данных, которые при внесении в них каких-либо изменений сохраняют все свои предыдущие состояния и доступ к ним, называются …

Тип ответа: Текcтовый ответ

Суть алгоритма Беллмана-Форда заключается в …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• нахождении кратчайшего пути между всеми парами узлов
• нахождении кратчайшего пути между исходным узлом и всеми остальными узлами
• нахождении наименьшего значения в исходном списке
• увеличении скорости обработки данных в динамически выделенной области памяти

Тремя основными видами алгоритмов являются:

Тип ответа: Множественный выбор • с выбором нескольких правильных ответов из предложенных вариантов

• линейный
• разветвляющийся
• прерывистый
• циклический

Узел, который находится на самом верху в бинарном дереве, называется …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• листовым
• дочерним
• корневым
• родительским

Упорядочивание данных по какому-либо признаку называется …

Тип ответа: Текcтовый ответ

Установите соответствие между каждым алгоритмом сортировки и его характерным свойством:

Тип ответа: Сопоставление

• A. Пузырьковая сортировка
• B. Быстрая сортировка
• C. Сортировка слиянием
• D. Сортировка вставкой
• E. Сравнивает соседние элементы и меняет их местами
• F. Использует стратегию “разделяй и властвуй”
• G. Объединяет два отсортированных подмассива
• H. Эффективен для небольших массивов или списков

Установите соответствие между свойствами алгоритмов и их значениями:

Тип ответа: Сопоставление

• A. Дискретность (разделение)
• B. Детерминированность (точность)
• C. Результативность
• D. Конечность
• E. Массовость
• F. Разбиение алгоритма на ряд отдельных законченных действий
• G. Строгое и недвусмысленное определение каждого действия алгоритма
• H. Приведение к достоверному и конечному решению
• I. Завершение каждого действия в отдельности
• J. Использование одного и того же алгоритма с разными исходными данными

Установите соответствие между свойствами алгоритмов и их значениями:

Тип ответа: Сопоставление

• A. Дискретность
• B. Результативность
• C. Детерминированность
• D. Массовость
• E. Конечность
• F. Разбиение алгоритма на ряд отдельных законченных действий
• G. Приведение к конечному и достоверному решению
• H. Недвусмысленное и строгое определение каждого действия алгоритма
• I. Многократное использование одного и того же алгоритма с разными данными
• J. Завершение каждого действия в отдельности

Установите соответствие между терминами и их значениями, относящимися к теме графов:

Тип ответа: Сопоставление

• A. Узел
• B. Ребро
• C. Список смежности
• D. Поиск в глубину
• E. Представление вершины в графе
• F. Соединение между двумя узлами в графе
• G. Структура данных для хранения связей графа
• H. Алгоритм обхода, исследующий граф

Установите соответствие между уровнями персистентности структур данных и их особенностями:

Тип ответа: Сопоставление

• A. Частичная
• B. Конфлюэнтная
• C. Функциональная
• D. Полная
• E. Можно изменять только последнюю версию структур данных
• F. Возможность объединения двух структур данных
• G. Запрещаются уничтожающие присваивания
• H. Возможность делать запросы и вносить изменения в любой версии структур данных

Установите соответствие между уровнями персистентности структур данных и их особенностями:

Тип ответа: Сопоставление

• A. Частичная
• B. Полная
• C. Функциональная
• D. Конфлюэнтная
• E. Можно изменять только последнюю версию структур данных
• F. Возможность делать запросы и вносить изменения в любой версии структур данных
• G. Запрещаются уничтожающие присваивания
• H. Возможность объединения двух структур данных

Функцией стандартной библиотеки C++, которая обычно используется для сортировки элементов в массиве, является …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• std::sort()
• std::reverse()
• std::max()
• std::find()

Функцией, которая находит абсолютное значение числа, является …

Тип ответа: Текcтовый ответ

Функция в C++, округляющая число с плавающей точкой к ближайшему целому числу, называется …

Тип ответа: Текcтовый ответ

Функция языка C++, которая может быть использована для изменения порядка следования элементов в контейнере — это …

Тип ответа: Текcтовый ответ

Функция std::sort() обычно использует алгоритм сортировки под названием …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• “Пузырьковая сортировка”
• “Сортировка вставкой”
• “Сортировка слиянием”
• “Быстрая сортировка”

Характерная структура данных, которая связана со стеком в языке C++ — это …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• список
• очередь
• массив
• дерево

Хеширование является фундаментальной концепцией в информатике и широко используется в различных приложениях для эффективного хранения и поиска данных. В языке C++ хеширование подразумевает сопоставление данных со значением фиксированного размера, обычно генерируемых из исходных данных с помощью хеш-функции. Вам нужно будет верно ответить на поставленные вопросы для того, чтобы проверить ваше понимание хеширования в языке C++. Какова основная цель использования хеш-функции? Какая временная сложность поиска в хорошо реализованной хэш-таблице? Что такое коллизия в контексте хэширования? Какая техника используется для обработки коллизий в хэш-таблицах?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• Основной целью хеш-функций является эффективное хранение и извлечение данных в структурах. Временная сложность поиска в хорошо реализованной хэш-таблице будет равна O(1). Коллизией называется случай, когда два различных элемента данных дают одно и то же хэш-значение. Для обработки коллизий используется техника разделения цепочек.
• Хэш-функции предназначены для хранения и извлечения сложных данных. Временная сложность поиска в хорошо реализованной хэш-таблице стримится к O(n). Коллизией является “столкновение” двух значений в таблице. Для её избежания используется техника “умного” массива.
• Смысл хэш-функций заключается в хранении и извлечении данных упрощённого типа. Временная сложность поиска в хэш-таблице будет равна O(n). Коллизия характеризует процесс нарушения данных при хэшировании. Для решения этой проблемы используется бинарное уравнивание данных.

Хранение и использование ранее решённых проблем в динамическом программировании — это …

Тип ответа: Текcтовый ответ

Цикл в графе, который не проходит через один узел более одного раза, называется …

Тип ответа: Текcтовый ответ

Цикл, который не проходит через одну вершину более одного раза, является …

Тип ответа: Текcтовый ответ

Циклом в графе называется …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• набор узлов без рёбер
• путь, который начинается и заканчивается в одном и том же узле
• путь, который проходит через каждую вершину только один раз
• узел, не имеющий рёбер

Явление, при котором функция вызывает сама себя называется …

Тип ответа: Текcтовый ответ

Язык C++ предоставляет множество мощных алгоритмов, позволяющих разработчикам эффективно манипулировать строками и обрабатывать их. Понимание и использование этих алгоритмов очень важно для продуктивной работы со строками. Чтобы проверить ваши знания по этой теме, вам нужно будет корректно ответить на поставленные вопросы. Какой метод используется для поиска последнего вхождения любого символа в строке? Что возвращает std::string::compare()? Какой метод используется для конкатенации строк? Какой метод удаляет из строки заданное количество символов, начиная с указанной позиции?

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• Для поиска последнего вхождения любого символа в строке используется метод std::string::find(). Возвращаемые значения для std::string::compare(): -1, 0, 1. Для сложения строк используется std::string::add(). Метод, который удаляет из строки заданное количество символов, начиная с указанной позиции, называется std::string::erase().
• Для поиска последнего вхождения любого символа в строке используется метод std::string::rfind(). Возвращаемые значения для std::string::compare(): <0, 0, >0. Для сложения строк используется std::string::append(). Метод, который удаляет из строки заданное количество символов, начиная с указанной позиции, называется std::string::erase().
• Для поиска последнего вхождения любого символа в строке используется метод std::string::rfind(). Возвращаемые значения для std::string::compare(): -1, 0, 1. Для конкатенации строк используется std::string::append(). Метод, который удаляет из строки заданное количество символов, начиная с указанной позиции, называется std::string::remove().