CS1027FinalApril07Master.doc

150 views12 pages
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
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 12 pages and 3 million more documents.

Already have an account? Log in
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
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 12 pages and 3 million more documents.

Already have an account? Log in
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
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 12 pages and 3 million more documents.

Already have an account? Log in

Get OneClass Grade+

Unlimited access to all notes and study guides.

Grade+All Inclusive
$10 USD/m
You will be charged $120 USD upfront and auto renewed at the end of each cycle. You may cancel anytime under Payment Settings. For more information, see our Terms and Privacy.
Payments are encrypted using 256-bit SSL. Powered by Stripe.