Data Structures and Algorithms Practice Exam

1 Data Structures and Algorithms Practice ExamIntroductionThe Data Structures and Algorithms portion of the Masters Comprehensive Exam (MCE) representsapproximately 1/3 of the exam. The DS&A portion emphasizes basic knowledge and reasoning overin-depth problem analysis, since it has over 30 questions, and the entire comprehensive exam lastsfor three the examSince the MCE lasts for three hours, this leaves about one hour to complete the DS&A portion,which in turn leaves about two minutes to answer each problem. There is NO penalty for guessing,so make sure to answer each one.

2 It is therefore recommended to take this Practice test in a hoursitting, and without referring to the answers until the exam has been of the examExam grades are determined by the CECS Graduate Committee. Please see the CECS GraduateAdvisor for more Which of the following expressions surely supports the statementf(n) = (g(n))?a)f(n) 4g(n) for alln 1b)f(n) 4g(n) for alln 136c) limn f(n)g(n)= 01d) none of the above2. Letkdenote the degree of polynomialp(n), andlthe degree of polynomialq(n). Ifp(n) =o(q(n)), then necessarilya)k= )k < )k > ) none of the above3.

3 Iff(n) = O(g(n)) andf(n) = (g(n)), then it is always true thata)f(n) = o(g(n)).b)f(n) = (g(n)).c)f(n) = (g(n)).d) both a) and b) are always Which of the following expressions best describes the growth of the sum 1+1/2+1/3+ +1/n?a) (1/n)b) (1)c) (logn)d) (nlogn)5. Given positive functionsf(n) andg(n), if we know that limn (logf(n) logg(n)) = 1, then wealso know thata)f(n) = o(g(n)).b)f(n) = (g(n)).c)f(n) = (g(n)).d) more information is needed aboutfandgto reach a definite An algorithm takes as input ann nBoolean matrixA. If the running time of the algorithmisT(n) = O(nlogn) whennis used as the input size parameter, then which of the followingexpressions describes the big-O growth ofT(m), the running time of the algorithm whenm=n2is used as the size parameter?

4 A) O( mlogm)b) O(m2logm)c) O(mlogm)d) O(m2log2m)7. Which of the following isnota desirable property of a hash functionh(x)?a) It should be computable in O(1) ) The range ofh(x) should stay within the desired hash-table ) The range ofh(x) should include a wide range of ) Ifx1,..,xnare the items to be hashed, then the numbersh(x1),..,h(xn) should beuniformly distributed over the If a separate-chaining hash table has load factor = 5, then the average length of a chainequalsa) ) log ) 5 log ) log(log 5).9. Perfect hashinga) may be applied to static hash ) means there are no collisions when retrieving data from the hash ) represents one of the most efficient ways of retrieving ) all of the above10.

5 The worst case running timeT(n) for insertingnelements into an initially-empty heap isa)T(n) = O(n2).b)T(n) = O( nlogn).c)T(n) = O(n).d)T(n) = O(nlogn).11. The worst case running timeT(n) for popping an element from a binary heap of sizenisa)T(n) = O(1).b)T(n) = O(logn).c)T(n) = O(n).d)T(n) = O(nlogn).12. Which of the following Algorithms doesnotrequire a heap for its efficient implementation?a) Huffman s algorithmb) Dijkstra s algorithmc) Kruskal s algorithmd) Prim s algorithm13. Which of the following graph problems cannot be solved in time that is linear with respect tothe sum of the number of vertices and edges in the graph ( O(m+n)).

6 A) determining if a simple graph is connectedb) determining if a simple graph is bipartitec) determining a minimum spanning tree for a connected weighted graphd) determining a topological sort of the vertices for a directed acyclic graph14. Suppose directed graphGis weakly but not strongly connected, and pathP=a,b,c,dprovidesa weak (but not strong) connection fromatodwithinG. Then we surely know thata) either (a,b), or (b,c), or (c,d) is an edge ) (a,b), and (b,c), and (c,d) are edges ) either (b,a), or (c,b), or (d,c) is an edge ) (b,a), and (c,b), and (d,c) are edges LetG= (V,E) be the undirected graph whose edges are{(a,b),(b,c),(c,d),(a,d)}.

7 IfTis thedepth-first spanning tree ofGrooted at vertexa, it follows thatThasbranch(es).a) 1b) 2c) 3d) 416. The worst case running timeT(n) for insertingnelements into an initially-empty binary searchtree isa)T(n) = O(n2).b)T(n) = O( nlogn).c)T(n) = O(n).d)T(n) = O(nlogn).17. Binary search treeTis said to be balanced when, for every nodeninT,a)n s left and right subtrees have equal )n s left and right subtrees have equal )n s left and right subtrees have heights that differ by at most )n s left and right subtrees have sizes that differ by at most If numbers from the set{1.}

8 ,n}are selected at random (without replacement) and insertedinto an initially-empty binary search tree, then the big-O expression that best describes theaverage (taken over all possible resulting trees) height of the resulting tree isa) O(n).b) O(logn).c) O( n).d) O(n).19. Which of the following sorting tasks wouldnotbe appropriate for Counting Sort?a) sorting millions of products by their 15-digit serial numbersb) sorting millions of employees by their agesc) sorting each day of the calendar year by the high temperature (in Celsius rounded to thenearest integer degree) recorded in the city of Long Beach on that given dayd) sorting each vehicle registered in the state of California by the year it was manufactured20.

9 Which of the following best describes the worset-case running time of Insertion Sort whensortingn32-bit unsigned integers?a)T(n) = ( n)b)T(n) = (n)c)T(n) = (nlogn)d)T(n) = (n2)21. Quicksort is guaranteed to run in time O(nlogn) so long as the pivot isa) randomly ) set to the median of the first, middle, and last array ) set to the median of the ) none of the above22. When following Kruskal s algorithm, the greedy choice is toa) remove the edge of greatest cost from the graph so long as its removal does not disconnectthe ) add the edge of least cost to the forest so long as its addition does not create a ) add the vertex having least connection cost to the current ) remove the vertex having greatest connection cost from the When following Huffman s algorithm, the greedy choice is toa) select the two probabilities of least value for ) select the two probabilities of greatest value for )

10 Add the codeword of shortest length to the code being ) remove the codeword of greatest length from the code being Which of the following greedy Algorithms has an implementation that most resembles that ofDijkstra s algorithm?a) Kruskal s algorithmb) Prim s algorithmc) Huffman s algoirthmd) Floyd-Warshall algorithm25. IfT(n) satisfiesT(n) = 2T(n/3) + n, thena)T(n) = ( n).b)T(n) = (n2).c)T(n) = (nlog32).d)T(n) = (nlog 3).26. Which of the following recurrencescannotbe solved directly by the Master Theorem?a)T(n) = 16T(n/4) +nb)T(n) =T(n/5) + 20c)T(n) = 3T(n/4) +nlognd)T(n) = 2T(n/2) +nlogn27.