Java Test 20120321 — различия между версиями
Antonk (обсуждение | вклад) |
Antonk (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | (3 балла) | + | '''(3 балла)''' |
Создайте параметризованный класс двоичного деревева поиска, позволяющий хранить объекты, реализующие интерфейс java.lang.Comparable. Дерево должно быть реализовано таким образом, что в левой ветке храняться узлы со значением меньше корня, а в правой - больше корня. | Создайте параметризованный класс двоичного деревева поиска, позволяющий хранить объекты, реализующие интерфейс java.lang.Comparable. Дерево должно быть реализовано таким образом, что в левой ветке храняться узлы со значением меньше корня, а в правой - больше корня. | ||
| Строка 7: | Строка 7: | ||
# поиск элемента | # поиск элемента | ||
| − | (3 балла) | + | '''(3 балла)''' |
Создайте параметризованный интерфейс Selector<T>, содержащий следующие методы: | Создайте параметризованный интерфейс Selector<T>, содержащий следующие методы: | ||
| Строка 15: | Строка 15: | ||
Добавьте к классу дерева два метода, один позволяет получать Selector, перебирающий элементы от меньшего к большему, а другой - от большего к меньшему, соответственно. | Добавьте к классу дерева два метода, один позволяет получать Selector, перебирающий элементы от меньшего к большему, а другой - от большего к меньшему, соответственно. | ||
| − | (3 балла) | + | '''(3 балла)''' |
Сделайте так, чтобы эти Selector'ы корректно работали в том случае, если после создания Selector'а и прохождения нескольких элементов в дерево были добавлены узлы. Такие узлы должны быть выданы селектором в "естественном" порядке, т.е., например, селектор перебирающий элементы от меньшего к большему, выдает минимальный элемент из не обработанных. | Сделайте так, чтобы эти Selector'ы корректно работали в том случае, если после создания Selector'а и прохождения нескольких элементов в дерево были добавлены узлы. Такие узлы должны быть выданы селектором в "естественном" порядке, т.е., например, селектор перебирающий элементы от меньшего к большему, выдает минимальный элемент из не обработанных. | ||
| Строка 23: | Строка 23: | ||
# hasNext, next - в лучшем случае О(1), в худшем О(logN) | # hasNext, next - в лучшем случае О(1), в худшем О(logN) | ||
| − | (1 балл) | + | '''(1 балл)''' |
Создайте непараметризованный класс, содержащий статический параметризованный метод, принимающий на вход Selector и печатающий все элементы контейнера, к которому относится переданный Selector. | Создайте непараметризованный класс, содержащий статический параметризованный метод, принимающий на вход Selector и печатающий все элементы контейнера, к которому относится переданный Selector. | ||
| − | (1 балл) | + | '''(1 балл)''' |
Ваша программа должна принимать в качестве параметра имя файла, содержащего целые числа. Эти числа должны добавляться в дерево в порядке их следования в файле. Программа должна выводить на экран эти числа от меньшего к большему и от большего к меньшему, используя описанные выше методы. | Ваша программа должна принимать в качестве параметра имя файла, содержащего целые числа. Эти числа должны добавляться в дерево в порядке их следования в файле. Программа должна выводить на экран эти числа от меньшего к большему и от большего к меньшему, используя описанные выше методы. | ||
Версия 09:28, 21 марта 2012
(3 балла)
Создайте параметризованный класс двоичного деревева поиска, позволяющий хранить объекты, реализующие интерфейс java.lang.Comparable. Дерево должно быть реализовано таким образом, что в левой ветке храняться узлы со значением меньше корня, а в правой - больше корня. В классе должны быть реализованы следующие методы:
- добавление узла (при добавлении элемента, значение которого уже присутствует в дереве должно быть сгенерированно Ваше собственное исключение BinaryTreeInsertionException)
- нахождение высоты дерева
- поиск элемента
(3 балла)
Создайте параметризованный интерфейс Selector<T>, содержащий следующие методы:
- T current()
- boolean hasNext()
- void next()
Добавьте к классу дерева два метода, один позволяет получать Selector, перебирающий элементы от меньшего к большему, а другой - от большего к меньшему, соответственно.
(3 балла)
Сделайте так, чтобы эти Selector'ы корректно работали в том случае, если после создания Selector'а и прохождения нескольких элементов в дерево были добавлены узлы. Такие узлы должны быть выданы селектором в "естественном" порядке, т.е., например, селектор перебирающий элементы от меньшего к большему, выдает минимальный элемент из не обработанных. Например, к дереву с корнем 5 добавили узлы 2, 0, 4, 8, 6, 10. После чего, был создан селектор и с его помощью пройдены улы 0, 2, 4, 5, 6. Если после этого в дерево добавили узлы 1, 3, 7, то селектор следующими выдаст 1, 3, 7, 8, 10. Selector'ы должны быть реализованы таким образом, чтобы время работы операций было следующим:
- current - O(1)
- hasNext, next - в лучшем случае О(1), в худшем О(logN)
(1 балл)
Создайте непараметризованный класс, содержащий статический параметризованный метод, принимающий на вход Selector и печатающий все элементы контейнера, к которому относится переданный Selector.
(1 балл)
Ваша программа должна принимать в качестве параметра имя файла, содержащего целые числа. Эти числа должны добавляться в дерево в порядке их следования в файле. Программа должна выводить на экран эти числа от меньшего к большему и от большего к меньшему, используя описанные выше методы.
