关于后端:CS1027A详情

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.
2. for (int i = 0; i < n; i++) {
3. for (int j = 0; j < n; j++) {
4. if (i % 2 == 0) {
5. System.out.println(“Hi”);
6. }
7. }
8. }
9. 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
10. 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
11. 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
12. 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
13. 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
14. 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
15. 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
16. 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.