Тесты СинергияАртём Хелп
Артём Help онлайнПолучить расчёт
Бесплатно оценим сроки и стоимостьОтправить задание в Telegram
Углубленные структуры и алгоритмы компьютерной обработки данных.фип_БАК_МОиАИС_н с

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

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

64 вопроса Вариант 4 Доступ 7 дней
Содержание теста

Вопросы и варианты

Без отметок и подсказок к правильным ответам

Вопрос 1

… - это четкая последовательность действий, направленная на достижение поставленной цели или решения задачи

  1. Алгоритм
  2. Программа
  3. Модель
  4. Метод
Вопрос 2

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

  1. массивах, где мало элементов
  2. отсортированных больших массивах
  3. хеш-таблицах
  4. деревьях поиска
Вопрос 3

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

  1. O(nlogn)
  2. O(n^2)
  3. O(logn^2)
  4. O(n!)
Вопрос 4

Факториал обозначается символом …

  1. #
  2. &
  3. !
  4. ^
Вопрос 5

… - это нотация, которая нужна для описания сложности алгоритмов

  1. BigO
  2. Big O
  3. Big-O
Вопрос 6

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

  1. Константы
Вопрос 7

Одним из минусов массивов является невозможность простого добавления элемента в начало или …

  1. центр
  2. середину
Вопрос 8

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

  1. Бинарный поиск
Вопрос 9

… - это операция, обратная возведению в степень

  1. Логарифм
Вопрос 10

… - это непрерывный участок памяти, который отводится для заполнения элементами

  1. Массив
Вопрос 11

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

  1. ОЗУ
  2. Оперативка
  3. Оперативная память
  4. RAM
  5. Random Access Memory
  6. оперативное запоминающее устройство
  7. память с произвольным доступом
Вопрос 12

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

  1. Динамический
Вопрос 13

Сопоставьте тип алгоритма и метод его функционирования:

  1. Циклический
  2. Линейный
  3. Разветвляющийся
  4. предусматривается многократное повторение одних и тех же действий
  5. команды выполняются последовательно, одна за одной
  6. есть условие, при проверке которого возможно разделение на несколько параллельных направлений
Вопрос 14

Сопоставьте временную сложность и её значение:

  1. O(1)
  2. O(n)
  3. O(n2)
  4. время постоянно
  5. алгоритмы перебора всех элементов входных данных
  6. алгоритмы двойного вложенного перебора элементов входных данных
Вопрос 15

Упорядочьте временные сложности от самой эффективной к самой неэффективной

  1. O(1)
  2. O(logn)
  3. O(nlogn)
  4. O(n^2)
  5. O(2n)
Вопрос 16

Упорядочьте шаги алгоритма бинарного поиска:

  1. Берем элемент из середины структуры данных
  2. Сравниваем его с поисковым элементом
  3. Если он больше нужного, то мы идем в середину левого блока и повторяем действи
  4. Если он меньше нужного, то мы идем в середину правого блока и повторяем действи
  5. Если он равен поисковому элементу, то мы возвращаем результат
Вопрос 17

Линейный поиск имеет временную сложность …

  1. O(1)
  2. O(log n)
  3. O(n^2)
  4. O(n)
Вопрос 18

… - это является одним из минусов массивов

  1. При добавлении новых элементов массив автоматически расширяется без необходимости создания нового массива
  2. Высокий расход памяти при малом количестве элементов
  3. Не зная индекса элемента, придется пробежаться по всему массиву, что даст нам сложность O(N)
  4. Медленный доступ к случайному элементу
Вопрос 19

… - это операция, обратная возведению в степень

  1. Логарифм
  2. Факториал
  3. Корень
  4. Модуль
Вопрос 20

… - это перебор каждого элемента, пока не будет найден нужный

  1. Полный перебор
  2. Линейный поиск
  3. Дихотомический поиск
  4. Хеширование
Вопрос 21

