Углубленные структуры и алгоритмы компьютерной обработки данных.фип_БАК_МОиАИС_н/с

Скачать тест — (Углубленные структуры и алгоритмы компьютерной обр_f9678e6b.pdf)

Свойство, обозначающее универсальность алгоритма, благодаря которому один и тот же алгоритм можно успешно применять к различным наборам исходных данных — это …
Свойство, обозначающее разрывность алгоритма и то, что процесс решения задачи должен быть разбит на последовательность отдельных шагов-команд, которые выполняются одна за другой — это …
Свойство, обозначающее то, что для одних и тех же наборов исходных данных на выходе будет даваться один и тот же результат, т.е. результат однозначно определяется исходными данными — это …
Свойство, обозначающее то, что алгоритм должен выдавать результат за конечное число шагов и обязательно конкретными результатами — это …
Свойство обозначающее то, что в алгоритм должны быть включены лишь те команды, которые доступны и понятны исполнителю, то есть входят в систему его команд — это …
Линейный поиск имеет временную сложность …
… — это является одним из минусов массивов
Один из плюсов массивов заключается в том, что …
… — это математическая функция, которая для натурального числа N определена как произведение всех чисел от единицы до N
O(2^…) — временная сложность для алгоритмов, рост которых удваивается при добавлении элементов во входные данные
… — это перебор каждого элемента, пока не будет найден нужный
К … сложности относятся те значения, которые отбрасываются при оценке сложности
… — это операция, обратная возведению в степень
… — это непрерывный участок памяти, который отводится для заполнения элементами
… — это область временного хранения данных, при помощи которой обеспечивается функционирование программного обеспечения
… массив — это массив, который может во время выполнения программы менять свою размерность
Сопоставьте тип алгоритма и метод его функционирования:
Сопоставьте временную сложность и её значение:
Упорядочьте временные сложности от самой эффективной к самой неэффективной
Упорядочьте шаги алгоритма бинарного поиска:
В приведённом коде временная сложность представляет собой …
public void printFirstElement(String[] stringArray) {
if (stringArray.length > 0) {
System.out.println(stringArray[0]);
}
}
…- это связанные между собой ссылками ячейки в памяти
Неверно, что …
… — это структура данных, которая работает по принципу «последним пришел — первым вышел»
Доказательство по индукции состоит в том, что сначала проверяется данное свойство для числа … (база индукции), а затем показывается, что если свойство выполнено для числа N, то оно верно и для числа N + 1
Быстрая сортировка имеет сложность O(…) в среднем случае
Быстрая сортировка имеет сложность O(…) в худшем случае
Функция … отвечает за слияние двух отсортированных массивов в один цельный отсортированный массив
Сложность сортировки слиянием — …
… это алгоритм сортировки, который ищет и помещает наименьший элемент массива в начало
… — это функция, которая вызывает саму себя, но с другими значениями параметров
… — это структура данных, которая используется для отслеживания последовательности вызовов функций в программе
… — это уравнение, согласно которому N-ый член последовательности чисел равен некоторой комбинации предыдущих членов
… — это условие, которое позволяет алгоритму остановить действия. Он представляет собой задачу настолько малую, что её можно решить без применения каких-либо дополнительных средств
… — это структура данных, которая работает по принципу FIFO (First In, First Out), то есть первым пришёл — первым ушёл
…- это алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно) в определенном порядке
… массива — это то числовой идентификатор (адрес) элемента в массиве, который определяет его позицию
Сопоставьте часть парадигмы “Разделяй и властвуй” с её значением:
Сопоставьте операцию для работы с очередями и её обозначение:
Упорядочьте этапы алгоритма быстрой сортировки:
Упорядочьте этапы алгоритма сортировки слиянием:
Вы разрабатываете программное обеспечение для управления базой данных онлайн-магазина. Ваша задача — отсортировать массив заказов по их стоимости, чтобы менеджеры могли быстро находить нужные сделки.
Исходные данные:
Количество заказов варьируется от 10 до 1 000 000.
В среднем массив уже частично отсортирован, так как новые заказы добавляются постепенно.
Производительность важна, так как сортировка выполняется часто.
Память ограничена, но не критично (предпочтительно использовать не слишком много дополнительной памяти).
… подойдёт для этой задачи лучше всего
… — это структура данных, реализующая интерфейс ассоциативного массива, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию удаления и операцию поиска пары по ключу
… — это метод часто называемый открытым хешированием. Его суть проста — элементы с одинаковым хешем попадают в одну ячейку
Неверно, что … является одним из плюсов красно-чёрных деревьев
… — это абстрактное представление множества объектов и связей между ними
… — это массив элементов, представленных в виде прямоугольной таблицы, для которых определены правила математических действий
… граф это граф, в котором каждое ребро обозначается числом
Алгоритм … позволяет найти кратчайшие пути из одной вершины не взвешенного (ориентированного или неориентированного) графа до всех остальных вершин
… — это алгоритм, который находит оптимальные маршруты и их длину между одной конкретной вершиной (источником) и всеми остальными вершинами графа. Алгоритм пошагово перебирает все вершины графа и назначает им метки, которые являются известным минимальным расстоянием от вершины источника до конкретной вершины
… хеш-функция это математический алгоритм, который отображает данные произвольного размера в битовый массив фиксированного размера
Результат, производимый хеш-функцией, называется «хеш-суммой» или же просто «хешем», а входные данные часто называют «…»
… — это двоичное дерево поиска, в котором баланс осуществляется на основе “цвета” узла дерева, который принимает только два значения
… это расстояние, которое определяется количеством черных вершин от корня до фиктивного листка(корень и лист в том числе). В красночерном дереве черная глубина от корня до любого фиктивного листка должна быть одинакова
Ключи в HashMap хэшируются с использованием метода …()
… в графе представляет собой связь или соединение между двумя вершинами графа
Граф, ни одному ребру которого не присвоено направление, называется … графом
Два ребра инцидентные одной вершине, называются …; две вершины, инцидентные одному ребру, также называются …
Сопоставьте методы HashMap и их обозначения:
Сопоставьте элементы дерева и их назначения:
Упорядочите этапы выполнения алгоритма поиска по графу в глубину:
Упорядочите этапы выполнения алгоритма поиска по графу в ширину :
Ты управляешь роботом, который должен добраться из одной точки в другую на карте. Тебе нужно выбрать правильный алгоритм. Робот ищет кратчайший путь в лабиринте, где все проходы имеют одинаковую стоимость перемещения
В такой ситуации нужно использовать …
… — это четкая последовательность действий, направленная на достижение поставленной цели или решения задачи
Из за того, что поиск по линейному алгоритму производится в худшем случае достаточно долго, его обычно используют при поиске в …
Неверно, что … является одной из самых распространённых временных сложностей
Факториал обозначается символом …
… — это нотация, которая нужна для описания сложности алгоритмов
…, то есть операции, которые выполняются за постоянное время, при оценке сложности не учитываются
Одним из минусов массивов является невозможность простого добавления элемента в начало или …
… — это тип поискового алгоритма, который последовательно делит пополам заранее отсортированный массив данных, чтобы обнаружить нужный элемент
… — это операция, обратная возведению в степень
… — это непрерывный участок памяти, который отводится для заполнения элементами
… — это область временного хранения данных, при помощи которой обеспечивается функционирование программного обеспечения
… массив — это массив, который может во время выполнения программы менять свою размерность
Сопоставьте тип алгоритма и метод его функционирования:
Сопоставьте временную сложность и её значение:
Упорядочьте временные сложности от самой эффективной к самой неэффективной
Упорядочьте шаги алгоритма бинарного поиска:
Линейный поиск имеет временную сложность …
… — это является одним из минусов массивов
… — это перебор каждого элемента, пока не будет найден нужный
В худшем случае поиск элемента в списке будет равен …
В Java за связный список отвечает реализация …
Неверно, что … является плюсом сортировки выбором
При получении очень большого количества входных элементов, сложность сортировки выбором будет расти …
Любой циклический алгоритм можно записать в рекурсивном виде, а любой рекурсивный алгоритм можно записать с помощью комбинации цикла и …
… рекурсии это условие, при выполнении которого рекурсивная функция завершает свое выполнение и перестает вызывать саму себя
Неверно, что … является плюсом стека
… функции вызывают сами себя, и стек вызовов помогает отслеживать их вызовы и возвраты
Оценка временной сложности для стека равна …
… — это парадигма разработки алгоритмов, заключающаяся в рекурсивном разбиении решаемой задачи на две или более подзадачи того же типа, но меньшего размера, и комбинировании их решений для получения ответа к исходной задаче
… — это условие, которое позволяет алгоритму остановить действия. Он представляет собой задачу настолько малую, что её можно решить без применения каких-либо дополнительных средств
… — это структура данных, которая работает по принципу FIFO (First In, First Out), то есть первым пришёл — первым ушёл
…- это алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно) в определенном порядке
… массива — это то числовой идентификатор (адрес) элемента в массиве, который определяет его позицию
Сопоставьте часть парадигмы “Разделяй и властвуй” с её значением:
Сопоставьте операцию для работы с очередями и её обозначение:
Упорядочьте этапы алгоритма быстрой сортировки:
Упорядочьте этапы алгоритма сортировки слиянием:
… — это структура данных, которая работает по принципу «последним пришел — первым вышел»
Доказательство по индукции состоит в том, что сначала проверяется данное свойство для числа … (база индукции), а затем показывается, что если свойство выполнено для числа N, то оно верно и для числа N + 1
Быстрая сортировка имеет сложность O(…) в среднем случае
Хеш-функция должна быть …, то есть одно и то же сообщение приводит к одному и тому же хеш-значению
… хеш-функции — это когда у двух разных входных элементов таблицы хеш-значение будет одинаковым
… заключается в том, что пары ключ-значение хранятся непосредственно в хеш-таблице
… в Java представляет собой структуру данных, которая реализует интерфейс Map и позволяет хранить пары ключ-значение
… — это структура данных, в которой у каждого узла может быть ноль или более подузлов — «детей». В первую очередь — это способ организации данных в виде иерархической структуры
… — это структура данных, которая имеет корень и дочерние узлы, без циклических связей
… в графе также называется узлом и представляет собой один из элементов графической структуры, который хранит данные (информацию) и может иметь связи (рёбра) с другими …
… — это граф, ребрам которого присвоено направление
Основным недостатком матрицы смежности является то, что она требует … пространства памяти относительно числа вершин, что может быть проблематично для больших графов
Создавая списки соседей для каждой вершины, а затем помещая все эти списки в другой список, вы получаете список …
Результат, производимый хеш-функцией, называется «хеш-суммой» или же просто «хешем», а входные данные часто называют «…»
… — это двоичное дерево поиска, в котором баланс осуществляется на основе “цвета” узла дерева, который принимает только два значения
… это расстояние, которое определяется количеством черных вершин от корня до фиктивного листка(корень и лист в том числе). В красночерном дереве черная глубина от корня до любого фиктивного листка должна быть одинакова
Ключи в HashMap хэшируются с использованием метода …()
… в графе представляет собой связь или соединение между двумя вершинами графа
Граф, ни одному ребру которого не присвоено направление, называется … графом
Два ребра инцидентные одной вершине, называются …; две вершины, инцидентные одному ребру, также называются …
Сопоставьте методы HashMap и их обозначения:
Сопоставьте элементы дерева и их назначения:
Упорядочите этапы выполнения алгоритма поиска по графу в глубину:
Упорядочите этапы выполнения алгоритма поиска по графу в ширину :
… — это алгоритм, который находит оптимальные маршруты и их длину между одной конкретной вершиной (источником) и всеми остальными вершинами графа. Алгоритм пошагово перебирает все вершины графа и назначает им метки, которые являются известным минимальным расстоянием от вершины источника до конкретной вершины
… хеш-функция это математический алгоритм, который отображает данные произвольного размера в битовый массив фиксированного размера