Computer Science II - Juniata College



Computer Science IISpring 2015100 pointsName _________key________________Miscellaneous, basic Java concepts. Matching. Place the letter in the blank that best matches the statement.[10 pts] __E___ The filename containing the compiled bytecodes for the class Test1.__I___ The header line when Test1a is a subclass of Test1 .__G___ The automatic recovery of memory used by objects no longer accessible through any references.__B___ Where Test1 source code is found.__L___ and ___O___ are Java primitive types.__R__ Java operation/method to check string equality.__M___ All classes are a subclass of this class.___T__ The method called upon to return a summary string of an object’s contents; usually it is overridden._U__ Used to compare if two object addresses are the same.Test1.sourceTest1.javaTest1.exeTest1.objTest1.classDefragmentingGarbage collectingSortingpublic class Test1a extends Test1public subclass Test1a of Test1StringdoubleObjectClassbooleanInteger.println().equals().strcmp().toString()==>=<Object-oriented programming design principles. (True/False)[10 pts]__T__ An Abstract Data Type hides its data structure organization and publicizes its operations.__F__ Copying method body blocks in place of a call is a quality software goal in object-oriented class design.__T__ Any method that returns an object can be called as part of a cascade of method calls._T___ A method of a subclass may called its parent’s class method using a super prefix. __F__ 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.__T__ A precondition defines what must be true about the parameters for a method to correctly carry out its task.__T__ An abstract class can be used to define shared methods and instance variables inheritable by related subclasses.__T__ An interface defines a set of abstract methods that must be implemented by a class that then may be used by other classes.__F__ A protected instance variable is like a public instance variable, but remains inaccessible within subclasses.___F_ Deep copying is generally preferred for pushing and popping stack operations of objects.Arrays. For this question just give segments of Java code. You need not write entire methods or classes.[20 pts total] Assume a sound mashup is composed as a completely filled array of Sound objects called clips[ ] and an int variable lsize holds the logical size of the array which is currently equal to the physical size of the array. a. Create another array of Sound objects called clips2 with clips.length*2 elements. [3]Sound [ ] clips2 = new Sound [clips.length*2] ; b. Use a for loop to shallow copy all the elements from clips over to clips2. [4]for (int i=0; i<lsize; i++) clips2[i] = clips[i]; c. What does the assignment statement clips = clips2; accomplish? [3]the old short array is now candidate for garbage collection and the clips array has effectively been doubled in size.d. Append a new Sound object referred by Sound variable nextClip to the array and adjust lsize accordingly. [3]clips [lsize ++] = nextClip;e. Use a for loop to delete the first element clips[0] of the array by shifting all elements by one index position. Adjust lsize accordingly. [5]for(int i=1; i<lsize; i++) clips[i-1] = clips[i];lsize --;f. Effectively delete the last element of the array. [2]lsize --;True/false on asymptotic dominance concepts on cost functions. Recall dominance != best.[10 pts]___F___ A cost function can relate running time to the number of Java source lines.__T____ A cost function can relate running time to the data size.___ T ____ A cost function is non-decreasing.____ F ___ Asymptotic dominance analysis considers both small data size as well as large data size.___ F ____ 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.___ F ____ Logarithms of lower base always dominate those of higher base.__ F ____ f(n) = 2n3 + 32n2 - 5n + 100 = O(n2)__ T ____ f(n) = 10k2 + 2n3 + 30 = O(n3)___ F ___ f(n) = 16 log n + 10n log n = O(log n)__ T ____ f(n) =2n + n6 = O(2n)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] ____O(n)_____for(j=n; j>5; j--){ 3 assignments and 1 output;} ____ O(n2)_____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 } _____ O(n3)___for (i=n-1; i>=0; i--) for(j=0; j<n; j++) for(k=10; k<i; k++){ // 3 assignments } ___O(n log n)__i = 1;while(i<=n){ for(j=0; j<=n; j=j+2){ foo(j,n); //foo takes constant time } i = i*2;} _____ O(n3)___i = n;while(i>0){ if(i % 2 == 1){ // if i is odd for(j=i; j<=n; j++){ foolin(j,n); //foolin’ executes in linear time } } for(j=i; j<=n; j++){ foolog(i,j); //foolog executes in log time } i = i-1;}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(n3)O(2n)O(n)O(1)O(n log n)456213True/false on the abstract data type of arrays and lists (general linked lists).[5 pts]__ T ___ An element of a linked list and of an array have exactly one successor and one predecessor, except first and last elements.___ T __ Access to the nth element in an array has better time complexity cost as accessing the nth element of a linked list.___ T __ A linked list must have a reference variable pointing to its first element.__ F ___ A linked list permits direct access to its elements, costing constant time.__ T ___ Data components of a linked list node can be any data type or object.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 “break”, “is”, and “soon”. That is, the info/data field of the nodes separately points to the String objects. Arrange the nodes in the order given. 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 “Spring” at the front of the list and “very” prior to “soon”. Just add these nodes above and “cut” and redraw adjusted links. Do not erase the original linkages from part a).DRAW ABOVEConvert 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[5 pts]a * b + c / (d * e) Prefix:______+ * a b / c * d e____Postfix:_____a b * c d e * / +_____________Evaluate the following prefix expression and postfix expression.[5 pts]- * / 6 2 4 + 1 2 = ___9____2 3 + 9 6 2 - - * = ____25___ Show the sequence of stack contents during the evaluation of the above right hand postfix expression. Show the stack contents anew after each operator evaluation. Fill in the blanks for the declarations and assignment statements in the Java LListNode and LListStack classes below to partially support the implementation of linked list stack of any object.[15 pts]public class LListNode // private ___Object___ info; private ___LListNode____ next; public LListNode(String x){//constructor _____info________ = _____x_____ ; _____next_________ = ____null___ ; }//end constructor public setInfo(Object x) { info = x }; public getInfo() { return info; } public setNext( __ LListNode __ p) next = p; }; public getNext() {return next; }}//end LListNode//--------------------------------------------public class LListStack // define and initialize the head pointer{ private __LListNode__ top ; public LListStack()//default constructor {_____top_______ = ___ null __ ; }//end constructor public Object pop(){ if ( ___ top _____ == __ null _ ) __throw__ new StackUnderflowException ("Stack is empty—cannot pop"); Object temp = ____top.getInfo()_________ ; _ top _ = ________ top.getNext()_________ ; return __temp___; }} ................
................

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

Google Online Preview   Download