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

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

Номер 1

Граф - это

Ответ:

(1) динамический массив

(2) совокупность объектов со связями между ними

(3) контейнер с ребрами и вершинами

Номер 2

Объекты графа носят название

Ответ:

(1) вершины

(2) модули

(3) маркеры

Номер 3

Связи в графе носят название

Ответ:

(1) мосты

(2) коннекторы

(3) ребра

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

Номер 1

Число вершин в графе носит название

Ответ:

(1) порядок

(2) глубина

(3) высота

Номер 2

Число ребер в графе определяет

Ответ:

(1) ширину графа

(2) размер графа

(3) степень графа

Номер 3

Если два ребра имеют общую концевую вершину, то они являются

Ответ:

(1) соседними

(2) побочными

(3) смежными

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

Номер 1

Если множества концевых вершин графа совпадают, то такие графы называются

Ответ:

(1) четными

(2) кратными

(3) битовыми

Номер 2

Если концы ребра совпадают, то ребро называется

Ответ:

(1) дугой

(2) петлей

(3) маркером

Номер 3

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

Ответ:

(1) контейнер

(2) путь

(3) трасса

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

Номер 1

Если ребра в пути не повторяются, такой путь является

Ответ:

(1) циклическим

(2) простым

(3) массивным

Номер 2

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

Ответ:

(1) массив ребер

(2) список ребер

(3) компонента ребер

Номер 3

Каким образом представляется ребро в списке ребер графа?

Ответ:

(1) весом

(2) номерами вершин

(3) компонентой соответствия

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

Номер 1

Две концевые вершины одного и того же ребра называются

Ответ:

(1) планарными

(2) соседними

(3) смежными

Номер 2

Вершина, степень которой равна 1, носит название

Ответ:

(1) стойкая

(2) висячая

(3) аддитивная

Номер 3

Вершина, степень которой равна 0, носит название

Ответ:

(1) модульная

(2) контекстная

(3) изолированная

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

Номер 1

Множество, на котором определено отношение частичного порядка, носит название

Ответ:

(1) гипермодальное

(2) частично упорядоченное

(3) авторизированное

Номер 2

Что представляет собой частичный порядок?

Ответ:

(1) бинарное отношение

(2) массивное отношение

(3) модульное отношение

Номер 3

Упорядочивание вершин бесконтурного ориентированного графа согласно частичному порядку, заданному ребрами орграфа на множестве его вершин, носит название

Ответ:

(1) глубинная сортировка

(2) топологическая сортировка

(3) динамическая сортировка

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

Номер 1

Каким должен быть граф при топологической сортировке?

Ответ:

(1) модальным

(2) контекстным

(3) бесконтурным

Номер 2

Граф при топологической сортировке должен быть

Ответ:

(1) ориентированным

(2) сильно связанным

(3) априорным

Номер 3

В качестве подпрограммы при топологической сортировке используется алгоритм

Ответ:

(1) CHM

(2) DFS

(3) AMT

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

Номер 1

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

Ответ:

(1) последовательным

(2) комплексным

(3) без циклов

Номер 2

Является ли топологическая сортировка рекурсивной?

Ответ:

(1) да, является

(2) нет, не является

(3) только в детерминированном графе

Номер 3

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

Ответ:

(1) весы ребер

(2) массивные подграфы

(3) путь, идущий по ребрам графа

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

Номер 1

При топологической сортировке номер начала дуги

Ответ:

(1) меньше номера конца дуги

(2) больше номера конца дуги

(3) равен номеру конца дуги

Номер 2

Если нумерация такова, что номер начала дуги всегда больше номера ее конца, то говорят

Ответ:

(1) о маркированной топологической сортировке

(2) об обратной топологической сортировке

(3) о модульной топологической сортировке

Номер 3

Нестрогий порядок называется

Ответ:

(1) аддитивным

(2) модификативным

(3) рефлексивным

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

Номер 1

В каком случае орграф называется сильно связным?

Ответ:

(1) если любые две его вершины сильно связаны

(2) если все его вершины сильно связаны

(3) если из каждой вершины существует не меньше двух путей в остальные

Номер 2

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

Ответ:

(1) модульными

(2) сильно связными

(3) комплексными

Номер 3

Сильно связными компонентами орграфа называются

Ответ:

(1) ребра графа

(2) вершины графа

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

Упражнение 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) множество подграфов

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