Final practice 2

  1. In which situations the array based implementation and the linked based implementation are most suitable?




    D.
  2. array based implementation is better for
    bounded stack adt
  3. linked based implementation is better for
    unbounded stack ADT
  4. Which of the following represents “quadratic” time?




    A.
  5. 3. Which of the following statements is TRUE about linked lists?




    D.
  6. does link list support random access
    no
  7. given a reference to this position, is removing a node from a linked list efficient or inefficient
    it is efficeint.
  8. how can you traverse in a singly linked list and in a circular linked list
    head to tail 

    head to tail tail to head
  9. Which of the following Java statement attempts to invoke methods that would potentially throw exception(s)?




    D.
  10. What is returned from the call example(8)?
    int example(int n)
    {
    if (n == 1)
    return 1;
    else
    return example(n / 2) + (2 * n - 1);
    }
    D
  11. 6. Which of the following structures did we classify as “non-linear”?




    C.
  12. NumberQueue q = new LinkedNumberQueue();
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    q.enqueue(40);
    q.enqueue(50);
    NumberStack s = new LinkedNumberStack();
    for (int i = 0; i < 3; i++) {
    s.push(q.dequeue());
    }
    while (s.size() > 0) {
    q.enqueue(s.pop());
    }
    D
  13. Under which circumstances should a recursive solution be preferred to an iterative solution?
    (1) When the recursive version is more easily understood.
    (2) When the running time is critical.
    (3) When space (memory) is critical.
    A. None of them
    B. Only (1)
    C. (1) and (2)
    D. (1) and (3)
    E. All of them
    only 1
  14. 9. Which of the following Queue method could throw the QueueOverflowException?




    E.
  15. 10. For the array based unbounded Queue implementation, what happens if the underlying array is full and an enqueue operation is attempted?




    B.
  16. Compare the time complexities of the enqueue and dequeue operations in the fixed front design and floating front design. Explain your answer.
    Fixed front enqueue O(1) because the elements are constant and not shifting and Deque O(N) bc it shifts everything after removing. This is inefficient. 

    Floating front enqueue dequeue are constant O(1) bc  the elements are constanct and not shifting.
  17. 12. What is the output of the following program?
    public class TestRecursion {

    public static void main(String[] args){
    myRec(10, 16);
    }

    public static void myRec(int a, int b)
    { if (a > 2)
       {
             System.out.println("b is " + b);
             myRec(b - 4, a - 2);
        }
        else
             System.out.println("a is " + a);
        }
    }
    B is 16

    B is 8

    B is 10

    B is 2

    A is -2
  18. Recursion can be used to test if the elements in an array are in increasing order. Assume that an array A has the following content:
    87
    15
    23
    17
    19
    20
    32
    40
    A boolean method isSorted(int[] A, int pos) is defined to check if the elements beginning at index pos are in increasing order. For example, isSorted(A, 0) returns false as the numbers 87, 15, 23 are out of order, but isSorted(A, 3) returns true since the rest of them are sorted.
    a) [6pts] Assuming you are going to implement the isSorted method, what would be your base case? As far as the general case, how do you determine if the array elements beginning at pos are sorted based on the return of the "smaller-case"?
    OUTPUT
    if (pos ==A.length-1)

    Return true;

    Else

    {

                    If (A[pos] > A[pos+1]

                                    Return false;

                    Else

                                    Return issorted(A, pos+1);

    }
  19. Given the following definition of the LNode class, implement the methods "push" and "pop" for the LinkedStack class. You can assume isEmpty() method is already implemented for you. You may throw a StackUnderflowException if needed without defining it.
    public class LNode
    {
    private int m_info;
    private LNode m_link;
    public LNode(int info) {
    m_info = info;
    m_link = null;
    }
    public void setLink(LNode link) {
    m_link = link;
    }
    public LNode getLink() {
    return m_link;
    }
    public void setInfo(int info) {
    m_info = info;
    }
    public int getInfo() {
    return m_info;
    }
    }
    public class LinkedStack
    {
    private LNode topOfStack;
    public LinkedStack()
    {
    topOfStack = null;
    }
    Push{

    LNode newNode = new LNode(v);

    newNode.SetLink(TopOfStack);

    topOfStack = newNode;

    } pop {

            If (isEmpty(1)

    Throw new StackUnderflowException(“..”);

    Else

    {

            Int v = topOfStack.getInfo();

            topOfStack = topOfStack.getLink();

            return v;

    }

    }
Author
lcsanc14
ID
344109
Card Set
Final practice 2
Description
final tes t
Updated