ࡱ> sur#` bjbj\.\. 3V>D>D82%2%2%8j%\%|VdN&d&z&z&z&111UVVVVVV$WhKZx$V21"122$Vz&z&A 9V ; ; ;2z&z&U ;2U ; ;R&QSz&B& to3_2%54RT OV0V8RbZ9Z<SZSX1"1 ;2+2111$V$V:d111V2222D$ Computer Science II 100 pts 3/2/07 Name _____________________________ For each abstract structure, check off which of those characteristics apply to the structure with a check mark [12 pts] CharacteristicArrayListStackHomogeneous elementsLinear organizationRandom access to elementsLIFO access only 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:________________________________ 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.  SHAPE \* MERGEFORMAT  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 ________ ; } 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 ______________________________________ + + ________________________________________; } Memory management True/False. [10 pts] ______ The bytecodes of a program are part of the system stack. ______ A programs 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. 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 fullcannot push"); ________ = _________ ____ 1 ; stack [__________] = _____________; return ; } 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. [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 BIf 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 Euclids 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){ }     Spring 2007 CS 240 Exam 2 Page  PAGE 2 #$GHPcdet}  E G q t w   ƺ{nh)IMhzCJmHsH h.CJ hN]^%,->?S ɿɿ򞃞wmgg hzCJhtL^htL^CJ\hCJOJQJ^Jh5 CJOJQJ^Jh'ghSCJOJQJ^JhSCJOJQJ^JhhCJ hCJ h5 CJh22CJOJQJh*CJOJQJhSCJOJQJ h*CJhhSCJ hhGCJ hSCJ hS5CJ'D[^z ^`gdS ^`gdS^gdS^gdS dh^gdS $ !a$gdS  !^gdS !0^`0gdS  & F !gd5  !gd5 0^`0gdS,DEde60dh^`0gd ee$0^`0a$gd#u & F gdvE dh^gd5 $a$gdgQ & F gd5 gdz^gdSCDCDBDcde|}#$()036ִֽЮФhvECJOJQJh#uCJOJQJh"4cCJOJQJhXhoCJOJQJ hvECJh"4ch#uCJ h"4c6CJ haCJ hXhoCJ h#uCJ h"4cCJ h BCJ h#WyCJ h5 CJ hCJ hgQCJ htL^CJ06CX`eghmrtvz "#$%*,NW#5κκ⪤ h`qCJ hvECJ hzFCJ h eeCJ hL<|CJ h BCJ h22CJ h#uCJh8ICJOJQJhXhoCJOJQJhCJOJQJhLCJOJQJhvECJOJQJh#uCJOJQJh"4cCJOJQJhaCJOJQJ26Z!*7s?0dh^`0gddh^$a$gd & F gd22 0^`0gd#u0dh^`0gd ee0dh^`0gd"4c56>qrs|=FS*.    ľq#h BhS5CJOJQJ^JaJ#h Bh*5CJOJQJ^JaJh*CJaJh{hSCJaJhmhSaJ hS5aJ hSaJ h5GaJ hSCJ hTtCJ hCJ h22CJ hL<|CJ h?:CJ hCJ h`qCJ h#uCJ hzFCJ(  .W567890dh^`0gdSgdS$0^`0a$gdS$0^`0a$gdS & F gd220dh^`0gd GIWei456901ŷܫśvpjd^d^dXdj huroCJ hUCJ h5GCJ h99eCJ hSCJh*5CJaJmHsHh B56CJaJh B5CJaJmHsHhShS5CJaJmHsHh BhS5CJaJh Bh*56CJaJh Bh B56CJaJh B5CJaJh BhS56CJaJhS5CJaJhmhS5CJaJ9  !(h^hgd5G$a$gd5G 0^`0gd5Ghuro0JCJmHnHuh99e0JCJjh99e0JCJU h99eCJh99eh99e5CJ\hGjhGUh99eh BCJOJQJh99eCJOJQJh BCJOJQJh^hgd5G1 0:p ee/ =!`"`#$@% $$If!vh5 55F5#v #v#vF#v:Vl t65 55F5yt)IM$$If!vh5 55F5#v #v#vF#v:Vl t65 55F5yt)IM$$If!vh5 55F5#v #v#vF#v:Vl t65 55F5yt)IM$$If!vh5 55F5#v #v#vF#v:Vl t65 55F5yt)IM$$If!vh5 55F5#v #v#vF#v:Vl t65 55F5yt)IMDd D  3 @@"?8@8 Normal_HmH sH tH B@B Heading 1$$@&a$5CJDA@D Default Paragraph FontVi@V  Table Normal :V 44 la (k(No List 4@4 Header  !4 @4 Footer  !.)@. Page NumbertC@"t Body Text Indent5$ p@ `'0^`0a$CJTR@2T Body Text Indent 20^`0CJHBH a Balloon TextCJOJQJ^JaJj@Sj 8KG Table Grid7:V0e@b SHTML Preformatted7 2( Px 4 #\'*.25@9 OJQJ^J2B@r2 S Body TextxV$GH,-./0ABCDEFG st (*8VEF}~./Wl  . ? ^ _ | }  D [ ^ , D Ede6Z!*7s?  .W5678900000 000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0000 000000000 000000000000000000000000000000000000000000000000000000000 000000000000 0000000000000 0000000000 0000000000000 0000000000000000000000000000000@0h00@0h00@0h00@0h00@0@0h00$GH,-./0ABCDEFG stW5 @0 @0 @00000j00 j00 j00 j00 00\j00 j00 j00 j00 00\j0 0 j0 0 j0 0 j0 0 00\j0 0 j0 0 j0 0 j0 0 00\j0 0 j0 0 j0 0 j0 0 00\00X00X00X00X00X00X00X00X00X00X00X00X00X00X00X00X0 77777: t  65 "#%') / D s 69 !$&(*_+24:!48@  (  ^  Q (q%]. #  s"*?`  c $X99?Q (q%].hL B ) g- B ) g-TB  C DB )C g-TB  C D ) g-TB  C DB g- g-t B ) g-  # #" 2 )g-TB   C DB )C g-TB   C D ) g-TB   C DB g- g-t B ) g-  # #" #)g-TB  C DB )C g-TB  C D ) g-TB  C DB g- g-t B ) g- # #" )g-TB  C DB )C g-TB  C D ) g-TB  C DB g- g-t B ) g- # #" )yg-TB  C DB )C g-TB  C D ) g-TB  C DB g- g-t B ) g- # #" )ig-TB  C DB )C g-TB  C D ) g-TB  C DB g- g-B S  ?($ tg?FG $.2W[4)+33333333333333333333333333333333333333333333333333333$E  */Vl  0 A \ !*    >Avz-.@6/Sd=D}TrtQ?,'a !YufCh6%\wdQ!~988^8`o()^`. L ^ `L.  ^ `.xx^x`.HLH^H`L.^`.^`.L^`L.88^8`o(. ^`hH.  L ^ `LhH.   ^ `hH. xx^x`hH. HLH^H`LhH. ^`hH. ^`hH. L^`LhH.88^8`o(.88^8`o(.^`. L ^ `L.  ^ `.xx^x`.HLH^H`L.^`.^`.L^`L.88^8`o()^`. L ^ `L.  ^ `.xx^x`.HLH^H`L.^`.^`.L^`L. hh^h`o(.0^`0o(. ^`hH.  L ^ `LhH.   ^ `hH. xx^x`hH. HLH^H`LhH. ^`hH. ^`hH. L^`LhH.hh^h`.h hh^h`o(hH.h 88^8`hH.h L^`LhH.h   ^ `hH.h   ^ `hH.h xLx^x`LhH.h HH^H`hH.h ^`hH.h L^`LhH.^`o(. ^`hH. pLp^p`LhH. @ @ ^@ `hH. ^`hH. L^`LhH. ^`hH. ^`hH. PLP^P`LhH.88^8`o(.^`. L ^ `L.  ^ `.xx^x`.HLH^H`L.^`.^`.L^`L.h ^`hH.h ^`hH.h pLp^p`LhH.h @ @ ^@ `hH.h ^`hH.h L^`LhH.h ^`hH.h ^`hH.h PLP^P`LhH. vz-d='a @6/\wAtQ?.!~h!Yuf 0*        >                          G        -E        -E                         POlL B5 }72260~MDg%!&%}f&. 9?:t1;vEzF8KGhG8IBmK?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`acdefghiklmnopqtRoot Entry F'o3_vData ,1Table4ZWordDocument3VSummaryInformation(bDocumentSummaryInformation8jCompObjq  FMicrosoft Office Word Document MSWordDocWord.Document.89q