Тест, Структуры и Алгоритмы компьютерной обработки данных Опции

[SiNaC0m]

М

Перенесено в теоретические вопросы

Кто разберается, проверте меня пожалуйсто.
В худшем случае поиск элемента в бинарном дереве поиска из N узлов осуществляется за время
а) O(n)
б) O(log n)
в) O(1)
г) O(n log n)
ответ: а

Для того, чтобы напечатать узлы бинарного дерева поиска в порядке возрастания нужно применить
а) инфиксный обход
б) постфиксный обход
в) префиксный обход
г) поуровневый обход
ответ: б

Пусть время работы алгоритма Т(n) = O(n3). Если 1000 элементов обрабатываются за 2 мсек., то при обработке 3000 элементов следует ожидать увеличения времени выполнения
а) в 9 раз
б) в 6 раз
в) в 30 раз
г) в 27 раз
ответ: г

Нижняя оценка времени работы алгоритма показывает
а) среднее время работы
б) лучшее время работы
в) гарантированное время работы
г) асимптотически точное время работы
ответ: б

Если при удвоении количества элементов время работы алгоритма (Т(n)) растёт на постоянную величину, то данный алгоритм относится к классу
а) линейных (Т(n) = О(n))
б) логарифмических (Т(n) = О(log n))
в) с постоянным временем выполнения (Т(n) = О(1))
г) экспоненциальных (Т(n) = О(2n))
ответ: б

Пусть время работы алгоритма Т(n) = O(n). Если 1000 элементов обрабатываются за 1 мсек., то при обработке 3000 элементов следует ожидать увеличения времени выполнения
а) в 3 раза
б) в 6 раз
в) в 9 раз
г) на постоянную величину
ответ: а?(так как при удвоении N, время удваивается)

Сообщение отредактировано: klem4 - 4.04.2007 11:13

[Максим]

Для того, чтобы напечатать узлы бинарного дерева поиска в порядке возрастания нужно применить
а) инфиксный обход
б) постфиксный обход
в) префиксный обход
г) поуровневый обход
ответ: б

Уже так понимаю неактуально. ответ (в).
1
2 3
4 5 6 7 (1-2-3-4-5-6-7)
это префиксный


А вот постфиксный.

7
3 6
1 2 4 5 (1-2-3-4-5-6-7)