Computer Science II - Juniata College



Computer Science IISpring 2016100 pointsName ___________KEY______________Miscellaneous, basic Java concepts. Fill in the blank.[10 pts]A Java source file has the extension ____.java___. It is compiled to a .class file and contains ___bytecodes___ that are interpreted by the Java __Virtual__ Machine. A class that extends another class is a ____subclass____ of the latter class, but all classes are extensions of the ___Object____ class. Two primitive types in Java are __int, float, char____ and ___boolean______. Strings cannot be effectively be compared with < and > but need to use the __compareTo/equals__ method, but if we want to test if two reference variables point to the same object, we can use __==_____. Recovery of memory used by unreferenced objects is called __garbage collection____.Object-oriented programming design principles. (True/False)[12 pts]__F__ An Abstract Data Type shows its data structure organization and hides its operations._ T __ Copying/pasting method body blocks in place of a simple call to the method is not quality software design._ T __ When a method returns a reference to an object, another method can be called on that object._ T __ A constructor of a subclass may called its parent’s constructor using a super prefix. _ T __ The information hiding principle says the user of a class need not know the details of its implementation while the implementer need not know how the class will be used._ F __ A precondition defines what must be true about the method’s return value.__ T _ An abstract class can be used to collect shared methods inheritable by related subclasses._ T __ An interface defines a set of abstract methods all of which must be implemented by a class__ T __ A protected instance variable is like a private instance variable, but becomes accessible within subclasses._ F __ Deep copying is generally preferred for most objects because it’s most efficient.__ T _ An interface can also be extended._ T __ A reference variable may be declared as an Interface type.Arrays. For this question just give segments of Java code. You need not write entire methods or classes.[18 pts total] Assume a collection of Employees is maintained as a array of Employee objects called emps[ ] 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 a second array of Employee objects called emps2 with the same number of elements as emps.[3]Employee [] emps2 = new Employee [emps.length];b. Use a for loop to shallow copy all the elements from emps over to emps2. [4]for (int i=0; i<lsize; i++){ emps2 [i] = emps [i];c. Append a new Employee object referred by Employee variable nextEmp to the array and adjust lsize accordingly. [3]emps[lsize++] = nextEmp;d. Use a for loop to insert nextEmp as a new n-th element emps[n] into the array by shifting all following elements by one index position. Adjust lsize accordingly. [6]for(int i=lsize; i>n; i--){ emps[i] = emps[i-1]; } emps[n] = nextEmp; lsize++;e. Effectively delete the last element of the array. [2]lsize --;emps[lsize] = null;// optionalTrue/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 bytecodes.___ T ___ A cost function can relate running time to the data size.___ F ___ A cost function is mostly increasing but can also have a decreasing section.___ T ___ Asymptotic dominance analysis considers only when the data size gets large.___ T ___ For the definition of big-O, f(n) = O(g(n)), where C*g(n) >= f(n) for some n > n0. C is any value that can make the equation true.__ T ___ Logarithms of lower base dominate those of higher base.__ F ___ f(n) = 2n3 + 24n2 - 5n + 100 = O(n2)__ T ___ f(n) = 10k5 + 2n3 + 30 = O(n3)___ T __ f(n) = 16 log n + 10 n2 = O(n2)___ F __ f(n) =2n + n6 = O(n6)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 and variables hold no values dependent on n.[10 pts] ___O(n)______for(j=5; j<n-5; j++){ 3 assignments and 1 output;} ____ O(n3)___for (i=0; i<n; i++) for(j=0; j<n; j++) for(k=1; k<n; 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 = n;while(i>0){ for(j=0; j<=n; j++){ foo(j,n); //foo takes constant time } i = i/3;} ____ O(n3)____i = n;while(i>0){ if(i % 2 == 1){ // if i is odd for(j=i; j<=n; j++){ foolog(i,j); //foolog executes in log time } } for(j=i; j<=n; j++){ foolin(j,n); //foolin’ executes in linear 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(log n)O(2n)O(n)O(1)O(n log n)526314True/false on the abstract data type of arrays and lists (general linked lists).[5 pts]_T__ Both arrays and linked lists are linear structures.__ F __ Access to the nth element in an array has the same 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, but costs logarithmic 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 “lists”, “are”, and “fun”. That is, the info/data field of the nodes separately points to the String objects. Arrange the nodes in the order given. Draw all objects as boxes.[5 pts]b) Show how the links above are rearranged to insert two nodes containing “linked” at the front of the list and “not” prior to “fun”. 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]- * + 8 2 3 * 2 4 = ___22____2 3 * 9 4 1 - - * = ___36_____ 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____ data; private __LListNode___ next; public LListNode(Object x){//constructor ______data________ = ____x_____ ; ______next________ = ____null____ ; }//end constructor public setData(____Object _____ x) { data = x;} public getData() { return __ data ____; } 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 void push(__Object ___ x){ //new node at front of list LListNode temp = new ___ LListNode _____ ( ___ x _____ ) ; __temp__ . __setNext__( __ top ___ ) ; top = _ temp ___ }} ................
................

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

Google Online Preview   Download