Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
1. Please write your solutions in English.
2. Submit your solutions to gradescope.com.
3. Set your FULL NAME to your Chinese name and your STUDENT ID correctly in Account Settings.
4. If you want to submit a handwritten version, scan it clearly. Camscanner is recommended.
5. When submitting, match your solutions to the according problem numbers correctly.
6. No late submission will be accepted.
7. Violations to any of the above may result in zero grade.
1: (12’) Multiple Choices
Each question has one or more correct answer(s). Select all the correct answer(s). For each question, you
get 0 point if you select one or more wrong answers, but you get 1 point if you select a non-empty subset of
the correct answers.
Note that you should write you answers of section 1 in the table below.
Question 1 Question 2 Question 3 Question 4 Question 5 Question 6
Question 1. Which of the followings are true?
(A) For a min-heap, in-order traversal gives the elements in ascending order.
(B) For a min-heap, pre-order traversal gives the elements in ascending order.
(C) For a BST, in-order traversal gives the elements in ascending order.
(D) For a BST, pre-order traversal gives the elements in ascending order.
Question 2. For a Binary Search Tree (BST), which of the followings are true?
(A) If we erase the root node with two children, then it will be replaced by the maximum object in its right
sub-tree.
(B) The cost for erasing the root node who has two children is O(n).
(C) In a BST with N nodes, it always takes O(log N) to search for an specific element.
(D) For a BST, the newly inserted node will always be a leaf node.