ࡱ> z|y 3bjbj~~ &f++ 8$ %P()))OOOOOOORTO)%))-O'gO'''1O')O''jJN ?S;L2NO0%PLGU'GUdN'N))) `:   CSE 142 Sample Final Exam #1 (based on Winter 2005's final; thanks to Stuart Reges) 1. Array Mystery Consider the following method: public static int arrayMystery(int[] array) { int x = 0; for (int i = 0; i < array.length - 1; i++) { if (array[i] > array[i + 1]) { x++; } } return x; } In the left-hand column below are specific arrays of integers. Indicate in the right-hand column what value would be returned by method arrayMystery if the integer array in the left-hand column is passed as its parameter. Original Contents of ArrayValue Returned int[] a1 = {8}; int result1 = arrayMystery(a1); int[] a2 = {14, 7}; int result2 = arrayMystery(a2); int[] a3 = {7, 1, 3, 2, 0, 4}; int result3 = arrayMystery(a3); int[] a4 = {10, 8, 9, 5, 6}; int result4 = arrayMystery(a4); int[] a5 = {8, 10, 8, 6, 4, 2}; int result5 = arrayMystery(a5); _____________________________ _____________________________ _____________________________ _____________________________ _____________________________  2. Reference Semantics Mystery The following program produces 4 lines of output. Write the output below, as it would appear on the console. import java.util.*; // for Arrays class public class ReferenceMystery { public static void main(String[] args) { int y = 1; int x = 3; int[] a = new int[4]; mystery(a, y, x); System.out.println(x + " " + y + " " + Arrays.toString(a)); x = y - 1; mystery(a, y, x); System.out.println(x + " " + y + " " + Arrays.toString(a)); } public static void mystery(int[] a, int x, int y) { if (x < y) { x++; a[x] = 17; } else { a[y] = 17; } System.out.println(x + " " + y + " " + Arrays.toString(a)); } } 3. Inheritance Mystery Assume that the following classes have been defined: public class Pen extends Sock { public void method1() { System.out.print("pen 1 "); } } public class Lamp { public void method1() { System.out.print("lamp 1 "); } public void method2() { System.out.print("lamp 2 "); } public String toString() { return "lamp"; } } public class Book extends Sock { public void method2() { System.out.print("book 2 "); super.method2(); } } public class Sock extends Lamp { public void method1() { System.out.print("sock 1 "); method2(); } public String toString() { return "sock"; } } Given the classes above, what output is produced by the following code? Lamp[] elements = {new Book(), new Pen(), new Lamp(), new Sock()}; for (int i = 0; i < elements.length; i++) { System.out.println(elements[i]); elements[i].method1(); System.out.println(); elements[i].method2(); System.out.println(); System.out.println(); } 4. File Processing Write a static method named wordStats that accepts as its parameter a Scanner holding a sequence of words and that reports the total number of words and the average word length. For example, suppose the Scanner is scanning an input source that contains the following words: To be or not to be, that is the question. For the purposes of this problem, we will use whitespace to separate words. That means that some words include punctuation, as in "be,". (This is the same definition that the Scanner uses for tokens.) For the input above, your method should produce exactly the following output: Total words = 10 Average length = 3.2 5. File Processing Write a static method named flipLines that accepts as its parameter a Scanner for an input file and that writes to the console the same file's contents with successive pairs of lines reversed in order. For example, if the input file contains the following text: Twas brillig and the slithy toves did gyre and gimble in the wabe. All mimsey were the borogroves, and the mome raths outgrabe. "Beware the Jabberwock, my son, the jaws that bite, the claws that catch, Beware the JubJub bird and shun the frumious bandersnatch." The program should print the first pair of lines in reverse order, then the second pair in reverse order, then the third pair in reverse order, and so on. Therefore your method should produce the following output to the console: did gyre and gimble in the wabe. Twas brillig and the slithy toves and the mome raths outgrabe. All mimsey were the borogroves, "Beware the Jabberwock, my son, Beware the JubJub bird and shun the jaws that bite, the claws that catch, the frumious bandersnatch." Notice that a line can be blank, as in the third pair. Also notice that an input file can have an odd number of lines, as in the one above, in which case the last line is printed in its original position. You may not make any assumptions about how many lines are in the Scanner. 6. Array Programming Write a static method named minGap that accepts an integer array as a parameter and returns the minimum 'gap' between adjacent values in the array. The gap between two adjacent values in a array is defined as the second value minus the first value. For example, suppose a variable called array is an array of integers that stores the following sequence of values. int[] array = {1, 3, 6, 7, 12}; The first gap is 2 (3 - 1), the second gap is 3 (6 - 3), the third gap is 1 (7 - 6) and the fourth gap is 5 (12 - 7). Thus, the call of minGap(array) should return 1 because that is the smallest gap in the array. Notice that the minimum gap could be a negative number. For example, if array stores the following sequence of values: (3, 5, 11, 4, 8) The gaps would be computed as 2 (5 - 3), 6 (11 - 5), -7 (4 - 11), and 4 (8 - 4). Of these values, -7 is the smallest, so it would be returned. This gap information can be helpful for determining other properties of the array. For example, if the minimum gap is greater than or equal to 0, then you know the array is in sorted (nondecreasing) order. If the gap is greater than 0, then you know the array is both sorted and unique (strictly increasing). If you are passed an array with fewer than 2 elements, you should return 0. 7. Array Programming Write a static method named longestSortedSequence that accepts an array of integers as a parameter and that returns the length of the longest sorted (nondecreasing) sequence of integers in the array. For example, if a variable named array stores the following values: int[] array = {3, 8, 10, 1, 9, 14, -3, 0, 14, 207, 56, 98, 12}; then the call of longestSortedSequence(array) should return 4 because the longest sorted sequence in the array has four values in it (the sequence -3, 0, 14, 207). Notice that sorted means nondecreasing, which means that the sequence could contain duplicates. For example, if the array stores the following values: int[] array2 = {17, 42, 3, 5, 5, 5, 8, 2, 4, 6, 1, 19} Then the method would return 5 for the length of the longest sequence (the sequence 3, 5, 5, 5, 8). Your method should return 0 if passed an empty array. 8. Classes and Objects Suppose that you are provided with a pre-written class Rectangle as described at right. (The headings are shown, but not the method bodies, to save space.) Assume that the fields, constructor, and methods shown are already implemented. You may refer to them or use them in solving this problem if necessary. Write an instance method named union that will be placed inside the Rectangle class to become a part of each Rectangle object's behavior. The union method accepts another rectangle r as a parameter and turns this rectangle into the union of itself and r ; that is, modifies the fields so that they represent the smallest rectangular region that completely contains both this rectangle and r . For example, if the following Rectangles are declared in client code: Rectangle rect1 = new Rectangle(5, 12, 4, 6); Rectangle rect2 = new Rectangle(6, 8, 5, 7); Rectangle rect3 = new Rectangle(14, 9, 3, 3); Rectangle rect4 = new Rectangle(10, 3, 5, 8); The following calls to the union method would modify the objects' state as indicated in the comments. rect1.union(rect2); // {(5, 8), 6x10} rect4.union(rect3); // {(10, 3), 7x9}// A Rectangle stores an (x, y) // coordinate of its top/left // corner, a width and height. public class Rectangle { private int x; private int y; private int width; private int height; // Constructs a new Rectangle // with the given x,y,w,h. public Rectangle(int x, int y, int w, int h) // returns the field values public int getX() public int getY() public int getWidth() public int getHeight() // example: {(5, 12), 4x8} public String toString() // your method would go here }  Solutions 1. Call int[] a1 = {8}; int result1 = arrayMystery(a1); int[] a2 = {14, 7}; int result2 = arrayMystery(a2); int[] a3 = {7, 1, 3, 2, 0, 4}; int result3 = arrayMystery(a3); int[] a4 = {10, 8, 9, 5, 6}; int result4 = arrayMystery(a4); int[] a5 = {8, 10, 8, 6, 4, 2}; int result5 = arrayMystery(a5);Value Returned 0 1 3 2 4 2. 2 3 [0, 0, 17, 0] 3 1 [0, 0, 17, 0] 1 0 [17, 0, 17, 0] 0 1 [17, 0, 17, 0] 3. sock sock 1 book 2 lamp 2 book 2 lamp 2 sock pen 1 lamp 2 lamp lamp 1 lamp 2 sock sock 1 lamp 2 lamp 2 4. public static void wordStats(Scanner input) { int count = 0; int sumLength = 0; while (input.hasNext()) { String next = input.next(); count++; sumLength += next.length(); } double average = (double) sumLength / count; System.out.println("Total words = " + count); System.out.println("Average length = " + average); } 5. public static void flipLines(Scanner input) { while (input.hasNextLine()) { String first = input.nextLine(); if (input.hasNextLine()) { String second = input.nextLine(); System.out.println(second); } System.out.println(first); } } 6. public static int minGap(int[] list) { if (list.length < 2) { return 0; } else { int min = list[1] - list[0]; for (int i = 2; i < list.length; i++) { int gap = list[i] - list[i - 1]; if (gap < min) { min = gap; } } return min; } } 7. public static int longestSortedSequence(int[] list) { if (list.length == 0) { return 0; } int max = 1; int count = 1; for (int i = 1; i < list.length; i++) { if (list[i] >= list[i - 1]) { count++; } else { count = 1; } if (count > max) { max = count; } } return max; } 8. public void union(Rectangle r) { // find the union's bounds int left = Math.min(x, r.getX()); int top = Math.min(y, r.getY()); int right = Math.max(x + width, r.getX() + r.getWidth()); int bottom = Math.max(y + height, r.getY() + r.getHeight()); x = left; y = top; width = right - left; height = bottom - top; }      PAGE 1 of  NUMPAGES 1 Td * D E S U t ' 8 h y z    < 3JsSZHMv};Del6JgmmrcpP e hL0jhLx0JhLx>*OJQJ hs hLxhLxhLx5hLxhLx>*CJhLxhLx>*h@f^hLx0J hLx0Jh FhLxmHsH hLx5h^{ZhLx5CJhLx?T * 4 : H J * E T U Qkd$$Ifl0P9( t644 la $IfgdLx h$If^hgdLxgdLxgdLxgdLxU V f  9 : Z z { |  P$If^gdLx $IfgdLx     # 6 I g h gdLxgdLx gdLxQkdZ$$Ifl0P9( t644 la P$If^gdLxh 8>?w*023$IfgdLxl gdLx@FGc 2KQSTuH$If^HgdLxl $If^gdLxl $IfgdLxl u YpkgdLxxkd$$Ifl0* t0644 laH$If^HgdLxl Y"=Wqs   &Hi-gdLxgdLx5Wt5): P s!!"(###%&$IfgdLxl gdLxgdLxgdLx P!U!!!!!F#G###$$4%9%:%D%Y%b%%%%%%%% &&&&I&&&&&&&A'B'''''Y(o((((((((((((((()) ) )) )!)')s)|)hLxhLx5 h(hLx h~hLx h7 hLxhLxhLx6 hLxhhLxhLx0J5 h<hLxh@f^hLx0JhLx hLx0JE&&'B'C'q''(.(V(v((((((( )")')I)$If^gdLxl dL$IfgdLxl $IfgdLxl $IfgdLxl I)h)))))))*1*2*Q*n*o*p******$If^gdLxl $If^gdLxl |))))))))))))) ****%*.*c*k*m*n*p*********++++++/03333333333333ƿ hLx0JjhLx0JUjhLxU hL0jhLxh FhLxmHsHhLxhLx>* h3hLx hthLxhLxhLxOJQJhLxhLx>*OJQJj3hLxUhLxhLx6hLxhLx5 h(hLxhLx4*********+}fSSSSS$IfgdLxl  P$IfgdLxl gdLxgdLxxkdX$$Ifl0P0* t0*644 la ++0+P+Q+n+++++++++++++++++ PC$If^CgdLxl  P$IfgdLxl $IfgdLxl ++++++++ ,,.,A,B,upppkkkkkgdLxgdLxvkd$$Ifl0|)Y t044 la$IfgdLxl B,C,D,G,L,c,r,s,x,~,,,,,,,,,,,,,--0-T-e---gdLxgdLx-----./.0.3.a.....%///R/X/Z/[/^//////0A0^0y0gdLxgdLxy0000000001111-1@1l11111111222.20232#gdLxgdLxgdLx32T2s2222=3>3L3Y3s333333333333333$a$gdLx33333333333 hL0jhLxhLx hLx0JjhLx0JUhLx0JmHnHu $1h/R / =!"#$%X$$If!vh55#v#v:V l t655X$$If!vh55#v#v:V l t655}$$If!vh55#v:V l t065% Dd4 TT^  C :A"rectangle_union2bs hVJ;<쒚6O wnG hVJ;<쒚6PNG  IHDRi'tEXtCreation Time * ׻vStIME 74q7 pHYs  ~ IDATx]hnr$G*v ~p ˜ ?" I`;OK)㚺%.X*R-[՗wwfW([5լVrݙ=3ggg"BStuXr,`-q4A"CuzB1F%BkD "{ЈFPd|XdX^Mg|LIG|ykzјc0I*)XH(g"1!DʣLjP)2'xǨZu@#t눱 l2udAZkc䱪EH##dFJdbi,/0V 0.~WPm)lSq#!8PHA, &6I)DLCga){/[JFO:E( f"L׉nX GI<Ġ)(5M$2l%oV$ W ,|oZ-;}c5ɜvg0͵jy(zt˧~wttܻwǾ\KC;|i۷cccʖ-[a},hwW^99%3&hp񞞞(ǎ۾}{hcǎׯ߸qcc/:>,:n݂]\BO>$ho>PɓGݿݻ8ԩS,H uh!^9Whn) Z˗/CTK7߹s*'N-@ԝdܹs2ww/yjY@գY y׿a`*x yM]]oo/?ppepp  mݺҥKiV's&`{vڹs熆zٳsΟ?m 2-cWGafUd#! at$'TNvRŌjCdO fET(qӿixufګilYR/P2 !$ PK&Q>+P$a(O{҄&W> %Zl8! fIDŽ3~GҦhB.SB Tpl^ DY{`jS|l`(& rOaӜ:@6ILO?ʥۇY? @x|i2Ry'ケR3[cxTQ'ad/svGʘ \;Q2h^ j_l ' jB >Pj#m4l4!ڞ[NR@Jf#Vh ]Zbٝ=N;{r~|1W`}D_Y@-}d.=ɗwai,GɖS((W|1AVU wKl5E54W(̻령X"UֺKϔI%WfYY1 `+YEb# Qae$0g0g|$9w&t5 Jq8ɶP*Ή͟#Wu2i[(_5Kj>H7EW6GRkj(>~8qR l˖-;wQio`|b||>,՟#xz|OyѼ;y޼y,b' Q1!`"foz&>g  pEzAA1Q=VPľQaqRvH}rE>Au&fSp>UGbeJX {\`=XIENDB`$$If!vh55#v#v:V l t0*655$$If!vh5Y5#vY#v:V l t05Y5$6666666662 0@P`p2( 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p8XV~_HmH nH sH tH @`@ NormalCJ_HaJmH sH tH V@V g Heading 1$$<@&a$5CJ KH OJQJaJ V@V  Heading 3$h<@&5CJOJQJ\^JaJDD  Heading 4$<@&5aJDA`D Default Paragraph FontVi@V  Table Normal :V 44 la (k (No List DZD Plain TextCJOJQJ^JaJ8O8 Code h^h CJOJQJ>O> Code Fragment CJOJQJ4"4 Header  !4 @24 Footer  !.)@A. Page NumberNRN Note Level 2$ & F@& OJPJQJDObD Paragraph$a$CJ^JHOarH Question$h^h`a$gdNON Section Problemhx^h`HH V Balloon TextCJOJQJ^JaJe HTML Preformatted7 2( Px 4 #\'*.25@9CJOJQJ^JaJ8"8 Caption5CJ\aJ@O@ *Code Compressedd8j@j * Table Grid7:V0FF   Code CharOJQJ_HaJmH sH tH hOq"h !22Question Header( hx^`gd5CJNN 22 Question CharCJ^J_HaJmH sH tH HH 22Question Header Char5CJhqrh 22Question First Paragraph"$x`a$gdDO2D 22Solution#hx^h`CJPK![Content_Types].xmlN0EH-J@%ǎǢ|ș$زULTB l,3;rØJB+$G]7O٭Vsקo>W=n#p̰ZN|ӪV:8z1f؃k;ڇcp7#z8]Y / \{t\}}spķ=ʠoRVL3N(B<|ݥuK>P.EMLhɦM .co;əmr"*0#̡=6Kր0i1;$P0!YݩjbiXJB5IgAФ޲a6{P g֢)҉-Ìq8RmcWyXg/u]6Q_Ê5H Z2PU]Ǽ"GGFbCSOD%,p 6ޚwq̲R_gJSbj9)ed(w:/ak;6jAq11_xzG~F<:ɮ>O&kNa4dht\?J&l O٠NRpwhpse)tp)af] 27n}mk]\S,+a2g^Az )˙>E G鿰L7)'PK! ѐ'theme/theme/_rels/themeManager.xml.relsM 0wooӺ&݈Э5 6?$Q ,.aic21h:qm@RN;d`o7gK(M&$R(.1r'JЊT8V"AȻHu}|$b{P8g/]QAsم(#L[PK-![Content_Types].xmlPK-!֧6 0_rels/.relsPK-!kytheme/theme/themeManager.xmlPK-!\theme/theme/theme1.xmlPK-! ѐ' theme/theme/_rels/themeManager.xml.relsPK] +f ***- |)33'*2U h uY&I)*++B,-y0323 !"#$%&()+,-./01 %'-!?2$nsԥV:][b$sEOO"U+b$FFGO5ņ5;@0(  B S  ?+++ ;D&*+2;ABGU[cgms}!'/359:AJPQV_cdijrx~gmci_!f!$$% %m%v%z%%%%F&O&p'v''''( (@(M(](n(x(0*1*********"+(+-+8+++++++++++++++%&>DVYfi:=Z]+.>AQTpwCI"3KQk| % : G T Z y  Y ^  & . A T [ n L N HKopWZcjsv*4Yc  . 9 y !!P!T!l!r!!!!!!!!!""" "9"@"U"["w"{"""""""""##0#3#Q#T#n#q#####G$K$L$P$c$g$s$w$x${$~$$$$$$$$$$$$$$$$$$$%%%F%Q%\%a%m%v%%%%%% &3&9&e&j&&&&&&''( (@(M(](n(x((((((((()))**"*(*0*2*3*9*[*_*w*z*****++B+C+P+Q+]+b+w+}++++++++++++++++++::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::"m2+| }:~ʸ~V8V@JԢ@.Z/rS?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefhijklmnoprstuvwx{Root Entry FS;}Data 41Table<UWordDocument&fSummaryInformation(gDocumentSummaryInformation8qCompObj` F Microsoft Word 97-2004 DocumentNB6WWord.Document.8