2210 Midterm Prep

Let T be a proper binary search tree with 5 nodes: a, b, c, d, e.
A postorder traversal of T visits the nodes in this order: a, c, b, e, d.
An inorder traversal of T visits the nodes in this order: a, d, c, e, b.

Which node is the right child of the root of T?
Hint: In tree T, the node d is the root.

• a

• b

• c

• d

• e

Consider a hash table of size 5 with the hash function h(k)=k mod 5 and secondary hash function h'(k) = 3 - (k mod 3). What are the contents of the table after inserting, in the given order, the following values into the table: 15, 25, 42, 38, and 57

• 15,57,25,42,38

• 15,38,25,42,57

• 15,42,25,57,38

• 15,25,42,38,57

Consider the following algorithm. What does the algorithm compute?

• The number of nodes in the tree

• The number of descendants of r.

• The height of the tree.

• The number of internal nodes in the tree.

• The number of nodes in the largest subtree of r.

What is the time complexity of this function?

f(n) = 3^15 + n^3(log(n^2)) + n^2.7 + 100n^3

• o(1)

• n^3log(n^2)

• n^2.7

• n^3

• n^3log(n)

Three programs P1, P2, and P3 have time complexities f1(n), f2(n), and f3(n), respectively,

such that

• f1(n) is O(f2(n)),

• f2(n) is O(f1(n)),

• f1(n) is O(f3(n)), and

• f3(n) is not O(f1(n)).

Which of the following statements is true?

• Program P1 is faster than P2 and P3 for very large size inputs.

• Program P2 is faster than P1 and P3 for very large size inputs.

• Program P3 is faster than P1 and P2 for very large inputs.

• Program P3 is slower than P1 and P2 for very large inputs.

• Program P1 must have the exact same running time as Program P2

What is the time complexity of Process?

• O(n)

• O(n^2)

• O(n^3)

• O(logn)

According to the definition of order or ”big Oh”, which of the following is a correct proof for

3n^2 + 4 is O(n^2)

• 3n^2 + 4 < 4n^2 for all n > 1

• 3n^2 + 4 <= 4n^2 for all n>= 3

• 3n^2+ 4 <= 3n^2 + 6 for all n>=1

• 3n^2 + 4 <= 4n^2

What is the value returned by traverse(r) when it's executed on the tree

• 1

• 2

• 3

• 4

• 6

Consider a hash table of size 7 with the hash function h(k)=k mod 7 that uses linear probing to resolve collisions. What are the contents of the table after inserting, in the given order, the following values into the table: 21, 34, 45, 56, 70, 85, 92

• 21, 56, 70, 45, 85, 92, 34

• 21, 70, 34, 45, 56, 85, 92

• 21, 56, 70, 45, 92, 85, 34

• None of the Above

Suppose we have an AVL tree, and after inserting a new entry, the first node

to be out of balance is z, the tallest child of z is y and the tallest child of y is

x. Suppose that we have not performed the triNodeRestructure algorithm yet,

and the height of node z is 41. What were the heights of x.left and x.right

before insertion?

• x.left = 38

  x.right = 38

• x.left = 36

  x.right = 37

• x.left = 37

  x.right = 37

• x.right = 36

  x.left = 37