Study Guides (238,095)
Canada (114,916)
CS 240 (5)

Midterm Fall 2007 useful for studying

13 Pages
Unlock Document

University of Waterloo
Computer Science
CS 240
Therese Biedl

University of Waterloo Student Name: David R. Cheriton School of Computer Science Midterm CS 240 Fall 2007 Course: CS 240 Student ID Number: Title: Data Structures and Data Management Section(s): 2 Instructors: Therese Biedl and Matthew Nichols 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 Instructions 1 18 • 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 offense. 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 exams. 7 5 8 7 Your Signature: 9 5 Bonus Total 67 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 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 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 external memory. 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). 40 31 25 18 28 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. Briefly 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? Briefly 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,
More Less

Related notes for CS 240

Log In


Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.