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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• 4
• 3.5
• 3.50
• 3

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

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

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

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

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

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

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

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

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

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

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

• const
• static
• extern
• auto

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

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

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

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

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

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

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

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

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

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

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

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

• double
• char
• SQLCHAR
• ofstream

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

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

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

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

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

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

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

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

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

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

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

• extern
• const
• auto
• static

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• 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++ — это …

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• 45
• 35
• 48
• 34

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

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

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

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

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

• char
• ofstream
• double
• SQLCHAR

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

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

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

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