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