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