В худшем случае поиск элемента в списке будет равен …

  1. O(logn)
  2. O(1)
  3. O(n^2)
  4. O(n)
Вопрос 22

В Java за связный список отвечает реализация …

  1. LinkedList
Вопрос 23

Неверно, что … является плюсом сортировки выбором

  1. производительность
  2. стабильность временной сложности
  3. эффективность на больших наборах данных
  4. малое количество свопов в память
Вопрос 24

При получении очень большого количества входных элементов, сложность сортировки выбором будет расти …

  1. квадратично
Вопрос 25

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

  1. стека
  2. стек
Вопрос 26

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

  1. Базовый случай
Вопрос 27

Неверно, что … является плюсом стека

  1. Эффективность
  2. Однонаправленность
  3. Гибкость
Вопрос 28

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

  1. Рекурсивные
Вопрос 29

Оценка временной сложности для стека равна …

  1. O(logn)
  2. O(1)
  3. O(n^2)
  4. O(n)
Вопрос 30

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

  1. Разделяй и властвуй
  2. Разделять и властвовать
Вопрос 31

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

  1. Базовый случай
Вопрос 32

… - это структура данных, которая работает по принципу FIFO (First In, First Out), то есть первым пришёл — первым ушёл

  1. Очередь
Вопрос 33

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

  1. Сортировка слиянием
Вопрос 34

… массива - это то числовой идентификатор (адрес) элемента в массиве, который определяет его позицию

  1. Индекс
Вопрос 35

Сопоставьте часть парадигмы “Разделяй и властвуй” с её значением:

  1. Разделяй
  2. Комбинируй
  3. Властвуй
  4. Если проблема небольшая, то решайте ее напрямую. В противном случае распределите задачу на меньшие подмножества той же проблемы
  5. Возьмите решения для подзадач и объедините это с решением исходной проблемы
  6. Решайте меньшие проблемы, решая их рекурсивно. Если подзадачи достаточно малы, рекурсия не нужна, и вы можете решить их напрямую
Вопрос 36

Сопоставьте операцию для работы с очередями и её обозначение:

  1. Добавление элемента в очередь
  2. Получение размера очереди
  3. Извлечение элемента из очереди
  4. Проверка наличия элементов в очереди
  5. enqueue
  6. size
  7. dequeue
  8. isEmpty
Вопрос 37

Упорядочьте этапы алгоритма быстрой сортировки:

  1. Выбрать опорный элемент (обычно первый элемент массива)
  2. Разделить массив на два подмассива: элементы меньше опорного и элементы больше опорного
  3. Рекурсивно применить быструю сортировку к каждому из подмассивов
  4. Объединить отсортированные подмассивы в один массив
Вопрос 38

Упорядочьте этапы алгоритма сортировки слиянием:

  1. Разделение
  2. Слияние
  3. Сортировка
  4. Повторение
Вопрос 39

… - это структура данных, которая работает по принципу "последним пришел - первым вышел"

  1. Стек
  2. Цикл
  3. Массив
  4. Список
Вопрос 40

Доказательство по индукции состоит в том, что сначала проверяется данное свойство для числа … (база индукции), а затем показывается, что если свойство выполнено для числа N, то оно верно и для числа N + 1

  1. 0
  2. 1
  3. nlogn
  4. n^2
Вопрос 41

Быстрая сортировка имеет сложность O(...) в среднем случае

  1. nlogn
Вопрос 42

Хеш-функция должна быть …, то есть одно и то же сообщение приводит к одному и тому же хеш-значению

  1. детерминированной
  2. детерминирована
Вопрос 43

… хеш-функции — это когда у двух разных входных элементов таблицы хеш-значение будет одинаковым

  1. Кеш
  2. Таблица
  3. Коллизия
  4. Стек
Вопрос 44

… заключается в том, что пары ключ-значение хранятся непосредственно в хеш-таблице

  1. Метод цепочек
  2. Открытая адресация
  3. Линейное пробирование
  4. Двойное хеширование
