CSC263H1 Summer 2021 Term Test 1
Submission Instructions
� You may type your answers or hand-write them legibly.
� You may submit your answers as a single document or as multiple documents.
� You may name your file(s) any way you want (there is no “required file” except for aidsheet.pdf).
� You may submit your answers in PDF or in photos (JPEG/JPG/PNG/GIF/HEIC/HEIF), but
NOT other formats (In particular, Word documents cannot be accepted – please export to
PDF before submitting.)
Question 1 General Demonstrate [10 marks]
(a) Given any starting max-heap H, perform the following sequence of operations:
1. x = ExtractMax(H)
2. Insert(H,x)
Is the resulting max-heap (i.e. after insertion) ALWAYS the same as the one we started with
(i.e. before ExtractMax)? Justify your answer with a proof or a counterexample.
(b) In class and in the AVL notes pdf, we discussed the maximum number of rotations required
after an insertion, where the maximum is taken over all possible AVL trees of height H, and all
possible Insert operations. We also discussed the maximum number of rotations required after a
deletion, where the maximum is taken over all possible AVL trees of height H, and all possible
Delete operations. These two maximums are not equal. First, state what these maximums are.
Second, explain why they are not equal HINT: Your answer should be roughly one paragraph
long so that it has enough details.
(c) Assume that we have a binary search tree with four distinct elements that were inserted in random
order. Every possible order in which the elements were inserted was equally likely. Calculate the
expected height of the tree and give an exact number (or fraction). Explain your work either
in plain English or diagrams. HINT: think about the rank of elements as you reason about the
insertion order.
There are 4 other questions in this test.
Remember that you must submit your aid sheet along with your answers.