Data Structures - Exam #1

Write your answers on the answer sheets provided.

\begin{displaymath}
\begin{array}{lcp{3.5in}}
\Theta(g(n)) = \{f(n) & \vert & t...
...(n) \leq f(n) \leq c_2g(n)$\ for all $n \geq n_0\}$
\end{array}\end{displaymath}

  1. (2 pts) Is $n+123123$ in $O(n^2)$?

  2. (4 pts) Prove that $\frac{1}{4}n^3 + 100n^2+5$ is in $\Theta(n^3)$. Specify values for $n_0$, $c_1$, and $c_2$.

  3. (6 pts) Determine the complexity of the following algorithm and express your answer in terms of big-O. Explain/show your work. You may assume that the variable a is an array containing at least n integer values.
    i=0;
    while (i<n && a[i]!=0) {
       for (j=0; j<5; j++)
          num= num+a[i]*j;
       i++;
    }
    

  4. (2 pts each) State (using $O$) the complexity of each of the following operations:
    1. insert in an unordered, linked list-based list
    2. minimum in an ordered linked list-based list
    3. search in an ordered, array-based list
    4. delete in an ordered array-based list
    5. binary search tree delete
    6. binary search tree search

  5. (10 pts) Consider these growth functions: $n^2$, $\lg n$, $n \lg n^2$, $2^n$, $2^{50}$, $n^7$, $n$.
    1. Write them in order from slowest growing to fastest growing.
    2. Give the name for each type of growth function represented.

  6. (4 pts) Using words give a recursive explanation of how a binary search works. NOTE: For it to be a recursive explanation you need to express your answer in terms of itself and you need to identify a base condition.

  7. (4 pts) Explain the relationship between the number of nodes in a binary search tree and the tree's height.

  8. Suppose a binary search tree will be used to store the following key values: 10, 12, 20, 27, 32, 38, 45.
    1. (3 pts) Order the elements above so that if inserted into the tree using a traditional binary search tree insert action it would produce a worst-case unbalanced tree.

    2. (3 pts) Order the elements above so that if inserted into the tree using a traditional binary search tree insert action it would produce a complete tree.

  9. (8 pts) Suppose a binary search tree is implemented using the following class:
    class TreeNode {
      String word;
      int count;
      TreeNode left, right;
    };
    
    Suppose a MyTree class has been built and is an implementation of a binary search tree that it has been used to track the number of times words in a document have been used. Assume the words are used as the ordering key. Write a method to be added to the MyTree class called showLoners that accepts no parameters and will alphabetically display all the words that appear only once. You may write additional helper methods as needed.

  10. (6 pts) Briefly outline the steps (3 cases) to delete an element from a binary search tree.

  11. (2 pts each) Use the diagram of the binary tree below to answer the following questions:
    1. Is this tree a binary search tree?
    2. Show order of visits using a preorder traversal.
    3. Show order of visits using an inorder traversal.
    4. Show order of visits using a postorder traversal.
    \includegraphics{tree.eps}

Quick Links