Computer Science II - Juniata College



Computer Science II

100 pts

3/2/07

Name _____________________________

1. For each abstract structure, check off which of those characteristics apply to the structure with a check mark

[12 pts]

|Characteristic |Array |List |Stack |

|Homogeneous elements | | | |

|Linear organization | | | |

|Random access to elements | | | |

|LIFO access only | | | |

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 - 8 5 = __________

9 3 - 6 5 2 * - + = __________

Show the sequence of stack contents during the evaluation of the above 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 (“apple”, “banana”, “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 insert the node containing “lime” 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 one String item and a next reference.

[17 pts]

public class LListNode

private __________ info;

private _____________ next;

public LListNode(String s){//constructor

______________________________ ;

______________________________ ;

}//end constructor

public setInfo(___________ s){ ________ = ______; }

public getInfo(){ return _________ ;}

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

public getNext() { return _________ ;}

}//end LListNode

public class LList

// define and initialize the head pointer

private LListNode __________ ;

public LList(){

____________________________________;

}//end constructor

…// more list methods here

}

d) Fill in the blanks for a complete non-recursive lengthIs() method that would traverse the list and count the nodes in the list.

[6 pts]

public int lengthIs(){

int count = 0;

LLNode cur = ____________ ;

while (_____ != _______) {

_________ ++ ;

cur = ____ . ____________ ;

}

return ________ ;

}

5. Fill in the blanks to implement a recursive algorithm that returns a concatenation of the strings in reverse order from the linked list. The public helper function that calls the recursive function is given: Use the getNext() and getInfo() methods.

public String Reverse(){

return Reverse(head);

}

[7 pts]

private String Reverse(LListNode cur){

if( __________ == null){

return ___________ ;

}

return ______________________________________

+ “ “ + ________________________________________;

}

6. Memory management True/False.

[10 pts]

______ The bytecodes of a program are part of the system stack.

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

______ Objects of an application are stored on the system stack among its activation records.

______ An activation record is associated with each method called and pushed onto the system stack.

______ Upon completion of (return from) a method, its activation record is popped off the system stack.

______ Global and static variables are part of the activation records.

______ A recursive call adds no additional activation record to the system stack.

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

______ Activation record sizes are fixed and limit the number of local variables.

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

7. Below is the method for push 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.

[8 pts]

public void push(Object obj){

if ( _____+1 == stack._________)

________ new StackOverflowException ("Stack is full—cannot push");

________ = _________ ____ 1 ;

stack [__________] = _____________;

return ;

}

8. True/False on Object-Oriented Design

[10 pts]

______ An interface defines a set of abstract methods that must be implemented by a class.

______ An abstract class can be directly instantiated.

______ An interface can be directly instantiated.

______ The array data structure allows dynamic growth of the collection.

______ A reference variable may be defined by an interface.

______ A subclass can extend (inherit from) multiple classes in Java.

______ A class can implement only one interface in Java.

______ A stack that is implemented with a linked list is considered bounded.

______ A linked list is an example of a dynamic growth structure.

______ The traversal of a linked list is an example of an iterator operation.

9. [CHOICE A] Below is a simple expression grammar. Use repeated replacements starting with expr to arrive at the given input expression to verify that it is legal. That is, replace occurrences of left-hand non-terminals with the right hand rules. The derivation is started. Order of replacements is not important

[10 pts]

a / ( b + c )

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"

9. [CHOICE B—If you do both A and B, then the grader chooses which one counts]

Write a recursive function in Java to compute the greatest common divisor of two integers, x and y, using Euclid’s algorithm:

[10 pts]

If y == 0 then the gcd(x,y) is x, otherwise the gcd(x,y) is gcd( y, x%y) where % is the Java modulus operation.

public static int gcd(int x, int y){

}

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

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

Google Online Preview   Download