CSC 225 Midterm: CSC 225 Midterm Fall 2009
31 Jan 2019
School
Department
Course
Professor
Document Summary
Put your name on every page of the exam. You should have 9 pages includ- ing this header page. Recall that you need at least 40% (40/100) in order to write the nal exam in this course. Suggested strategy: read through the exam before starting, and begin with the questions which are easiest for you. [10] list the data values according to the order that the cells of the binary tree are visited for each type of traversal listed. [20] solve the following recurrence using repeated substitution. [15] prove by induction that your solution to question #2 is correct. Or for part marks [5], apply induction to the point where you realize that your solution to #1 is incorrect, and explain what goes wrong. T (n) = n + t (n / 2), t (8) = 42. You may assume that n = 2k for some integer k 3.
