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

Структуры и алгоритмы компьютерной обработки данных.фип_БАК_231213 — вариант 2

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

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

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

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

Вопрос 1

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

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

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

  1. определённое направление
  2. несколько направлений
  3. только динамическую длину
  4. только статическую длину
Вопрос 3

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

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

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

  1. матрица смежности
Вопрос 5

Фундаментальный строительный блок, представляющий объект или точку в графе — это …

  1. узел;вершина
Вопрос 6

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

  1. ребра
Вопрос 7

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

  1. Узел
  2. Ребро
  3. Список смежности
  4. Поиск в глубину
  5. Представление вершины в графе
  6. Соединение между двумя узлами в графе
  7. Структура данных для хранения связей графа
  8. Алгоритм обхода, исследующий граф
Вопрос 8

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

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

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

  1. корневым
  2. листовым
  3. родительским
  4. дочерним
Вопрос 10

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

  1. имеет хотя бы один дочерний элемент
  2. не имеет дочерних элементов
  3. имеет ровно два дочерних элемента
  4. имеет ровно один дочерний элемент
Вопрос 11

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

  1. идеальным
Вопрос 12

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

  1. 15;;пятнадцати
Вопрос 13

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

  1. дерево с одним узлом
  2. связный список с бинарными данными
  3. бинарное дерево с тремя дочерними узлами для каждого узла
  4. структура данных с информацией об интервалах массива в виде дерева
Вопрос 14

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

  1. диапазон массива
  2. корень дерева
  3. один элемент массива
  4. двоичное значение
Вопрос 15

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

  1. 2;;двум
Вопрос 16

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

  1. 1;;один
Вопрос 17

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

  1. бинарное дерево, сбалансированное по высоте
  2. дерево отрезков, сбалансированное по высоте
  3. бинарное дерево, несбалансированное по высоте
  4. дерево отрезков, несбалансированное по высоте
Вопрос 18

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

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

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

  1. сбалансированным
Вопрос 20

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

  1. несбалансированным
Вопрос 21

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

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