CSC 241- Exam 2        Name:

1. What does it mean to dynamically allocate space?

2. What does it mean to statically allocate space?

3. Give at least two reasons why we would use a linked list instead of an array to hold data?

4. Why do we use the equals method from the String class when comparing two strings instead of simply using the == comparison operator.

5. Consider the following method:

   
       static void out(stringQueue q) {
           while(!q.empty()) {
             String text = q.dequeue();
             System.out.println(text+" was removed from the queue");
           }
       }
       

   As you know, stringQueue is an abstract class. Why is this method written with an object of an abstract class as a parameter that has no implementation?

6. What is the purpose of a Base Case in recursive algorithms?

7. What makes a method recursive?

8. In what way is genStack generic and what is the key in making it generic?

9. When using the big-O notation, is it valid to say the complexity of an algorithm is O(n²)+2O(n)? Why?

10. What is the complexity of Binary Search algorithm? O(n),O(n²),O(log₂n), O(nlog₂n))

                      |5 |===|15|===|-8|===|3 |===|6 |===||
                      head

             Now assume the following node class:
             
             class Node {
                int element;
                Node next;
                Node prev;
                Node (Node n, Node p, int e) {
                  prev=p;
                  next=n;
                  element=e;
                }
             }
             

1. What is the value of head.next.prev.element?
2. For the list above, what are the steps that add, say 19, at the end of the list. Start with Node temp=head;

public class intList {
  public intList()
  public boolean empty()
  public int find(int val)
  public void append(int val) 
  public int addBefore(int pos, int val) 
  public int addAfter(int pos, int val) 
  public int remove(int pos) 
  public int valAt (int pos)
  public int last()   /** Return the position of the last element **/
  public String dump ()
}

1. int Largest (intList list)
   //This method either returns the largest value in list or -1 if list is empty.

2. int Average (intList list)
   //Determine the average and return it. Return zero if list is empty.

  public String dump () {
    String text;
    if (head == null) 
      text = new String ("List is Empty");
    else {
      text= new String("head-> ");
      Node temp;
      int last;
      for (temp=head,last=0;temp != null;temp=temp.next,last++)
          text=text.concat(new String(temp.element + "-> "));
    }
    return text;
  }

  public String dump () {
    String text;
    if (head == null) 
      text = new String ("List is Empty");
    else {
      text= new String("head-> ");
      text.concat(recursiveDump(head));
    }
  }

   public static int fib (int n) {
      if ((n==1)||(n==2)) return 1;  // base case
      return fib(n-1) + fib(n-2);    // note that two separate calls are made
   }

                                           fib(5)
                                         {return 5}

                  fib(4)                    +                   fib(3)
                {return 3}                                    {return 2}

        fib(3)       +       fib(2)                      fib(2)  +  fib(1)
      {return 2}            {return 1}                 {return 1}  {return 1} 

   fib(2)  +  fib(1)
 {return 1} {return 1}