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

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

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

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

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

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

Вопрос 1

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

Лист
Корень
Лес
Остовное дерево
вершина степени 1
вершина с нулевой степенью захода, в которую не ведут дуги
набор непересекающихся деревьев
подграф, содержащий все вершины исходного графа без циклов

Вопрос 2

Упорядочьте шаги алгоритма Прима:

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

Вопрос 3

Говоря о графе «дерево», можно утверждать, что … (укажите 3 варианта ответа)

дерево может содержать циклы
это связный граф без циклов
в дереве с n вершинами количество ребер равно n – 1
между любыми двумя вершинами дерева существует ровно один путь

Вопрос 4

В бинарном дереве поиска …

оба потомка равны родителю
правый потомок всегда меньше родителя
левый потомок всегда меньше родителя
правый потомок всегда равен родителю

Вопрос 5

Минимальное остовное дерево …

всегда единственно
может не быть единственным
содержит все возможные ребра графа
имеет максимально возможную сумму весов ребер

Вопрос 6

В полном бинарном дереве …

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

Вопрос 7

В алгоритме Прима …

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

Вопрос 8

Количество ребер в дереве с 10 вершинами – … ребер

9
девять

Вопрос 9

Количество листьев в полном бинарном дереве высотой 3 – … листьев

8
восемь

Вопрос 10

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

бинарным

Вопрос 11