Базовые алгоритмы для школьников

Упражнение 1:

Номер 1

Для решения каких задач используется поиск в глубину?

Ответ:

(1) для поиска односвязных компонент

(2) для поиска двусвязных компонент

(3) для топологической сортировки

Номер 2

Сколько входов и выходов из верешин будет выполнено при поиске в глубину по приведенному графу при условии, что поиск начинается с вершины (1)?

Ответ:

(1) 13

(2) 14

(3) 15

Номер 3

Сколько входов и выходов из верешин будет выполнено при поиске в глубину по приведенному графу при условии, что поиск начинается с вершины (1)?

Ответ:

(1) 10

(2) 11

(3) 12

Упражнение 2:

Номер 1

Какой граф является ациклическим?

Ответ:

(1)

(2)

(3)

Номер 2

Для каких графов может быть выполнена топологическая сортировка?

Ответ:

(1)

(2)

(3)

Номер 3

Для каких графов не может быть выполнена топологическая сортировка?

Ответ:

(1)

(2)

(3)

Упражнение 3:

Номер 1

Какие утверждения являются верными?

Ответ:

(1) топологическая сортировка может быть выполнена для любого неориентированного графа

(2) топологическая сортировка может быть выполнена для любого ориентированного графа

(3) топологическая сортировка может быть выполнена только для ациклического ориентированного графа

(4) топологическая сортировка может быть выполнена только для циклического ориентированного графа

Номер 2

Какие утверждения являются неверными?

Ответ:

(1) топологическая сортировка может быть выполнена для любого неориентированного графа

(2) топологическая сортировка может быть выполнена для любого ориентированного графа

(3) топологическая сортировка может быть выполнена только для ациклического ориентированного графа

(4) топологическая сортировка может быть выполнена только для циклического ориентированного графа

Номер 3

Для каких графов выполняется топологическая сортировка?

Ответ:

(1) для всех ориентированных графов

(2) для ациклических ориентированых графов

(3) для циклических ориентированых графов

(4) для всех неориентированных графов

Упражнение 4:

Номер 1

Какой номер будет иметь вершина (1) после топологической сортировки графа?

Ответ:

(1) 1

(2) 2

(3) 3

(4) 4

Номер 2

Какой номер будет иметь вершина (2) после топологической сортировки графа?

Ответ:

(1) 1

(2) 2

(3) 3

(4) 4

Номер 3

Какой номер будет иметь вершина (3) после топологической сортировки графа?

Ответ:

(1) 1

(2) 2

(3) 3

(4) 4

Упражнение 5:

Номер 1

Какие утверждения являются верными после выполнения топологической сортировки?

Ответ:

(1) если граф был ациклическим, то будет построена его топологическая сортировка

(2) если граф был циклическим, то у него не будет топологической сортировки

(3) если граф был ациклическим, то у него не будет топологической сортировки

(4) если граф был циклическим, то будет построена его топологическая сортировка

Номер 2

Какие утверждения являются неверными после выполнения топологической сортировки?

Ответ:

(1) если граф был ациклическим, то будет построена его топологическая сортировка

(2) если граф был циклическим, то у него не будет топологической сортировки

(3) если граф был ациклическим, то у него не будет топологической сортировки

(4) если граф был циклическим, то будет построена его топологическая сортировка

Номер 3

Что произойдет после выполнения топологической сортировки для циклического графа?

Ответ:

(1) будет построена верная топологическая сортировка графа

(2) будет построена неверная топологическая сортировка графа

(3) у графа не будет топологической сортировки

Упражнение 6:

Номер 1

Для чего предназначен алгоритм Дейкстры?

Ответ:

(1) для поиска кратчайшего пути между всеми парами вершин в графе

(2) для поиска кратчайшего пути между двумя данными вершинами в графе, если длины дуг неотрицательны

(3) для определения, существует ли цепь <u,v>

Номер 2

Какое утверждение является верным?

Ответ:

(1) алгоритм Дейкстры находит кратчайший путь между всеми парами вершин в графе

