University of Waterloo
David R. Cheriton School of
Midterm CS 240 Fall 2007
Course: CS 240 Student ID Number:
Title: Data Structures and
Instructors: Therese Biedl and
Date of Exam: November 1, 2007
Time Period Start time: 4:30 pm End time: 6:20 pm
Duration of Exam: 1 hour 50 minutes
Number of Exam Pages: 13 (including cover sheet)
Additional Materials Allowed: One 8.5” x 11” double-sided help sheet
No Calculators. No Other Additional Materials
Problem Your Mark Out of Marker
• Please sign this exam below these in-
structions. 2 6
• Please ensure that the information 3 4
recorded on the exam label is correct.
• Cheating is an academic oﬀense. Your 4 12
signature on this page indicates that 5 6
you understand and agree to the Uni-
versity’s policies regarding cheating on 6 4
CS 240 Initials: 1 of 13 Problem 1 (18 marks)
For each question below, indicate in the box provided whether the statement is True or False.
No explanation is required. Please do not simply write T or F as these as easily misread. You
will receive 2 marks for a correct answer, 0 for a blank answer, and -0.5 for a wrong answer. Your
minimum total mark is 0.
a. If f(n) ∈ O(g(n)) then f(n) ∈ o(g(n)).
b. Traversing any heap (in binary-tree form) in pre-order will always yield the
stored keys in decreasing order.
c. Depending on the input data, insertion sort may require fewer comparisons
d. When using external memory, the number of accesses to external memory is far
more important for time complexity than the number of operations done in internal memory.
e. In a randomly built binary search tree, all elements are equally likely to be the
f. A heap of n elements can have height greater than an AVL tree of n elements.
g. If your professor asks you to develop an algorithm that takes O(n ) time, then
submitting an algorithm that takes O(n) time is acceptable.
h. For double hashing, the choice of hash functions is not that important since all
hash operations can be done in θ(1) worst-case time regardless.
i. In extendible hashing, most operations require only 1 or 2 pages accesses from
CS 240 Initials: 2 of 13 Problem 2 (6 marks)
a. Consider the max-heap given below. Show the heap that results after inserting the key 10
into this heap. (Note that key 10 is smaller than every other key in the heap).
b. Suppose we have a max-heap H that contains n elements. H is stored as an array A, with
the elements of the heap at indices 1..n. Now we insert into H a key k that is smaller than all
other keys in H. At which index of array A will k be located after we have fully completed
the insert operation? (Note that array indices start at 1, not at 0). You may assume array A
is large enough to accommodate the additional element. Brieﬂy explain your answer.
CS 240 Initials: 3 of 13 Problem 3 (4 marks)
Suppose we want to sort the data set 3, 9, 2, 14, 5, 12, 17, using quicksort. In order to have
the best-possible running time, which element would have to be the pivot in the initial recursion?
Brieﬂy explain your answer.
CS 240 Initials: 4 of 13 Problem 4 (12 marks)
For each of the following situations, indicate which sorting algorithm you would choose to im-
plement. You must choose one of the following options: Heapsort, Count Sort,