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