ࡱ> bda5@ bjbj22 DXX3<4 h,DpL  Fjsssc1e1e1e1>1 ; E$tGRIEQ"sEsE@#@#@#8c1@#c1@#X@#$/0  `m`z/O1E0 F0LJ"LJ(0"  LJ0ls0"@# sssEE  $#  Spring 03 April 2, 2003 Name_____________________________ 1. Linked lists. a) Fill in the Java inner class below to support the implementation of a linked list in which each node holds one String and a next reference. [5 pts] private class Node { private _______ info; private _______ next; private Node(String s){ info = _______; _________ = ________; } } b) Indicate how the head pointer instance variable of the linked list is declared and start as the empty list. The linked list starts with a dummy head node. [4 pts] ___________ head = new _______________________; c) 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. [5 pts] d) Fill in the blanks so that Java code that would add the value ant as a new first node of this ordered list. [5 pts] Node temp = new Node (ant); temp. _______ = _______ . ________; head.______ = ______ ; 2. Fill in the code below to complete the enqueue operation using a singly linked list implementation (no dummy head node). [5 pts] public void enqueue(Object item){ if (item == null) throw new IllegalArgumentException ("Trying to insert null onto the queue"); Node node = new Node (______); if (size == 0){ head = _________; } else { tail._______ = _______; } tail = node; size_____; } 3. Give the time complexities, O(1) or O(n) for each of the operations of the implied data structure that are implemented as a linked list. [8 pts] _________ pop() _________ dequeue() _________ enqueue(item) _________ push(item) _________ insert(item) //into a sorted list _________ insert(item) //unsorted list _________ getNextItem() _________ isThere(item) 4. Fill in the blanks to implement a recursive binary search algorithm. Assume there is a public helper function that calls the recursive function: public int binarySearch(Comparable key){ return binarySearch(key, 0, vec.length 1); } [10 pts] private int binarySearch(Comparable key, int lo, int hi){ if( ____ > ____ ) { return -1; //not found } else { int mid = ____________; int comp = vec[mid].compareTo(key); if(comp > 0){ return binarySearch(key, ________,________); } else if(comp ____ 0){ return binarySearch(key, ________,________); } else { // found it return ________ ; } } } 5. A recursive definition for determining the greatest common denominator is credited to Euclid. For example, the GCD of 16 and 12 is 4. If b==0 then the GCD(a,b) = a, otherwise the GCD (a,b) = GCD (b, a%b) //% is modulus [10 pts] Write this recursive Java function to implement the calculation of the greatest common denomionator. public static int GCD(int a, int b){ } 6. Trees. [10 pts] Assume the root is at level 0. What is the level of node F? ____ Circle the largest subtree that is a binary tree. How many leaves are there in the whole tree? _____ If each node could have at most three children, how many nodes total could be stored in this 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 count the number of 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 nodes on the left and the nodes on the right, plus one for the root. [7 pts] public int Counter( _________ curNode) { if(curNode _____________ ) return ____ ; return Counter ( _________________ ) + __________ ( _________________ ) + ____ ; } b) Finish the recursive Java function to return if the item exists in the binary search tree. [8 pts] public boolean isThere( BSTNode root, Comparable item) { if (_______ == null) return false; int comp = item.compareTo( _________ . ___________) if(comp == 0) return ___________ ; if(comp < 0) return isThere ( ______ . ______ , item ) else return isThere (_______ . _______, item); } 8. Create a binary search tree from the following character data entered into the bst left to right. [4 pts] D T W A B Q M N a) List the nodes of your tree above from an inorder traversal. [3 pts] b) List the nodes of your tree above from a preorder 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 postorder traversal of your expression tree. [3 pts] 10. True/False [6 pts] ______ A doubly linked list permits traversal in both forward and backward directions ______ A doubly linked list doubles the algorithm complexity of the operations over a singly linked list. ______ Most operations on a binary tree depends on the depth of the tree which is logarithmic 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 the same as a reversed preorder travsersal. ______ The maximum number of nodes in a binary tree at level N is 2N CS 240 Computer Science II Exam 3 Page PAGE2 A / \ B C / \ \ D E F / \ /|\ G H I J K   ;?v  ; C L P S Z     % U A D o p q r 䯦 hUqCJhlCJOJQJ hfCJ hl6CJhf56CJh~d-hl56CJ hq^CJh~d-CJOJQJhlCJOJQJhl6CJ] h~d-CJ hlCJ h'CJ h'5 h~d-5 h[8g56 ;<M + F \ x }   % $0^`0a$gdl^gdl dh^gdl $^a$gdl 0^`0gdl<^<gdl 0^`0$a$$a$% U V p x Z b ^$a$ 0^`0gdf 0^`00dh^`0gdq^$0^`0a$gdl 0^`0gdl ^`gdlr s x | C X b ' ( D F J L M R k p !"()38DKMY`fhrʾʴĐʇ~~h'5CJ\h_C5CJ\ hDCJh~d-CJOJQJhW)CJOJQJhfCJOJQJh'CJOJQJ hfCJ hW)CJ h'CJhlCJOJQJ^Jhq^CJOJQJ^Jh~d-CJOJQJ^J hlCJ h~d-CJ1  ) A M k p ():Oh}dhdh^$a$ 0^`0^r|}L =DHJ^j(bƽַ跱豥~~~rh.WCJOJQJ^JhW)CJOJQJ^Jh'CJOJQJ^Jh'gh'CJOJQJ^Jh'gCJOJQJ^J h'gCJ hW)CJhDh'CJ hDCJ\hW)5CJ\h'5CJ\hD5CJ\ h'CJhW)hW)5CJ hW)5CJ+~6U !"#$%&(8^8^gd-`$a$@ ^@ gd.W 0^`0gd.Wdh^ $ !a$ !0^`0gd'g ! 569=CGJOS_c{~  ()*ǾǮ}q}q}q}q}q}ke h'gCJ h{CJhCJOJQJ^Jh'CJOJQJ^J h-`CJ hCJ h'CJhh'H*\aJ h\aJh5\aJ hq^\aJhq^5\aJhq^hq^5\aJ hq^aJh-`5\aJhq^h'aJhq^h'CJ h.WCJ hq^CJ$(*4>o~+ 0^`0gd{ @ `^@ ``gd{ `^``gd{ & Fxgd{$a$gd{gd{gd'g*+48o$*/GWY`tu}  3189;AHOPWYvzhUqCJaJhCJOJQJaJh!eCJOJQJaJh{CJOJQJaJh{h{CJOJQJaJh-`CJaJ(jh{h{CJUaJmHnHuhCJaJh{h{CJaJh{CJaJ7+3Z\9Axz,cep0dh^p`0gd!e dh^gd!e$0^`0a$gd{ 0^`0gd{ p0^p`0gd{^gd{^gd{$ `^``a$gd{ )+19begh./089:ehyz{λ}uj}}u`Vh{OJQJaJhOJQJaJhL^hL^CJaJh{CJaJh{hL^CJaJhL^CJaJh{h{CJaJmHsHh{h{5CJaJmHsHh!eh{5CJaJh!eh{CJaJhCJaJh{h{CJaJh;CJOJQJaJh!eCJOJQJaJh{h{CJOJQJaJeg.678y^gd{$a$gd{$a$gd{ 0^`0gd{gd{EGI%ļ}xk[J[ jh[8gh'5CJUaJh[8gh'5CJaJmH sH h[8g5CJaJmH sH  h'5h{hlCJaJhL^hL^CJH*aJ hL^CJ hX1CJ hlCJ hCJhlCJaJhUqCJaJh{CJaJh'gCJaJ#h{h{5CJOJQJ^JaJh{h{CJaJh{OJQJaJh{h{OJQJaJ;CDEFGV^ x^gdL^ $dha$gdlgdl$a$gd{ & Fgd{gd'ggd{ 0^`0gd{$0^`0a$gd{$0^`0a$gd{bgd{$a$gd{  !'gd'g0x^`0gdL^0x^`0gdX1Ǵh{hlCJaJhEah{hh{mHsH$h{h{CJOJQJaJmHsHhfh'h[8gh'CJaJmH sH  hf5CJaJmHnHsH u jh[8gh'5CJUaJ +0PPP/ =!"#$%J 00PPP:pW)/ =!"#$% P04 00PPP:pW)/ =!"#$%<@< NormalCJ_HmH sH tH DAD Default Paragraph FontViV  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^`0CJ;;>)D-DyD ;<M+F\x}%UVpxZb)AMkp ():Oh}~ 6 U  ! " # $ % & ( * 4 > o ~  +3Z\9Axz,ceg.678y;CDEFGV^b00000p00000p000p0p0000p0p00p0p00p000000000000000000000000000000000000000000000000000000000p0p0 0 0 0 0 0 0 00000000000000000000000000000000000000000000000000000000 0000000000p0p0p0000@0z000b"00000000My00>0222222222222222225r r*!% (+e (-/5!8@*(    C F. `tt`TT`TTt" B S  ? `E'` BMM1"M|    8*urn:schemas-microsoft-com:office:smarttagsdate9*urn:schemas-microsoft-com:office:smarttagsplace8*urn:schemas-microsoft-com:office:smarttagsCity 220034DayMonthYearnuDKY` &).1}= I K N h k w z      :=QX_fHOPWY` @G"(V`.5LP15bh/3sw38DMYarw G K U ^ 39\_AGz|!$,0ef%)il333333333333333333333333333333333333333333333Fbp|ks :h}* > { h o 9A,c.8y;EGVLoren K. RhodesLoren K. RhodesLoren K. RhodesLoren K. RhodesLoren K. RhodesLoren K. RhodesLoren K. RhodesLoren K. RhodesLoren K. RhodesLoren K Rhodesa \Ҟ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!feH*\wQA0dBHHa e @h8^8`56>*CJOJQJo(. *f                 @                  @ @ @Ea;lW)~d-_CD.WL^'g[8gUq{-`'fq^X1!e'@\\OSERVER2\BSCA214-HP4100NNe01:winspoolHP LaserJet 4100 PS\\OSERVER2\BSCA214-HP4100N S odXXLetPRIV''''T\K\K!kTRJPHAAMICKELJUNTITLED\\OSERVER2\BSCA214-HP4100N S odXXLetPRIV''''T\K\K!kTRJPHAAMICKELJUNTITLEDooooP@UnknownGz Times New Roman5Symbol3& z Arial?5 z Courier New71 Courier;Wingdings"CVhsSs&Rs& P;m ';m '"V24d 3QVH(?'Computer Science II Rhodes FamilyLoren K Rhodes(       Oh+'0 , H T ` lxComputer Science IIompRhodes FamilycehodhodNormalFLoren K Rhodese9reMicrosoft Word 10.0@- @gU@(֏@*y;m՜.+,0 px  Juniata CollegeJ'  Computer Science II Title  !"$%&'()*,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPRSTUVWXZ[\]^_`cRoot Entry FeData #1Table+tJWordDocumentDSummaryInformation(QDocumentSummaryInformation8YCompObjj  FMicrosoft Word Document MSWordDocWord.Document.89q