Java Test 20120321 — различия между версиями

Материал из SEWiki
Перейти к: навигация, поиск
Строка 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. Дерево должно быть реализовано таким образом, что в левой ветке храняться узлы со значением меньше корня, а в правой - больше корня. В классе должны быть реализованы следующие методы:

  1. добавление узла (при добавлении элемента, значение которого уже присутствует в дереве должно быть сгенерированно Ваше собственное исключение BinaryTreeInsertionException)
  2. нахождение высоты дерева
  3. поиск элемента

(3 балла)

Создайте параметризованный интерфейс Selector<T>, содержащий следующие методы:

  1. T current()
  2. boolean hasNext()
  3. 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'ы должны быть реализованы таким образом, чтобы время работы операций было следующим:

  1. current - O(1)
  2. hasNext, next - в лучшем случае О(1), в худшем О(logN)

(1 балл)

Создайте непараметризованный класс, содержащий статический параметризованный метод, принимающий на вход Selector и печатающий все элементы контейнера, к которому относится переданный Selector.

(1 балл)

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