Computer Science Fundamentals II Wednesday, December 8, 2019
Final Exam Practice Problems
CS1027A University of Western Ontario
1. Compute the time complexity of the given code. You must explain how you com-
puted the time complexity and you must give the order (big-Oh) of the time
complexity.
1 for (int i = 0; i < n; i++) {
2 for (int j = 0; j < n; j++) {
3 if (i % 2 == 0) {
4 System.out.println("Hi");
5 }
6 }
7 }
2. Write exactly two for loops that are nested inside of each other such that your code
fragment has a time complexity of O(n · log(n)).
1
3. Draw the binary tree from the given level-order traversal. We have not included ”null”
for every empty position in every level of the tree; instead, we have written null when
an existing node has no child in that position.
• A, B, C, null, D, null, null, null, F
4. Draw the binary tree such that:
• a pre-order traversal visits the nodes in this order: 5, 1, 4, 2, 3, and
• an in-order traversal visits the nodes in this order: 1, 5, 2, 4, 3.
2
5. Consider the binary tree shown in Figure 1. Perform the iterative pre-order tree
traversal using a stack as shown to you in class. Write your answers in the U-shaped
diagrams in Figure 2. For the first stack, show the value on the stack before entering
the loop. For the rest of the stacks, show the values on the stack at the end of each
loop iteration.
Figure 1
Figure 2
3
6. Consider the array A = [1, 2, 3, 4]. Trace through a stack-based implementation of
insertion sort on this array. During each step, draw 3 stacks: (1) the sorted stack with
the new number in it, (2) the temp stack holding whatever numbers are necessary to
have drawn the previous sorted stack, and (3) the sorted stack with everything from
temp in it.
4
7. Consider the array A = [5, 4, 3, 2, 1]. Trace through the quicksort algorithm on this
array. Use the middle (rounded down) element as the pivot. For each recursive
call, draw the execution stack (don’t worry about other methods such as main(), show
the pivot, and show the arrays smaller, equal, and larger. Show the sorted sub-arrays
at the appropriate times in the recursion.
5
8. Consider a binary search tree formed by linking together node objects of class Binary-
TreeNode. The BinaryTreeNode class provides methods getLeft(), setLeft(), getRight(),
setRight(), and getElement(). You can create a new node by calling the constructor
of this class using BinaryTreeNode<>(element) to create a new node storing value
element whose left and right children are null.
Write an algorithm public BinaryTreeNode find(BinaryTreeNode node, T el-
ement) in Java or in detailed Java-like pseudocode that searches the binary search
tree for the node containing element. If element is in the tree, you must return the
BinaryTreeNode containing element ; otherwise, you must throw a NonExisten-
tKeyException (you can assume this exception has already been created).
You can assume that the variable element is of a class that implements Comparable.
6
9. A binary tree is symmetric if for every internal node the number of nodes in its left
subtree is the same as the number of nodes in its right subtree. Given a node p, let
p.size() return the number of nodes in the subtree with root p, and p.getLeftChild()
and p.getRightChild() return the left and right children of p, respectively. Write a
recursive algorithm public boolean isSymmetric(BinaryTreeNode r) that receives
as parameter the root r of a binary tree and it returns true if the tree is symmetric and
it returns false otherwise. For example for the tree below with root r the algorithm
must return true, but for the tree with root s it must return false.
Figure 3
7

欢迎咨询51作业君