CS 315: Example Questions for Midterm Exam

Big O:

• If f(x) = 3 x² + 4 x + 7, what is its Big O?
• What is an optimal Big O for sorting?
• Which is better, O(n²) or O(n * log(n)) ?
• What is the Big O of the following code?

  for ( int i = 0; i < n; i++ )
    for ( int j = 0; j < n; j++ )
      x[i][j] = 0;
  

Linked Lists:

• What is the result of (rest '(a b c))
• What is the Big O of reverse of a list of length n?
• What is the result of (mapcar 'twice '(3 4 5)) given (defun twice (x) (* 2 x))

Stack, Queue:

• If the following operations are done on a Stack, what comes out? Push a, Push b, Pop, Push c, Pop, Pop.
• If the following are operations done on a Queue, what comes out? Insert a, Insert b, Remove, Insert c, Remove, Remove.

Java Collections:

• If coll is a LinkedList of Integer, write a function to add up all the elements.

Trees:

• Write the following expression as a tree: x = (a + b) * c
• Give an advantage of the first-child / next-sibling form of tree.
• What is Big O of search for a specified String in a binary search tree containing n Strings, if the tree is balanced?
• In a depth-first search of a tree with branching factor b and depth d, what is Big O of time required? How much stack depth is required?

Vocabulary: