University of Waterloo
Final Preparation Examination
Course Number:CS 240
Course Title: Data Structures and Data Management
Sections: 001, 002
Instructors: Amir H. Chinaei and Eric Y. Chen
Date of Exam: |
Time Period: |
Duration: 2.5 hours
Exam Type: Closed Book
Prob Mark Max Init. † Calculators are not allowed.
1 6 † Do not open the examination until the start of the exam is
2 8 announced.
3 9 † Do not separate the pages of the examination.
4 6 † If you need additional space, use the back of the previous
5 5 page, and indicate clearly that you have done so. If you
make a mistake be sure to cross it out clearly so we are sure
6 5 which answer to mark.
† In the interests of fairness and to treat all students equally,
8 6 we cannot answer any questions about the examination. If
you believe there to be an error in the examination paper,
9 9 you may bring it to our attention. If we determine that there
10 2 is an error, we will inform the entire class.
† Please sign your initials in the space at the bottom-right
Total 69 corner of each page.
CS 240 Final Page 1 of 12 Initials: 1. = 6 True/False
Write either True or False in the box, and justify your answer brie°y.
(a) A radix sort algorithm always take O(n) time to sort n keys.
(b) Using the LZW algorithm, we compress two pieces of text (ASCII coded) into two strings of
bytes (8-bits per byte). If two substrings, one from each compressed text are the same, then
the two substrings in the original text corresponding to these substrings are the same.
(c) Given a Huﬁman tree and the correct compressed text, we consider two sub strings of bits 1
and s 2 in the compressed text. If 1 and s2are the same, then the original text represented
by s 1nd s a2e also the same.
CS 240 Final Page 2 of 12 Initials: 2. = 8 Running-Time Analysis
Analyze the running time (in terms of n) for each of the following code fragments, using £-notation,
and justify your answer brie°y.
(a) = 4
int one count(n)
// base case: 1
if n == 0
// base case: 2
if n == 1
m ˆ dlogne
nlˆ n >> dm=2e << dm=2e
n ˆ n ¡ n
nlˆ n >l dm=2e
return one count(n l + one count(n )r
Assume n is a non-negative integer, and it can ﬂt in one machine word. Shifting operations
can be done in O(1) time. Bit 0 will be shifted in from both the left and right ends.
Hint: consider the length of the bit representation of n
CS 240 Final Page 3 of 12 Initials: = 4
sum ˆ 0
for i from 1 to n
for j from 1 to 3
CS 240 Final Page 4 of 12 Initials: = 9
3. Hash Tables Operations
Given input 4070, 1020, 6070, 4090, 4372, 9690, 1983 and a hash function h(x) = x mod 10, show
the resulting hash table (of size 10) if we resolve collisions with
(a) = 3 Chaining
(b) Open addressing with linear probing
(c) = 3 Open addressing with double hashing where the second hash function is h (x) =
(xmod3) + 1