Главная / Алгоритмы и дискретные структуры /
"Продвинутые" алгоритмы для школьников / Тест 11
"Продвинутые" алгоритмы для школьников - тест 11
Упражнение 1:
Номер 1
Какие данные можно записывать в вершины корневого дерева?
Ответ:
 (1) числа 
 (2) идентификаторы 
 (3) массивы 
Номер 2
В каком случае двоичное дерево будет деревом поиска?
Ответ:
 (1) если в одной части дерева хранятся значения, больше вершины, а в другой - меньше 
 (2) если матрица достижимости для него будет бинарной 
 (3) если орграф такого дерева будет циклическим 
Номер 3
Может ли двоичное дерево быть деревом поиска?
Ответ:
 (1) да, может 
 (2) нет, не может 
 (3) только матричное дерево 
Упражнение 2:
Номер 1
Максимальное расстояние от корня до листа в дереве носит название
Ответ:
 (1) высота 
 (2) ширина 
 (3) длина 
Номер 2
Высота дерева - это
Ответ:
 (1) количество его вершин 
 (2) сумма весов его ребер 
 (3) максимальное расстояние от корня до листа 
Номер 3
Максимальное расстояние от корня до листа в дереве составляет 5. Какова высота дерева?
Ответ:
 (1) 4 
 (2) 5 
 (3) 6 
Упражнение 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) AVL-дерево 
 (3) 2-3-дерево 
Упражнение 5:
Номер 1
Может ли дерево поиска быть случайным?
Ответ:
 (1) да, может 
 (2) нет, не может 
 (3) только ассоциативное дерево 
Номер 2
Корнем дерева может быть
Ответ:
 (1) только главная вершина 
 (2) только ассоциативная вершина 
 (3) любая вершина 
Номер 3
Двоичное дерево поиска, у которого каждая вершина является корнем с равной вероятностью, носит название
Ответ:
 (1) случайное 
 (2) модифицированное 
 (3) контекстное 
Упражнение 6:
Номер 1
Пусть N
- количество вершин в случайном двоичном дереве поиска. Тогда вероятность того, что вершина может быть корнем, составляет
Ответ:
 (1) 1/N
 
 (2) N-2
 
 (3) logN
 
Номер 2
Функция, которая возвращает случайное число, носит название
Ответ:
 (1) mode
 
 (2) random
 
 (3) rect
 
Номер 3
Для чего в Паскале применяется функция random?
Ответ:
 (1) для возврата случайного числа 
 (2) для округления переменных 
 (3) для целочисленного деления 
Упражнение 7:
Номер 1
Что нужно сделать, чтобы добавить вершину в корень?
Ответ:
 (1) разбить дерево на два поддерева и подвесить их к вершине 
 (2) использовать вызов ассоциативных массивов 
 (3) применить алгоритм Флойда-Уоршелла 
Номер 2
Какова вероятность подвесить дерево с одной вершиной?
Ответ:
 (1) 0,5 
 (2) 0 
 (3) 1 
Номер 3
Имеются два дерева: A
и B
. C какой вероятностью корень будет лежать в дереве A
?
Ответ:
 (1) A/(A+B)
 
 (2) A/B
 
 (3) A-B
 
Упражнение 8:
Номер 1
Сколько ключей хранится в вершине декартового дерева?
Ответ:
 (1) 1 
 (2) 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) структурное дерево