Computer Science II



Computer Science IISpring 2014, Friday, 3/21/14100 pointsName _____________________________Miscellaneous, basic Java concepts. Matching. Place the letter in the blank that best matches the statement.[10 pts] _____ The filename containing the compiled bytecodes for the class Test1._____ Where Test1 source code is found._____ The header line when Test1a is a subclass of Test1 ._____ The automatic recovery of memory used by objects no longer accessible through any references._____ and _____ are Java primitive types._____ Java operation/method to check string equality._____ All classes are a subclass of this._____ The method called upon to return a summary string of an object’s contents; usually it is overridden._____ Used to compare if two objects’ addresses are different.java.Test1Test1.classTest1.exeTest1.javaDefragmentationGarbage collectionpublic class Test1a extends Test1public subclass Test1a of Test1StringdoubleObjectClasschar.println().equals().strcmp().toString()==!=<Object-oriented programming design principles. (True/False)[10 pts]____ An Abstract Data Type hides its data structure organization and publicizes its operations.____ Copying and pasting code is a quality software goal in object-oriented class design.____ A method that returns an object can be called as part of a cascade of method calls.____ The this instance reference in a method can always be omitted.____ A method of a subclass may called its parent’s class method using a super prefix. ____ The information hiding principle says the user of a class need not know the details of its implementation while the implementer should be made aware of how the class will be used.____ A precondition defines what must initially hold for a method to correctly carry out its task.____ A class may not define multiple methods with the same name even if the parameter set (signature) is different.____ A protected instance variable is like a private instance variable, but remains accessible within subclasses.____ A variable designated as static in a class makes it a class variable of which there can only be one instance.Arrays. For this question just give segments of Java code. You need not give entire methods or classes.[9 pts] a. Assume a sound mashup is composed as an array of Sound objects called soundClips[ ]. Give Java code segments to 1) create a second array of Sound objects called revSounds with soundClips.length elements and 2) use a single for loop to initialize each element of revSounds to the reversed Sound objects from the soundClips array using the reverse() method (which returns a Sound object) AND reverse the order of the clips in the new array. Only use one loop! The result should be a totally reversed sound mashup. [9]Fill in Java code in the method makeBlackAndWhite() below to modify a Picture object that generates the photographic negative of the image. This is done by setting the RGB values each to the average of the original RGB values.[6 pts]public _____________ makeBlackAndWhite() { Pixel [] pixels = this.getPixels(); for(Pixel pix : _________ ){ ______ grayscale = _____________________________________________ / 3;____.setRed (_________________);____.setGreen (_______________);____.setBlue (________________); }}Below is a main program to draw something with turtles. a. Draw a possible scenario from executing this code in the 400x400 pixel box. This is testing your code reading.[5 pts]public class SomethingByTurtles { private static final int N = 2; public static void main(String[] args){ World myWorld = new World(); Turtle [][] myTurtles = new Turtle[N][N]; Turtle s; //temporary reference int dist; for (int i=0; i < N; i++) { for (int j=0; j < N; j++) { myTurtles[i][j] = s = new Turtle(myWorld); //cascading assignment //initially centered at 200,200; heading up/north356235060960 s.penDown(); s.moveTo(i*100+2,j*100+2); //+2 to keep off border } } for (int i=0; i < N; i++) { for (int j=0; j < N; j++) { dist = i*100+j*100; s = myTurtles[i][j]; s.turn(90); s.forward(dist); } }}True/false on asymptotic dominance concepts on cost functions.[10 pts]_______ A cost function can relate running time to the number of Java bytecodes._______ A cost function can relate running time to the data size._______ A cost function can be decreasing._______ Asymptotic dominance analysis considers both small data size as well as large data size._______ For the definition of big-O, f(n) = O(g(n)), where C*g(n) >= f(n) for some n > n0. C is a value that is dependent on n._______ Logarithms of lower base always dominate those of higher base.______ f(n) = 2n3 + 3200n2 - 5n + 100 = O(n2)______ f(n) = 10n2 + 2k3 + 30 = O(k3)______ f(n) = 16 log n + 10n = O(n)______ f(n) = n6 +2n = O(n6)Rank the algorithm complexities from "fastest" to "slowest" (increasing dominance). 1 is fastest (good, low cost) and 6 is slowest (bad, high cost).[5 pts]O(n2)O(log n)O(2n)O(n)O(1)O(n log n)Estimate the running times using the big-O notation for each of these code segments. The size of the data set is n. Assume all variables are integer.[10 pts] ____________for(j=1; j<=n-20; j++){ sum += j;} ____________for (i=0; i<n; i++) for(j=0; j<n; j++) for(k=1; k<99; k++){ // 4 assignments // 2 square root function calls } ____________for (i=n-1; i>=0; i--) for(j=0; j<n; j++) for(k=j; k<n; k++){ // 3 assignments } ____________i = 1;while(i<=n){ for(j=0; j<=n; j=j+2){ foo(j,n); //foo takes linear time } i = i*2;} ____________i = n;while(i>0){ if(i % 2 == 1){ // if i is odd for(j=i; j<=n; j++){ foo(j,n); //foo executes in linear time } } for(j=i; j<=n; j++){ foo(i,j); //foo executes in log time } i = i-1;}True/false on the abstract data type of arrays and lists (general linked lists).[5 pts]_____ A linked list’s and an array’s elements have a single successor and predecessor, except first and last ones._____ Access to the nth element in an array has the same cost as in a linked list._____ A list must have a reference variable pointing to its first element._____ A linked list permits direct access to its elements, costing constant time._____ Data elements of a linked list node must be a primitive data type.Assume we have an instance array picts of Picture objects to be implemented in a class called Pictures. There is an integer instance variable np that accurately tracks the logical number of pictures in the array. [10 pts]private Pictures [] ______;private int _____ ;Show the code in Java for the default constructor of Pictures to set picts array initially with room for 100 pictures and set np to reflect no elements.public Pictures(){ picts = new ___________________ ; np = _____;}Complete the method to delete a picture from the front of the array by shifting all elements one position.public void deleteFirst(){ for(int i= ____; i< ___; i++){ picts [______] = picts [______] ; } ______ --;}Linked lists.a) Draw a box and pointer diagram representing a linked list pointed to by a reference variable head. The list should point to the String objects “dog”, “fish”, and “snake”. That is, the info/data field of the nodes separately points to the String objects. Keep the data in sorted order by name. Remember that Strings are not primitives. Draw all objects as boxes.[5 pts]b) Show how the links above are rearranged to insert two nodes containing “bear” and “pig” into the list at the appropriate points. Just add these nodes above and “cut” and redraw adjusted links.DRAW ABOVESupply the declarations and assignment statements in the Java PNode class below to partially support the implementation of a linked list in which each node holds a Picture pic pointer and a next pointer.[15 pts]public class PNode //instance variables declaration Picture pic; _________ next;public PNode(Picture x){//constructor pic = _________ ; next = _________ ;}public Picture getPicture(){ return __________ ; }public void setNext(PNode pn){ _______ = _______; }public PNode getNext(){ return _________ ; } //embed each picture into the background bg, left to right on bottom //by traversing the listpublic void drawFromMeOn(Picture bg){int X = 0;int Y = bg.getHeight()-1;PNode curr = ____________ ; while ( curr != _______) {curr.getPicture().drawMeOn(bg,X,Y);X = X + curr.getPicture().getWidth();curr = ________.__________;} } //--------------------------------------------public static void main(String args[]){ _______ head; //track the linked list of nodes// lots of stuff to create the list pointed to by head……….. // now arrange the composite picture from left to rightPicture bg = new Picture(“background.jpg”);______ . drawFromMeOn( _______ );_______ .show(); //display the picture} ................
................

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

Google Online Preview   Download