代写CS1027A、代写Java编程语言

日期：2021-12-17 09:45

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.