Теория графов.dor_БАК_25-122-Б — вариант 2

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

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

Содержание теста

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

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

Вопрос 1

Установите соответствие между понятиями из теории графов и их определениями:

Простой путь
Цикл
Цепь
Компонента связности
путь без повторений вершин и ребер
замкнутый путь без повторений вершин и ребер
максимальный связный подграф
путь без повторений ребер, но с возможными повторениями вершин

Вопрос 2

Расположите в правильном порядке шаги алгоритма BFS:

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

Вопрос 3

Алгоритм обхода графа, который использует стек, – это алгоритм …

BFS
DFS
Дейкстры
Крускала

Вопрос 4

Операция упрощения графа путем объединения компонент сильной связности – это …

транзитивное замыкание
дополнение
стягивание
конденсация

Вопрос 5

… – это граф, который всегда является ациклическим

Полный граф
Дерево
Двудольный граф
Ориентированный граф

Вопрос 6

… путь проходит через все вершины графа ровно один раз

Гамильтонов
Эйлеров
Простой
Полный

Вопрос 7

У графа с n вершинами и 0 ребрами – … компонент связности

0
1
n
n – 1

Вопрос 8

В полном графе с 5 вершинами – … ребер

10
десять

Вопрос 9

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

цикл
циклом
контур
контуром

Вопрос 10

Количество компонент связности у графа, состоящего из 3 изолированных вершин, равно …

3
три
трем
трём

Вопрос 11