CIS 120 Midterm: CIS 120 UPenn Midterm1 15sp solutions Exam
31 Jan 2019
School
Department
Course
Professor
Document Summary
Recall the de nition of generic binary trees and the bst insert and lookup functions: type "a tree = let rec lookup (x: "a) (t: "a tree) : bool = | node of "a tree * "a * "a tree let rec insert (t:"a tree) (n:"a) : "a tree = begin match t with. | node(lt, x, rt) -> if x = n then t else if n < x then node (insert lt n, x, rt) else node(lt, x, insert rt n) end begin match t with. | hd::tl -> insert_list tl (insert hd t) end let big_tree : int tree = insert_list a_million_ints empty. Answer: a randomly-ordered list would perform better because a sorted list creates a skewed, list-like tree, so the bst search would not be able to prune the search space. Grading scheme: 2 points for correctly identifying random , 3 points for the explanation, 2 or 3 points for almost correct other explanations.
