CS61B (Yelick)
Spring 2003
Your name:
Person to your left: Person to your right:
Your cs61b login:
Lab time:
Lab TA¡¯s name:
Do not open this booklet until you are told to begin!
Exam 3 April 21, 2003
Do not open this booklet until you are told to begin!
There are 20 points on this exam. Read each problem carefully, and avoid spending too much time on any one question.
Problem 0 (1 point, 2 minutes): Identification
Fill out your name, your neighbors¡¯ names, and other information in this grid. You may do this before you are told to begin.
Grading: Do not write below this line. The following grid will be used for grading.
Problem 0 1 2 3 4 5 6 7 8 Total Possible 1 2 2 3 1.5 3 1.5 3 3 20 Score
Version 1
Name: ____________________ Login: __________
Problem 1: (2 points, 4 minutes) Heaps
Suppose that there are N distinct values in a binary max heap (the maximum is at the top). In an
th array representation, which positions could be occupied by the 4
apply. Assume the heap index starts at 0.
1) 0
2) 1or2
3) 3,4,5, or 6
4) 7 through 14
5) 15 or higher
Answer: __________
Problem 2: (2 points, 4 minutes) BSTs
largest element? List all that
Consider the BST created by inserting the following characters in the given order into an initially empty BST, where the ordering operation is alphabetical: A E F G B D C
For which of the following insert orders will the same BST be created? List all that produce the same BST.
1) CABEGDF 2) AFEGDBC 3) AEBGCDF 4) AEGCFDB 5) EAGBDFC
Answer: __________
Problem 3: (3 points, 8 minutes) 2-3-4 Trees
Part A. Given a 2-3-4 tree (called a (2,4) tree in the book) in which all external/sentinel nodes are at depth 3, what is smallest number of keys the tree may have? (Not counting external nodes, this tree has height 2.)
Answer: __________
Part B. Assume your tree from Part A contains even keys 2-2*N, where N is your answer to Part A. What sequence of 2-3-4 operations, as they are defined in the book and lecture notes, will produce your tree from part A? Your answer should have as few operations as possible.
Answer:
Name: ____________________ Login: __________
Problem 4: (1.5 points, 2 minutes) Asymptotic Complexity Analysis
Consider the time to insert an element into an arbitrary BST of n elements. Give the simplest, tightest, most accurate expression for each of the following, or state that no such expression exists.
Part A) A big-O expression Answer: __________
Part B) A big- expression Answer: __________
Part C) A big- expression Answer: __________
Problem 5: (3 points, 7 minutes) Graph operations
Consider the directed graph that contains 5 vertices, labeled 0-4, and 14 directed edges, the following 7 edges and the reverse of each: 0-1 0-2 0-3 1-2 1-3 2-3 3-4
Part A. How many edges does a DFS explore in the worst case to find a path from 0 to 4? The graph is represented using an adjacency list representation, but the edges are inserted and stored in an arbitrary order rather than the order given above. The edges incident to a vertex are traversed in the order they are stored. Be sure to count edges, and not vertices. List the exploration order of the edges in addition to the count.
Count: __________
Exploration Order: _______________________________________________________
Part B. Answer the same question for a BFS. Assume each vertex is inserted into the queue at most once.
Count: __________
Exploration Order: _______________________________________________________
Problem 6: (1.5 points, 3 minutes) Transitive Closure
Consider the graph with 5 vertices, labeled 0-4, and 6 directed edges: 0-1 1-4 4-0 0-2 2-3 3-2. Give the transitive closure of this graph by filling in the following adjacency matrix for the result.
from
to
01234
01
11 21 31 41
Name: ____________________ Login: __________
Problem 7: (3 points, 10 minutes) Dijkstra¡¯s Algorithm
Run Dijkstra¡¯s Algorithm on the following graph to compute the shortest path from 0 to 7. At each step show the contents of the distance vector (D in the book and d in the lecture notes) after each vertex is visited. Give the resulting path by listing the edges.
23
144
17 2 3 2
0 5 2 20 5 7 7 2 11 7 13
8
376
visited D[0] D[1] D[2] D[3] D[4] D[5] D[6] D[7] vertex
Name: ____________________ Login: __________
Problem 8: (3 points, 10 minutes) Prim-Jarnik Algorithm
Run the Prim-Jarnik Algorithm on the following graph starting from the vertex 0. Show the vector of best-weights-so-far, which is called the D in the book and d in the lecture notes, after each vertex is visited. At each step indicate which vertex is being visited. Also show the final tree by listing the edges in the tree.
6
1 13 4
15 12 5 2
0 10 2 14 5 3 7 9 11 1 4
8
376
visited D[0] D[1] D[2] D[3] D[4] D[5] D[6] D[7] vertex