Computer Science II - Juniata College



Computer Science II

100 pts

3/6/09

Name _____________________________

1. True/false on the abstract datatype structures of arrays, lists and stacks.

[8 pts]

_____ An array is composed of heterogeneous elements.

_____ An array is unbounded in size.

_____ A list is non-linear in organization.

_____ A stack is unbounded in size.

_____ An array permits random access to its elements

_____ A stack limits access to the top element in last-in-first-out order

_____ A stack is linear in organization.

_____ A stack permits random access to its elements.

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.

[6 pts]

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

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

[pic]

4. Linked lists.

a) Draw a box and pointer diagram to represent a linked list whose info field of the nodes separately point to the strings ( “banana”, “grape”, “orange”) as pointed to by reference variable head. Keep the data in sorted order.

[5 pts]

b) Show how the links above are rearranged to “push” the node containing “apple” into the list at the appropriate point.

[3 pts]

c) Supply the declarations and assignment statements in the Java LListNode and LList classes below to support the implementation of the linked list in which each node holds a numeric double item and a next reference.

[16 pts]

public class LListNode

private double info;

private _____________ next;

public LListNode(______________ x){//constructor

______________________________ ;

______________________________ ;

}//end constructor

public _______ setInfo(___________ x){ ________ = ______; }

public _______ getInfo(){ return _________ ;}

public _______ setNext(_____________ n){ ________ = ____ ; }

public _______ getNext() { return _________ ;}

}//end LListNode

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

public class LList

// define and initialize the head pointer

{

private _____________ head ;

public LList()

{

____________ = _____________;

}//end constructor

// more list methods here

}

d) Fill in the blanks for a complete non-recursive sumOf() method that would traverse the list and compute the sum of the nodes in the list.

[10 pts]

public double sumOf(){

_________ sum = 0;

LLNode cur = ____________ ;

while (_____ != _______) {

sum _____ ______________ ;

cur = ______ . ____________ ;

}

return ________ ;

}

5. Fill in the blanks to implement a recursive algorithm that prints the accumulated sums of the items in reverse order from the linked list. So if the list contains {3.0, 5.0, 2.0} the sequence printed is 2.0, 7.0, 10.0. The public helper function that calls the recursive function is given: Use the getNext() and getInfo() methods.

[10 pts]

___________ void SumsReversed()

{

double dummy = __________________(head);

}

private double SumsReversed (LListNode cur){

if( __________ == null){

return ___________ ;

}

double sumToEnd = _________________ + ____________________________ ;

System.out.println( ________________ );

return ___________ ;

}

6. Memory management True/False.

[10 pts]

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

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

______ Local variables of an application’s methods are stored in the object heap.

______ The activation record contains the return address (point of return) to the calling method.

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

______ Only one activation record is associated with each method regardless of the number of recursive calls.

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

______ Static variables are stored in the activation records.

______ The garbage collector has no need for information in the activation records.

______ 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. 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(Object obj){

if ( ____________________ )

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

_________ temp = stack [__________];

________ = _________ ____ 1 ;

return _________;

}

8. Object-Oriented Design

[10 pts]

Below is the UML for the stack ADT as an example.

[pic]

a. What is an interface, in general? Why are they necessary? (do not be specific to the stack ADT)

b. If we wanted to add a size() method to this stack ADT, describe or show where appropriate modifications would be made to this design.

c. Describe how the implementation of size() might vary between the linked list and array implementations.

9. Below is a simple expression grammar. Use repeated replacements starting with expr to arrive at the given expression to verify that it is legal. That is, replace occurrences of left-hand non-terminals with the right hand rule definitions. The derivation is started.

[8 pts]

( b + c ) % a

expr := term

expr := expr addOp term expr -> term

term := factor -> term multOp factor

term := term multOp factor ->term % factor

factor := var -> factor % factor

factor := "(" expr ")" ->

addOp := "+" | "-"

multOp := "*" | "/" | "%"

var := "a" | "b" | "c"

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

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

Google Online Preview   Download