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

Структуры и алгоритмы компьютерной обработки данных > Тест 3 /Тест 4 / Итоговый тест

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

Структуры и алгоритмы компьютерной обработки данных

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Тип ответа: Тек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++ деревом отрезков называется …

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• const
• static
• extern
• auto

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

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

• double
• char
• SQLCHAR
• ofstream

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• char
• ofstream
• double
• SQLCHAR

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• extern
• const
• auto
• static

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• 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товый ответ

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

Тип ответа: Тек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().