26 Apr 2012

School

Department

Course

Professor

Questions from the Computer Science 027b Final Exam April 2007

With Solutions

•This is not the entire 3-hour exam, since there were topics on the exam that are not

relevant this term.

•The marks for each individual question are given. Allow approximately 1 minute per

mark on average.

Note that the StackADT, QueueADT, Iterator, ListADT, UnorderedListADT, OrderedListADT,

BinaryTreeADT and BinarySearchTreeADT interfaces were provided at the back of the exam paper, as well

as the code for LinearNode.java and BinaryTreeNode.java.

1. (9 marks) For each of the following, give the time complexity using Big-O

notation. Assume an input of size n in each case.

a) for ( int i = n; i > 0 ; i-- ) Answer: _____O(n^2)

{ for ( int j = 1; j < n; j ++ )

System.out.println(j, i);

for ( int k = n; k > 1; k = k - 2)

System.out.println(k, i);

}

b) for (int k = 1; k < n; k++) Answer: ______O(n log n)

{ j = n;

while (j >0)

{ System.out.println(j);

j = j / 2;

}

}

c) for (int i = 1; i <= 5; i++) Answer: _______O(n)

for ( int j = 1; j <= n; j ++)

for (int k = 1; k <= 3; k++)

System.out.println(i, j*i, j*k);

1

2. (7 marks) For each of the following algorithms or methods from the collection

classes used in this course, suppose that the container in question contains n

elements. Using Big-O notation, give the worst-case time complexity for each.

a) The method push(T element) from class ArrayStack

_____O(n)

b) The method dequeue() from class CircularArrayQueue

_____ O(1)

c) The method find(T targetElement) from class LinkedBinaryTree

_____ O(n)

d) The algorithm to search for a specific element in a binary search tree

_____ O(n)

e) The algorithm to search for a specific element in a binary search tree, if the

binary search tree is known to be balanced

______ O(log n )

f) The Selection Sort algorithm from the course notes that is implemented

using Queues, to sort a queue of n data items

_____ O(n^2)

g) The Insertion Sort algorithm from the course notes that is implemented

using Stacks, to sort a queue of n data items

______ O(n^2)

2

3. (8 marks)

a) Draw the binary search tree that results when the following integer values are

inserted into an initially empty tree in the order shown:

55 30 65 14 45 57 38 26 60

55

30 65

14 45 57

26 38 60

b) If the integer values were inserted in a different order, would the resulting binary

search tree always be the same as the one of part a) ?

Answer: Yes / No

Give a brief reason for your answer:

____first value is always at root, so different tree if different first value

(or, last insertions are always the leaves, so …)

3