ࡱ> hjgq` bjbjqPqP L::?<46h\^T6Ihi i i 65858585Ay5 m? aI$HKhMIi G "i i i IsI'''i 865'i 65''l24  AH#d354I0Ix32NA&T2N((4"2NJ4i i 'i i i i i II'ji i i Ii i i i 666d666666 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)<=tol; otherwise, = sqrRoot(number, approx*approx+number)/(2*approx),tol) [10 pts] Write a recursive Java function to implement the calculation of the square root. public static double sqrRoot(double number, double approx, double tol){ } 6. Trees. [10 pts] Assume the root is at level 0. What is the level of node I? ____ Circle the largest subtree that is a binary tree. How many leaves are there in the whole tree? _____ If each node is limited to two children, how many nodes total could be stored in this (binary) tree without adding any more levels? ______ List the ancestors of node H ______________________ List the descendants of node C. _______________________ Draw the conversion of this general tree as a binary tree (left child as first child of the general tree and right child as a sibling in the general tree) 7. Assume nodes in a binary tree are defined in an inner class having the following instance variables. Comparable info; BSTNode left; BSTNode right; a) Finish the recursive Java function to sum up the values of the nodes in a binary tree. The algorithm works as follows. If the root (of tree or subtree) is null then return 0; otherwise return the sum of the sume of the nodes on the left and the sum of the nodes on the right, plus the value of the root. [7 pts] public int Sum( _________ curNode) { if(curNode _____________ ) return ____ ; return Sum ( _________________ ) + __________ ( _________________ ) + (int)curNode._____ ; } b) Finish the recursive Java function to return the equal item from the binary search tree. [8 pts] public __________ retrieve( BSTNode root, Comparable item) { if (_______ == null) return null; int comp = item.compareTo( _________ . ___________) if(comp == 0) return _________.______ ; if(comp < 0) return retrieve ( ______ . ______ , item ) else return retrieve (_______ . _______, item); } 8. Create a binary search tree from the following character data entered into the BST left to right. [4 pts] S G A N I L E D a) List the nodes of your tree above from an inorder traversal. [3 pts] b) List the nodes of your tree above from a postorder traversal. [3 pts] 9. Draw the following infix arithmetic expression as an expression tree. Represent precedence properly. [4 pts] a/b-c*(d+e) Show a preorder traversal of your expression tree. [3 pts] 10. True/False [5 pts] ______ A doubly linked list permits random access to the nodes like an array. ______ Most operations on a binary tree depends on the depth of the tree which is linear to its capacity. ______ A binary search tree always generates the same inorder traversal regardless of the sequence the nodes were entered into the tree. ______ A postorder traversal is necessary to effectively remove all nodes from a tree. ______ The maximum number of nodes in a binary tree of N levels is 2N+1-1     CS 240 Computer Science II Exam 3 Page PAGE5 A / \ B C / \ \ D E F /|\ / \ G H I I K   2TXi* a h m }   + 4 8 ? F J M ڻڻڵǫڢڜڒ~tjt~h~d-CJOJQJhlCJOJQJhrYCJOJQJh}CJOJQJhACJOJQJ hCJhl6CJ]hr:hrY6CJ hr:CJ h~d-CJ hACJ hrYCJ h}6CJ h}CJ hlCJ h'CJ hr:5 h'5 hxq5 h~d-5 h[8g5) 2TUf # $ % & ' 6 M t dh^gdrY dh^gdl $^a$gdl 0^`0gdl$0^`0a$gd} 0^`0gd}<^<gdl 0^`0$a$$a$t    7 8 d e A I $0^`0a$gdl 0^`0gd 0^`0gdl^gdl dh^gdl       * 6 7 = C R c d e  8 ? @ A B C D I l m  ξ hW)CJ h'CJhlCJOJQJ^JhCJOJQJ^JhhlCJ hr:CJ h~d-CJ hlCJ hCJhr:CJOJQJhCJOJQJhrYCJOJQJh~d-CJOJQJhACJOJQJhlCJOJQJ1I m | &ESf|( 0^`0 dh^gd`{V^$a$ 0^`0gdf 0^`00d^`0gdr: 1 2 ; ? D H { | } ~ Sdefk|&)*01;BDPW]_iκΰΰΰΪh_C5CJ\h'5CJ\ hDCJh`{Vhxq5CJ hW)CJhW)CJOJQJh`{VCJOJQJhCJOJQJh'CJOJQJ h`{VCJhr:h'CJ hr:6CJ hr:CJ h'CJ hfCJ5(01F_p K^^gdd!T 0^`0gd.W $ !a$ !0^`0gd'g !dhdh^$a$inpz  >TfĻIJĻͲ͖͜~~~~~oh'gh'CJOJQJ^Jh&}CJOJQJ^Jh'gCJOJQJ^J h&}CJ h'gCJhDh'CJ hDCJ\hW)5CJ\h'5CJ\hD5CJ\ h'CJhW)hW)5CJ hW)5CJ h&}5CJ hW)CJ h`{VCJh`{V5CJ\+ )/;DHNPRTWY[lpq},/09CKLMOs*35;vh>hd!T6aJh>hJ`6aJh>hJ`5aJh>hJ`aJhq^h'CJ hd!TCJ hJ`CJ h'gCJ h&}CJh'gCJOJQJ^Jh.WCJOJQJ^JhW)CJOJQJ^Jh&}CJOJQJ^Jh'CJOJQJ^J h'CJ.;O\]^gjk  &'AIKOPQZȿwwwwwwqi^h{h{CJaJh{CJaJ h'gCJhd!TCJOJQJ^Jh'CJOJQJ^J h-`CJ hd!TCJ hCJ h'CJhh'H*\aJh>hd!T5\aJhr:5\aJhq^h'aJ hd!TaJh>h'6aJ hJ`aJ h>6aJh>hJ`6aJ hr:6aJ#DEFGHIJKLMOPZd  & Fxgd{$a$gd{gd{gd'g8^8@^@gdd!T^gd-`Z^ *bkLRWo!$%23ADjpu{:Ebo}}}hCJOJQJaJh!eCJOJQJaJh{CJOJQJaJh{h{CJOJQJaJh>CJaJh-`CJaJh{CJaJhr:CJaJ(jh{h{CJUaJmHnHuhoOCJaJh{h{CJaJhCJaJ1#1@Au}(* p0^p`0gd{^gd{^gd{$ `^``a$gd{ 0^`0gd{ @ `^@ ``gd{ `^``gd{gd{}%*-S^fko%(1;BCHMZai%ѾѶѮ񖢖񖊢ƂƾhCJaJh;CJOJQJaJh!eCJOJQJaJha/CJOJQJaJhUqCJaJha/CJaJhr:CJaJh{h{CJaJh{CJaJhr#CJOJQJaJhgCJOJQJaJh{h{CJOJQJaJ2%M%-=>?@$a$gd{$a$gd{ 0^`0gd{gd{ 0^`0gd{ p0^p`0gd{p0dh^p`0gd!e dh^gd!e^gd{$0^`0a$gd{%-<FH&EFNOQZʿʤʿ{{{l]K#h{h{5CJOJQJ^JaJh>5CJOJQJ^JaJh C5CJOJQJ^JaJh{h{OJQJaJh{OJQJaJhOJQJaJh>CJaJh CCJaJhL^hL^CJaJh{CJaJh{h{CJaJh{hL^CJaJhL^CJaJh{h{CJaJmHsHh C5CJaJh!eh{CJaJ@ABCDEFFNZ[\]^gd'g 0^`0gd{$0^`0a$gd{$0^`0a$gd{^gd{$a$gd{gd{Z]^_`j A\mnMj~vrvrvrvrm h'5h "jh "Uh{hlCJaJ hghL^hghgCJH*aJhL^hL^CJH*aJ hL^CJ hX1CJ hgCJ hr:CJ hlCJ hCJhlCJaJh CCJaJhUqCJaJh{CJaJh'gCJaJh{h{CJaJ(^_`nN0x^`0gdL^0x^`0gdX1 x^gdL^ $dha$gdlgdlgd{$a$gd{ & Fgd{gd'ggd'ggd{$a$gd{  !'ѱ{wshh{hlCJaJhEah{hh{mHsHhoOCJOJQJaJmHsH$h{h{CJOJQJaJmHsHh "h'h[8gh'CJaJmH sH  hr:5CJaJmHnHsH u jh[8gh'5CJUaJh[8gh'5CJaJmH sH h[8g5CJaJmH sH 70PPP/ =!"#$% V 00PPP:pW)/ =!"#$% P0 @ 00PPP:pW)/ =!"#$% <@< NormalCJ_HmH sH tH Z@Z d!T Heading 1$<@&5CJ KH OJQJ\^JaJ DA@D Default Paragraph FontVi@V  Table Normal :V 44 la (k@(No List 4@4 Header  !4 @4 Footer  !PC@P Body Text Indent ^ CJOJQJTR@"T Body Text Indent 2 ^ CJOJQJTS@2T Body Text Indent 30^`0CJH@BH r: Balloon TextCJOJQJ^JaJ;;>1L9LL 2TUf#$%&' 6Mt78deAIm| &ESf|(01F_p   K  ^ D E F G H I J K L M O P Z d #1@Au}(*%M%-=>?@ABCDEFFNZ[\]^_`nN0000000@0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 0 0 0 0 0 0 00000000000000000000000000000000000000000000000000000000 00000000000000I00I00I00I00@0I00ɓI00 00000000I00 >>>>>>>>>>>>>>>>>A  i;Z}%Z "%t I (@^!#$49;A!8@*(    C F. `tt`TT`TTt" B S  ? `E'` Bhm'4;BPW       ) Y \ k r   > A #*18 t{UX    8?DL)-VXlp;DPXinz $   ^ g  }%(MPz}NS uvUX3333333333333333333333333333333333333333333dd8?2{H O  * b k :E^f a \ҞHHH*zJQA*CJOJQJo() ^`o(.h ^`OJQJo(h ^`OJQJo(oh pp^p`OJQJo(h @ @ ^@ `OJQJo(h ^`OJQJo(oh ^`OJQJo(h ^`OJQJo(h ^`OJQJo(oh PP^P`OJQJo(88^8`o(.^`. L ^ `L.  ^ `.xx^x`.HLH^H`L.^`.^`.L^`L.@h8^8`56>*CJOJQJo(. 88^8`o(.^`. L ^ `L.  ^ `.xx^x`.HLH^H`L.^`.^`.L^`L.!f!f8H*\wQA0dBHHa D @h8^8`56>*CJOJQJo(. *f                 @                  @ @ @('EaoO}; Cgl "W)~d-a/_CDd!T`{V.WL^J`'g[8gUqhy{&}>-`'fq^xqX1r#A!er:w'rY@\\printserver\BSCC217-HP4100NNe08:winspoolHP LaserJet 4100 PS\\printserver\BSCC217-HP4100N S odXXLetterPRIV0''''T\K\K!kTRJPHAAGUESTC\\printserver\BSCC217-HP4100N S odXXLetterPRIV0''''T\K\K!kTRJPHAAGUESTC6P@UnknownGz Times New Roman5Symbol3& z Arial?5 z Courier New5& zaTahoma;Wingdings"Vh"&nFF _: )_: )!V4d 2QVHX?'2Computer Science II Rhodes Family Loren Rhodes(       Oh+'0 , L X d p|Computer Science IIRhodes FamilyNormalLoren Rhodes7Microsoft Office Word@r@OWv@ti@>_:՜.+,0 px  Juniata CollegeJ)  Computer Science II Title  !"#$%&()*+,-.0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVXYZ[\]^`abcdefiRoot Entry F|HkData '1Table/ZNWordDocumentLSummaryInformation(WDocumentSummaryInformation8_CompObjq  FMicrosoft Office Word Document MSWordDocWord.Document.89q