Algorithms and Data Structures (M)

Exam Code

Question 1

Parts (i) - (v) refer to the Java interface for an abstract data type NewStack, the implementing class, LinkedNewStack, and a testing class containing a main method, TestNewStack shown in Boxes 1, 2 and 3.

(i)        The code defining the Node class within the LinkedNewStack class is referred to as a

(a) defining class

(b) subclass

(c) inner class

(d) linked class

(ii)       Even though the toString method of the interface is not implemented within the LinkedNewStack class, there is no corresponding Java compile-time error reporting an unimplemented method. Why?

(a) The toString method isnot called in the main method in the TestNewStack class, so it doesn’t matter

(b) The toString method is a public method in the Object class, so it will just not be overridden

(c) There would not be an error message if any of the NewStack methods were not implemented in LinkedNewStack

(d) There will be an error reported at runtime rather than at compile time

(iii)      Suppose that we had a correct (according to the descriptive comment in  the interface) implementation of the toString() method in the LinkedNewStack class, which of the following strings correctly shows the contents ofthe stack after the main method has executed?

(a) 4, 2, 0

(b) 8, 6, 4

(c) 6, 4, 2, 0

(d) 0, 2, 4

(iv)      If these two lines of code were added to the bottom of the main method, what would happen?

int stackSize = stack1.size ();

System.out.println("The stack has size " + stackSize);

(a)  The following would be output: "The stack has size 3"

(b)  The following would be output: "The stack has size 4"

(c) The following would be output: "The stack has size "

(d) There would be an error, as the method  size() is undefined for the type NewStack

(v)       Suppose that I have an alternative implementing class, ArrayNewStack, that implements all the methods of NewStack, but uses an array to store the elements of  the stack. To what should I change the instantiation of stack1 in TestNewStack to use a NewStack of that type? (Note that the line breaks in (c) and (d) are not relevant, the code would not fit on one line in these cases).

(a)  ArrayNewStack stack1 = new NewStack()

(b)  NewStack stack1 = new ArrayNewStack()

(c)  ArrayNewStack stack1 =

new NewLinkedStack()

(d)NewStack stack1 =

new NewStack> ();

(vi)      Which of the following correctly describes an Abstract Data Type (ADT)?

(a) a type characterised by its possible values, operations and data representation

(b) a type characterised by its data representation and operations only

(c) a type characterised by its possible values and operations only

(d) a type characterised by its possible values and data representation only

(vii)     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 S3 are true

(d) only S1, S3 and S4 are true

(viii)     What is printed when  the following code is executed?

ArrayList list = new ArrayList<>();

list.add(3);

list.add(2);

list.add(1);

list.add(0);

list.remove(3);

System.out.println(list);

(a) [2,1,0]

(b) [3,2,1]

(c) [2,1,0]

(d) [3,2,1,0]

(ix)      Consider the following algorithm:

Let L be an empty list

For i = 1, … , n, repeat:

For j = 1,… , n, repeat:

For k=1,… , 3, repeat:

For m=1,… , 11, repeat:

Multiply i,j,k and m and add to L

What is the complexity of this algorithm? You may assume that adding to the list is a constant time operation.

(a) O(n2)

(b) O(n3)

(c) O(n4)

(d) O(1)

(x)        Consider the following algorithm to sort an array of integers b

Let len be the length of b

For i = len-1, … , 1, repeat:

For j = i-1, … , 0, repeat:

if b[j] is more than b[i] swap b[i] and b[j]

What is the complexity of this algorithm?

(a)  O(n2)

(b)  O(n3)

(c)  O(n4)

(d)  O(1)

Question 2

Parts (i) - (iv) refer to the following trees, labelled (A) to (D):

(i)        Which tree is the result of adding the elements 0,1,2,3,4,5,6 in the given order to an empty binary search tree (i.e. without balancing)?

(a) A

(b) B

(c) C

(d) D

(ii)       Which tree is the result of adding the elements 0,1,2,3,4,5,6 in the given order to an empty AVL (i.e. with balancing)?

(a) A

(b) B

(c) C

(d) D

(iii)   Balancing the  tree in question (ii) required the use of which of the following rotations? Note that SR(x) and SL(x) denote a single right/left rotation about the node containing the value x, and DLR(x) and DRL(x) denote a double left- right/double right-left rotation about the node containing the value x.

(a)   SR(0) and SR(2), SR(1), SR(4)

(b)  SL(0), SL(2), SL(1), SL(4)

(c) SL(0), SL(2), DLR(1)

(d) SR(0), SL(2), DLR(4)

(iv)      Which of the sequences below denotes a postorder traversal oftree (C)?

(a) 0, 1, 2, 3, 4, 5, 6

(b) 3, 1, 0, 2, 4, 5, 6

(c) 0, 2, 1, 6, 5, 4, 3

(d) 6, 5, 4, 3, 2, 1, 0

(v)       Which of the sequences below denotes a preorder traversal oftree (C)?

(a) 0, 1, 2, 3, 4, 5, 6

(b) 3, 1, 0, 2, 4, 5, 6

(c) 0, 2, 1, 6, 5, 4, 3

(d) 6, 5, 4, 3, 2, 1, 0

Parts (vi) - (viii) refer to the partition algorithm, shown in Box 4.

(vi)      If array a is  {2,3,7,10,8,4,1,5,12,0} and the partition algorithm shown in Box 4 is applied to a, with left=0 and right=9, and m is (the integer part of ) (right-left)/2, what is the final state of a?

(a)  {2,3,4,1,0,5,7,8,12,10}

(b) {0,1,2,3,4,5,7,8,10,12}

