Spring 2009 CSE310 Midterm Examination II (in class)Instructions:• There are five questions in this paper. Please use the space provided (below thequestions) to write the answers.• Budget your time to answer various questions and avoid spending too much time on aparticular question.• This is a closed book examination. You may not consult your books/notes.NAMEASUIDQuestion ScoreQ1Q2Q3Q4Q5Total0P1. (20 points: 10+10)(10 pts) Describe chaining in hashing.(10 pts) Describe linear probing in hashing.1P2. (20 points: 5+5+5+5)The following four questions deal with binary search trees.0510152025303540ABCDE F GH IFigure 1: A binary search tree.(5 pts) For each of the following sequences, write YES if there exists a binary search tree Tand an integer k such that the search for k will visit exactly the given sequence ofnumbers; write NO otherwise. Please note that this problem has nothing to dowith the tree in Figure 1.(A) 90, 80, 70, 120(B) 80, 90, 50, 85(C) 360, 100, 300, 200(D) 100, 200, 400, 150(E) 100, 200, 150, 550(5 pts) Show the sequence obtained by post-order tree walk of the tree in Figure 1.(5 pts) Show the resulting binary search tree obtained by inserting the number 4 into thebinary search tree in Figure 1.(5 pts) Show the resulting binary search tree obtained by deleting the number 20 from thebinary search tree in Figure 1.2P3. (20 points: 5+5+5+5)The following four questions deal with red-black trees.05101520253035404550556065288Figure 2: A red-black tree, where a thick circle represents a black node and a thin circlerepresents a red node. Only the data-bearing nodes are shown.(5 pts) List the five properties of a red-black tree, in the correct order.(5 pts) Ignore the colors, draw the tree obtained by performing a right-rotation at node withvalue 50 in the tree of Figure 2, i.e., the rotation involving the edge connecting 50 and60.3(5 pts) Draw the red-black tree obtained after inserting 56 into the red-black tree in Figure 2.(5 pts) Draw the red-black tree obtained after deleting 45 from the red-black tree in Figure 2.4P4. (20 points: 10+5+5)This problem is related to disjoint set operations. Assume that we are using union by rankand find with path compression. Suppose that you are given a disjoint set structure describedby the following array representation.i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| 16|A |-3 | 1 | 1 | 3 | 7 | 7 | 1 | 6 |-3 | 9 | 9 | 11| 9 | 13| 13| 15|1. Draw the tree structure of the given disjoint sets.2. Write the array representation of the disjoint set structure after applying union(16, 8)to the given disjoint set structure.3. Write the array representation of the disjoint set structure after applying union(3, 10)to the given disjoint set structure.5P5. (20 points: 10+5+5)We are given the following two sequences.X=<1, 3, 2, 4, 3>Y=<1, 2, 3, 4>Use the dynamic programming algorithm in the textbook to compute an LCS of X and Y .You need to show both the c matrix and the b matrix computed, as well as the LCS obtained.1. Compute all entries of the c matrix and the b matrix. When drawing the table, placeX on the left and Y on top.2. Write the LCS computed by the algorithm.3. What is the worst case time complexity of the dynamic programming algorithm forcomputing the LCS of a sequence of length n and a sequence of length
View Full Document
Unlocking...