Computer Science II - Juniata College



Spring ‘04

March 31, 2004

(100 points out of 105)

Name_____________________________

1. Linked lists.

a) Draw a box and pointer diagram to represent the ordered list (“cat”, “dog”, “fish”) as pointed to by head. The linked list starts with a dummy head node. Make the list circular.

[5 pts]

b) Supply the declarations and assignment statements in the Java LList class below to support the implementation of a simple (non-circular) linked list in which each node holds one Listable item and a next reference.

[12 pts]

public class LList implements ListInterface

private class Node {

_________________________________

__________________________________

private Node(Listable s){

______________________________

______________________________

}//end constructor

}//end Node inner class

// define and initialize the head pointer

______________________________

public LList(){

__________________________________

}//end constructor

}

c) Show the Java code that would add the value “ant” as a new first node of this ordered list (push).

[6 pts]

_______________________________

_______________________________

_______________________________

2. Fill in the code below to complete the dequeue operation using a singly linked list implementation (no dummy head node). Assume head and tail are Node pointer instance variables for the queue.

[7 pts]

public Listable dequeue(){

if (______ == null)

throw new IllegalArgumentException

("Trying to dequeue an empty queue");

Node node = ________;

head = _________._________;

size_____;

if (size == 0){

tail = _______;

}

return ___________;

}

3. Give the complexities, linear or constant for each of the operations of the implied data structure that are implemented as a linked list.

[8 pts]

_________ dequeue()

_________ enqueue(item)

_________ pop()

_________ delete(item)

_________ insert(item) //into a sorted list

_________ insert(item) //unsorted list

_________ getNextItem()

_________ isThere(item)

4. Fill in the blanks to implement a recursive linked list (unsorted) search algorithm. Assume there is a public helper function that calls the recursive function:

public Listable LLSearch(Listable key){

return LLSearch(key, head);

}

[10 pts]

private Listable LLSearch(Comparable key, Node current){

if( __________ == _______ ) {

return null; //not found

} else {

if(______.compareTo(_________.info) != ___ ){

return LLSearch(______ , ________.________);

} else { // found it

return ___________.________ ;

}

}

}

5. The following defines a function that calculates an approximation of the square root of a number (number), starting with an approximate answer(approx) to within the specified tolerance (tol).

sqrRoot(number,approx,tol) = approx, if abs(approx*approx-number) ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download