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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Тип ответа: Тек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товый ответ

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

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

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

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

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

• char
• ofstream
• double
• SQLCHAR

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

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

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

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

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

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

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

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

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

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

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

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

• extern
• const
• auto
• static

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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