Spring 2009 CSE310 Midterm Examination II in class Instructions There are five questions in this paper Please use the space provided below the questions to write the answers Budget your time to answer various questions and avoid spending too much time on a particular question This is a closed book examination You may not consult your books notes NAME ASUID Question Score Q1 Q2 Q3 Q4 Q5 Total 0 P1 20 points 10 10 10 pts Describe chaining in hashing 10 pts Describe linear probing in hashing 1 P2 20 points 5 5 5 5 The following four questions deal with binary search trees A 15 B 5 D 0 30 C E 10 20 F H 25 G 40 35 I Figure 1 A binary search tree 5 pts For each of the following sequences write YES if there exists a binary search tree T and an integer k such that the search for k will visit exactly the given sequence of numbers write NO otherwise Please note that this problem has nothing to do with 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 the binary search tree in Figure 1 5 pts Show the resulting binary search tree obtained by deleting the number 20 from the binary search tree in Figure 1 2 P3 20 points 5 5 5 5 The following four questions deal with red black trees 30 15 50 5 0 25 10 20 40 28 35 60 45 55 65 8 Figure 2 A red black tree where a thick circle represents a black node and a thin circle represents 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 with value 50 in the tree of Figure 2 i e the rotation involving the edge connecting 50 and 60 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 4 P4 20 points 10 5 5 This problem is related to disjoint set operations Assume that we are using union by rank and find with path compression Suppose that you are given a disjoint set structure described by 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 5 P5 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 place X 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 for computing the LCS of a sequence of length n and a sequence of length m 6
View Full Document
Unlocking...