Algorithms and Data Structurs M
COMPSCI5004
April-May diet 2021
(Multiple Choice)
This exam is multiple-choice and contains 25 questions ((i)-(xxv)). You should select exactly one answer (a, b, c, d) for each question (if multiple answers are given the question will be marked as wrong). Each correct answer is worth 2 marks. This paper will be implemented as a Moodle quiz.
This examination paper is worth a total of 50 marks
(i) Suppose that I have a Java class ArrayStack that implements a Java interface Stack, whose operations include the usual push, pop and isEmpty operations. Consider the following Java class:
// import statements omitted
public class StackExample {
public static void main(String[] args) {
Stack myStack = new ArrayStack(10);
String[] nameArray = { "Albert", "Eddie", "Anna",
"David", "Fiona", "Greta" };
String[] newArray = new String[7];
for (String s : nameArray) myStack.push(s);
int i = 0;
while (!myStack.isEmpty()) {
newArray[i] = myStack.pop();
i++;
}
}
}
What are the final contents of array newArray?
(a) [“Albert”, “Eddie”, “Anna”, “David”, “Fiona”, “Greta”]
(b) [“Albert”, “Anna”, “David”, “Eddie”, “Fiona”, “Greta”]
(c) [“Greta”, “Fiona”, “David”, “Anna”, “Eddie”, “Albert”]
(d) [“Greta”, “Fiona”, “Eddie”, “David”, “Anna”, “Albert”]
(ii) Consider the recursive factorial algorithm below, for positive integer n:
Factorial(n): yields the factorial of n
If n=1 yield 1
Else, yield n*Factorial (n-1)
What is the time complexity of this algorithm?
(a) O(n)
(b) O(2n)
(c) O(n2)
(d) O(log n)
(iii) Consider the following Java class:
public class ListExample {
public static void pListSet(List l,
Set 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 myList = new ArrayList(7); Set mySet = new TreeSet();
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);
}
pListSet (myList,mySet);
}
}
What is the output?
(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) Let T(n) denote the number of comparisons required to sort an array of size 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
(v) 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)
(vi) 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)?
(vii) Which of the following (unbalanced) Binary Search Trees would result from deleting the value 7 from the search tree depicted as (d) in part (vi)?
(viii) 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)?
(ix) Which of the following statements is true for the preorder traversal of a binary search tree?
(a) It always returns the values of the tree in increasing order
(b) It always returns the values of the tree in decreasing order
(c) Inputting the values from the traversal in the order they are returned allows us to reproduce the binary search tree
(d) It allows us to successively delete the tree from the leaves up in an efficient way.
(x) Suppose that instead of dividing in half at each stage of mergesort, you divide into four sets, sort each fourth and finally combine all of them using a four-way merge subroutine. What is the time complexity of this algorithm?
(a) O(n2)
(b) O(n)
(c) O(n4 log n)
(d) O(n log n)
(xi) The following algorithm changes 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.
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"]
(xii) What is the time complexity of the algorithm of part (xi), 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)
(xiii) 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”
(xiv) If binary search is instead used to search the array from part (xiii) 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”
(xv) Which of the following correctly describe an Abstract Data Type (ADT)?
(a) a type characterised by its values, operations and data representation
(b) a type characterised by its data representation and operations only
(c) a type characterised by its values and data representation only
(d) a type characterised by its values and operations only
(xvi) The QuickSort algorithm for sorting an array involves a sub-algorithm known as Partition which acts on an array a [left…right]. The algorithm is shown below:
|
1. Let pivot be the element in a [left],and set p = left
2. For r = left+1, … , right, repeat:
2.1. If a [r] is less than pivot:
2.1.1. Copy a [r] into a [p], a [p+1] into a [r], and pivot into a [p+1].
2.1.2. Increment p.
3. Terminate yielding p
|
If array a is:
What is the result of applying the Partition algorithm to a?
(xvii) 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()
(xviii) 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
(xix) 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? You may assume that del is not the first or last node.
(a) A,C
(b) B,D
(c) A,D
(d) C,B
(xx) 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
(xxi) Consider the following Java method to determine whether two sets s1 and s2 are equal (i.e. they contain the same elements) or not:
|
public static boolean equals(Set set1, Set set2){ if(set1.size()!=set2.size()) return false;
Iterator i1 = set1.iterator();
Iterator i2 = set2.iterator();
while(i1.hasNext() && i2.hasNext())
if(!i1.next().equals(i2.next())) return false;
return true; }
|
If A is the average time complexity of the algorithm implemented by this method when applied to sets s1 and s2 of equal size n, instantiated as follows:
Set s1 = new TreeSet();
Set s2 = new TreeSet();
and B the time complexity of the algorithm implemented by this method when applied to s1 and s2 of equal size n, instantiated as follows:
Set s1 = new HashSet();
Set s2 = new HashSet();
Which of the following is true?
(a) A = O(log n) and B = O(n)
(b) A = O(n) and B=O(n)
(c) A = O(log n) and O(n2)
(d) A = O((log n)2
) and B=O(n2
)
(xxii) 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 of k1 and k3 the left child of k2, 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
(xxiii) 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? You can assume that comparisons only take place within a bucket.
(a) 2
(b) 1
(c) 0
(d) 4
(xxiv) Let map1 and map2 be Maps used to store details of library books. In each Map the keys denote the book code, and the values the book title.
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}
(xxv) If the Java code fragment in question (vi) 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 an 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}