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

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

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

Имеется список целых чисел: 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 осуществляется при помощи метода …

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

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

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

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

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

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

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

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

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

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

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

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

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

• const
• static
• extern
• auto

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

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

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

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

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

• extern
• const
• auto
• static

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• double
• char
• SQLCHAR
• ofstream

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

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

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

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

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

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

• 4
• 3.5
• 3.50
• 3

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

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

• 45
• 35
• 48
• 34

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• char
• ofstream
• double
• SQLCHAR

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

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

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

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

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

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

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

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

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

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

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

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