Algorithms and Data Structures (M)
SAMPLE EXAM
This exam is multiple-choice and contains 25 questions ((i)-(xxv)). You should select one answer (a, b, c, d) for each question. Each correct answer is worth 2 marks. Incorrect answers will result in a penalty of two thirds of a mark to discourage guessing. A negative mark overall for this question will be rounded up to zero.
(i) Which of the following would we use to declare a class named A with a single generic type?
(a) public class A { ... }
(b) public class A { ... }
(c) public class A(E) { ... }
(d) public class A(E, F) { ... }
(ii) Which of the following methods is not in the Collection interface?
(a) clear()
(b) isEmpty()
(c) size()
(d) getSize()
(iii) You can use a for-each loop to traverse all elements in a container object that implements which of the following interfaces?
(a) Iterator
(b) Collection
(c) Iterable
(d) ArrayList
(iv) If list is a LinkedList that contains 1 million int values and A and B are the following fragments of code:
A:
for (int i = 0; i < list.size(); i++)
sum += list.get(i);
B:
for (int i: list)
sum += i;
Which of the following statements is true?
(a) Code fragment A runs faster than code fragment B
(b) Code fragment B runs faster than code fragment A
(c) Code fragment A runs as fast as code fragment B
(d) It is impossible to tell which of A or B is faster without knowledge of the size of the input integers
(v) What will be displayed by the following code?
List list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");
list.add("D");
for (int i = 0; i < list.size(); i++)
System.out.print(list.remove(i));
(a) ABCD
(b) AB
(c) AC
(d) BCD
(vi) What is the output from the following code?
import java.util.*;
public class Test {
public static void main(String[] args) {
Set set = new HashSet();
set.add(new A());
set.add(new A());
set.add(new A());
set.add(new A());
System.out.println(set);
}
}
class A {
int r = 1;
public String toString() {
return r + "";
}
public int hashCode() {
return r;
}
}
(a) [1]
(b) [1, 1]
(c) [1, 1, 1]
(d) [1, 1, 1, 1]
(vii) For a sorted list of 1024 elements, a binary search takes at most x
comparisons (where a comparison is a check whether an element is greater than, equal to, or less than another element). What is x?
(a) 11
(b) 100
(c) 512
(d) 6
(viii) The following recursive algorithm is to calculate the nth Fibonacci number, Fib(n).
1 if n ≤ 2
return 1
2. else
return Fib(n-1) + Fib(n-2)
The time complexity for Fib(n) is:
(a) O(nlogn)
(b) O(n2)
(c) O(logn)
(d) O(2n)
(ix) Consider the following code:
public class Test {
public static void main(String[] args) {
Map map = new HashMap();
map.put("123", "John Smith");
map.put("111", "Ella Smith");
map.put("123", "Steve Price");
map.put("222", "Steve Price");
}
}
Which one of the following statements is true?
(a) After all the four entries are added to the map, "123" is a key that corresponds to the value "John Smith"
(b) After all the four entries are added to the map, "123" is a key that corresponds to the value "Steve Price"
(c) After all the four entries are added to the map, "Steve Price" is a key that corresponds to the value "222"
(d) A runtime error occurs because two entries with the same key "123" are added to the map.
(x) What is the worst-case time complexity for quick-sort?
(a) O(log n)
(b) O(n log n)
(c) O(n)
(d) O(n2)
(xi) What is the best-case time complexity for quick-sort?
(a) O(log n)
(b) O(n log n)
(c) O(n)
(d) O(n2)
(xii) Which of the following Binary Search Trees would result from inserting the values 1, 10, 16, 7, 5 and 2 into an empty Binary Search tree in the given order
(i.e. without balancing)?
(xiii) Which of the following AVL Trees would result from inserting the values
1, 10, 16, 7, 5 and 2 into an empty AVL tree in the given order (i.e. with balancing)?
(xiv) What is the preorder traversal ofthe binary search tree below?
(a) 1, 2, 4, 3, 2, 6, 6, 9, 8, 10
(b) 2, 4, 3, 1, 6, 5, 8, 10, 9, 7
(c) 7, 5, 1, 3, 2, 4, 6, 9, 8, 10
(d) 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
(xv) What is the postorder traversal ofthe binary search tree in (xiii)?
(a) 1, 2, 4, 3, 2, 6, 6, 9, 8, 10
(b) 2, 4, 3, 1, 6, 5, 8, 10, 9, 7
(c) 7, 5, 1, 3, 2, 4, 6, 9, 8, 10
(d) 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
(xvi) What is the inorder traversal ofthe binary search tree in (xiii)?
(a) 1, 2, 4, 3, 2, 6, 6, 9, 8, 10
(b) 2, 4, 3, 1, 6, 5, 8, 10, 9, 7
(c) 7, 5, 1, 3, 2, 4, 6, 9, 8, 10
(d) 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
(xvii) Consider the following algorithm for reading a file of (unsorted) values into a sorted array. There are n values in the file.
1.Set m to 0.
2.While not at end of file f, repeat:
2.1. Read value val from f
2.2. Insert val into the correct position in the
sorted array a [0…m–1]
2.3. Increment m
3.Terminate.
The complexity of this algorithm is:
(a) O(n)
(b) O(n2)
(c) O(log n)
(d) O(n log n)
(xviii) Consider the following statements:
(S1) When you create an array using new int[10], an array object is created with ten integers of value 0.
(S2) When you create an array using new int[10], an array object is created with no values in the array
(S3) When you create an ArrayList using new ArrayList<> (), an ArrayList object is created with no elements in the ArrayList object.
(S4) When you create an ArrayList x using new ArrayList<> (10), x.size() is 10
Which of the following is correct?
(a) only S2, S3 and S4 are true
(b) only S2 and S4 are true
(c) only S1 and S4 are true
(d) only S1 and S3 are true
(ixx) What is list after the following code is executed?
ArrayList list = new ArrayList<>();
list.add(1);
list.add(2);
list.add (3);
list.add(4);
list.remove(2);
System.out.println(list);
(a) [1,2,3,4]
(b) [1,3,4]
(c) [1,1,1,1]
(d) [1,2,4]
(xx) What is the output from the following code?
LinkedHashSet set1 = new LinkedHashSet();
set1.add("bubblegum");
set1.add("starburst");
LinkedHashSet set2 =
(LinkedHashSet)(set1.clone());
set1.add("smarties");
set2.add("dolly mixture");
set1.remove("bubblegum");
System.out.println(set2);
(a) [bubblegum, starburst, smarties, dolly mixture]
(b) [starburst, smarties, dolly mixture]
(c) [bubblegum, starburst, dolly mixture]
(d) [starburst, smarties, dolly mixture]
(xxi) What are the best-case and worst-case complexities of the MergeSort algorithm respectively?
(a) n log n, n log n
(b) n log n, n2
(c) n2, n log n
(d) n2, n2
(xxii) Consider the following code:
public class Test {
public static void main(String[] args) {
Map map = new HashMap();
map.put(100, "Darth Vader");
map.put(75, "Kylo Ren");
map.put(150, "Yoda");
map.put(200, "Han Solo");
map.put(150, "R2-D2");
map.put(150, "Boba Fett"); }
}
Which one of the following statements is true?
(a) A runtime error occurs because more than one entry with the same key 150 are added to the map
(b) After all the six entries are added to the map, 150 is a key that corresponds to the value "Boba Fett"
(c) After all the six entries are added to the map, "Boba Fett" is a key that corresponds to the value 150
(d) After all the six entries are added to the map, 150 is a key that corresponds to the value "Yoda R2-D2 Boba Fett"
(xxiii) Suppose that we use a closed bucket hash table H of size 520 to store a set
of 1000 words.
The load factor of H is approximately:
(a) 1/1520
(b) 1520
(c) 2
(d) 0.5
(xxiv) Suppose lists L1 and L2 are represented using singly linked lists whose headers contain only references to the first node of the list in each case. If L1 and L2 have n and n9 elements respectively, the time complexity of concatenating the two lists is:
(a) O(1)
(b) O(nn9)
(c) O(n+n9)
(d) O(n)
(xxv) Suppose lists L1 and L2 are as for part (xxiii) but this time their using headers contain references to the first and last nodes of the list in each case. The time complexity of concatenating the two lists is now:
(a) O(1)
(b) O(nn9)
(c) O(n+n9)
(d) O(n)