- A polynomial can be represented by a linked list of nodes, where each node
is of the following type:
public class PolyNode
{
// Constructors
PolyNode( double coef, int exp )
{
this( coef, exp, null )
}
PolyNode( double coef, int exp, PolyNode n)
{
coefficient = coef;
exponent = exp;
next = n;
}
// data fields
double coefficient;
int exponent;
PolyNode next;
}
Assume you also have an iterator that is defined as follows:
public class PolyListItr
{
// Constructor
PolyListItr( PolyNode theNode)
{
current = theNode;
}
PolyNode current; // current position
}
Write a Java method int polyCompare(PolyListItr p1, PolyListItr p2)
that takes a PolyListItr p1 referencing polynomial1
and a
PolyListItr p2 referencing polynomial2, and returns 1 if
polynomial1 is >
polynomial2, 0 if they are equal, and -1 if polynomial1 is < polynomial 2.
Assume the PolyNodes are ordered by decreasing exponent. Note,
you may add methods (i.e. write them yourself) to the
PolyListItr class for use in polyCompare,
but you may not assume you have any available to you.
- Write a recursive Java method int sameStack(StackLi s1, StackLi s2)
to test whether two integer stacks contain the same elements. The
method will return 1 if the stacks contain the same elements and 0 otherwise.
No points will be given for an iterative solution. You can use the
StackLi methods
below in your method, and don't worry about how the data type
StackLi is implemented.
int topAndPop()
void push(int x)
boolean isEmpty()
- Prove by induction that the number of nodes in a full binary tree of
height k is 2^(k+1) - 1.
- Analyze the running time of binary search and show it is
O(Log(N)).
- Given the postfix expression 6 3 + 8 4 - *, describe in English
a stack algorithm that can be used to evaluate this expression.
- Given the infix expression (5 * (4 + 3^2) * 4 - 6), (a) draw an expression
tree for the expression, (b) write the prefix equivalent of the expression,
and (c) write the postfix equivalent of the expression.
- Write a Java method LinkedListItr evenList(LinkedListItr L)
that will take a linked list pointed to by a
LinkedListItr
L and return a LinkedListItr pointing
to a new linked list
that contains the even numbered elements of the list (2nd, 4th, 6th elements,
etc.). Assume each ListNode has an integer data field data
and a ListNode reference field next pointing to
the next node. Your method should leave the list L intact.
Assume ListNode is defined as follows:
public class ListNode
{
// Constructors
ListNode( int x )
{
this( x, null )
}
ListNode( int x, ListNode n)
{
data = x;
next = n;
}
// data fields
int data;
ListNode next;
}
Assume you also have an iterator that is defined as follows:
public class LinkedListItr
{
// Constructor
LinkedListItr( ListNode theNode)
{
current = theNode;
}
ListNode current; // current position
}
Note, you may add methods (i.e. write them yourself) to the
LinkedListItr class for use in evenList,
but you may not assume you have any available to you.
- A deque (double ended queue) is a queue in which additions and deletions
can be made from both ends or the queue. Assume we implement a deque as a
circularly linked list with an external pointer pointing to the rearmost
element of the queue. Which of the 4 operations on the deque, addFront,
addRear, deleteFront, deleteRear is the most difficult to implement with
this data structure? Why?
- A doubly linked list contains ListNodes that include left
and right pointers that allow traversal in either direction
along the list. Given a
LinkedListItr p that
references a
node to be deleted, write a Java method void delete(LinkedListItr p)
that deletes the node
from the list. Don't worry about any boundary conditions (i.e. empty list,
single element list, etc.). Assume you also have an iterator that is defined
as follows:
public class LinkedListItr
{
// Constructor
LinkedListItr( ListNode theNode )
{
current = theNode;
}
ListNode current; // current position
}
Note, you may add methods (i.e. write them yourself) to the
LinkedListItr class for use in delete,
but you may not assume you have any available to you.
- Write a Java method LinkeListItr reverse(LinkedList tail)
to
reverse the order of the elements of a circular queue. A circular queue
is represented by a pointer to the tail element of the queue. The method
is sent a
LinkedListItr referencing the tail node and will
return a LinkedListItr referencing the new tail node after the
list is reversed (the head node becomes the new tail node). Assume a standard
ListNode class for a node with a data field and a
next pointer. You may also
assume have an iterator that is defined as follows:
public class LinkedListItr
{
// Constructor
LinkedListItr( ListNode theNode )
{
current = theNode;
}
ListNode current; // current position
}
Note, you may add methods (i.e. write them yourself) to the
LinkedListItr class for use in reverse,
but you may not assume you have any available to you.
- Given the following orders of traversals of a binary tree, recreate the
tree:
Postorder: G, D, B, H, I, E, F, C, A
Inorder: D, G, B, A, H, E, I, C, F
- Given the following binary tree, print out the order of the nodes for an
inorder traversal, preorder traversal, and postorder traversal.
/ (division operator)
/ \
/ \
- *
/ \ / \
/ \ 2 a
^ *
/ \ / \
b 2 * c
/ \
4 a
- Write a recursive Java method void childSwap(BinaryNode t)
that will take a binary tree node t and swap the left and right children of
every node of the tree. Assume a tree node is defined by the following class:
class BinaryNode
{
Object element; // The data in the node
BinaryNode left; // Left child
BinaryNode right; // Right child
}
- Write a nonrecursive Java method
static AvlNode doubleRotateWithLeft(AvlNode k3) that performs
a double rotation on an AVL tree, without the inefficiency of doing two single
rotations. You can assume the following AvlNode class definition:
class AvlNode
{
// Constructors
AvlNode( Comparable theElement )
{
this( theElement, null, null )
}
AvlNode( Comparable theElement, AvlNode lt, AvlNode rt )
{
element = theElement;
left = lt;
right = rt;
height = 0;
}
// data fields
Comparable element; // The data in the node
AvlNode left; // Left child
AvlNode right; // Right child
int height; // Height
}
Assume you may also use the following method to compute the height of an
AVL node:
// returns the height of node t, or -1, if null
private static int height( AvlNode t )
{
return t == null ? -1 : t.height;
}
- (a) Show the result of inserting 3, 1, 4, 6, 9, 2, 5, 7 into an initially
empty binary search tree.
(b) Show the result of deleting the root.