Вопрос 45

… в Java представляет собой структуру данных, которая реализует интерфейс Map и позволяет хранить пары ключ-значение

  1. HashMap
Вопрос 46

… - это структура данных, в которой у каждого узла может быть ноль или более подузлов — «детей». В первую очередь — это способ организации данных в виде иерархической структуры

  1. Дерево
Вопрос 47

… - это структура данных, которая имеет корень и дочерние узлы, без циклических связей

  1. двоичное дерево
  2. бинарное дерево
Вопрос 48

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

  1. Ребро
  2. Грань
  3. Вершина
  4. Корень
Вопрос 49

… - это граф, ребрам которого присвоено направление

  1. орграф
  2. Ориентированный граф
Вопрос 50

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

  1. логарифмического
  2. линейного
  3. кубического
  4. квадратичного
Вопрос 51

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

  1. смежности
Вопрос 52

Результат, производимый хеш-функцией, называется «хеш-суммой» или же просто «хешем», а входные данные часто называют «…»

  1. сообщением
  2. сообщение
Вопрос 53

… - это двоичное дерево поиска, в котором баланс осуществляется на основе “цвета” узла дерева, который принимает только два значения

  1. Красно-чёрное дерево
  2. красно-чёрное
  3. Красно-черное дерево
  4. красно-черное
  5. Красно чёрное дерево
  6. красно чёрное
  7. Красно черное дерево
  8. красно черное
Вопрос 54

… это расстояние, которое определяется количеством черных вершин от корня до фиктивного листка(корень и лист в том числе). В красночерном дереве черная глубина от корня до любого фиктивного листка должна быть одинакова

  1. Черная глубина
Вопрос 55

Ключи в HashMap хэшируются с использованием метода …()

  1. hashCode
Вопрос 56

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

  1. Ребро
Вопрос 57

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

  1. неориентированным
Вопрос 58

Два ребра инцидентные одной вершине, называются …; две вершины, инцидентные одному ребру, также называются …

  1. смежными
Вопрос 59

Сопоставьте методы HashMap и их обозначения:

  1. get(key)
  2. containsKey(key)
  3. keySet()
  4. put(key, value)
  5. возвращает значение по заданному ключу, или null, если ключ отсутствует
  6. проверяет наличие ключа в HashMap
  7. возвращает множество всех ключей в HashMap
  8. добавляет новую пару ключ-значение в HashMap
Вопрос 60

Сопоставьте элементы дерева и их назначения:

  1. Корень
  2. Лист
  3. Предок
  4. Потомок
  5. узел, не имеющий предка/родителя
  6. узел, не имеющий потомков
  7. узел, имеющий потомка. В зависимости от типа дерева может иметь разное количество потомков
  8. узел, имеющий предка/родителя. Узел может иметь не более одного родителя
Вопрос 61

Упорядочите этапы выполнения алгоритма поиска по графу в глубину:

  1. Пойти в какую-нибудь смежную вершину
  2. Обойти все, что доступно из смежной вершины
  3. Вернуться в начальную вершину
  4. Повторить для остальных вершин, смежных с начальной
Вопрос 62

Упорядочите этапы выполнения алгоритма поиска по графу в ширину :

  1. Поместить начальную вершину в очередь
  2. Извлечь вершину из очереди
  3. Проверить все её соседние вершины
  4. Добавить соседние вершины в очередь для дальнейшей проверкÅ
  5. Пометить текущую вершину как посещенную
  6. Повторять, пока не будет достигнута целевая вершина или не будут перебраны все вершины
Вопрос 63

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

  1. Алгоритм Дейкстры
  2. Дейкстры
  3. Дейкстра
Вопрос 64

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

  1. Криптографическая
  2. Контрольная сумма
  3. Универсальная хеш-функция
  4. Хеш-таблица