Главная /
Основы дискретной математики /
Какие из следующих утверждений о работе алгоритма Дейкстры на графе с n вершинами верны? А) Значения D[w] текущего расстояния от исходной вершины до вершины w, добавляемой на каждом этапе к множеству отмеченных вершин S, не возрастают.Б) Число этапов (ите
Какие из следующих утверждений о работе алгоритма Дейкстры на графе с n вершинами верны?
А) Значения D[w]
текущего расстояния от исходной вершины до вершины w
, добавляемой на каждом этапе к множеству отмеченных вершин S
, не возрастают. Б) Число этапов (итераций основного цикла) не превосходит (n - 1)
. В) На каждом этапе алгоритма Дейкстры кратчайший путь из исходной вершины в любую вершину множества S
не длиннее кратчайшего пути из исходной вершины в любую вершину множества (V \ S)
.
вопрос
D[w]
текущего расстояния от исходной вершины до вершины w
, добавляемой на каждом этапе к множеству отмеченных вершин S
, не возрастают.(n - 1)
.S
не длиннее кратчайшего пути из исходной вершины в любую вершину множества (V \ S)
.Правильный ответ:
только А
только Б
только В
А и Б
А и В
Б и В
все
Сложность вопроса
77
Сложность курса: Основы дискретной математики
82
Оценить вопрос
Комментарии:
Аноним
Я провалил зачёт, какого чёрта я не нашёл этот великолепный сайт с всеми ответами по тестам интуит до того как забрали в армию
12 мар 2020
Аноним
ответ подошёл
23 янв 2020
Аноним
Экзамен сдан на 4 с минусом. Спасибо сайту
28 июл 2017
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Какое из следующих перечислений вершин бинарного дерева T: [Большая Картинка] представляет его обход в прямом (префиксном) порядке?
- # Построить для заданного нагруженного неориентированного графа G=(V,E) минимальный остов. V= {a, b, c, d, e, f, g, h, k },E= {(a,b; 10), (a,c; 9),(a,f; 20), (a,k; 7), (b, d; 17), (b,f; 27), (b,g; 10), (c, d; 17), ( c,g; 3), (c, h; 9), (d, e; 5), (d,f; 20), (h,g; 10), (h,k; 12) }. (здесь каждая скобка (u,v; D) задает ребро (u,v) из E и его "вес" c(u,v)=D ). Каков вес этого остова?
- # [Большая Картинка] Представленная выше таблица показывает бинарное кодирование десятичных цифр от 0 до 9 (коды начинаются с 4-ой строки). Какие из булевых формул задают множество всех ошибочных кодов?
- # Булева функция f(X0, X1, X2)равна 1, если число, двоичная запись которого имеет вид X2X1X0, равно 3, 4, 5или 7. Какая из следующих формул задает эту функцию?
- # Какие из следующих формул логики предикатов являются тождественно истинными? ( ∀x P(x) → ∀x Q(x) ) → ∀x ( P(x) → Q(x) )∀x ( P(x) → Q(x) ) → ( ∀x P(x) → ∀x Q(x) )(∃x P(x) → ∃x Q(x) ) → ∃x ( P(x) → Q(x) )