School

University of WaterlooDepartment

Computer ScienceCourse Code

CS240Professor

Therese BiedlStudy Guide

MidtermThis

**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