Fall 2003 CS61B Midterm (50/300 points)
;;;;
Meta
;;;;
GS = Grading Standard
We’ve tried to include the common errors and grading standard for
every question.
;;;;;;;;;;
QUESTION 1
;;;;;;;;;;
GS: The T/F questions were worth 1/2 point each. You got a -1/2 point
if you answered a T/F question incorrectly. The fill-in-the-blank
questions were worth 1 point each.
a) F
b) F
c) T
d) T
e) 4^h
f) 3
;;;;;;;;;;
QUESTION 2
;;;;;;;;;;
GS: 5 points total, but everyone received full credit for parts d) and e).
a) 1 point for drawing the correct heap after removing 20
31 /\ 32 35
/\ 38 45
b) 1/2 point
——————————-
| 20 | 31 | 35 | 38 | 32 | 45 |
——————————-
c) 1/2 point
1
——————————-
| 31 | 32 | 35 | 38 | 45 | |
——————————-
d) 1.5 points
This question was impossible to answer because binary heaps
must be complete. With the numbers provided, you could not
form a complete binary search tree, thus you couldn’t form a
max binary heap. Everyone received all the points for this question.
e) 1.5 points
This question was thrown out as well because of the same reason as
(d). It could be impossible to make both a balanced BST and a max
heap from a given set of data. Everyone received the max points for it.
;;;;;;;;;;
QUESTION 3
;;;;;;;;;;
GS: 4 points
Each part was worth 1/2 point.
a) >
b) >
c) =
d) =
e) =
f) <
g) =
h) =
;;;;;;;;;;
QUESTION 4
;;;;;;;;;;
GS: 2 points, 1 point for each part.
a) For any number n, all numbers n + 5*i where i is a positive integer >= 0
will be mapped to the same location as n.
For example: (5, 10, 15) or (7, 12, 17)
b) g(n) is better because f(n) can’t ever map to an even number. f(n) effectiv
reduces the possible buckets by half.
;;;;;;;;;;
QUESTION 5
;;;;;;;;;;
2
GS: Part a) was worth 2 points with each blank being worth 1/2 point. If you
forgot to put object()’s constructor call, you were only penalized 1/2 poin
one time.
Part b) was worth 4 points total. 1 point was taken off for each incorrect
blank up to 0 points total for the question.
a) i. Dog, Animal, Object
ii. Rabbit, Animal, Object
iii. Poodle, Dog, Animal, Object
iv. None
Common errors: Almost everyone forgot to put the Object constructor. There we
a handful of people that caught this though.
b) i. Animal
ii. Rabbit
iii. Dog
iv. Dog
v. Rabbit
vi. CT
Common errors: Most people didn’t know that vi. will cause a Compile-time exce
This happens because Animal doesn’t define a hop() method and thus you must cas
the variable b to a Rabbit before you can call that method on it.
i.e. ((Rabbit)b).hop();
;;;;;;;;;;
QUESTION 6
;;;;;;;;;;
GS: Part a) was worth 3 points. You either got the entire 3 points or nothing.
For part b), you were given the full 1 point if you wrote out the in-order
traversal for the tree you drew in part a).
Part c) was worth 1 point with no partial credit.
a) 88 /
6 /\
1 30 \/ 3 10
/\ \
2 5 20
/ 4
Common errors: A lot of people didn’t verify that their tree was in fact a BST
By looking at your tree, you should never have a larger number to the left of
3
a smaller number and vice-versa. An examples of what people put is:
30 /\
10 20 <- smaller than 30
b) 1, 2, 3, 4, 5, 6, 10, 20, 30, 88
The in-order traversal of a BST are the numbers from lowest to highest. But to
get full credit for this problem, you must put the in-order traversal of the
tree you drew in part a). So if you drew the wrong tree, you must put the
in-order traversal of that tree. If you drew the wrong tree, but gave the
in-order traversal for the correct tree, we only took off 1/2 point.
c) 10 /\
4 30 /\/\
2 6 20 88 /\ /
1 35
Common errors: A lot of people drew a minimal height tree, but didn't make
it *complete*.
;;;;;;;;;;
QUESTION 7
;;;;;;;;;;
GS: 8 points. The grading for this is similar to question 3 on the Quiz.
public Object dequeue() throws EmptyQueueException {
if( empty() ) throw new EmptyQueueException();
Object o = pop();
if( empty() ) return o;
Object front = this.dequeue();
enqueue( o );
return front;
}
* -1/2 pt for the first instance of a small compile-time error
Examples:
- Omitting parenthesis in function calls (eg dequeue vs
dequeue()... only deducted for the first time).
- Misspelled methods
4
* -1 for first instance of severe compile-time errors
Examples:
- Forgetting to return a value (if you declared the function non-void)
- Not declaraing variables (such as the Objects o and front)
- Calling dequeue recursively and passing it 'this' or something else despite
the fact that it takes no parameters
* -1 for all instances of run-time errors/statements that generate
the wrong output.
;;;;;;;;;;
QUESTION 8
;;;;;;;;;;
GS: 16 points total
The answers for part a) and b) below are broken up into 4 columns: the # points
using that datastructure, and the properties that must hold to use that ds and
For each of the three methods, we've outlined the credit you would receive give
the solutions that used the most appropriate datastructures in a way that maxim
for that method.
For example, if I put the following answer for lookupByName():
Method DS Worst Case Efficiency Properties
lookupByName() 3 O(log n) Each student is put in
Then by looking at the following table, I see that 2 points were awarded for th
efficient to use a Hashtable with the student name, a string object, as the key
time would be O(1) as opposed to O(log n) with a BBST.
There was a constraint added during the exam that your nextElement() method of
run in 0(1) time.
Problem 8a
# pts given
sortByScore
3 ? 0 0 3 ? 0 0
datastructure
Vector (1)
Linked List (2)
big-O
O(1)
O(n)
O(n log n)
O(n^2)
O(1)
O(n)
O(n log n)
O(n^2)
properties
Maintain in sorted orde
Need to clone to preven
Unsorted
Unsorted
Sorted
Need to clone to preven
Unsorted
Unsorted
5
3 Balanced tree (3)
1
1
0.5
0 Hashtable (4)
0 Stack (5)
0 Queue (6)
2 Heap (7)
1 0 ? 0
lookupByName
3 Hash Table (4)
3 1
2 Balanced Tree (3)
3 Vector (1)
2 Vector (1)
0 Others (2,5-7)
studentsWithScoreAtLeast
3 Vector (1)
1
1
1
0
0
3 Linked List (2)
1
1
0
1 Balanced tree (3)
3
1
0.5
0 Hashtable (4)
1 Stack (5)
0 Stack (5)
1 Queue (6)
0 Queue (6)
0 Heap (7)
Problem 8b
lookupByLogin
3 Hash Table (4)
3 Vector (1)
2 Balanced Tree (3)
2 Vector (1)
0 Others (2,5-7)
O(n)
O(log n)
O(log n)
O(log n)
*
*
*
O(n log n)
O(n)
O(1)
O(1)
O(log n)
O(1)
O(n)
O(n)
O(log n)
O(1)
O(log n)
*
O(1)
O(n)
O(n)
O(log n)
O(n log n)
O(n^2)
O(1)
O(n)
O(n)
*
O(n)
O(log n)
O(log n)
O(log n)
*
O(n)
O(n)
O(n)
O(n)
*
O(1)
O(1)
O(log n)
O(log n)
*
Do an inorder traversal
Inorder traversal done
Explain that it is O(lo
Don't say that you need
*
*
*
Copy heap, O(n), remove
Copy heap, and do heap
Forget to copy, enumera
nextElement moves from
*
* Anything true
Bad hash code (but it's
Write your own hash tab
Sorted, Binary search
*
Maintain in sorted orde
Sorted with linear sear
Unsorted, copy elements
Binary search in first
Unsorted
Unsorted
Sorted in descending or
Sorted with linear sear
Unsorted, copy elements
Unsorted
Do an inorder traversal
Walk down to starting e
Explain that it is O(lo
Insufficient explanatio
*
Pop all off, push all b
Insufficient explanatio
Dequeue all, enqueue al
Insufficient explanatio
* (A heap can only be
Only if you didn't use
Direct mapped table: Us
Sorted vector with bina
*
6
For part c), the worst case efficiency is specified below depending on the data
Problem 8c
1 O(n) If sorted vector or if
1 O(log n) If BBST
For part d), some people didn't realize that although you could only use 1 type
each instance for a different purpose. For example, if I chose a sorted vector
I sort on and make another instance with the student's score as the key. Then
and O(1) for studentsWithScoreAtLeast. Only a sorted vector and BBST provided
# pts
Problem 8d
3 3 0
datastructure
Sorted Vector (1)
Balanced BST (3)
*
reasoning
Can do all lookups in O
Can do all lookups in O
Makes no logical sense
7