(2) алгоритм Дейкстры находит кратчайший путь между двумя данными вершинами в графе, если длины дуг неотрицательны

(3) алгоритм Дейкстры позволяет ответить на вопрос, существует ли цепь <u,v>

Номер 3

Какие утверждения являются неверным?

Ответ:

(1) алгоритм Дейкстры находит кратчайший путь между двумя данными вершинами в графе, если длины дуг неотрицательны

(2) алгоритм Дейкстры находит кратчайший путь между всеми парами вершин в графе

(3) алгоритм Дейкстры позволяет ответить на вопрос, существует ли цепь <u,v>

Упражнение 7:

Номер 1

Что такое остовное дерево?

Ответ:

(1) ациклический связный подграф данного графа, в который входят все его вершины и является деревом

(2) циклический связный подграф данного графа, в который входят все его вершины

(3) связный граф без циклов

Номер 2

Какой алгоритм позволяет построить остовное дерево?

Ответ:

(1) поиск в ширину

(2) поиск в глубину

(3) алгоритм Дейкстры

Номер 3

Каким условиям должны удовлетворять подмножества рёбер графа, из которых состоит остовное дерево?

Ответ:

(1) из любой вершины графа можно попасть в любую другую вершину, двигаясь по этим рёбрами

(2) подмножество рёбер графа не содержит циклов

(3) подмножества рёбер графа содержит циклы

Упражнение 8:

Номер 2

Сколько остовных деревьев имеет заданный граф?

Ответ:

(1) 1

(2) 3

(3) 9

Номер 3

Какой граф имеет остов?

Ответ:

(1) любой граф

(2) связный граф

(3) несвязный граф

Упражнение 9:

Номер 1

Какие утверждения являются верными?

Ответ:

(1) связный граф может иметь только один остов

(2) связный граф может иметь много остовов

(3) несвязный граф может иметь только один остов

(4) несвязный граф не имеет остова

Номер 2

Какие утверждения являются неверными?

Ответ:

(1) связный граф может иметь только один остов

(2) связный граф может иметь много остовов

(3) несвязный граф может иметь только один остов

(4) несвязный граф не имеет остова

Номер 3

На каких рисунках изображен кратчайший остов заданного графа?

Ответ:

(1)

(2)

(3)

Упражнение 10:

Номер 1

Какие алгоритмы предназначены для построения минимального остовного дерева взвешенного связного неориентированного графа?

Ответ:

(1) алгоритм Краскала

(2) алгоритм Дейкстры

(3) алгоритм Прима

Номер 2

Какие алгоритмы не предназначены для построения минимального остовного дерева взвешенного связного неориентированного графа?

Ответ:

(1) алгоритм Краскала

(2) алгоритм Дейкстры

(3) алгоритм Прима

Номер 3

Сколько рёбер у разреза заданного графа, если (С) - синяя вершина, (К) - красная вершина?

Ответ:

(1) 0

(2) 2

(3) 4

Упражнение 11:

Номер 1

Какие утверждения являются верными?

Ответ:

(1) остовный лес не может содержать одно дерево

(2) остовый лес может содержать несколько деревьев

(3) остовный лес может не содержать ни одного ребра

Номер 2

В каком случае изображен остовный лес?

Ответ:

(1)

(2)

(3)

Номер 3

В каком случае изображен не остовный лес?

Ответ:

(1)

(2)

(3)

Упражнение 12:

Номер 1

Какие утверждения являются верными?

Ответ:

(1) взвешенный граф является допустимым, если его можно достороить до минимального остовного дерева

(2) само минимальное остовное дерево является допустимым

(3) разрез согласован с лесом, если в разрезе нет рёбер леса

Номер 2

В каком случае остовный лес является допустимым?

Ответ:

(1)

(2)

(3)

Номер 3

В каком случае остовный лес не является допустимым?

Ответ:

(1)

(2)

(3)

Базовые алгоритмы для школьников - тест 6