EECS2011 M: Fundamentals of Data Structures Midterm Test February 26, 2019 Instructions: Closed book No electronic computation or communication devices Manage your time wisely Student Last Name: First Name: York Student ID #: EECS account: 1. 20% 2. 20% 3. 30% 4. 30% Total 100% Department of EECS York University Term: Winter 2019 Instructor: Andy Mirzaian 1 1. [20% ] Fill in the underlined blanks with a short answer. All logarithms are base 2. a) [3%] Suppose Child class is a subclass of Parent class . Is Child[ ] a subtype of Parent[ ]? Answer:__________________________________________ . Is List a subtype of List? Answer:____________________________________ . b) [4%] What do each of the following print? System.out.println( “83” + 1 + 7); Answer: ____________________________________ . System.out.println(8 + 3 + “17”); Answer: ____________________________________ . System.out.println(9 + (6 + “25”)); Answer: ____________________________________ . c) [4%] What will be the output of the following program? public class Demo { static class A { public A() { System.out.print ( “” ); } } static class B extends A { public B() { System.out.print ( “” ); } } static class C extends B { public C() { System.out.print ( “” ); } } public static void main( String[] args ) { C c = new C(); } } Answer: _____________________________________________________________________ . d) [4%] What value does the following method return? public static int foo ( int n ) { int k = 0; for ( int i = 0 ; i < n; i++ ) k += ++k ; return k; } Answer:______________________________________________________________________ . e) [5%] Order the following three functions of in increasing order of growth rate: () = 2 + 3 5 (1+4 log ) , = 2 (4 + 7 log ) + 5 log , = 7 log + 8(log )/9 . Answer: ______________________________________________________________________ . 2 2. [20%] Multiple choice questions: Circle the most appropriate choice. a) [7%] log + 6 + 5 log 10 + 2+6 7 + log is A. Θ 2 . B. Θ 2 log . C. Θ 2.5 . D. Ω 3 . b) [7%] What is the asymptotic running time of the method below as a function of ? public void quiz ( int n ) { for ( int i = n; i > 0; i– ) for ( int k = i; k > 0; k /= 5 ) System.out.println( (i-1) * (k+5) ); } A. O log . B. O . C. Θ log . D. Ω 2 . c) [6%] What is the value of the postfix expression 6 3 2 4 + – * ? A. Some number between -100 and -15 . B. Some number between -15 and -5. C. Some number between -5 and 5. D. Some number between 5 and 15. E. Some number between 15 and 100 . 3 3. [30%] Give short answers: a) [12%] What does the following code fragment print? int[ ] a = new int[10]; for ( int k = 0; k < 10 ; k++ ) a[k] = 9 - k; for ( int k = 0; k < 10 ; k++ ) a[k] = a[a[k]]; for ( int k = 0; k < 10 ; k++ ) System.out.print( a[k] + “ ” ); Answer: ____________________________________________________________________. b) Consider the following algorithm. public static void mystery( int n) { if (n <= 0) return; mystery(n/2); System.out.println( n*(n+1)*(n+2) ); mystery(n/2); } i. [6%] The recurrence relation for the running time of this algorithm is Answer: T n = ii. [12%] The solution to this recurrence relation is Answer: T n = Θ ____________________ . Briefly show the derivation of this solution by the iteration method: 4 4. [30%] This question concerns the Singly Linked List (SLL) with a head pointer but no tail pointer. Suppose the following recursive method is implemented inside the SLL class (hence, it has access to its private members) and modifies an instance SLL in some specific way that you will need to figure out below. 5 public static Node modifySLL( Node p ) { if ( p == null || p.getNext() == null ) return null ; Node q = p.getNext() ; p.setNext( modifySLL( q ) ) ; return q ; } Continued on the next page a) [10%] What would be the result of applying the instruction Node h2 = modifySLL( h1 ) ; on the SLL below? Draw a diagram of the resulting state of the data. In that diagram also clearly show where h1 and h2 point to. ‘A’ null h1 ‘B’ ‘C’ ‘D’ ‘E’ ‘F’ ‘G’ 4. Continued … b) [5%] Describe, in general, exactly what is the post-condition of modifySLL( h1 ) on an arbitrary SLL with a head pointer h1. c) [15%] Write a linear-time iterative instance method modifySLL_Iterative() such that list.modifySLL_Iterative() has the same post-condition as modifySLL( list.head ). Assume this method is also implemented inside the SLL class. public Node modifySLL_Iterative() { // the rest of your code goes below this line 6
