CIS 256 Data structure. 1. Three programs P1, P2, and P3 have time complexities
ID: 3821337 • Letter: C
Question
CIS 256 Data structure.
1. Three programs P1, P2, and P3 have time complexities f1(n), f2(n), and f3(n), respectively,
such that
• f1(n) is O(f2(n)),
• f2(n) is O(f1(n)),
• f1(n) is O(f3(n)), and
• f3(n) is not O(f1(n)).
Which of the following statements is true?
(A) Program P1 is faster than P2 and P3 for very large size inputs.
(B) Program P2 is faster than P1 and P3 for very large size inputs.
(C) Program P3 is faster than P1 and P2 for very large inputs.
(D) Program P3 is slower than P1 and P2 for very large inputs.
(E) Program P1 must have the exact same running time as P2.
2. Consider the following pairs of functions: f(n), g(n). For which pair, the functions are such that f(n) is O(g(n)) and g(n) is not O(f(n))?
(A) f(n) = n 2 , g(n) = 2n 2 + 7
(B) f(n) = log n, g(n) = log(n 2 )
(C) f(n) = 17, g(n) = n + 1
(D) f(n) = n, g(n) = 3000n + 1
(E) f(n) = log n, g(n) = 1/n
3. Consider a hash table of size M that initially stores n keys. Assume that the hash function
maps keys uniformly across the entire table and that separate chaining is used to resolve
collisions. What is the worst case time complexity of the find(k) algorithm invoked on this
hash table when its parameter is a key k that is not in the table? Assume that n is much
bigger than M.
(A) O(1) time
(B) O(n) time
(C) O(M) time
(D) O(n/M) time
(E) O(log n) time
4. Consider the following algorithms, where A is an array storing n positive integer values.
Algorithm foo(A, n)
Input: Array A of size n
for k 0 to n 1 do {
if A[k] > 0 then foofoo(A, n)
else A[k] A[k] 1
}
Algorithm foofoo(A, n)
Input: Array A of size n
i 0
while i < n do {
for j 0 to n 1 do {
A[j] A[j] + 1
i i + 1
}
}
What is the worst case time complexity of algorithm foo?
(A) O(n)
(B) O(nk)
(C) O(n^2)
(D) O(n^2i)
(E) O(n^3)
5. Let T be a proper binary tree with root r. Consider the following algorithm.
Algorithm traverse(r)
Input: Root r of a proper binary tree.
if r is a leaf then return 0
else {
t traverse(left child of r)
s traverse(right child of r)
return s + t + 1
}
What does the algorithm do?
(A) It computes the height of the tree.
(B) It computes the number of nodes in the tree.
(C) It computes the number of nodes in the tree plus 1.
(D) It computes the number of leaves in the tree.
(E) It computes the number of internal nodes in the tree.
7. A set of n keys: {k1, . . . , kn} is to be stored in an initially empty binary search tree. Which
of the following statements is always true?
(A) The resulting binary search tree has the same height, regardless of the order in which the
keys are inserted in the tree.
(B) If ki
is the largest key, then in every binary search tree storing the above set of keys, the
right child of the node storing ki
is a leaf.
(C) A preorder traversal of the tree visits the keys in increasing order of value.
(D) After inserting the keys, the key stored at the root of the tree is the same regardless of
the order in which the keys are inserted.
(E) None of the above statements is always true.
8. Let T be a proper binary tree with 7 nodes: a, b, c, d, e, f, g.
A preorder traversal of T visits the nodes in this order: b, g, d, a, c, f, e.
An inorder traversal of T visits the nodes in this order: d, g, c, a, f, b, e.
Which node is at distance 3 from the root of T? (Hint. In tree T, node a is the right child
of node g.)
(A) a
(B) c
(C) d
(E) e
(F) g
Explanation / Answer
1) (d) Program P3 is slower than P1 and P2 for very large inputs.
2) I am not sure : It can be (E) f(n) = log n, g(n) = 1/n , all others can be made O(g(n)) and g(n) is O(f(n))
3) (B) O(n) time : Because it may happen that all the keys are mapped to Same Row and Chained across
4)(E) O(n^3) [because foo runs for n times and for n times foofoo runs n^2 times , So n^3]
5) (E) It computes the number of internal nodes in the tree. [For Leaf it returns 0 and for other nodes its 1 , So Number of internal nodes is the answer]
7) (B) If ki
is the largest key, then in every binary search tree storing the above set of keys, the
right child of the node storing ki
is a leaf. [because that largest element will be at the bottom right and it will always be a leaf]
8) (B) c is definitely at distance 3 from root because b is root, its left is g and g's right is a [given in hint ]
Now if we see Inorder it says c is left of a and it will be at distance 3