Pre-Exam3# CSE205
Last Name (Print) First Name ASU ID
1. Define the best (simplest) Big-Oh notation for each function, where the n is the number of elements
(1 Pts).
5𝑛!+ 𝑛 ∙ log
(
𝑛
)
+log
(
𝑛
)
+𝑛+100 = 𝑂(? ? ?
) O ( )
𝑛 ∙ log
(
𝑛"
)
+100𝑛 + log
(
𝑛#
)
= 𝑂(? ? ?
) O ( )
2. Write the traversals for the given the right B-tree.
(2 pts)
Pre-order
In-order
Post-order
3. Show the Binary Search Tree (BST) that results when the following values are added, in
order (added to the BST from left to right), to a new tree. (1 Pt)
[6 7 3 9 5 1]
4. Given the following array:
[4 5 3 9 1 2]
Show how the array is sorted in Merge Sort. Use special symbols (such as [ ], |, *, etc.) to
display the split and merged process clearly in your way. (1 Pt)
5. Given the following array
[3 6 2 8 0 1]
When sorting the array using QuickSort, list up all changes of swapping. Use the first (left)
element as a pivot. (1 Pt)
6. Build (Heapify) a max-heap from the array containing the following: the largest is stored at
the root. Show the update for all swaps to make it a max heap. (Not the tree but the array)
(2 Pt)
5 8 3 4 9 1 2
public class {
}
In-class Exercise. Write the answer in 20-30 minutes, then switch the paper to your next classmates, and
grade them by listening to the instructor’s solution.
Grader name Score
After grading, explain why you make the mistakes in your words in the open space, and submit the
scanned image to Gradescope “Pre-Exam3” to get the attendance point.
Powered by TCPDF (www.tcpdf.org)
7. Suppose that a Student class has getExam() method to return the exam score as an
integer. Make a StudentComparator class implementing the
Comparator<Student> interface, and override the compare method. (2 pts)
