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

Упражнение 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

Количество поддеревьев узла составляет 2. Какова степень данного узла?

Ответ:

(1) 2

(2) 4

(3) 3

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

Номер 1

Узел с нулевой степенью носит название

Ответ:

(1) замкнутый узел

(2) матричный узел

(3) концевой узел

Номер 2

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

Ответ:

(1) концевой узел

(2) матрицу смежности

(3) модуль вершины

Номер 3

Неконцевой узел носит название

Ответ:

(1) узел соответствия

(2) узел ветвления

(3) узел достижимости

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

Номер 1

Дерево с отмеченной вершиной называется

Ответ:

(1) конечным деревом

(2) корневым деревом

(3) модульным деревом

Номер 2

Подграф данного графа, содержащий все его вершины и являющийся деревом, носит название

Ответ:

(1) терминальное дерево

(2) остовное дерево

(3) комплексное дерево

Номер 3

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

Ответ:

(1) конечное дерево

(2) ориентированное дерево

(3) структурное дерево

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

Номер 1

Сколько ребер входит в корень ориентированного дерева?

Ответ:

(1) 1

(2) множество

(3) ни одного

Номер 2

Множество, не содержащее ни одного непересекающегося дерева, носит название

Ответ:

(1) лес

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

(3) вариант

Номер 3

Степени вершин в двоичном дереве не превосходят

Ответ:

(1) 2

(2) 3

(3) 4

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

Номер 1

Исходящие степени вершин двоичного дерева не превосходят

Ответ:

(1) 2

(2) 3

(3) 1

Номер 2

Может ли степень вершин двоичного дерева быть равной 4?

Ответ:

(1) да, может

(2) нет, не может

(3) только для связного графа

Номер 3

Могут ли исходящие степени вершин двоичного дерева быть равными 3?

Ответ:

(1) да, могут

(2) нет, не могут

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

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

Номер 2

Любое дерево с n вершинами содержит

Ответ:

(1) n-1 ребро

(2) 2n ребер

(3) 2n-1 ребро

Номер 3

Любое дерево является

Ответ:

(1) комплексным графом

(2) модульным графом

(3) двудольным графом

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

Номер 1

Любое дерево, содержащее счётное количество вершин, является

Ответ:

(1) унимодальным графом

(2) планарным графом

(3) комбинированным графом

Номер 2

Число различных деревьев, которые можно построить на n нумерованных вершинах, равно

Ответ:

(1) n²

(2) n^{n - 1}

(3) n^{n - 2}

Номер 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) O(Elog(V²))

(2) O(Elog(V))

(3) O(log(V))

Номер 3

Асимптотика Фибоначчиевой пирамиды в алгоритме Прима оценивается величиной

Ответ:

(1) O(logV²)

(2) O(E + Vlog(V))

(3) O(V²-1)

"Продвинутые" алгоритмы для школьников - тест 3