Ответы на вопросы из коллекции "📝Алгоритмы и структуры данных Темы 1-4"

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В программе объявлен и проинициализирован объект: 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

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

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

Имеется список целых чисел: 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Используя стандартную нумерацию вершин дерева отрезков, корень будет иметь номер …

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

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

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

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

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

• const
• static
• extern
• auto

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• 45
• 35
• 48
• 34

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• 120
• 24
• 125
• 110

Основной целью алгоритма Беллмана-Форда является …

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

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

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

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

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

Функция в 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().

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

• double
• char
• SQLCHAR
• ofstream

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

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

• 4
• 3.5
• 3.50
• 3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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