Computer Science II - Juniata College



Computer Science II

100 pts

3/5/10

Name _____________________________

1. True/false on the abstract data types for arrays, lists (general linked lists) and stacks.

[10 pts]

_____ An array is bounded in size.

_____ An array is composed of heterogeneous elements.

_____ A list is composed of heterogeneous elements.

_____ A list is non-linear in organization.

_____ A stack’s bounded-ness in size is determined by its implementation.

_____ An array is limited to linear access to its elements.

_____ A stack limits access to the “top” element in first-in-first-out order.

_____ A stack has direct access operations to its elements.

_____ A list permits direct access to its elements.

_____ A stack may have two or more implementations.

2. Convert the following infix expression to prefix and postfix. Account for proper operator precedence. Be sure the operands in the expressions (a,b,c,d,e) are in the same original order

[6 pts]

a + b * c / (d – e) Prefix:________________________________

Postfix:________________________________

3. Evaluate the following prefix expression and postfix expression.

[8 pts]

- * / 8 2 3 + 1 5 = __________ 5 3 + 7 6 2 - - * = __________

Show the sequence of stack contents during the evaluation of the above right hand postfix expression. Show the stack contents anew after each operator evaluation.

[pic]

4. Linked lists.

a) Draw a box and pointer diagram representing a linked list pointed to by a reference variable head. The list should point to the strings “banana”, “grape”, and “orange”. That is, the info/data field of the nodes separately points to the strings. Keep the data in sorted order.

[6 pts]

b) Show how the links above are rearranged to insert the node containing “lime” into the list at the appropriate point. Just add the node above and “cut” and redraw adjusted links.

[3 pts]

c) Supply the declarations and assignment statements in the Java LListNode and LList classes below to partially support the implementation of the above linked list in which each node holds a String info pointer and a next pointer.

[24 pts]

public class LListNode //[5 pts]

private _____________ info;

private _____________ next;

public LListNode(String x){//constructor

______________________________ ;

______________________________ ;

}//end constructor

// [define a getter and setter for each of the instance variables][8 pts]

}//end LListNode

//--------------------------------------------

public class LList //[4 pts]

// define and initialize the head pointer

{

private _____________ head ;

public LList()//default constructor [fill in appropriate initialization]

{

}//end constructor

// overriding toString method: return a string separated by “\n”

//containing the strings in the list in order from front to end.

//[some code is provided] [8 pts]

public String toString(){

String result = “”;

LLNode cur = ____________ ;

while (_____ != _______) {

}

return ________ ;

}

}

5. Below is a recursive method and two calls to it. Determine the output of the two calls. For the second call, show the sequence of x and y values for each call to gcd in the box below on the right

[10 pts]

public static int gcd(int x, int y)

{

if(y==0) return x;

return gcd (y, x % y); //recall % gives the remainder

}//

System.out.println(“gcd of 4 and 2 is “+gcd(4,2));

|x |y |

|12 |15 |

_______________________________________________

System.out.println(“gcd of 12 and 15 is “+gcd(12,15);

________________________________________________________

6. Memory management True/False.

[10 pts]

______ The bytecodes of a program are part of the static memory allocation area.

______ Activation record sizes vary according to the number of local variables and parameters.

______ A program’s run-time stack and object heap share the same available memory area.

______ Static variables of a class are stored in the object heap.

______ The return address (point of return) to the calling method is found in the system stack within the called method’s activation record.

______ There is an activation record is associated for each method’s call including recursive calls.

______ Upon entry into (call to) a method, its activation record is pushed on the system stack.

______ Instantiated objects are stored within the activation records.

______ The garbage collector recovers space only in the object heap.

______ When an uncaught exception occurs, the stack of activation records is used to produce the traceback.

7. Below is the method for pop in an array implementation of a stack of Objects. Fill in the code to complete the implementation. An instance variable top is part of the stack class and is initialized to -1.

[8 pts]

public __________ pop(){

if ( __________ != ______ )

________ new StackUnderflowException ("Stack is empty—cannot pop");

Object temp = stack [__________];

________ ____ ; //[use ++ or -- here]

return _________;

}

8. Object-Oriented Design

[15 pts]

Below is the UML for the stack ADT.

[pic]

a. Describe the distinction between the BoundedStackInterface and UnboundedStackInterface. Why have both? [7]

b. Many applications need to duplicate the top element of the stack, that is, push a copy of the top element. Show where appropriate modifications would be made to this design by writing in a duplicate method in one (or more?) boxes above. [3]

c. Show the code to implement a duplicate method for both an array implementation and for a list implementation. Can you use the same code for both? [5]

................
................

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

Google Online Preview   Download