Java Test 20120321 - История изменений

Antonk в 08:16, 21 марта 2012

2012-03-21T08:16:20Z

Antonk в 06:52, 21 марта 2012

2012-03-21T06:52:59Z

Antonk в 06:37, 21 марта 2012

2012-03-21T06:37:32Z

Antonk в 06:30, 21 марта 2012

2012-03-21T06:30:56Z

Antonk в 06:28, 21 марта 2012

2012-03-21T06:28:31Z

Antonk в 06:27, 21 марта 2012

2012-03-21T06:27:51Z

Antonk: Новая страница: «(3 балла) Создайте параметризованный класс двоичного деревева поиска, позволяющий хранит…»

2012-03-21T06:13:40Z

Новая страница: «(3 балла) Создайте параметризованный класс двоичного деревева поиска, позволяющий хранит…»

Новая страница

(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 балл)

Ваша программа должна принимать в качестве параметра имя файла, содержащего целые числа. Эти числа должны добавляться в дерево в порядке их следования в файле. Программа должна выводить на экран эти числа от меньшего к большему и от большего к меньшему, используя описанные выше методы.

@@ Строка 4: / Строка 4: @@
 В классе должны быть реализованы следующие методы:
 # добавление узла (при добавлении элемента, значение которого уже присутствует в дереве должно быть сгенерированно Ваше собственное исключение BinaryTreeInsertionException)
-# нахождение высоты дерева
+# нахождение высоты дерева (возвращает int)
-# поиск элемента
+# поиск элемента (возвращает boolean)
 '''(3 балла)'''

@@ Строка 23: / Строка 23: @@
 Selector'ы должны быть реализованы таким образом, чтобы время работы операций было следующим:
 # current - O(1)
-# hasNext, next - в лучшем случае О(1), в худшем О(logN)
+# hasNext, next - в лучшем случае О(1), в худшем О(высоты дерева)
 '''(1 балл)'''

@@ Строка 13: / Строка 13: @@
 # boolean hasNext()
 # void next()
-Добавьте к классу дерева два метода, один позволяет получать Selector, перебирающий элементы от меньшего к большему, а другой - от большего к меньшему, соответственно.
+Добавьте к классу дерева два метода, один возвращает Selector, перебирающий элементы от меньшего к большему, а другой - от большего к меньшему, соответственно.
 '''(3 балла)'''

@@ Строка 18: / Строка 18: @@
 Сделайте так, чтобы эти 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)