Основи теорії алгоритмів на графах | Тест з інформатики

Запитання 1

Реалізацію якого алгоритму зображено на малюнку?

(a - матриця суміжності навантаженого графа)

варіанти відповідей

пошук в ширину

пошук в глибину

алгоритм Дейкстри

алгоритм Флойда-Уоршалла

Запитання 2

Реалізацію якого алгоритму зображено на малюнку?

(a - матриця суміжності невантаженого графа

queue - черга вершин, що обробляються

visible - список "побачених" вершин)

варіанти відповідей

пошук в глибину

алгоритм Дейкстри

пошук в ширину

алгоритм Флойда-Уоршалла

Запитання 3

Реалізацію якого алгоритму зображено на малюнку?

(a - матриця суміжності невантаженого графа

stack - стек вершин, які обробляються

visited - список відвіданих вершин )

варіанти відповідей

пошук в ширину

пошук в глибину

алгоритм Дейкстри

алгоритм Флойда-Уоршалла

Запитання 4

Реалізацію якого алгоритму зображено на малюнку?

(a - матриця суміжності навантаженого графа,

visit - список відвіданих вершин,

dist - список мінімальних відстаней від стартової вершини до всіх решти )

варіанти відповідей

пошук в глибину

алгоритм Дейкстри

пошук в ширину

алгоритм Флойда-Уоршалла

Запитання 5

Для розв'язку яких із наведених нижче проблем можна використати ОДНЕ використання алгоритму ПОШУКУ В ГЛИБИНУ (граф заданий матрицею суміжності)?

варіанти відповідей

дослідження, чи є шлях від однієї вершини до іншої

пошук мінімального шляху між двома вершинами

визначення всіх вершин, що знаходяться в одній компоненті зв'язності графа із поточною

пошук шляху мінімальної сумарної ваги (для навантаженого графа)

пошук шляху мінімальної сумарної ваги (для навантаженого графа) для всеможливих комбінації стартових та кінцевих вершин

Запитання 6

Для розв'язку яких із наведених нижче проблем можна використати ОДНЕ використання алгоритму ПОШУКУ В ШИРИНУ (граф заданий матрицею суміжності)?

варіанти відповідей

дослідження, чи є шлях від однієї вершини до іншої

визначення всіх вершин, що знаходяться в одній компоненті зв'язності графа із поточною

пошук шляху (мінімальна кількість пройдених ребер) між двома вершинами

пошук шляху мінімальної сумарної ваги (для навантаженого графа) для ОДНІЄЇ пари вершин: стартової та кінцевої

пошук шляху мінімальної сумарної ваги (для навантаженого графа) для всеможливих комбінації стартових та кінцевих вершин

Запитання 7

Для розв'язку яких із наведених нижче проблем можна використати ОДНЕ використання алгоритму ДЕЙКСТРИ (граф заданий матрицею суміжності)?

варіанти відповідей

дослідження, чи є шлях від однієї вершини до іншої

визначення всіх вершин, що знаходяться в одній компоненті зв'язності графа із поточною (мінімальні відстані в списку буть менші за "умовну нескінченність")

пошук кількості компонент зв'язності в графі

пошук шляху мінімальної сумарної ваги (для навантаженого графа) для всеможливих комбінацій стартових та кінцевих вершин

пошук шляху мінімальної сумарної ваги (для навантаженого графа) для ОДНІЄЇ пари вершин: стартової та кінцевої

Запитання 8

Для розв'язку яких із наведених нижче проблем можна використати ОДНЕ використання алгоритму Флойда-Уоршалла (граф заданий матрицею суміжності)?

варіанти відповідей

дослідження, чи є шлях від однієї вершини до іншої (шлях відсутній, якщо a[i,j] = 0)

пошук шляху мінімальної сумарної ваги (для навантаженого графа) для ОДНІЄЇ пари вершин: стартової та кінцевої

визначення всіх вершин, що знаходяться в одній компоненті зв'язності графа із поточною (мінімальні відстані в списку відстаней буть менші за "умовну нескінченність")

пошук ВАГИ шляху мінімальної сумарної ваги (для навантаженого графа) для всеможливих комбінацій стартових та кінцевих вершин

пошук ВАГИ шляху мінімальної сумарної ваги (для навантаженого графа) для ОДНІЄЇ пари вершин: стартової та кінцевої

Запитання 9

Які з наведених алгоритмів не змінюють в процесі свого виконання матрицю суміжності графа?

варіанти відповідей

Пошук в ширину

Пошук в глибину

Алгоритм Дейкстри

Алгоритм Флойда-Уоршалла

Запитання 10

Які із наведених алгоритмів недоцільно (чи немає змісту) використовувати для ненавантажених графів?

варіанти відповідей

пошук в ширину

пошук в глибину

алгоритм Дейсктри

алгоритм Флойда-Уоршалла

Запитання 11

Чи можна використовувати алгоритм Дейкстри та Флойда-Уоршалла для графів із від'ємними вагами ребер?

варіанти відповідей

Так, завжди можна

Ні, не можна.