Exam 2 Answers
Sec 01

1. C
2. C
3. D
4. D but B is also acceptable
5. True

6.    2
      5
      8
      11
   

7. 1. The queue elements from front to back are: 35 75 95 50 25
   2. The queue elements from front to back are: 80 10 15 60

8.    public T inspector(int count) {
         if (count > numElements -1)
            throw new QueueUnderflowException();
         int i;
         LLNode<T> curr = front;
         for (i = 0 ; i < count ; i++)
            curr = curr.getLink();
         return curr.getInfo();
      }
   

9. The inspector method will have to start at the beginning of the linked list and access count elements to find and return the element at position count. In the worst case count is N-1, since the first element is at position 0, which gives a complexity of O(N).

10. 1.  

       

    2.    public int compareTo(Phone two) {
             int comp = manufact.compareTo(two.manufact);
             if (comp != 0)
                return comp;
             return model.compareTo(two.model);
          }
       

       This method must be in the Phone class.

    3.    SortedABList<Phone> phSortList = new SortedABList<>();
       

    4. This method must be in the Phone class.

    5.    SortedABList<Phone> phSortList = new SortedABList<>(Phone.screenComparator());
       

    6.    int countBefore(ABList<Phone> phList, Phone phone) {
            int count = 0;
            Phone phoneFromList;
            Iterator<Phone> phIter = phList.iterator();
            while (phIter.hasNext()) {
               phoneFromList = phIter.next();
               if (phoneFromList.compareTo(phone) < 0)
                  count++;
            }
            return count;
          }
       

11.    void addAll(LinkedCollection<T> two) {
          LLNode<T> newnode;
          LLNode<T> temp = two.head;
          while (temp != null) {
             newnode = new LLNode<T>(temp.getInfo());
             newnode.setLink(head);
             head = newnode;
             temp = temp.getLink();
          }
          numElements += two.numElements;
       }
    

12. 1. No, it's not balanced. It's out of balance at 500 and 539.
    2. No, it's not a BST because 377 is in the right subtree of 454.
    3. The height is equal to the maximum level of a node. The maximum level is 4 (nodes 125, 475, 545, and 625) so the height is 4.
    4. pre: 454 221 100 88 172 125 250 256 522 500 377 475 539 576 545 625
       in: 88 100 125 172 221 250 256 454 377 475 500 522 539 545 576 625
       post: 88 125 172 100 256 250 221 475 377 500 545 625 576 539 522 454

Email Me | Office Hours | My Home Page | Department Home | MCC Home Page

© Copyright Emmi Schatz 2023