CS 202 Midterm Exam 2Page 1 of 7
UIC 2002 Summer Session
CS 202 Midterm Exam 2
July 15, 2002
Solutions
Problem 1 (26 points)
Show the result of inserting the elements 5, 3, 9, 10, 19, 6, 13, and 16, one at a time, into an initially empty AVL tree. (Show intermediate steps if you wish, but only the final result is required.)
Answer:
Problem 2 (16 points total)
Given the input {13, 15, 20, 14, 21} (in that order) and a hash function show the resulting:
a)Open addressing hash table using linear probing with (5 points)
Answer:
0 / 201 / 15
2 / 14
3 / 21
4
5
6 / 13
b)Open addressing hash table using quadratic probing with (5 points)
Answer:
0 / 201 / 15
2 / 21
3
4 / 14
5
6 / 13
Problem 2 (continued)
c)Open addressing hash table using double hashing with where (6 points)
Answer:
0 / 141 / 15
2
3
4 / 20
5 / 21
6 / 13
Problem 3 (26 points total)
a)Show the result of inserting 20, 24, 1, 28, 12, 9, 16, 29, 5, 17, 13, 8, 21, 25, and 4, one at a time, into an initially empty binary heap. (Show intermediate steps if you wish, but only the final result is required.) (13 points)
Answer:
b)Show the result of performing three deleteMin operations on the heap that you created in (a). (Show intermediate steps if you wish, but only the final result is required.) (13 points)
Problem 3 (continued)
Answer:
Problem 4 (16 points)
Run Shellsort on the input array
using Hibbard’s increments,
a)What is the largest increment that will be used? (1 point)
Answer: 7
b)Show the result of phase 1 on (5 points)
Work: Phase 1 increment is 7.
1st swap:
2nd swap:Done.
Answer:
Problem 4 (continued)
c)Show the result of phase 2 on (5 points)
Work: Phase 2 increment is 3.
1st swap:
2nd swap:Done.
Answer:
d)Show the result of phase 3 on (5 points)
Work: Phase 3 increment is 1.
1st swap:
2nd swap:
3rd swap:
4th swap:Done.
Answer:
Problem 5 (16 points total)
Suppose that you are sorting the input array
in place, using quicksort with median-of-three partitioning (where the element position ) and a cutoff of three.
Problem 5 (continued)
a)What is the value of the first pivot, ? (3 points)
Answer:
After finding quicksort (i) partitions into two disjoint subarrays, (ii) places into its final position, and then (iii) makes two recursive quicksort calls.
b)What is the final position of ? (3 points)
Work:
Swap out :
Swap :
1st swap done:
Swap :
2nd swap done:
cross:
Swap :Done.
Answer: Position = 6.
Problem 5 (continued)
c)Show immediately after has been placed in its final position (i.e., immediately before any subsequent quicksort operations). (5 points)
Answer:
Two disjoint subarrays, (on the left side of ) and (on the right side of ) are now passed into two separate quicksort routines.
d)List the elements, in order, in and (5 points)
Answer: , .
Extra credit (6 points total)
e)What is the value of the pivot, in ? (3 points)
Answer:
f)Is there a pivot in ? If so, find its value. Otherwise, explain why there is no pivot. (3 points)
Answer: No pivot in , because is the cutoff size, 3, and will thus be sorted by insertion sort, which does not use a pivot. Quicksort computes pivots only for subarrays that are larger than the cutoff size.
Instructor: / James A. Inglehart / 1125 SEO / TR 11–12 /TA: / Xin Li / 2260 SEL / R 11–1 /