CSSE 304 Exam 2 Part 3a 10/16/2018 (day 26.5) Name_____________________ Section (circle one): 01(9:00) 02 (9:55) 03 (10:50)
Problem
Possible
Earned
Comments
C1
15
Unless you have an accommodation in writing, you may not use email, IM, cell phone, PDA, headphones, earbuds, or any other communication device or software.
Part 3a programming You may use a Scheme editing/programming environment, CSSE 304 textbooks including TSPL, Chez Scheme Users’ Guide, PLC grading program, and any materials that I provided online for the course. You are allowed to look at and copy any Scheme code that you (or you and your partner) wrote before the exam, but nothing else that was written by others, including CSSE 304 students from previous terms. You may not use any other web or network resources.
C1 (15 points) The height of a node in a binary tree is its distance from the bottom of the tree. Here we will use the EoPL textbook’s definition of binary tree:
each of the number nodes has height 0; the height of node b is 1, and the height of node a is 2. The height-sum of a binary tree is the sum of the heights of all of its nodes. For example, the height-sum of the above tree is 3. One way to calculate the height-sum would be to write a node-height procedure, call it at each tree node, and add the results together. But this would be inefficient. You can earn 5 of the 15 points for this problem by doing it that way. For full credit you must write height-sum so that its running time is proportional to N(T), the number of nodes in bintree T. A general approach that works is similar to the approach for max- interiorandsubst-leftmost. Mutationisnotallowed.
> (define t1 3)
> (define t2 ‘(a 1 3))
> (define t3 ‘(a (b (c 1 4) 2) 6)) > (define t4 ‘(a (b (c 1 4) 2)
(d 4 (e 1 7))))
> (define t5 ‘(a (b (c (d 3 5)
(e 2 (f 1
(g 2 7))))
(h 1 (i 2 (j 3 4))))
5))
> (list
(BST-height-sum t1)
(BST-height-sum t2)
(BST-height-sum t3)
(BST-height-sum t4)
(BST-height-sum t5)
)
(0 1 6 9 28)
If you finish this part before finishing Part 3b, please go ahead and submit this one so we can get it graded. That will help me be able to get the exams graded in time to return them to you in Thursday¡¯s class.
Submit your code to assignment
E2-201910-Problem C1 (non-interpreter)
on the PLC server