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.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- igcse computer science workbooks pdf
- igcse computer science workbook
- igcse computer science workbook answer
- igcse computer science coursebook pdf
- computer science people
- what is computer science like
- computer science revision
- igcse computer science revision notes
- college computer science project ideas
- ideas for computer science project
- computer science projects for students
- computer science final project