Программирование и знакомство с алгоритмами

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

Номер 1

Граф это

Ответ:

(1) граф - это совокупность объектов со связями между ними

(2) граф - это набор несвязанных объектов

(3) граф - это совокупность всех связей одного объекта

Номер 2

Графом называют

Ответ:

(1) граф - это пара непустое множество вершин объекта

(2) граф - это пара <V, E>, где V - непустое множество вершин, а Е - множество ребер, соединяющих эти вершины

(3) граф - это пара <E, V>, где V - непустое множество вершин, а Е - множество ребер, соединяющих эти вершины

Номер 3

Вершина v достижима из вершины u

Ответ:

(1) если существует путь, начинающийся в u и заканчивающийся в v

(2) только если эти вершины смежны

(3) только в том случае если расстояние между этими вершинами равно 0

Упражнение 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) для любых вершин u,v есть путь из u в v

(2) количество вершин равно количеству рёбер

(3) распределение типов данных

Номер 2

Если для любых вершин u,v есть путь из u в v, то граф называют

Ответ:

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

(2) связным

(3) полным

Номер 3

Граф называется деревом, если

Ответ:

(1) он связный и не содержит простых циклов

(2) он связный и содержит простые циклы

(3) он несвязный и не содержит простых циклов

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

Номер 1

Граф называется сильно связным если

Ответ:

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

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

(3) из любой вершины в любую другую имеется путь

Номер 2

Ориентированный граф, из любой вершины которого имеется ориентированный путь в любую другую, называется

Ответ:

(1) связным

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

(3) слабо связным

Номер 3

Граф называется полным, если

Ответ:

(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) таблица, которая показывает количество вершин у каждого ребра

(2) таблица, которая показывает количество рёбер у каждой вершины

(3) среди перечисленных вариантов нет правильного

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

Номер 2

В сильно связном ориентированном графе матрица смежности

Ответ:

(1) нулевая

(2) симметрична относительно главной диагонали

(3) симметрична относительно побочной диагонали

Номер 3

Матрица смежности

Ответ:

(1) это таблица, которая показывает соединённые вершины

(2) это таблица, которая показывает количество вершин

(3) это таблица, которая показывает количество рёбер

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

Номер 1

Смешанный граф это

Ответ:

(1) граф, в котором некоторые рёбра могут быть ориентированными, а некоторые - неориентированными

(2) граф, в котором все рёбра ориентированы

(3) граф, в котором все рёбра неориентированы

Номер 2

Граф, в котором некоторые рёбра могут быть ориентированными, а некоторые - неориентированными называется

Ответ:

(1) нулевым

(2) несмежным

(3) смешанным

Номер 3

Верно ли утверждение, что ориентированный и неориентированный графы являются частными случаями смешанного?

Ответ:

(1) да, верно

(2) нет, неверно

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

Программирование и знакомство с алгоритмами - тест 10