CSE214 Final Review

Order from least to greatest Time complexity

• O(3), O(log n), O(n log n), O(10n), O(n^2), O(n^10), O(2^n), O(n!), O(n^n)

• O(3), O(log n), O(10n), O(n^2), O(n log n), O(n^10), O(2^n), O(n!), O(n^n)

• O(3), O(log n), O(10n), O(n log n), O(n^2), O(2^n), O(n^10), O(n^n), O(n!)

• O(3), O(log n), O(10n), O(n log n), O(n^2), O(n^10), O(2^n), O(n!), O(n^n)

Evaluate the time complexity

• O(N)

• O(N^2)

• O(N log N)

• O(1)

For N=20, what will be printed?

Consider the following method, which is supposed to remove all nodes of a linked list containing a value and return the new head. Select the 2 test cases where the removeVal(head,1); performs as expected

• 1 -> 2 -> 3 -> 4

• 2 -> 1 -> 1 -> 2

• 2 -> 2 -> 2 -> 2

• 2 -> 1 -> 2 -> 2

What are the benefits of using a DOUBLY linked list rather than a SINGLY

(You have access to head and tail)

• Remove Head becomes faster

• Remove Tail becomes faster

• Insert Tail becomes faster

• Doubly uses less space than singly

For a stack implemented using a singly linked list with top = head and no tail reference, what are the time complexities?

• PUSH: O(1)

  POP: O(1)

• PUSH: O(1)

  POP: O(N)

• PUSH: O(N)

  POP: O(1)

• PUSH: O(N)
  POP: O(N)

For a stack implemented using a singly linked list with bottom = head and top = tail, what are the time complexities?

• PUSH: O(1)

  POP: O(1)

• PUSH: O(1)

  POP: O(N)

• PUSH: O(N)

  POP: O(1)

• PUSH: O(N)
  POP: O(N)

Evaluate the prefix expression of integers:
- / + 5 * 4 3 2 4

Evaluate the postfix expression of integers:

5 4 * 2 1 - - 3 /

Convert the infix to postfix:

A + (B + C / D) * E

• A B C + D / + E * +

• A B C D / + E + *

• A B + C + D / E *

• A B C D / + E * +