MIDTERM
2
CS203,
Spring 2006
Please upload your source code and other files using CSNS
at the
end of the exam.
Note that file
uploading will be disabled automatically after 3:30PM, so please turn
in your work on time. Before turn in
your programs, try to
compile and run them and make sure they work correctly. If your program
does not even compile, you receive an automatic 50% credit deduction
for that
problem, no matter how "close" the program seems to be correct.
Consider an OrderedLinkedList
class, which is similar
to the DoubleLinkedList
class we implemented in Homework
1, except
that the nodes in the list are always sorted based on the value
field
in the ListNode
class. Note that
there is a class variable order
in the
OrderedLinkedList
class, which
indicates whether the nodes are sorted in
ascending order or descending
order. For this problem, you must
complete the OrderedLinkedList
class by implementing the following two
methods:
- (30pt) OrderedLinkedList
intersect(OrderedLinkedList other)
- returns a new ordered list which contains the elements that appear in
both lists. For example, if one list contains the elements 10, 20, 21,
and 30, and the other list contains 10, 15, 30, and 40, then the
intersection of the two lists is 10 and 30. Note that the two lists may
be sorted in different order.
- (30pt) void
insert(OrderedLinkedList other)
- insert all the elements in the given list into this list. Note that
the two lists may be sorted in different order.
- (40pt) OrderedLinkedList
remove(int beginIndex, int endIndex)
- remove all the elements between beginIndex
and endIndex-1, and
return
them as an OrderedLinkedList.
For example, if beginIndex
is 0 and endIndex is 3,
the method should remove the first three (not four) elements from the
original list. The method should throws an exception if
the indexes are out of bound.
The worst-case complexity of
all the methods above must be linear or better; otherwise you will not
receive any credit. You may add more methods to the OrderedLinkedList
class if necessary, however, you may not add or remove any class
variables, and
you may not change the ListNode
class in any way.