(c)  {2,3,7,4,1,5,0,8,12,10}

(d) {8,10,12,4,0,1,2,3,5,7}

(vii)  For an array of length n, what is the maximum number of times that step 3.2.1 is executed?

(a) n

(b) n-1

(c) log n

(d) 1

(viii)    If the partition algorithm is used in the partitioning step of the quicksort algorithm, to sort an array of length n, what is the worst-case complexity of quicksort?

(a) O(n log n)

(b) O(n2)

(c) O(n2 log n)

(d) O(1)

(ix)      The recursive Quicksort algorithm is to be used to sort an array of length 15.

How many times is Quicksort called (including the original call, and the call to all subarrays, including the arrays of size 1 and 0)? You may assume that the partitioning algorithm used at each stage successfully divides the subarray (excluding the pivot) into parts whose sizes differ by at most 1.

(a) 8

(b) 15

(c) 15 x 15

(d) 15 x 3 (i.e. 15 x (log 15))

(x)       What are the best-case and worst-case complexities of the MergeSort  algorithm respectively?

(a) O(n log n), O(n log n)

(b) O(n log n), O(n2)

(c) O(n), O(n log n)

(d) O(n2),  O(n2)

Question 3

(i)         A programmer uses a closed-bucket hash table to store the set of book titles available in a small children’s library. Each book is uniquely identified by a code called an ibcode which consists of the first two letters of the author’s surname (in lower case), the first two letters of the book title (in lower case), and four digits denoting the year of publication. E.g., the ibcode for the book titled “Crossfire” by Malorie Blackman, published in 2019 is blcr2019.

The programmer uses a hashtable of size 89, and the hash function determined using the algorithm given in Box 5. What is the hashcode for the book above (with ibcode blcr2019)?

(a) 31

(b) 34

(c) 9

(d) 44

(ii)       For the hashtable example described in (i), what is the hashcode for the book titled “Gruffalo” by Julia Donaldson, published in 1999?

(a) 116

(b) 16

(c) 27

(d) 12

(iii)   For the hash table described  in part  3(i), assuming that all feasible ibcodes are possible, what is the maximum value that the load factor can be?

(a) 89/(262 x 102)

(b) 89/(264 x 104)

(c) (262 x 102)/89

(d) (264 x 104)/89

Parts (iv) – (v) refer to maps map1 and map2, the data for which is shown in Box 6.

(iv)      Suppose that map1 and map2 are maps used to store details of the names of

players of an online game and their usernames.  In each map the keys denote the player names, and the values the usernames.

Suppose that some Java code involves the instantiation of both maps as empty treemaps with initial size 20 and their population with the data shown in Box 6, followed by the following code fragment:.

map1.putAll(map2);

map1.remove("Jessica");

System.out.println("Map 1 is now: " + map1);

What is output when the code is run?

(a) {Zihan=twoShoes, Ann=m_Inc, Navid=prospo}

(b) {Ann=m_Inc, Jessica=notMyBag, Navid=prospo, Zihan=twoShoes}

(c)  {Ann=m_Inc, Navid=prospo, Zihan=twoShoes}

(d)   {Ann=m_Inc, Navid=tigerLily, Zihan=twoShoes}

(v)      What would the output be guaranteed to be ifa hashmap of size 20 were used to implement each of map1 and map2, and the code fragment of part 3(iv) executed?

(a) {Navid=prospo, Zihan=twoShoes, Ann=m_Inc}

(b) {Ann=m_Inc, Jessica=notMyBag, Navid=prospo, Zihan=twoShoes}

(c)  {Ann=m_Inc, Navid=prospo, Zihan=twoShoes}

(d)  None of the above. It is impossible to predict the order in which elements are stored in a hashmap .

(vi)      Suppose that we have a map with n entries whose keys are integers between 0 and m-1 and whose values are strings (where n ≤ m). We could store the map in the following ways: (a) as a key-indexed array of size m, (b) as a binary search tree,  (c)  as an ordered singly linked list. Which of these representations would allow the fastest implementation of the put operation?  You may assume that the binary search tree is well balanced.

(a) The key-indexed array

(b) The singly linked list

(c) The binary search tree

(d) They will be the same - they all have O(n) complexity as we potentially must search the whole map to insert a new entry.

(vii)       Which of the representations in part (vi) would allow the fastest

implementation of the remove operation (which removes the element with a given key - if it exists)?

(a) The key-indexed array

(b) The singly linked list

(c) The binary search tree

(d) They will be the same – they all have O(n) complexity as we potentially must search the whole map to remove a new entry.

Parts (viii – x) refer to the list of linked list instructions in Box 7.

(viii)  Let SLL denote a singly linked list of nodes, each of which contain an element

and a link to the next node in the list and suppose that SLL’s header consists ofa  link to its first node,first.  Assuming that the list is not empty, which sequence of instructions from Box 7 should be carried out to insert a new node containing element e into SLL after an existing node pred?

(a) G, J, D

(b) G, D, J

(c) G, D, E

(d) D, J, B

(ix)      If instead we want to add  a new node containing element e into an empty singly linked list, what sequence of instructions must we carry out?

(a) E, G

(b) G, E

(c) G, L

(d) G, B

(x)       Let DLL denote a doubly linked list of nodes, each of which contain an element and links to the next and previous nodes in the list and suppose that DLL’s header consists of links to its first and last nodes,first and last.  Assuming that the list is not empty, which sequence of instructions from Box 7 should be carried out to insert a new node containing element e into DLL after last?

(a) A, H, F, K

(b) A, K, H, F

(c) A, C, H, F

(d) A, D, F, H