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

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

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

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

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

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

Вопрос 1

Соотнесите алгоритмы с их ключевыми свойствами:

  1. Алгоритм Дейкстры
  2. Алгоритм Форда–Беллмана
  3. Алгоритм Флойда–Уоршелла
  4. Алгоритм А*
  5. работает только с неотрицательными весами
  6. обнаруживает отрицательные циклы
  7. находит пути между всеми парами вершин
  8. использует эвристику для ускорения поиска
Вопрос 2

Упорядочьте шаги алгоритма Форда–Беллмана:

  1. инициализировать расстояния: 0 для стартовой вершины, ∞ для остальных
  2. для каждого ребра (u, v) выполнить релаксацию: если d[u] + w(u, v) < d[v], обновить d[v]
  3. повторить релаксацию n – 1 раз (где n – число вершин)
  4. проверить наличие отрицательных циклов: если на n-й итерации происходит релаксация, цикл есть
  5. вернуть итоговые расстояния или сообщение об отрицательном цикле
Вопрос 3

Алгоритм … требует хранения всей матрицы расстояний

  1. Дейкстры
  2. Форда–Беллмана
  3. Флойда–Уоршелла
  4. Крускала
Вопрос 4

Если применить алгоритм Дейкстры к графу с отрицательными весами, …

  1. это всегда даст правильный результат
  2. это может дать неправильный результат
  3. алгоритм будет работать медленнее
  4. алгоритм прекратит работу с ошибкой
Вопрос 5

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

  1. Форда–Беллмана
  2. Флойда–Уоршелла
  3. Дейкстры
  4. Прима
Вопрос 6

Алгоритм … использует релаксацию ребер (укажите 2 варианта ответа)

  1. Флойд–Уоршелл
  2. Форда–Беллмана
  3. Дейкстры
  4. A*
Вопрос 7

Алгоритм … основан на динамическом программировании

  1. Дейкстры
  2. Форда–Беллмана
  3. Флойда–Уоршелла
Вопрос 8

… – это путь, сумма весов ребер которого минимальна

  1. Эйлеров путь
  2. Гамильтонов путь
  3. Кратчайший путь
  4. Минимальный остов
Вопрос 9

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

  1. Релаксация
Вопрос 10

… граф – это граф, где каждому ребру присвоено числовое значение

  1. Взвешенный
Вопрос 11

На рисунке представлен ориентированный граф.  

  1. 6
  2. 7
  3. 8
  4. 12