Study Guides (400,000)
CA (160,000)
UW (7,000)
CS (400)
CS240 (6)
Midterm

# CS240 Study Guide - Midterm Guide: Binary Search Tree, Double Hashing, Avl Tree

Department
Computer Science
Course Code
CS240
Professor
Therese Biedl
Study Guide
Midterm

This preview shows pages 1-3. to view the full 13 pages of the document.
University of Waterloo
David R. Cheriton School of
Computer Science
Midterm CS 240 Fall 2007
Course: CS 240
Title: Data Structures and
Data Management
Section(s): 2
Instructors: Therese Biedl and
Matthew Nichols
Student Name:
Student ID Number:
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
Instructions
Please sign this exam below these in-
structions.
Please ensure that the information
recorded on the exam label is correct.
Cheating is an academic oﬀense. Your
signature on this page indicates that
you understand and agree to the Uni-
versity’s policies regarding cheating on
exams.
Your Signature:
Problem Your Mark Out of Marker
1 18
2 6
3 4
4 12
5 6
6 4
7 5
8 7
9 5
Bonus
Total 67
CS 240 Initials: 1 of 13

Only pages 1-3 are available for preview. Some parts have been intentionally blurred.

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
than heapsort.
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
root.
f. A heap of nelements can have height greater than an AVL tree of nelements.
g. If your professor asks you to develop an algorithm that takes O(n2) 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
external memory.
CS 240 Initials: 2 of 13

Only pages 1-3 are available for preview. Some parts have been intentionally blurred.

Problem 2 (6marks)
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).
40
31
18 28
25
b. Suppose we have a max-heap Hthat contains nelements. His stored as an array A, with
the elements of the heap at indices 1..n. Now we insert into Ha key kthat is smaller than all
other keys in H. At which index of array Awill kbe 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
###### You're Reading a Preview

Unlock to view full version