Главная / Алгоритмы и дискретные структуры /
Комбинаторные алгоритмы для программистов / Тест 4
Номер 3
Ответ:
Комбинаторные алгоритмы для программистов - тест 4
Упражнение 1:
Номер 1
Ответ:
Номер 1
Что называют конечным корневым деревом Т?
Ответ:
(1) конечное корневое дерево
Т формально определяется как непустое множество упорядоченных узлов, таких, что существует один выделенный узел, называемый корнем дерева, а оставшиеся узлы разбиты на m≥0 поддеревьев Т1,Т2,...,Тm
(2) структура данных, представляющая дерево
(3) обобщение грамматики для описания древовидных структур
Номер 2
Ответ:
Что называют корнем дерева?
Ответ:
(1) исходный узел древовидной структуры, от которого доступны все остальные узлы
(2) корневой каталог
(3) корневой сегмент
(4) компонент транслятора, выполняющий оптимизацию
Что называют листьями дерева?
Ответ:
(1) узлы дерева, не имеющие поддеревьев
(2) вершины дерева, не имеющие сыновних вершин
(3) вершины дерева, не имеющие дочерних вершин
(4) лексический анализатор
Упражнение 2:
Номер 1
Ответ:
Номер 1
Какое дерево называют бинарным Т?
Ответ:
(1) либо пустое дерево, либо такое, которое состоит из выделенного узла, называемого корнем, и двух бинарных поддеревьев: левого
Тl и правого Тr
(2) неориентированное дерево
(3) связный граф без циклов
(4) связный граф с циклами
Номер 2
Ответ:
Что называют лесом?
Ответ:
(1) совокупность деревьев; удаление корневой вершины
(2) набор литер определенного размера и начертания
(3) символ управления форматом
(4) программу или часть системы подготовки текстов
Номер 3
Ответ:
Что понимают под обходом дерева?
Ответ:
(1) перебор вершин дерева
(2) древовидную топологию
(3) длительность цикла обработки
Упражнение 3:
Номер 1
Ответ:
Номер 1
Чем отличается процедура прохождения в глубину от процедуры прохождения в прямом порядке?
Ответ:
(1) процедура прохождения в глубину по дереву - это эквивалент процедуры прохождения в прямом порядке
(2) ничем не отличаются
(3) процедура прохождения в глубину по дереву более надежна
(4) на процедуру прохождения в глубину по дереву затрачивается меньше времени, чем на выполнение процедуры прохождения в прямом порядке
Номер 2
Ответ:
Чем отличается симметричный порядок для бинарных деревьев от лексикографического порядка?
Ответ:
(1) симметричный порядок для бинарных деревьев эквивалентен лексикографическому порядку
(2) симметричный порядок для бинарных деревьев более трудоемкий, чем лексикографический порядок
(3) симметричный порядок для бинарных деревьев менее трудоемкий, чем лексикографический порядок
(4) это одинаковые понятия
Номер 3
Ответ:
Что называют высотой дерева?
Ответ:
(1) максимальное число ребер, образующих путь от корня к листу дерева
(2) минимальное число ребер, образующих путь от корня к листу дерева
(3) максимальное число узлов, образующих путь от корня к листу дерева
(4) максимальное число корней, образующих путь от узла к листу дерева