Algorithms and Data Structures (M)
MOCK EXAM
Question 1
Parts (i) – (ii) refer to the algorithm shown in Box 1. The algorithm takes an array a and searches it for a substring that matches a shorter array b. This uses an auxiliary algorithm that compares two subarrays of equal length.
|
Main algorithm:
To search the array a[0 …n-1] for a subarray that matches b[0 …m-1], where m < n:
1. For i = 0, … , n-m, repeat:
1.1. Ifa[i …i+m-1] matches b[0 …m-1], terminate with answer i.
2. Terminate with answer none.
Auxiliary algorithm:
To test whether a[i …i+m-1] matches b[0 …m-1]:
1. For j = 0, … , m-1, repeat:
1.1. Ifa[i+j] ≠ b[j], terminate with answer false.
2. Terminate with answer true.
|
Box 1 An algorithm to search an array for a matching subarray.
For example:
Here the answer should be 1 (the index of the leftmost matching substring in a).
(i) What is the average time complexity of the auxiliary algorithm in terms of the length n of the subarray a?
(a) O(n)
(b) O(n2)
(c) O(log n)
(d) O(1)
(ii) If array a is as above but b is
What answer should the main algorithm give?
(a) 8
(b) 4
(c) -1
(d) none
Parts (iii) - (iv) refer to the Java code shown in Box 2.
|
public class ListExample {
public static void pListSet (List<Integer> l, Set<Integer> s){
for(Integer i:l) System.out.print (i + " ");
System.out.print ("; ");
for(Integer j:s) System.out.print (j + " ");
}
public static void main(String[] args) {
List<Integer> myList = new ArrayList<Integer>(7);
Set<Integer> mySet = new TreeSet<Integer>();
int temp = 0;
for(int i=0;i<6;i++){
if(i%2==0) temp = 8 - 2*i;
else temp = 10 - 2*i;
myList.add (i,temp);
mySet.add (temp);
}
printListSet (myList,mySet);
}
}
|
Box 2 Java code for list example
(iii) What is the output from running the main method?
(a) 8 8 4 4 0 0 ; 8 4 0
(b) 8 8 4 4 0 0 ; 0 4 8
(c) 8 4 0 ; 0 4 8
(d) 8 8 4 4 0 0 ; 0 0 4 4 8 8
(iv) If the line initialising mySet is replaced by the line:
Set mySet = new HashSet();
What would the output be now?
(a) 8 8 4 4 0 0 ; 8 4 0
(b) It is not possible to predict the order without knowing the hash function used
(c) 8 4 0 ; 0 4 8
(d) 8 8 4 4 0 0 ; 0 0 4 4 8 8
(v) Let T(n) denote the number of comparisons required to sort an array ofsize n using the mergesort algorithm. Assuming that n-1 comparisons are required to merge two arrays of total length n together, which of the following recursive expressions correctly describes T(n):
(a) T(n) = 2T(n-1) + 1, T(1) = 0
(b) T(n) = 2T(n/2), T(1) = 0
(c) T(n)=2T(n/2) + n-1, T(1) = 0
(d) T(n) = 2T(n/2) + T(n-1), T(1) = 0
(vi) What are the best-case time and space complexities of the mergesort algorithm?
(a) O(n2) and O(n)
(b) O(n2) and O(2n)
(c) O(n log n) and O(n log n)
(d) O(n log n) and O(n)
(vii) Which of the following trees are binary search trees and would result from
inserting the values 9, 4, 7, 5, 1, 3, 8, 11 into an empty Binary Search tree in the given order (i.e. without balancing)?
(viii) Which of the following (unbalanced) Binary Search Trees would result from deleting the value 7 from the search tree depicted as (d) in part (i)?
(ix) Which of the following trees is an AVL tree that would result from inserting the values 9, 4, 7, 5, 1, 3, 8, 11 into an empty AVL tree in the given order (i.e. with balancing)?
(x) Which of the following sequences correspond to a pre-order traversal of the search tree depicted in (c) above?
(a) 8, 5, 3, 1, 4 ,11, 9, 7
(b) 1, 3, 4, 5, 8, 7, 9, 11
(c) 1, 4, 3, 5, 7, 9, 11, 8
(d) 3, 1, 4, 5, 11, 9, 7, 8
Question 2
Parts (i) - (ii) refer to the algorithm shown in Box 3 to change the order of
elements in an array a containing copies of the Strings “red”, “yellow ” and
“green”. Values left and Right denote the smallest and largest indices of a.
|
1. Set g to left, set r to left, and set y to left.
2. While r ≤ right, repeat:
If a[r] is “red” :
Increment r.
Else
if a[r] is “green”
if r > g
swap a[r] with a[g] increment g and r
Else
if a[r] is “yellow” :
if r > y
swap a[r] with a[y].
if r > g, swap a[r] with a[g].
Increment y, g, and r.
3. Terminate.
|
Box 3 Algorithm to reorder elements in an array
(i) If the algorithm is applied to the array a below:
a = ["green", "yellow", "red", "green", "red"]
What is the final state of a?
(a) ["green", "yellow", "red", "green", "red"]
(b) ["yellow", "green", "green", "red", "red"]
(c) ["green", "green", "yellow", "red", "red"]
(d) ["red", "red", "yellow", "green", "green"]
(ii) What is the time complexity of the algorithm of part (i), given that swapping two elements of the array is a constant time operation?
(a) O(n2)
(b) O(n)
(c) O(log n)
(d) O(1)
(iii) Consider the following sorted array:
If linear search is used to locate the string “pear”, what are the strings contained in the first 3 array positions visited?
If required, you may assume that, for an array with smallest and largest indices left and right respectively, the index approximately at the middle of the array is calculated as the integer part of (left+right)/2.
(a) “melon”, “raspberry”, “pear”
(b) “satsuma”, “raspberry”, “pear”
(c) “melon”, “pear” (no further positions need to be visited)
(d) “apple”, “banana”, “grape”
(iv) If binary search is instead used to search the array from part (xiii), what are the strings contained in the first 3 array positions visited?
If required, you may assume that, for an array with smallest and largest indices left and right respectively, the index approximately at the middle of the array is calculated as the integer part of (left+right)/2.
(a) “melon”, “raspberry”, “pear”
(b) “satsuma”, “raspberry”, “pear”
(c) “melon”, “pear” (no further positions need to be visited)
(d) “apple”, “banana”, “grape”
(v) Java’s generic Iterator interface, Iterator supports which of the following sets of methods?
(a) hasNext(),next(),remove()
(b) getFirst(),next(),addLast()
(c) hasNext(),getFirst(),remove()
(d) getFirst(),next(),remove()
(vi) This question involves the deletion of a node from a non-empty doubly linked list L with first node first. Any Node N consists of an element (N.elem) and references to the next node in the list (N.next) and the previous node in the list, (N.pred).
Assuming that del is the node to be deleted, which pair of steps from the following list, when performed in the given order, will delete the node from the list?
(a) A, C
(b) B,D
(c) A,D
(d) C,B
(vii) Suppose that two binary search trees BST1 and BST2 store sets S1 and S2 respectively, where S1 and S2 have size n. What are the average and worst time complexities respectively for determining if the sets are equal (i.e., they contain the same elements)? You may assume that the average height of a BST containing n elements is O(log n).
(a) O(n log n) and O(n2)
(b) O(n log n) and O(n log n)
(c) O(n2) and O(n2)
(d) O(n2) and O(n log n)
(viii) Suppose that a new node N is inserted into an AVL tree using standard Binary Search Tree insertion prior to balancing and that k1 is the deepest node in the tree to become unbalanced by the insertion. Let k2 be the right child ofk1 and k3 the left child ofk2, where k2 and k3 are the next nodes on the path from k1 to N.
Consider the following actions:
A: single right rotation about k1
B: single left rotation about k1
C: single right rotation about k2
D: single left rotation about k2
Which sequence of actions when performed in the given order will balance the tree?
(a) C, A
(b) B
(c) C, B
(d) D, A
(ix) Suppose that in part (viii), k3 were the right child ofk2. Which of the actions A-D, when performed in the given order will balance the tree?
A: single right rotation about k1
B: single left rotation about k1
C: single right rotation about k2
D: single left rotation about k2
(a) C, A
(b) B
(c) C, B
(d) D, A
(x) Which of the following statements is not true?
(a) the Queue ADT is a special case of the List ADT
(b) the Stack ADT is a special case of the List ADT
(c) the Stack ADT is a special case of the Queue ADT
(d) A Java ArrayList is one of several implementations ofthe List ADT
Question 3
(i) Suppose that we use a closed bucket hash table H of size 32 to store a set of 4567 words. The load factor of H is:
(a) 32/4567
(b) 4567 - 32
(c) 32 - 4567
(d) 4567/32
(ii) If a hash table is used to represent a Set of integers, which of the following statements about the hash function is true?
(a) The hash function should always leave some buckets empty
(b) The hash function should ensure that data is spread evenly and thinly throughout the table
(c) The hash function should always ensure that a prime number of buckets are used
(d) The hash function should always be applied to the first few digits of the inputs
(iii) Consider a hypothetical university in which each student-number is a string of 4 decimal digits. The student records are to be stored in a closed-bucket hash-table of size 7, in which the keys are student-numbers. Assume the hash function is:
hash(k) = remainder on division by 7 of the last digit of k
So for example, hash(0001) = 1 and hash(3457) = 0. Starting with an empty hash- table, the following student-numbers are added to the hash table: 8001, 7008, 0002, and 1443. What is the number of comparisons required when the resulting hash-table is searched for the student-number 4158?
(a) 2
(b) 1
(c) 0
(d) 4
Parts (iv)-(vi) refer to the maps map1 and map2 shown in Box 4.
Box 4 Maps map1 and map2
Box 4 shows two maps used to store details of library books. In each map the keys denote the book code, and the values the book title.
(iv) Suppose that some Java code involves the instantiation of both maps as empty
HashMaps with initial size 20 and their population with the data above, followed by the following code fragment:.
map1.putAll(map2);
System.out.println(map1);
What is output when the code is run?
(a) {5=The Little Prince, 9=Pollyanna, 10=The Gruffalo, 16=The Borrowers}
(b) {2=[Desert Island, Jane Eyre], 5=The Little Prince,
7=[Snow White, The BFG], 9=Pollyanna,10=The Gruffalo, 16=The Borrowers}
(c) {2=Jane Eyre, 5=The Little Prince, 7=The BFG,
9=Pollyanna,10=The Gruffalo, 16=The Borrowers}
(d) {2=Desert Island, 5=The Little Prince, 7=Snow White, 9=Pollyanna,10=The Gruffalo, 16=The Borrowers}
(v) If the Java code fragment in question (iv) is replaced by:
map1.remove(16,map1.get(16));
System.out.println(map1);
what is output when the full code is run?
(a) There is a syntax error, as the method get(int) is undefined for the type Map
(b) An exception is thrown as map1 has no entry with key 16
(c) {} (the empty map)
(d) {2=Desert Island, 7=Snow White, 9=Pollyanna, 10=The Gruffalo}
(vi) If the code fragment were instead replaced with:
for(String title:map1.values()) System.out.print(title+", ");
what is output when the full code is run?
(a) there is an error - we cannot iterate over map1.values
(b) there is an error - there is no Map method values()
(c) Desert Island, Snow White, Pollyanna, The Gruffalo,
(d) Snow White, Pollyanna, The Gruffalo, Desert Island,
(vii) 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) { ... }
(viii) Which of the following methods is not in the Collection interface?
(a) clear()
(b) isEmpty()
(c) size()
(d) getSize()
(ix) 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
(x) 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]