игра брюс 2048
Главная / Алгоритмы и дискретные структуры / "Продвинутые" алгоритмы для школьников / Тест 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)

 (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) 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)

 (3)


Номер 3
Имеются два дерева: A и B. C какой вероятностью корень будет лежать в дереве A?

Ответ:

 (1) A/(A+B) 

 (2) A/B 

 (3) A-B 


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




Главная / Алгоритмы и дискретные структуры / "Продвинутые" алгоритмы для школьников / Тест 11